带不可用时间段的部分可续型单机最大完工时间调度

Minimizing makespan in semiresumable case of single-machine scheduling with an availability constraint

研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需部分进行重新加工.文中简单说明了此问题为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.