Improved Quantum-behaved Particle Swarm Optimization for Solving Multi-objective Flexible Job-Shop Scheduling Problems

Abstract

Abstract: Due to the complexity of flexible job-shop scheduling problem (FJSP), it is still the hot topic for research. FJSP was given deep insight into with three objectives to be minimized simultaneously: makespan, maximal machine workload and total workload. Quantum-behaved particle swarm optimization (QPSO) with different coefficient selection methods was compared. The benchmark function tests show that QPSO with adaptive coefficient outperforms other selection methods in unimodal functions, while QPSO with cosine coefficient performs better in multi-modal functions. Therefore, QPSO with cosine decreasing coefficient is adopted to solve the multi-objective FJSP, which is a complex multi-modal optimization problem. Simulation results of four representative FJSP examples indicate the effectiveness and efficiency of the proposed method.

Key words: quantum-behaved particle swarm optimization, adaptive coefficient, cosine coefficient, multi-objective problem flexible job-shop scheduling problems, critical path

CLC Number:

TP183

Tian Na, Ji Zhicheng. Improved Quantum-behaved Particle Swarm Optimization for Solving Multi-objective Flexible Job-Shop Scheduling Problems[J]. Journal of System Simulation, 2015, 27(12): 2948-2957.

References

[1] P Brandimarte.Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research (S1572-9338), 1993, 41(3): 157-183.
[2] G Zhang, X Shao.An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J]. Computers & Industrial Engineering (S0360-8352), 2009, 56(4): 1309-1318.
[3] 李俊, 刘志雄, 张煜, 等, 柔性作业车间调度优化的改进模拟退火算法[J]. 武汉科技大学学报, 2015, 38(2): 111-116.
[4] Z Davarzani, M Akbarzadeh, N Khairdoost.Multiobjective artificial immune algorithm for flexible job shop scheduling problem[J]. International Journal of Hybrid Information Technology (S1738-9968), 2012, 5(3): 75-88.
[5] I Kacem, S Hammadi. P Borne, Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man and Cybernetics (S0018-9472), 2002, 32(1): 1-13.
[6] G Moslehi, M Mahnam.A pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics (S0925-5273), 2011, 129(1): 14-22.
[7] T Lin, S Horng.An efficient job-shop scheduling algorithm based on particle swarm optimization[J]. Expert Systems with Applications (S0957-4174), 2009, 37(3): 2629-2636.
[8] X Shao, W Liu, Q Liu, et al. Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology (S1433-3015), 2013, 67(9/12): 2885-2901.
[9] B Panigrahi, V Pandi, S Das, Adaptive particle swarm optimization approach for static and dynamic economic load dispatch[J]. Energy Conversion and Management (S0196-8904), 2008, 49(6): 1407-1415.
[10] 吴定会, 孔飞, 田娜, 等, 教与同伴学习粒子群算法求解柔性作业车间调度问题[J]. 计算机应用(S1001-9081), 2015, 35(6): 1617-1622.
[11] K Deb.Multi-objective optimization using evolutionary algorithms[M], Chichester, UK: Wiley, 2001.
[12] I Kacem, S Hammadi, P Borne.Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic[J]. Mathematics and Computers in Simulation (S0378-4754), 2002, 60(3-5): 245-276.
[13] T Hsu, R Dupas, D Jolly, et al.Evaluation of mutation heuristics for the solving of multi-objective flexible job shop by an evolutionary algorithm [C]// Proc. IEEE International Conference on Systems, Man and Cybernetics, Hammamet, Tunisia. USA: IEEE Press, 2002, 5: 655-660.
[14] J Kennedy, R Eberhart.Particle swarm optimization [C]// IEEE International Conference on Neural Networks, Perth, Australia. USA: IEEE Press, 1995: 1942-1948.
[15] R Eberhart, Y Shi.Comparison between genetic algorithm and particle swarm optimization[C]// Evolutionary Programming VII, Lecture Notes in Computer Science 1447. Germany: Springer Berlin, Heidelberg, 1998: 611-616.
[16] F Van Den Bergh. An analysis of particle swarm optimizers [D]. South Africa: University of Pretoria, 2001.
[17] M Clerc, J Kennedy.The particle swarm: explosion, stability, and convergence in a multi-dimensional complex space[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2002, 6(1): 58-73.
[18] J Sun, B Feng, W Xu.Particle swarm optimization with particles having quantum behaviour [C]// Proc. IEEE Congress Evolutionary Computation, Portland. USA: IEEE Press, 2004: 325-331.
[19] J Sun, W Xu, J Liu, Parameter Selection of Quantum-behaved particle Swarm optimization[J]. Lecture Notes in Computer Science (S0302-9743), 2005, 3612: 543-552.
[20] J Sun, W Xu, B Feng.A global search strategy of quantum-behaved particle swarm optimization [C]// IEEE Conference on Cybernetics and Intelligent Systems, Singapore. USA: IEEE Press, 2004: 111-116.
[21] J Sun, W Fang, X Wu.Quantum-behaved particle swarm optimization: analysis of the individual particle's behavior and parameter selection[J]. Evolutionary Computation (S1530-9304), 2012, 20(3): 349-393.
[22] A Nickabadi, M Ebadzadeh, R Safabakhsh.A novel particle swarm optimization algorithm with adaptive inertia weight[J]. Applied Soft Computing (S1568-4946), 2011, 11(4): 3658-3670.
[23] K Lei, Y Qiu, Y He.A new adaptive well-chosen inertia weight strategy to automatically harmonize global and local search ability in particle swarm optimization [C]// Proc. Symposium Systems and Control in Aerospace and Astronautics, Harbin, China. USA: IEEE Press, 2006: 19-21.
[24] N Tian, C Lai, K Pericleous.Contraction-expansion coefficient learning in quantum-behaved particle swarm optimization [C]// 10th International Symposium on Distributed and Applications to Business, Engineering and Science, Wuxi, China. USA: IEEE Press, 2011: 304-308.