改进量子粒子群求解多目标柔性作业车间调度

系统仿真学报 ›› 2015, Vol. 27 ›› Issue (12): 2948-2957.

改进量子粒子群求解多目标柔性作业车间调度

田娜^1,2, 纪志成²

1.江南大学教育信息化研究中心,江苏无锡 214122;
2.江南大学电气自动化研究所,江苏无锡 214122

收稿日期:2015-03-30 修回日期:2015-09-06 出版日期:2015-12-08 发布日期:2020-07-30
作者简介:田娜(1983-),女,河北,博士,副教授,研究方向为智能控制,系统辨识;纪志成(1959-),男,浙江,博士,教授,研究方向为智能控制,系统辨识。
基金资助:
江苏省博士后基金(1401004B); 国家高技术研究发展计划项目(2013AA040405)

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

Tian Na^1,2, Ji Zhicheng²

1. Institute of Educational Informatization, Jiangnan University, Wuxi 214122, China;
2. Institute of Electrical Automation, Jiangnan University, Wuxi 214122, China

Received:2015-03-30 Revised:2015-09-06 Online:2015-12-08 Published:2020-07-30

摘要/Abstract

摘要： 柔性作业车间调度问题(FJSP),由于其求解的复杂性,仍然是研究者们的研究热点。对基于不同的缩放系数选择策略的量子粒子群算法(QPSO)进行了比较研究,标准测试函数的仿真结果表明,自适应的缩放系数在单峰问题上优于其他选择策略;而余弦递减系数由于帮助粒子避免了陷入早熟而在多峰问题上表现比较好,故将其应用于求解多目标柔性作业车间调度问题(最大完工时间,最大机器工作时间,全部机器工作时间)。4个经典的仿真实例测试结果表明了算法的有效性和相较于其他算法的优越性。

关键词: 量子粒子群算法, 自适应系数, 余弦系数, 多目标柔性作业车间调度, 关键路径

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

中图分类号:

TP183

田娜, 纪志成. 改进量子粒子群求解多目标柔性作业车间调度[J]. 系统仿真学报, 2015, 27(12): 2948-2957.

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.

参考文献

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