近似支配的NSGA-Ⅲ算法求解柔性作业车间调度问题  

Approximate dominance NSGA-Ⅲ algorithm for solving flexible job-shop scheduling problem

作　　者：安友军 陈晓慧[1] An Youjun;Chen Xiaohui(The State Key Laboratory of Mechanical Transmission,Chongqing University,Chongqing 400030,China)

机构地区：[1]重庆大学机械传动国家重点实验室,重庆400030

出　　处：《系统工程学报》2021年第3期416-432,共17页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(51035008);国家科技重大专项基金资助项目(2016ZX04004-005);重庆大学机械传动国家重点实验室基础研究基金资助项目(SKLMT-ZZKT-2017M16).

摘　　要：针对NSGA-Ⅲ算法求解多目标柔性作业车间调度问题时存在的收敛性、局部搜索和精英存储上的不足,依次设计了近似支配原则、变邻域局部搜索和精英存储策略,进而提出了一种近似支配的NSGA-Ⅲ-AD算法.结合柔性作业车间调度问题的特点,建立了多目标优化模型,设计了种群个体的初始化方法、近似支配的选择操作和变邻域的遗传操作.在仿真实验中,运用三个优化目标和六个优化目标的调度实例对提出算法的整体和局部性能进行测试,并利用收敛性、多样性、分布性和超体积等指标对非支配解集进行综合评价.实验结果表明,NSGA-Ⅲ-AD算法所获解集优于或近似等于现存方法,验证了提出算法的有效性和可行性.NSGA-Ⅲ algorithm is insufficient on the convergence,the local search,and the elite storage when solving the multi-objective flexible job-shop scheduling problem.For overcoming its shortcomes,the principle of approximate dominance,the variable neighborhood local search,and the elite storage strategy are designed in turn,then an approximate dominance NSGA-Ⅲ-AD algorithm is proposed.Considering the characteristics of the flexible job-shop scheduling problem,the multi-objective optimization model is established,thereafter,the initial method of population individual,the approximate dominance select operation,and the genetic operation of variable neighborhood are designed.In the simulation experiments,the overall and local performances of the proposed algorithm are tested by applying scheduling examples with three optimization objectives and six optimization objectives.Otherwise,the non-dominated solution sets are comprehensively evaluated in terms of the metrics of convergence,diversity,distribution,and hypervolume.The experimental results show that the solution set obtained by NSGA-Ⅲ-AD algorithm is better than or approximately equal to the existing methods,which further proves the validity and feasibility of the proposed algorithm.

关 键 词：柔性作业车间调度问题 NSGA-Ⅲ 近似支配 变邻域搜索 精英存储策略 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]