论文研究 带不可用时间段的部分可续型单机最大完工时间调度.pdf

论文研究-带不可用时间段的部分可续型单机最大完工时间调度.pdf,  研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需部分进行重新加工.文中简单说明了此问题为NP-难问题,并证明了最大加工时间优先LPT规则的误差上限是α/2（其中α为重加工系数），且举例说明该界限是紧的。在此基础上，简单地说明了该算法对不可续型问