Scheduling algorithm for flow shop with two batch-processing machines and arbitrary job sizes
Scheduling algorithm for flow shop with two batch-processing machines and arbitrary job sizes
复制标题
DOI：
10.1080/00207721.2012.724107
复制
发表时间：
2014-03
影响因子：
4.3
通讯作者：
B. Cheng;Shanlin Yang;Xiaoxuan Hu;Kai Li
中科院分区：
文献类型：
--
作者：
B. Cheng;Shanlin Yang;Xiaoxuan Hu;Kai Li
本文研究了在作业大小任意且机器容量有限的情况下，流水车间中两台批量加工机器的调度问题。作业分批处理，每批作业的总大小不能超过机器的容量。一旦处理了一个批处理，就不允许中断，直到其中的所有作业完成为止。最小化完工时间的问题在很大程度上是np难题。首先，我们用整数程序建立了该问题的数学模型。我们给出了问题可行解的规模，并给出了最优性性质。然后，我们提出了一个多项式时间算法，其运行时间为O（nlogn）。作业首先以可行的批量分配，然后在机器上调度。对于一般情况，我们证明了该算法的性能保证为4。对于两台机器上每个作业的处理时间满足p1j = ap2j的特殊情况，性能保证为> 0。
This article considers the problem of scheduling two batch-processing machines in flow shop where the jobs have arbitrary sizes and the machines have limited capacity. The jobs are processed in batches and the total size of jobs in each batch cannot exceed the machine capacity. Once a batch is being processed, no interruption is allowed until all the jobs in it are completed. The problem of minimising makespan is NP-hard in the strong sense. First, we present a mathematical model of the problem using integer programme. We show the scale of feasible solutions of the problem and provide optimality properties. Then, we propose a polynomial time algorithm with running time in O(nlogn). The jobs are first assigned in feasible batches and then scheduled on machines. For the general case, we prove that the proposed algorithm has a performance guarantee of 4. For the special case where the processing times of each job on the two machines satisfy p 1 j = ap 2 j , the performance guarantee is for a > 0.