Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance
Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance
复制标题
DOI：
10.1016/j.cor.2011.11.002
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
Ju-Yong Lee;Yeong-Dae Kim
中科院分区：
文献类型：
--
作者：
Ju-Yong Lee;Yeong-Dae Kim
本文主要研究需要定期维护的单机作业调度问题，目标是最小化拖期作业的数量。提出了一种两阶段启发式算法，该算法首先用Moore算法的一种改进方法求出初始解，然后在第二阶段对解进行改进。通过对随机产生的问题实例的计算实验，对所提出的启发式算法的性能进行了评估，结果表明，该启发式算法在更短的时间内得到了接近于商业整数规划求解器的解，并且在解质量方面优于现有的启发式算法。
This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality.