骨干双粒子群算法求解柔性作业车间调度问题

doi:10.16182/j.issn1004731x.joss.201706015

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (6): 1268-1276.doi: 10.16182/j.issn1004731x.joss.201706015

骨干双粒子群算法求解柔性作业车间调度问题

戴月明, 王明慧, 王春, 王艳

江南大学教育部物联网技术应用工程研究中心,江苏无锡 214122

收稿日期:2016-08-22 修回日期:2016-11-06 出版日期:2017-06-08 发布日期:2020-06-04
通讯作者: 戴月明(1964-)，男，江苏常熟，硕士，副教授，硕导，研究方向为人工智能和软件工程。
作者简介:戴月明(1964-),男,江苏常熟,硕士,副教授,硕导,研究方向为人工智能和软件工程。
基金资助:
国家自然科学基金(61572238),江苏省杰出青年基金(BK20160001)

Double Bare Bones Particle Swarm Algorithm for Solving Flexible Job-shop Scheduling Problem

Dai Yueming, Wang Minghui, Wang Chun, Wang Yan

Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China

Received:2016-08-22 Revised:2016-11-06 Online:2017-06-08 Published:2020-06-04

摘要/Abstract

摘要： 针对柔性作业车间调度问题,以最小化最大完工时间为优化目标,提出了一种骨干双粒子群算法(Double Bare Bones Particle Swarm Algorithm,DBBPSO)。算法结合基于冯诺依曼拓扑结构的改进骨干粒子群算法与基于混沌变异的骨干粒子群算法,利用种群交流机制使两个种群协同进化,实现了算法在全局搜索与局部开发之间的平衡,并提出一种基于最小加工时间的机器选择策略。将所提算法在四个经典算例与一个柔性作业车间调度实例上与其他不同算法进行仿真对比,结果表明所提算法比其他对比算法具有更好的寻优能力,更适合解决该类调度问题。

关键词: 柔性作业车间调度, 骨干双粒子群算法, 协同进化, 机器选择策略

Abstract: To solve flexible job shop scheduling problem, a double bare bones particle swarm algorithm (DBBPSO) was proposed to minimize the makespan. Combining Von-neumann bare bones particle swarm optimization algorithm and chaotic mutation bare bones particle swarm optimization algorithm, the algorithm DBBPSO used a communication method to cooperate evolution. This approach could keep balance between global exploration and local exploration, and a machine selection method was proposed based on the tenet of minimizing makespan. The proposed algorithm was compared with other algorithms on four benchmark problems and a scheduling optimization example. Simulation results indicate that the improved algorithm has the ability to obtain the optimal solution, and it is more suitable for solving the scheduling problem.

Key words: flexible job-shop scheduling, double bare bones particle swarm optimization, cooperate evolution, machine selection

中图分类号:

TP278

戴月明, 王明慧, 王春, 王艳. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2017, 29(6): 1268-1276.

Dai Yueming, Wang Minghui, Wang Chun, Wang Yan. Double Bare Bones Particle Swarm Algorithm for Solving Flexible Job-shop Scheduling Problem[J]. Journal of System Simulation, 2017, 29(6): 1268-1276.

参考文献

