Single machine scheduling with release dates and rejection
Single machine scheduling with release dates and rejection
复制标题
具有发布日期和拒绝的单机调度
DOI：
10.1016/j.ejor.2008.10.006
复制
发表时间：
2009-11
影响因子：
6.4
通讯作者：
Lu, Lingfa
中科院分区：
文献类型：
--
作者：
Yuan, Jinjiang;Zhang, Liqi;Lu, Lingfa
本文研究了带交货期和拒收的单机排序问题。作业要么被拒绝(在这种情况下必须支付拒绝罚金)，要么被接受并在机器上处理。目标是最小化被接受的作业的完工时间和被拒绝的作业的总拒绝惩罚之和。我们证明了该问题是一般意义上的NP难问题。然后，我们给出了两种伪多项式时间算法。因此，可以在多项式时间内解决两种特殊情况。最后，给出了该问题的2-逼近算法和完全多项式时间逼近格式。
In this paper, we consider the single machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the machine. 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 the problem is NP-hard in the ordinary sense. Then we provide two pseudo-polynomial-time algorithms. Consequently, two special cases can be solved in polynomial-time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem.
登录
查看更多内容
DOI：
--
发表时间：
--
期刊：
--
影响因子：
--
作者：
L. Epstein;J. Noga;G. Woeginger
通讯作者：
L. Epstein;J. Noga;G. Woeginger
影响因子：
0.8
作者：
Bartal, Y;Leonardi, S;Stougie, L
通讯作者：
Stougie, L
DOI：
10.1016/0196-6774(84)90032-4
发表时间：
1982
期刊：
J. Algorithms
影响因子：
--
作者：
David S. Johnson
通讯作者：
David S. Johnson
NP 完整性专栏：持续指南
DOI：
10.1016/0196-6774(81)90037-7
发表时间：
1981
期刊：
J. Algorithms
影响因子：
--
作者：
David S. Johnson
通讯作者：
David S. Johnson
无界并行批处理机调度，包含发布日期和拒绝，以最大限度地缩短完工时间
影响因子：
1.1
作者：
Lu, Lingfa;Zhang, Liqi;Yuan, Jinjiang
通讯作者：
Yuan, Jinjiang