共查询到19条相似文献,搜索用时 93 毫秒
1.
2.
3.
4.
5.
6.
7.
8.
本文考虑工件首先在单机上加工,完工的工件由一辆容量有限的车配送到指定客户的模型,目标是最小化makespan。对于工件物理大小相同的情况,我们考虑了常数个客户的情形,并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况,我们讨论了一类特殊的三个客户的情形,并给出了一个2-近似算法。 相似文献
9.
本文考虑了n个工件在同一台机器上加工的调度问题 ,其中工件的加工时间和交货期都是具有任意分布的随机变量 .我们考虑了一个非常规目标函数 ,其中工件的权数与平均加工时间成比例 .在工件的交货期与加工时间满足相容条件下 ,得到了个简单的最优排序策略 . 相似文献
10.
研究了具有学习效应的三层供应链排序问题. 多个客户分布在不同位置,每个客户都有订 单需要制造商进行生产. 制造商需要针对每一个不同订单的客户从不同的地方进购对应的原材料进行生产,生产完工后需要利用有限的车辆将工件运输到相应客户处. 要求每辆运输车装载尽可 能多的货物才开始运输. 利用动态规划算法研究了最大流程时间、总流程时间以及最大延迟三个目标函数. 相似文献
11.
We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs; the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments; we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal. 相似文献
12.
In this paper we consider the problem of scheduling n jobs on a single batch processing machine in which jobs are ordered by two customers. Jobs belonging to different customers are processed based on their individual criteria. The considered criteria are minimizing makespan and maximum lateness. A batching machine is able to process up to b jobs simultaneously. The processing time of each batch is equal to the longest processing time of jobs in the batch. This kind of batch processing is called parallel batch processing. Optimal methods for three cases are developed: unbounded batch capacity, b > n, with compatible job groups and bounded batch capacity, b n, with compatible and non compatible job groups. Each job group represents a different class of customers and the concept of being compatible means that jobs which are ordered by different customers are allowed to be processed in a same batch. We propose an optimal method for the problem with incompatible groups and unbounded batches. About the case when groups are incompatible and bounded batches, our proposed method is considered as optimal when the group with maximum lateness objective has identical processing times. We regard this method, however, as a heuristic when these processing times are different. When groups are compatible and batches are bounded we consider another problem by assuming the same processing times for the group which has the maximum lateness objective and propose an optimal method for this problem. 相似文献
13.
We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only
compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. All jobs
are available at the same date. The capacity of the batch processing machine is finite or infinite. The processing time of
a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem
and present polynomial algorithms for several special cases. 相似文献
14.
《European Journal of Operational Research》2005,162(1):184-190
In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure. 相似文献
15.
In this paper, we consider a single machine that processes a set of jobs having two (ordered) phases. After processing the first phase of a job, this job must be removed from the machine for some exact amount of time, after which the machine must immediately begin processing its second phase. During this “dead time” between job phases, the machine may be used to process other similar jobs. We first prove that the problem of interleaving these jobs in order to minimize the makespan (or to process as many jobs as possible by a given deadline) is strongly NP-hard. Next, we compare the effectiveness of a mixed-integer programming formulation based on a continuous time domain to that of a discrete-time integer programming model for solving problems having different data characteristics. These comparisons are performed on a set of realistic synthetic problems based on different scenarios arising in radar pulsing applications. 相似文献
16.
We consider the problem of scheduling n jobs on m parallel machines. Each job has a deterministic processing time and a weight associated with it. For uniform machines we show that discounted flowtime is minimized by serving jobs preemptively in increasing order of their remaining processing times, assigning the job with the shortest remaining processing time to the fastest available machine. 相似文献
17.
本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。 相似文献
18.
19.
Mourad Boudhar 《Journal of Mathematical Modelling and Algorithms》2003,2(1):17-35
We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. Jobs have release dates. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases. Relating scheduling theory and graph theory appears to be an interesting and important concept. 相似文献