求解多目标柔性作业车间调度问题的两层遗传算法  

Two-phase genetic algorithm for multi-objective flexible job-shop scheduling problem

作　　者：张立果 黎向锋[1] 左敦稳[1] 张丽萍[2] 唐浩 ZHANG Liguo;LI Xiangfeng;ZUO Dunwen;ZHANG Liping;TANG Hao(College of Mechanical and Electrical Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing Jiangsu 210016,China;College of Science,Nanjing University of Aeronautics and Astronautics,Nanjing Jiangsu 210016,China)

机构地区：[1]南京航空航天大学机电学院,南京210016 [2]南京航空航天大学理学院,南京210016

出　　处：《计算机应用》2020年第S01期14-22,共9页journal of Computer Applications

基　　金：国家自然科学基金资助项目(51575269)。

摘　　要：多目标柔性作业车间调度是复杂加工系统中一类重要的调度问题。针对大多数算法求解多目标柔性作业车间调度问题所存在的稳定性差、搜索深度不够、无法对多目标中单一目标进行深入搜索的问题,对传统遗传算法作出改进,设计了一套新的交叉策略,并舍去选择算子,在此基础上提出了一种求解多目标问题的双层遗传算法。引入了信息熵的概念对所提算法优化后的种群进行了分析,并从最大完工时间、最大机器负载、机器总负载三个方面对经典案例进行测试。与其他同类算法相比,该双层遗传算法共获得了31个可支配其他算法所求解的非支配解,和96个新的支配解。实验结果表明,所提算法在保留种群多样性的同时,仍拥有较好的深度搜索能力和跳出局部最优的能力,体现了算法的可靠性。Multi-objective Flexible Job-shop Scheduling Problem(Mo-FJSP)is a kind of important scheduling problems in complex manufacturing system.Aiming at the problem that the majority of algorithms used for Mo-FJSP tend to have the characteristics of poor stability,insufficient search depth and inability to deeply search a single object in a multi-objective problem,the general Genetic Algorithm(GA)was improved by designing a new crossover strategy and deleting the selection operator.On this basis,a method called two-phase GA was proposed.The conception of information entropy was introduced to analyze the population optimized by the proposed algorithm and from the respects of minimizing maximal completion time of machines,minimizing workload of the most loaded machine and minimizing the total workload of all machines,several classic examples were tested by the proposed algorithm.The two-phase GA achieved 31 non-dominated answers which can dominate other answers got by other the same kind algorithms and 96 new non-dominated answers.Experimental results show that the proposed algorithm has a good ability of deep searching and can jump out of local optimization while retaining the diversity of population,which shows the reliability of this algorithm.

关 键 词：柔性作业车间调度问题 遗传算法 多目标调度 选择策略 信息熵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]