The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan
The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan
复制标题
无界并行批处理机调度，包含发布日期和拒绝，以最大限度地缩短完工时间
DOI：
10.1016/j.tcs.2008.02.015
复制
发表时间：
2008-05-10
影响因子：
1.1
通讯作者：
Yuan, Jinjiang
中科院分区：
文献类型：
--
作者：
Lu, Lingfa;Zhang, Liqi;Yuan, Jinjiang
本文研究了带放行期和拒绝的无界并行批处理机排序问题。一个作业要么被拒绝并支付一定的罚款，要么被接受并在并行批处理机上分批处理。一批工件的加工时间定义为该批工件的最长加工时间，目标函数是最小化被接受工件的最大完工时间和被拒绝工件的总拒绝惩罚之和。我们证明了这个问题是二进制NP-难的，并提供了一个伪多项式时间算法。当工件具有相同的拒绝惩罚时，该问题可以在多项式时间内求解。最后给出了该问题的2-近似算法和完全多项式时间近似格式。(C)2008由爱思唯尔公司出版
In this paper, we consider the unbounded parallel batch machine scheduling with release dates and rejection. A job is either rejected with a certain penalty having to be paid, or accepted and processed in batches on the parallel batch machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that this problem is binary NP-hard and provide a pseudo-polynomial-time algorithm. When the jobs have the same rejection penalty, the problem can be solved in polynomial time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem. (C) 2008 Published by Elsevier B.V.