Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan
Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan
复制标题
对恶化的作业进行并行批量调度，并指定发布日期，以最大限度地缩短完工时间
DOI：
10.1016/j.ejor.2010.11.021
复制
发表时间：
2011-05-01
影响因子：
6.4
通讯作者：
Yuan, Jinjiang
中科院分区：
文献类型：
--
作者：
Li, Shisheng;Ng, C. T.;Yuan, Jinjiang
我们考虑在单个批处理机上调度n个具有放行日期的劣化作业的问题。每个作业的处理时间是其开始时间的一个递增的简单线性函数。这台机器可以批量同时处理多达b个作业。目标是最小化最大完成时间，即makespan。对于无界模型，即b =∞，我们得到了一个O（n log n）动态规划算法。对于有界模型，即b < n，我们首先证明了即使只有两个不同的发布日期，问题也是二元np困难的。然后，我们提出了O（nb）和O(（nb/h)(h)）算法，分别适用于预先确定作业加工顺序的情况和h， h >= 2的不同恶化率的情况。此外，我们提供了一个完全多项式时间近似方案的情况下，不同的发布日期的数量是一个常数。(C) 2010 Elsevier B.V.版权所有
We consider the problem of scheduling n deteriorating jobs with release dates on a single batching machine. Each job's processing time is an increasing simple linear function of its starting time. The machine can process up to b jobs simultaneously as a batch. The objective is to minimize the maximum completion time, i.e., makespan. For the unbounded model, i.e., b = infinity, we obtain an O(n log n) dynamic programming algorithm. For the bounded model, i.e., b < n, we first show that the problem is binary NP-hard even if there are only two distinct release dates. Then we present O(nb) and O((nb/h)(h)) algorithms for the case where the job processing order is predetermined in advance and for the case where there are h, h >= 2, distinct deteriorating rates, respectively. Furthermore, we provide a fully polynomial-time approximation scheme for the case where the number of distinct release dates is a constant. (C) 2010 Elsevier B.V. All rights reserved.