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

Heuristic algorithm for uniform-machine scheduling with machine release times

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

This paper considers a problem of uniform-machine scheduling with machine release times to minimize makespan. Firstly, four properties of swapping jobs are proposed. Then, based on the properties, a heuristic algorithm is presented, which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan. Finally, computational results show that the presented heuristic is efficient and effective.