带机器准备时间的同类机调度问题的启发式算法

作者：马英; 杨善林; 汤大为

来源：系统工程理论与实践, 2012, (09): 2022-2030.

• 同类机调度
• 机器准备时间
• LPT uniform-machine scheduling
• machine release times
• longest processing time

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

• 单位
  合肥工业大学