基于改进NSGA2算法的多目标柔性作业车间调度

doi:10.3969/j.issn.1007-7375.e17-3276

工业工程 ›› 2018, Vol. 21 ›› Issue (2): 55-61.doi: 10.3969/j.issn.1007-7375.e17-3276

基于改进NSGA2算法的多目标柔性作业车间调度

陈辅斌¹, 李忠学¹, 杨喜娟²

1. 兰州交通大学机电工程学院, 甘肃兰州 730070;
2. 兰州交通大学电子与信息工程学院, 甘肃兰州 730070

收稿日期:2017-11-15 出版日期:2018-04-30 发布日期:2018-05-12
作者简介:陈辅斌(1989-),男,甘肃省人,硕士研究生,主要研究方向为先进制造系统
基金资助:
国家自然科学基金资助项目（71361019）；兰州交通大学校青年基金资助项目（2015007）

Multi-objective Flexible Job Shop Scheduling based on Improved NSGA2 Algorithm

CHEN Fubin¹, LI Zhongxue¹, YANG Xijuan²

1. School of Mechatronic Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China;
2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

Received:2017-11-15 Online:2018-04-30 Published:2018-05-12

摘要/Abstract

摘要： 柔性作业车间调度问题（FJSP）是经典作业车间调度问题的重要扩展，其中每个操作可以在多台机器上处理，反之亦然。结合实际生产过程中加工时间、机器负载、运行成本等情况，建立了多目标调度模型。针对NSGA2算法收敛性不足的缺陷，引入免疫平衡原理改进NSGA2算法的选择策略和精英保留策略，成功避免了局部收敛问题，提高了算法的优化性能。通过与启发式规则以及多种智能算法进行比对仿真实验，改进的NASA2算法能获得更好的解。用改进的NAGA2算法求解实例，不仅有效地克服多目标间数量级和量纲的障碍，而且得到了满意的pareto解集，进一步验证了该算法和模型的可行性。

关键词: 柔性作业车间调度, 多目标模型, 免疫平衡, 选择策略, 精英保留策略

Abstract: Flexible Job Shop Scheduling Problem (FJSP) is an important extension of the classic job shop scheduling problem where each operation can be handled on multiple machines and vice versa. Combined with the actual production process of processing time, machine load, operating costs and other conditions, a multi-objective scheduling model is established. Aiming at the defect of insufficient convergence of NSGA2 algorithm, the immune balance principle is introduced to improve the selection strategy and elite retention strategy of NSGA2 algorithm, avoiding the local convergence problem and improving the optimization performance of the algorithm. By comparing with heuristic rules and various intelligent algorithms, the improved NASA2 algorithm can get a better solution. Using improved NAGA2 algorithm to solve the case not only effectively overcomes the barriers in order of magnitude and dimension of the objectives, but also obtains a satisfactory pareto solution set, further verifying the feasibility of the algorithm and the model.

Key words: flexible job shop manufacturing, multi-objective scheduling model, immune balance, selection strategy, elite retention strategy

中图分类号:

TP278

陈辅斌, 李忠学, 杨喜娟. 基于改进NSGA2算法的多目标柔性作业车间调度[J]. 工业工程, 2018, 21(2): 55-61.

CHEN Fubin, LI Zhongxue, YANG Xijuan. Multi-objective Flexible Job Shop Scheduling based on Improved NSGA2 Algorithm[J]. Industrial Engineering Journal , 2018, 21(2): 55-61.

参考文献

