带不可用时间段的两台同类机加权完工时间和调度

Two-uniform machine scheduling with an availability constraint to minimize the total weighted completion time

研究了两台同类机加权完工时间和调度,其中一台机器在一个固定的时间段内不可用,并且被不可用时间段中断的工件是部分可续的,即被中断工件在机器不可用之前已加工的部分在机器重新可用之后需进行部分重新加工.首先简单说明了此问题的NP难性,然后证明了最优调度的一个性质,并在此基础上提出了一种动态规划算法来求得小规模问题的最优解,另外还提出了一种启发式算法来求得中大规模问题的近优解.实验结果表明了这两种算法的有效性.

The two-uniform machine scheduling problem to minimize the total weighted completion time where one of the machines is unavailable in a fixed interval was considered. The disrupted job by the machine availability constraint is supposed to be semiresumable, i. e. , it has to partially restart after the machine is available again. First, it was easily shown that this problem is NP-hard. Then a property of the optimal solution was proposed. Based on these, a dynamic programming algorithm was developed to derive the optimal solution to the small-sized problems. Additionally, a heuristic was proposed to obtain the near-optimal solution to the medium-to-large sized problems. Experiment results show their effectiveness.