摘要：研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题，并假定被中断工件是部分可续的，即其已加工部分在机器重新可用之后需部分进行重新加工．文中简单说明了此问题为NP一难问题，并证明了最大加工时间优先LPT规则的误差上限是α／2（其中α为重加工系数），进而提出了一个基于LPT规则的启发式算法．实验结果证明了此算法的高效性，此外对不同参数对此算法性能的影响也进行了分析．

关键词：单机调度 部分可续型 最长加工时间优先 

单位：合肥工业大学管理学院 合肥230009 过程优化与智能决策教育部重点实验室 合肥230009 特鲁瓦工业大学工业系统优化实验室 特鲁瓦10010