[1] 王凌. 车间调度及其遗传算法[M]. 北京:清华大学出版社, 2003.
[2] WANG L, ZHOU G, XU Y, et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2012, 60(1-4):303-315.
[3] 薛宏全, 魏生民, 张鹏, 等. 基于多种群蚁群算法的柔性作业车间调度研究[J]. 计算机工程与应用, 2013, 49(24):243-261.XUE Hongquan, WEI Shengmin, ZHANG Peng, et al. Study on flexible job shop scheduling based on multi-group ant colony algorithm[J]. Journal of Computer Engineering and Applications, 2013, 49(24):243-261.
[4] 赵敏, 殷欢, 孙棣华, 等. 基于改进人工鱼群算法的柔性作业车间调度[J]. 中国机械工程, 2016, 8(12):1059-1065.ZHAO Min, YIN Huan, SUN Dihua, et al. Fuzzy job shop scheduling based on improved artificial fish swarm algorithm[J]. China Mechanical Engineering, 2016, 8(12):1059-1065.
[5] WU Xiuli, ZHANG Zhiqiang, DU Yanhua, et al. An improved bacteria foraging algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2015, 21(5):1262-1270.
[6] 雷德明. 基于新型教学优化算法的低碳柔性作业车间调度[J]. 控制与决策, 2017, 32(9):1621-1627.LEI Deming. Low-carbon flexible job shop scheduling based on new teaching optimization algorithm[J]. Control & Decision, 2017, 32(9):1621-1627.
[7] 赵诗奎, 方水良. 基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J]. 机械工程学报, 2013, 49(16):160-169.ZHAO Shikui, FANG Shuiliang. Optimization of job shop scheduling based on genetic algorithm and process coding[J]. Journal of Mechanical Engineering, 2013, 49(16):160-169.
[8] I Driss, KN Mouss, A Laggoun, et al. A new genetic algorithm for flexible job-shop scheduling problems[J]. Journal of Mechanical Science & Technology, 2015, 29(3):1273-1281.
[9] ZHANG G, GAO L, SHI Y, et al. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2011, 38(4):3563-3573.
[10] KACEM I, HAMMADIS, BORNEP. Approach by localization and muti-objective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transaction System, Man, and Cybernetics-Part C, 2002, 32(1):1-13.
[11] 张超勇, 董星, 王晓娟, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报, 2010, 46(11):156-164.ZHANG Chaoyong, DONG Xing, WANG Xiaojuan, et al. Multi-objective flexible job shop scheduling based on improved non-dominated ranking genetic algorithm[J]. Journal of Mechanical Engineering, 2010, 46(11):156-164.
[12] ROOHOLLAH Javadi, MARYAM Hasanzadeh. A new method for hybridizing metaheuristics for multi-objective flexible job shop scheduling[C]. International eConference on Computer and Knowledge Engineering. 2012.
[13] 吴秀丽, 孙树栋, 杨展, 等. 多目标柔性Job Shop调度问题的技术现状和发展趋势[J]. 计算机应用研究, 2007, 24(3):1-5, 9.WU Xiuli, SUN Shudong, YANG Zhan, et al. Status and development trend of multi-objective flexible job shop scheduling problem[J]. Application Research of Computers, 2007, 24(3):1-5, 9.
[14] 雷德明, 严新平. 多目标智能优化算法及其应用[M]. 北京:科学出版社, 2009.
[15] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-1997.
[16] 莫宏伟, 左兴权. 人工免疫系统[M]. 北京:科学出版社, 2009.
[17] 魏巍, 谭建荣, 冯毅雄, 等. 柔性工作车间调度问题的多目标优化方法研究[J]. 计算机集成制造系统, 2009, 15(8):1592-1598.WEI Wei, TAN Jianrong, FENG Yixiong, et al. Multi-objective optimization method for flexible work shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2009, 15(8):1592-1598.
[18] ABDULLAH Konak, DAVID W COIT, Alice E Smith, et al. Multi-objective optimization using genetic algorithms:A tutorial[J]. Reliability Engineering and System Safety, 2006(9):992-1007.
[19] 张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7):145-151.ZHANG Guohui, GAO Liang, LI Peigen, et al. An improved genetic algorithm to solve the problem of flexible job shop scheduling[J]. Journal of Mechanical Engineering, 2009, 45(7):145-151.

基于改进NSGA2算法的多目标柔性作业车间调度

Multi-objective Flexible Job Shop Scheduling based on Improved NSGA2 Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.
[3]	吴健, 鲁芳, 罗定提. 基于游客感知服务质量的多目标旅游产品优化设计[J]. 工业工程, 2018, 21(3): 41-48.