解非等同并行多机调度问题的并行遗传算法  

Parallel Genetic Algorithm for Solving Non-identical Parallel Multi-machine Schedule Problem

作　　者：高家全[1] 方蕾[1] 

机构地区：[1]浙江工业大学之江学院,杭州310024

出　　处：《计算机工程》2007年第1期198-199,203,共3页Computer Engineering

基　　金：浙江省教委基金资助项目(20051436)

摘　　要：针对最小化完工时间的非等同并行多机调度一类问题,提出了一种混合遗传算法。该算法根据问题的特点,采用一种自然编码方案,此编码与调度方案一一对应,并对初始种群、交叉和变异等方法进行了研究。在鉴于遗传算法自然的并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,并行混合遗传算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,能适用于大规模非等同并行多机调度问题。In order to solve a kind of non-identical parallel machine scheduling problem for minimizing the make-span, a parallel hybrid genetic algorithm is suggested. Its coding method is simple and can effectively reflect the scheduling policy, and the methods of the generation of the initial population, crossover and mutation are also researched. Considering the requirements of adapting it to this kind of lager scale problem and real-time scheduling, it is parallelly implemented under the mode of master-slave control networks. The computational results suggest that the genetic algorithm is efficient, and advantageous over genetic algorithms and heuristic procedures, and fit for large-scale non-identical parallel machine scheduling problem.

关 键 词：并行混合遗传算法 非等同并行多机调度 MPI 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]