摘要：研究了带机器准备时间的同类机最大完工时间调度问题，首先证明了工件互换的四个性质，进而提出了一种启发式算法，此算法以LPT算法得到的序列作为初始解，利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换，以提高解的质量．实验结果证明了此算法的有效性．

关键词：同类机调度 机器准备时间 lpt 

单位：合肥工业大学管理学院 合肥230009 过程优化与智能决策教育部重点实验室 合肥230009 Manchester Business School University of Manchester Manchester M15 6PB UK