带不可用时间段的部分可续型单机加权完工时间和调度

Minimizing total weighted completion time in semiresumable case of single-machine scheduling with an availability constraint

研究了机器带有一个不可用时间段的单机最小化加权完工时间和调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需进行部分重新加工.文中简单说明此问题为NP-难问题,并提出了一种动态规划算法和一种分枝定界算法来求得此问题的最优解.实验结果证实了这两种算法的正确性及有效性,且表明分枝定界算法要优于动态规划算法.

Single-machine scheduling with an availability constraint to minimize total weighted completion time under the assumption that the disrupted job is semiresumable is considered in this paper.It is easily shown that this problem is NP-hard,and a dynamic programming algorithm and a branch-and-bound algorithm are developed to solve it optimally.Experiment results show that these two algorithms are accurate and efficient,and that the branch-and-bound outperforms the dynamic programming absolutely.