An efficient exact algorithm for general single-machine scheduling with machine idle time
An efficient exact algorithm for general single-machine scheduling with machine idle time
复制标题
DOI：
10.1109/coase.2008.4626508
复制
发表时间：
2008-09
期刊：
影响因子：
--
通讯作者：
Shunji Tanaka;Shuji Fujikuma
中科院分区：
文献类型：
--
作者：
Shunji Tanaka;Shuji Fujikuma
本文给出了允许机器空闲时间的一般单机排序问题的精确算法。该算法是基于SSDP(逐次升华动态规划)方法的无机器空闲问题的扩展算法。在该算法中，通过对原问题的拉格朗日松弛进行动态规划来计算下界，然后通过对松弛施加附加约束来逐步改进下界，直到上下界之间的差距减小。在算法过程中消除了不必要的动态规划状态，以减少计算工作量和内存使用。实验结果表明，该算法可以解决200个单机总加权提前-拖期问题的作业实例。
In this paper we propose an exact algorithm for the general single-machine scheduling problem where machine idle time is permitted. The algorithm is an extension of the authorspsila previous algorithm for the problem without machine idle time, which is based on the SSDP (successive sublimation dynamic programming) method. In this algorithm a lower bound is computed by applying dynamic programming to a Lagrangian relaxation of the original problem and then it is successively improved by imposing additional constraints on the relaxation until the gap between lower and upper bounds diminishes. Unnecessary dynamic programming states are eliminated in the course of the algorithm to reduce both computational efforts and memory usage. Experimental results show that the proposed algorithm can solve 200 jobs instances of the single-machine total weighted earliness-tardiness problem.