摘要
研究了两台同类机加权完工时间和调度,其中一台机器在一个固定的时间段内不可用,并且被不可用时间段中断的工件是部分可续的,即被中断工件在机器不可用之前已加工的部分在机器重新可用之后需进行部分重新加工.首先简单说明了此问题的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.
基金
国家自然科学基金(70631003)
高等学校博士点基金(200803590007)
国家自然科学基金重大研究计划(90718037)资助
关键词
同类机调度
不可用时间段
部分可续型
加权最短加工时间优先规则
动态规划
uniform machine scheduling
availability constraint
semiresumable case
weighted shortest processing time (WSPT)
dynamic programming