[1] 王万良, 吴启迪. 生产调度智能算法及其应用 [M]. 北京: 科学出版社, 2007: 12-13.
(Wang Wanliang, Wu Qidi.Intelligent Scheduling Algorithm for Production and Application [M]. Beijing, China: Science Press, 2007: 12-13. )
[2] Brucker P, Schlie R.Job-shop scheduling with multi purpose machines[J]. Computing (S0010-485X), 1990, 45(4): 369-375.
[3] Girish B S, Jawahar N.A particle swarm optimization algorithm for flexible jobshop scheduling problem [C]// IEEE International Conference on Automation Science and Engineering. USA: IEEE Press, 2009: 298-303.
[4] Deroussi L.A Hybrid PSO Applied to the Flexible Job Shop with Transport [M]// Swarm Intelligence Based Optimization. Germany: Springer International Publishing, 2014: 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] 周恺, 纪志成. 关于柔性作业车间调度问题的仿真研究[J]. 计算机仿真, 2016, 33(3): 282-287.
(Zhou Kai, Ji Zhicheng.Simulation Research on Flexible Job Shop Scheduling Problem[J]. Journal of System Simulation (S1004-731X), 2016, 33(3): 282-287.)
[7] Kennedy J.Bare bones particle swarms[C]// Proc of the Swarm Intelligence Symposium. USA: IEEE, 2003: 80-87.
[8] 雷阳, 李树荣, 张强, 等. 基于骨干粒子群的混合遗传算法及其应用[J]. 计算机工程与应用, 2010, 46(36): 7-10.
(Lei Yang, Li Shurong, Zhang Qiang, et al.Novel hybrid GA based on bare bones PSO and its application[J]. Computer Engineering and Applications, 2010, 46(36): 7-10.)
[9] Zhang Y, Gong D, Geng N, et al.Hybrid bare-bones PSO for dynamic economic dispatch with valve-point effects[J]. Applied Soft Computing, 2014, 18(C): 248-260.
[10] 史丽萍, 王攀攀, 胡泳军, 等. 基于骨干微粒群算法和支持向量机的电机转子断条故障诊断[J]. 电工技术学报, 2014, 29(1): 147-155.
(Shi Liping, Wang Panpan, Hu Yongjun, et al.Broken Rotor Bar Fault Diagnosis of Induction Motors based on Bare-Bone Particle Swarm Optimization and Support Vector Machine[J]. Transactions of China Electrotechnical Society, 2014, 29(1): 147-155.)
[11] Yao J, Han D.Improved barebones particle swarm optimization with neighborhood search and its application on ship design[J]. Mathematical Problems in Engineering (S1024-123X), 2013, 12(7): 1-13.
[12] 高亮, 张国辉, 王晓娟. 柔性作业车间调度智能算法及其应用 [M]. 武汉: 华中科技大学出版社, 2012: 13-15.
(Gao Liang, Zhang Guohui, Wang Xiaojuan.Flexible Job Shop Scheduling Intelligent Algorithm and Its Application [M]. Wuhan, China: Huazhong University of Science and Technology Press, 2012: 13-15.)
[13] 李莉. 柔性作业车间调度中的群智能优化算法研究 [D]. 哈尔滨: 东北林业大学, 2011.
(Li Li.Research on Group Intelligent Optimization Algorithm in Flexible Job Shop Scheduling [D]. Harbin, China: Northeast Forestry University, 2011.)
[14] 陈自郁, 何中市, 张程. 基于冯诺依曼邻居的粒子群多阀值分割算法[J]. 计算机应用研究, 2009, 26(5): 1979-2000.
(Chen Zi-yu, He Zhong-shi, Zhang Cheng.Image multi-level thresholds based on PSO with Von Neumann neighborhood[J]. Application Research of Computers, 2009, 26(5): 1979-2000.)
[15] Rifaie M, Blackwell T.Bare bones particle swarms with jumps[C]// Algorithmic Number Theory Symposium. Brussels, Belgium: Springer, 2012: 49-60.
[16] LU H J.A new optimization algorithm based on Chaos[J]. Journal of Zhejiang University Science A (S1673-565X), 2006, 7(4): 539-542.
[17] 吴定海, 张培林, 李胜, 等. 基于混沌变异的自适应双粒子群优化[J]. 控制与决策, 2011, 26(7): 1083-1095.
(Wu Dinghai, Zhang Peilin, Li Sheng, et al.Adaptive Double Particle Swarms Optimization Algorithm Based on Chaotic Mutation[J]. Control and Decision, 2011, 26(7): 1083-1095.)
[18] 孔飞, 吴定会, 纪志成. 基于双层粒子群优化算法的柔性作业车间调度优化[J]. 计算机应用, 2015, 35(2): 476-480.
(Kong Fei, Wu Dinghui, Ji Zhicheng.Flexible Job-shop Scheduling Optimization Based on Two-layer Particle Swarm Optimization Algorithm[J]. Computer Application, 2015, 35(2): 476-480.)
[19] Kacem I, Hammadi S, Borne P.Approach by localization and multi-objective evolutionary optimization for flexible job shop scheduling problems[J]. IEEE Trans on Systems, Man and Cybernetics, Part C: Applications and Reviews (S1094-6977), 2002, 32(1): 1-13.
[20] Maroua N, Abdelghani B, Abderezak J.An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Journal of Intelligent Manufacturing (S0956-5515), 2014, 24(3), 1-13.
[21] Ho N B, Tay J C.GENACE: An efficient cultural algorithm for solving the flexible job-shop problem[C]// Proc of the Congress on Evolutionary Computation (CEC), Portland. USA: IEEE, 2004: 1759-1766.
[22] 张超勇, 饶运清, 李培根. 柔性作业车间调度问题的两级遗传算法[J]. 机械工程学报, 2007, 43(4): 119-124.
(Zhang Chaoyong, Rao Yunqing, Li Peigen.Two - level Genetic Algorithm for Flexible Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2007, 43(4): 119-124.)
[23] 张超勇, 刘琼, 邱浩波, 等. 考虑加工成本和时间的柔性作业车间调度问题研究[J]. 机械科学与技术, 2009, 28(8): 1005-1011.
(Zhang Chaoyong, Liu Qiong, Qiu Haobo, et al.Research on Flexible Job Shop Scheduling Problem Considering Processing Cost and Time[J]. Mechanical Science and Technology, 2009, 28(8): 1005-1011.)

骨干双粒子群算法求解柔性作业车间调度问题

Double Bare Bones Particle Swarm Algorithm for Solving Flexible Job-shop Scheduling Problem

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[2]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[3]	陈晖, 马亚平. 基于多级协同MOEA/D的联合火力打击目标分配方法[J]. 系统仿真学报, 2018, 30(8): 2942-2949.
[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]. 系统仿真学报, 2016, 28(4): 867-873.
[9]	田娜, 纪志成. 改进量子粒子群求解多目标柔性作业车间调度[J]. 系统仿真学报, 2015, 27(12): 2948-2957.