改进粒子群算法在考虑运输时间下的FJSP研究

doi:10.16182/j.issn1004731x.joss.19-0672

系统仿真学报 ›› 2021, Vol. 33 ›› Issue (4): 845-853.doi: 10.16182/j.issn1004731x.joss.19-0672

改进粒子群算法在考虑运输时间下的FJSP研究

陈魁, 毕利

宁夏大学信息工程学院,宁夏银川 750021

收稿日期:2019-12-24 修回日期:2020-04-17 出版日期:2021-04-18 发布日期:2021-04-14
通讯作者: 毕利(1968-),女,硕士,教授,研究方向为信息系统集成。E-mail：billy1968@163.com
作者简介:陈魁(1995-),男,硕士生,研究方向为车间调度和智能算法。E-mail：972463178@qq.com
基金资助:
国家自然科学基金(61662058); 西部一流大学科研创新项目(ZKZD2017005)

Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time

Chen Kui, Bi Li

School of Information Engineering, Ningxia University, Yinchuan 750021, China

Received:2019-12-24 Revised:2020-04-17 Online:2021-04-18 Published:2021-04-14

摘要/Abstract

摘要： 在实际的柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)生产环境中,不仅存在工件的加工时间,而且还存在工件在机器之间的运输时间,因此考虑运输时间的柔性作业车间调度更具实际意义。提出混合离散粒子群算法求解考虑运输时间的柔性作业车间调度问题。针对粒子群算法的不稳定性和早熟问题,应用了邻域搜索算法提高其稳定性,引入竞争学习机制和随机重启算法避免算法的早熟。通过实验对比近期的同类算法,证明了混合离散粒子群算法在求解考虑运输时间FJSP时的可行性和有效性。

关键词: 混合离散粒子群算法, 柔性作业车间调度, 邻域搜索算法, 竞争学习机制

Abstract: In the actual FJSP(Flexible Job-shop Scheduling Problem) production environment, there is not only the processing time of the workpiece, but also the transport time of the workpiece between the machines, so the flexible job shop scheduling considering the transport time is more practically significant. A hybrid discrete particle swarm optimization algorithm is proposed to solve the flexible job-shop scheduling problem considering transport time. Aiming at the instability and precocity of particle swarm optimization algorithm, the neighborhood search algorithm is applied to improve its stability, and the combination of competitive learning mechanism and random restart algorithm are introduced to avoid the precocity of pso algorithm. By comparing recent similar algorithms, the feasibility and effectiveness of the hybrid discrete particle swarm optimization algorithm for FJSP with transport time is proved.

Key words: hybrid discrete particle swarm optimization, flexible job shop scheduling, neighborhood search algorithm, competitive learning mechanism

中图分类号:

TP391.9

陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.

Chen Kui, Bi Li. Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time[J]. Journal of System Simulation, 2021, 33(4): 845-853.

参考文献

