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

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

针对最小化完工时间的非等同并行多机调度一类问题,提出了一种混合遗传算法。该算法根据问题的特点,采用一种自然编码方案,此编码与调度方案一一对应,并对初始种群、交叉和变异等方法进行了研究。在鉴于遗传算法自然的并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,并行混合遗传算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,能适用于大规模非等同并行多机调度问题。

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.