Parallel-machine scheduling with deteriorating jobs and rejection
Parallel-machine scheduling with deteriorating jobs and rejection
复制标题
具有恶化作业和拒绝的并行机器调度
DOI：
10.1016/j.tcs.2010.06.008
复制
发表时间：
2010-09-06
影响因子：
1.1
通讯作者：
Yuan, Jinjiang
中科院分区：
文献类型：
--
作者：
Li, Shisheng;Yuan, Jinjiang
本文考虑了几个平行机排序问题，其中工件的加工时间是其起始时间的（简单）线性增函数，工件可以通过支付罚款而被拒绝。目标是最小化被接受工件的调度成本加上被拒绝工件的总惩罚。本文考虑了调度成本的三种变化。第一个是完工时间，第二个是总加权完工时间（对于简单线性恶化），第三个是总完工时间。对于前两个问题，我们提出了两个完全多项式时间的近似方案来解决他们的机器数量是固定的。对于最后一个问题，当所有工件的劣化率相等时，我们给出了一个O（n（2））时间的最优动态规划算法。(C)2010 Elsevier B.V.保留所有权利。
We consider several parallel-machine scheduling problems in which the processing time of a job is a (simple) linear increasing function of its starting time and jobs can be rejected by paying penalties. The objective is to minimize the scheduling cost of the accepted jobs plus the total penalty of the rejected jobs. Three variations of the scheduling cost are considered in this paper. The first is the makespan, the second is the total weighted completion time (for simple linear deterioration), and the third is the total completion time. For the former two problems, we propose two fully polynomial-time approximation schemes to solve them when the number of machines is fixed. For the last problem, we present an optimal O(n(2))-time dynamic programming algorithm when the deteriorating rates are equal for all jobs. (C) 2010 Elsevier B.V. All rights reserved.