A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
复制标题
DOI：
10.1007/s10951-011-0242-0
复制
发表时间：
2011-06
影响因子：
2
通讯作者：
Shunji Tanaka;Shuji Fujikuma
中科院分区：
文献类型：
--
作者：
Shunji Tanaka;Shuji Fujikuma
针对允许机器空闲时间的一般单机排序问题，提出了一种有效的精确算法。该算法是基于SSDP(逐次升华动态规划)算法的无机器空闲问题的推广。我们首先将以前的算法扩展到机器空闲时间问题，然后提出了几点改进。然后，将该算法应用于四类单机调度问题：交货期相同(零)的总加权提前-拖期问题、不同交货期的总加权完工时间问题和不同交货期的总加权拖期问题。计算实验表明，我们的算法性能优于现有的精确算法，前三个问题的实例最多可以解决200个作业，而最后一个问题的实例最多可以解决80个作业。
This paper proposes an efficient exact algorithm for the general single-machine scheduling problem where machine idle time is permitted. The algorithm is an extension of the authors’ previous algorithm for the problem without machine idle time, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. We first extend our previous algorithm to the problem with machine idle time and next propose several improvements. Then, the proposed algorithm is applied to four types of single-machine scheduling problems: the total weighted earliness-tardiness problem with equal (zero) release dates, that with distinct release dates, the total weighted completion time problem with distinct release dates, and the total weighted tardiness problem with distinct release dates. Computational experiments demonstrate that our algorithm outperforms existing exact algorithms and can solve instances of the first three problems with up to 200 jobs and those of the last problem with up to 80 jobs.