并行多机调度问题的一种基于组合规则的遗传算法

Genetic Algorithm Method Based on Combinatorial Rules in Identaical Parallel Machine Scheduling Problem

本文对最小化完工时间并行多机调度问题提出了一种基于组合规则的遗传算法 .用遗传算法来优化调度策略 ,使得在不同的调度阶段 ,可采用不同的调度规则以提高算法性能 ,并用计算实例表明了该遗传算法优于基于机器编码的模拟退火算法和遗传算法 ,并能适用于大规模并行多机调度问题 ,算法计算量小 ,鲁棒性强 .

A kind of genetic algorithm based on combinatorial rules is presented for solving the identical machine scheduling problem of minimizing the makespan,that is,scheduling policy is optimized by genetic algorithm,and it allows that different scheduling rule to be adopted at different scheduling stage to improve the performance of the algorithm.Computational results show that the genetic algorithm has advantage over simulated annealing and genetic algorithms based on machine code and is fit for large scale identical parallel machine scheduling problem,and that the algorithm has small quantity of calculation and strong robustness.