[1] 王雷, 蔡劲草, 唐敦兵, 等. 基于改进遗传算法的柔性作业车间调度[J]. 南京航空航天大学学报, 2017, 49(6): 779-785.
Wang Lei, Cai Jincao, Tang Dunbing, et al.Flexible Job Shop Scheduling Problem Based on Improved Genetic Algorithm[J]. Journal of Nanjing University of Aeronautics & Astronautic, 2017, 49(6): 779-785.
[2] 张国辉, 张凌杰, 吴立辉, 等. 精英进化策略求解柔性作业车间调度问题[J]. 计算机应用研究, 2016, 33(12): 3579-3581.
Zhang Guohui, Zhang Lingjie, Wu Lihui, et al.Solving Flexible Job-Shop Scheduling with Elite Evolution Strategy[J]. Application Research of Computers, 2016, 33(12): 3579-3581.
[3] 靳彬锋, 毕利. 基于遗传算法的多目标车间调度[J]. 组合机床与自动化加工技术, 2019, 39(4): 157-160.
Jin Binfeng, Bi Li.Multi-objective Shop Scheduling Based on Genetic Algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2019, 39(4): 157-160.
[4] 程冰, 徐华, 王玲娣, 等. 改进人工蜂群求解多目标柔性作业车间调度问题[J]. 信息与控制, 2019, 48(1): 115-122.
Cheng Bing, Xu Hua, Wang Lingdi, et al.Improved Artificial Bee Colony Algorithm for Solving Multi- objective Flexible Job-Shop Scheduling Problem[J]. Information and Control, 2019, 48(1): 115-122.
[5] 张静, 王万良, 徐新黎, 等. 基于改进粒子群算法求解柔性作业车间批量调度问题[J]. 控制与决策, 2012, 27(4): 513-518.
Zhang Jing, Wang Wanliang, Xu Xinli, et al.Improved Particle Swarm Algorithm for Batch Splitting Flexible Job Shop Scheduling[J]. Control and Decision, 2012, 27(4): 513-518.
[6] 侯晓莉, 刘永, 江来臻, 等. 多目标FJSP的一维编码粒子群优化求解方法[J]. 计算机工程与应用, 2015, 51(13): 47-51.
Hou Xiaoli, Liu Yong, Jiang Laizhen, et al.Multi-objective Optimization Method for Flexible Job-shop Scheduling Problems Based on Unidimensional-encoded Particle Swarm Optimization[J]. Compyter Engineering and Applications, 2015, 51(13): 47-51.
[7] 仲于江, 杨海成, 莫蓉, 等. 基于小生境粒子群算法的柔性作业车间调度优化方法[J]. 计算机集成制造系统, 2015, 21(12): 3231-3238.
Zhong Yujiang, Yang Haicheng, Mo Rong, et al.Optimization Method of Flexible Job-shop Scheduling Problem based on Niching and Particle Swarm Optimization Algorithms[J]. Computer Integrated Manufacturing Systems, 2015, 21(12): 3231-3238.
[8] Huang S, Tian N, Wang Y, et al.Multi-objective Flexible Job-shop Scheduling Problem Using Modified Discrete Particle Swarm Optimization[J]. Springer Plus (S2193-1801), 2016(5): 1432-1454.
[9] Kato E R R, Aranba G D D A, Tsunaki R H. A New Approach to Solve the Flexible Job Shop Problem based on a Hybrid Particle Swarm Optimization and Random-Restart Hill Climbing[J]. Computers & Industrial Engineering (S0360-8352), 2018, 125: 178-189.
[10] Huang X B, Guan Z L, Yang L X.An Effective Hybrid Algorithm for Multi-objective Flexible Job-shop Scheduling Problem[J]. Advances in Mechanical Engineering (S1687-8140), 2018, 10(9): 1-14.
[11] 朱伟, 赵水晶. 考虑工件移动和成本的多目标柔性作业车间调度问题优化研究[J]. 现代制造工程, 2019(7): 104-110.
Zhu Wei, Zhao Shuijing.Research on Multi-objective Flexible Job-shop Scheduling Problem Considering Workpiece Movement and Operation Cost[J]. Modern Manufacturing Engineering, 2019(7): 104-110.
[12] 赵宁, 李开典, 田青, 等. 考虑运输时间柔性作业车间调度问题的快速寻优方法[J]. 计算机集成制造系统, 2015, 21(3): 724-732.
Zhao Ning, Li Kaidian, Tian Qing, et al.Fast Optimization Approach of Flexible Job Shop Scheduling with Transport Time Consideration[J]. Computer Integrated Manufacturing Systems, 2015, 21(3): 724-732.
[13] Zhang G H, Sun J H, Liu X, et al.Solving Flexible Job Shop Scheduling Problems with Transportation Time based on Improved Genetic Algorithm[J]. Mathematical Biosciences and Engineering (S1547-1063), 2019, 16(3): 1334-1347.
[14] Huang Z, Yang J J.A Hybrid Approach for Solving the Flexible Job-Shop Scheduling Problem with Considering Transporting Time and Deteriorating Effect[C]. Beijing: CISC LNEE, 2019, 593: 295-305.
[15] Huang X B, Yang L X.A Hybrid Genetic Algorithm for Multi-objective Flexible Job Shop Scheduling Problem Considering Transportation Time[J]. International Journal of Intelligent Computing and Cybernetics (S1756-378X), 2019, 12(2): 154-174.
[16] Kacem I, Hammadi S, Borne P.Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-shop Scheduling Problems[J]. IEEE Transactions on Systems Man & Cybernetics Part C (S1094-6977), 2002, 32(1): 1-13.
[17] 李小华. 基于粒子群算法的车间作业调度研究[D]. 武汉: 武汉科技大学, 2009.
Li Xiaohua.Research on Job-shop Scheduling Problem Based on Particle Swarm Optimization Algorithom[D]. Wuhan: Wuhan University of Science and Technology, 2009.
[18] 戴月明, 王明慧, 王春, 等. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2017, 29(6): 1268-1276.
Dai Yueming, Wang Minghui, Wang Chun, et al.Double Bare Bones Particle Swarm Algorithm for Solving Flexible Job-Shop Scheduling Problem[J]. Journal of System Simulation, 2017, 29(6): 1268-1276.
[19] Ziaee M.A Heuristic Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. Int J Adv Manuf Technol (S0268-3768), 2014, 71: 519-528.

改进粒子群算法在考虑运输时间下的FJSP研究

Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价

[1]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[2]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[3]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[4]	李珂, 王艳, 纪志成. 基于混合策略的入侵杂草算法的FJSP问题研究[J]. 系统仿真学报, 2018, 30(5): 1918-1926.
[5]	张新, 李珂, 严大虎, 纪志成. 改进入侵杂草算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2018, 30(11): 4469-4476.
[6]	张晓星, 王艳, 严大虎, 纪志成. 改进的混合蛙跳算法求解柔性作业车间调度[J]. 系统仿真学报, 2017, 29(9): 2093-2099.
[7]	许世鹏, 吴定会, 孔飞, 纪志成. 基于改进鸡群算法的柔性作业车间调度问题求解[J]. 系统仿真学报, 2017, 29(7): 1497-1505.
[8]	戴月明, 王明慧, 王春, 王艳. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2017, 29(6): 1268-1276.
[9]	张国辉, 吴立辉, 聂黎, 王永成. 考虑机器故障的柔性作业车间鲁棒调度方法[J]. 系统仿真学报, 2016, 28(4): 867-873.
[10]	田娜, 纪志成. 改进量子粒子群求解多目标柔性作业车间调度[J]. 系统仿真学报, 2015, 27(12): 2948-2957.