Minimizing number of tardy jobs on a single machine subject to periodic maintenance
Minimizing number of tardy jobs on a single machine subject to periodic maintenance
复制标题
DOI：
10.1016/j.omega.2008.01.001
复制
发表时间：
2009-06
影响因子：
6.9
通讯作者：
Wen‐Jinn Chen
中科院分区：
文献类型：
--
作者：
Wen‐Jinn Chen
研究了具有周期性维护的单机调度问题。在本研究中，一个维护计划由几个维护周期组成，每个维护周期以一个周期的时间间隔进行安排。目标是找到一个计划，使需要定期维护的延迟作业和不可恢复作业的数量最小化。在摩尔算法的基础上，提出了一种有效的启发式算法，为该问题提供了接近最优的调度。提出了一种分支定界算法来求解最优调度。该算法实现了与该问题相关的一些重要定理。计算结果证明了所提启发式算法的有效性。
This paper considers a single-machine scheduling problem with periodic maintenance. In this study, a schedule consists of several maintenance periods and each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the number of tardy jobs subject to periodic maintenance and nonresumable jobs. Based on the Moore's algorithm, an effective heuristic is developed to provide a near-optimal schedule for the problem. A branch-and-bound algorithm is also proposed to find the optimal schedule. Some important theorems associated with the problem are implemented in the algorithm. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.