面向多目标流水车间调度的多种群多目标遗传算法

Multipopulation multiobjective genetic algorithm for multiobjective permutation flow shop scheduling problem

中文关键词  多种群  遗传算法  多目标优化  流水车间调度

英文关键词  multipopulation  genetic algorithm  multiobjective optimization  flow shop scheduling

中文摘要

      针对制造型企业普遍存在的流水车间调度问题, 建立了以最小化最迟完成时间和总延迟时间为目标的多 目标调度模型, 并提出一种基于分解方法的多种群多目标遗传算法进行求解. 该算法将多目标流水车间调度问题 分解为多个单目标子问题, 并分阶段地将这些子问题引入到算法迭代过程进行求解. 算法在每次迭代时, 依据种群 的分布情况选择各子问题的最好解及与其相似的个体分别为当前求解的子问题构造子种群, 通过多种群的进化完 成对多个子问题最优解的并行搜索. 通过对标准测试算例进行仿真实验, 结果表明所提出的算法在求解该问题上 能够获得较好的非支配解集.

英文摘要

      Since the permutation flow shop scheduling problem exits extensively in manufacturing enterprises, a multiobjective flow shop scheduling problem with the objectives of minimizing the makespan and the total tardiness is investigated in this paper. In order to solve it, a multipopulation multiobjective genetic algorithm based on decomposition is proposed. The proposed algorithm decomposes the investigated problem into multiple single objective subproblems introduced into the iteration course step by step. At each iteration, multiple subpopulations are constructed for the current solved subproblems based on the distribution of population, which realizes the goal of solving them simultaneously. The evolution of multiple subpopulations can be used to search the optimal solutions of multiple subproblems. Experimental results on some instances show that the proposed algorithm can get better performance in solving the multiobjective permutation flow shop scheduling problem.