求解一类并行多机调度问题的混合启发式算法  

A Hybrid Heuristic Algorithm for a Kind of Identical Parallel Machines Scheduling Problem

作　　者：常俊林[1] 张春慨[1] 邵惠鹤[1] 

机构地区：[1]上海交通大学自动化系,上海200030

出　　处：《计算机仿真》2004年第3期121-123,54,共4页Computer Simulation

基　　金：8 63计划 ( 2 0 0 2AA412 0 10 )

摘　　要：该文研究了一类工件具有不同释放时间的并行多机调度问题 ,调度目标为使总流程时间最小。针对该类调度问题具有强NP -hard的特点 ,首先构造了的一种启发式算法 ,该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降 ,结合遗传算法的全局搜索能力 ,提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点 ,能够在较短的时间内求解较大规模的调度问题 ,算法的计算量小 。This paper considers the identical parallel machines scheduling problem with the objective of minimizing the sum of the job-completion times(Jobs processed in the problem have different release times). In view of the strong NP-hard nature of this problem, a constructive heuristic algorithm which can provide good solutions in a modest amount of computer time is first proposed. Since the quality of the solutions provided by heuristics degrades with the increase of the problem's scale, and combining the global search ability of genetic algorithm, we proposed a hybrid heuristic to improve the quality of solutions further. Simulation results show that the hybrid heuristic combines the advantages of heuristic and genetic algorithm effectively. The algorithm has low computational complexity and strong robustness.

关 键 词：并行多机调度问题 车间调度问题 混合启发式算法 NP问题 

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]