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

doi:10.16182/j.issn1004731x.joss.201706015

Abstract

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

CLC Number:

TP278

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.

References

[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.)