An exact algorithm for the precedence-constrained single-machine scheduling problem
An exact algorithm for the precedence-constrained single-machine scheduling problem
复制标题
DOI：
10.1016/j.ejor.2013.02.048
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
Shunji Tanaka;Shun Sato
中科院分区：
文献类型：
--
作者：
Shunji Tanaka;Shun Sato
针对优先级受限的单机调度问题，在不允许机器空闲的情况下，提出了一种有效的精确算法，以最小化总作业完成成本。该算法基于连续升华动态规划（SSDP）方法，是对先前无优先约束问题算法的扩展。该方法通过动态规划求解原问题的拉格朗日松弛得到下界，然后通过在松弛中添加约束对下界进行改进，直至下界与上界之间的间隙消失。数值实验结果表明，该算法能够求解优先级约束下的总加权迟到和总加权迟到-迟到问题的所有不超过50个作业的实例，以及前者的大多数100个作业的实例。
This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors’ previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness–tardiness problems, and most instances with 100 jobs of the former problem.