Abstract: To solve the bi-objective permutation flowshop scheduling problem with makespan and total flow time minimized,an improved Multi-objective Evolutionary Algorithm based on Decomposition (MOEA/D) algorithm was proposed.To improve the quality of non-dominant solutions and enhance the efficiency of proposed algorithm,the grouping and statistical learning mechanism was embedded in a two-stage local search strategy,which was used to improve the external archive.The population was updated by adopting the perpendicular distance-based replacement strategy,and the effectiveness of the grouping mechanism was ensured.Computational results on the Taillard benchmark problems showed that the proposed improved MOEA/D was significantly superior to the traditional MOEA/D,NSGA-Ⅱ and MEDA/D-MK algorithms.

Key words: permutation flowshop scheduling, multi-objective, decomposition, evolutionary algorithm, statistical learning

摘要： 针对工期和总流水时间的两目标置换流水车间调度问题,提出一种改进的基于分解的多目标进化算法(MOEA/D)。为了改进非支配解集的质量,提高算法效率,在MOEA/D中嵌入分组和统计学习机制提出一种两阶段局部搜索策略改进外部存档。利用基于距离的替换策略更新种群,提高种群的多样性,保证了分组机制的有效性。基于Taillard标准测试问题的实验结果表明,所提出的改进MOEA/D算法明显优于传统MOEA/D、NSGA-Ⅱ、MEDA/D-MK等算法。

关键词: 置换流水车间调度, 多目标, 分解, 进化算法, 统计学习