求解多目标作业车间调度问题的双种群遗传算法

Double-population genetic algorithm for multi-objective Job Shop scheduling problem

针对多目标作业车间调度问题,提出一种将正逆序调度方法与生成调度活动的遗传算法相结合的双种群遗传算法。该算法利用活动调度缩减解空间,提出采用正、逆序遗传调度算法分别在不同种群优化不同目标函数,将多目标问题分解成多个单目标问题。在进化过程中,通过个体迁移算子加快多个目标的并行搜索,并提出了一种构造Pareto解集的精英锦标赛法则。通过基于Benchmark算例的仿真实验,验证了该算法求解多目标作业车间调度问题的有效性。

To solve multi-objective Job Shop scheduling problem,a double-population genetic algorithm based on forward-backward scheduling approach and Giffler-Thompson algorithm was proposed.The method reduced the solution space by means of active scheduling.Forward-backward genetic scheduling algorithm was proposed to optimize different objective functions in different populations and multi-objective problems were decomposed into various single-objective problems.In each generation of the evolving process,individual migration operator was applied to accelerate the parallel searching.An elitist arena＇s principle was presented to improve the efficiency of constructing the Pareto optimal solutions.The experimental results of the Benchmark instances taken from literature demonstrated the effectiveness of the algorithm proposed on solving multi-objective job shop scheduling problems.