并行机问题的模拟退火调度算法研究

Research on Simulated Annealing Scheduling Algorithm for Parallel Machine Problem

研究了一类调度目标是最小化最大完成时间的并行机调度问题。考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解。分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法。除了交换变换,还引入插入变换以改变各子调度中作业个数。大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解。

This paper considers a kind of parallel machine scheduling problem with minimizing makespan.Considering the NP-hardness of this problem,the simulated annealing approach is introduced to obtain the near-optimal solutions with high quality.The limitation of the existing simulated annealing algorithm for this problem is analyzed.Two kinds of machines,crucial machine and non-crucial machine,are identified.A simulated annealing algorithm including a process of local optimization is designed.Apart from the swap operation,the insertion operation is presented to change the number of the sub-schedules.A large set of randomly generated instances are made to test the solution quality and the efficiency of the algorithm.Computational results show that the simulated annealing algorithm proposed in this paper can solve the problems with large size in a reasonable time.