摘要
研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需部分进行重新加工.文中简单说明了此问题为NP-难问题,并证明了最大加工时间优先LPT规则的误差上限是α/2(其中α为重加工系数),进而提出了一个基于LPT规则的启发式算法.实验结果证明了此算法的高效性,此外对不同参数对此算法性能的影响也进行了分析.
Single machine scheduling with an unavailability interval to minimize makespan is considered in this paper under the assumption that the disrupted job has to partially restart after the machine becomes available again. It is easily shown that this problem is NP-hard, and it is shown that the Longest Pro- cessing Time （LPT） algorithm has a relative worst-case error bound of α/2, where α is re-processing rate. Furthermore, an example is provided to show that this bound is tight. Then a LPT-based heuristic is proposed. Computational results show that this heuristic is quite effective in finding an optimal or near-optimal schedule. Effects of different parameters on this heuristic are also analyzed in this paper.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2009年第4期128-134,共7页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(70631003)
国家高技术研究发展计划863重点项目(2008AA042901)
关键词
单机调度
部分可续型
最长加工时间优先
single-machine scheduling
semiresumable case
longest processing time first
