Journal of System Simulation ›› 2024, Vol. 36 ›› Issue (10): 2371-2382.doi: 10.16182/j.issn1004731x.joss.23-0740
• Papers • Previous Articles
Xu Yuanxing1, Zhang Mengjian2, Wang Deguang1
Received:
2023-06-19
Revised:
2023-09-05
Online:
2024-10-15
Published:
2024-10-18
Contact:
Wang Deguang
CLC Number:
Xu Yuanxing, Zhang Mengjian, Wang Deguang. Chaotic-encode Quantum PSO Algorithm for Flexible Job-shop Scheduling Problem[J]. Journal of System Simulation, 2024, 36(10): 2371-2382.
Table 6
Experimental results for Brandimarte benchmarks by 4 algorithms
算例 | 规模 | 理论最优值 | CQPSO | PSO | QPSO | HGA | ||||
---|---|---|---|---|---|---|---|---|---|---|
最优值 | 相对偏差 | 最优值 | 相对偏差 | 最优值 | 相对偏差 | 最优值 | 相对偏差 | |||
MK01 | 36 | 38 | 0 | 41 | 0.078 9 | 42 | 0.105 3 | 40 | 0.111 1 | |
MK02 | 24 | 26 | 0 | 26 | 0 | 30 | 0.153 8 | 26 | 0 | |
MK03 | 204 | 204 | 0 | 207 | 0.014 7 | 220 | 0.078 4 | 204 | 0 | |
MK04 | 48 | 60 | 0 | 65 | 0.083 3 | 62 | 0.033 3 | 60 | 0 | |
MK05 | 168 | 170 | 0 | 171 | 0.005 9 | 174 | 0.023 5 | 172 | 0.011 6 | |
MK06 | 33 | 63 | 0 | 61 | -0.031 7 | 67 | 0.063 5 | 63 | 0 | |
MK07 | 133 | 137 | 0 | 173 | 0.262 8 | 144 | 0.051 1 | 139 | 0.014 6 | |
MK08 | 523 | 523 | 0 | 523 | 0 | 526 | 0.005 7 | 523 | 0 | |
MK09 | 299 | 304 | 0 | 307 | 0.009 9 | 316 | 0.019 4 | 307 | 0.009 9 | |
MK10 | 165 | 195 | 0 | 312 | 0.600 0 | 211 | 0.024 2 | 197 | 0.010 3 |
Table 7
Comparison of average values for Brandimarte benchmarks by four algorithms
算例 | 规模 | CQPSO | PSO | QPSO | HGA | ||||
---|---|---|---|---|---|---|---|---|---|
平均值 | 相对偏差 | 平均值 | 相对偏差 | 平均值 | 相对偏差 | 平均值 | 相对偏差 | ||
MK01 | 38.51 | 0 | 41.29 | 0.072 2 | 43.14 | 0.120 2 | 40.21 | 0.044 1 | |
MK02 | 26.33 | 0 | 26.66 | 0.012 5 | 30.21 | 0.147 4 | 26.79 | 0.017 5 | |
MK03 | 204.36 | 0 | 207.37 | 0.014 7 | 220.16 | 0.077 3 | 204.48 | 0.000 6 | |
MK04 | 60.61 | 0 | 65.42 | 0.079 4 | 62.79 | 0.036 0 | 60.96 | 0.005 8 | |
MK05 | 170.90 | 0 | 171.83 | 0.005 4 | 174.43 | 0.020 7 | 173.12 | 0.013 0 | |
MK06 | 63.82 | 0 | 61.42 | -0.037 6 | 67.41 | 0.056 2 | 63.33 | 0.007 6 | |
MK07 | 137.67 | 0 | 173.31 | 0.258 9 | 144.52 | 0.049 8 | 139.26 | 0.011 5 | |
MK08 | 523.00 | 0 | 523.00 | 0 | 526.06 | 0.005 9 | 523.00 | 0 | |
MK09 | 304.81 | 0 | 307.14 | 0.007 6 | 316.09 | 0.037 0 | 307.43 | 0.008 6 | |
MK10 | 195.33 | 0 | 312.63 | 0.600 5 | 211.43 | 0.082 4 | 197.19 | 0.009 5 |
1 | Xie Jin, Gao Liang, Peng Kunkun, et al. Review on Flexible Job Shop Scheduling[J]. IET Collaborative Intelligent Manufacturing, 2019, 1(3): 67-77. |
2 | Lei Kun, Guo Peng, Zhao Wenchao, et al. A Multi-action Deep Reinforcement Learning Framework for Flexible Job-shop Scheduling Problem[J]. Expert Systems with Applications, 2022, 205: 117796. |
3 | Houssem Eddine Nouri, Olfa Belkahla Driss, Ghédira Khaled. Solving the Flexible Job Shop Problem by Hybrid Metaheuristics-based Multiagent Model[J]. Journal of Industrial Engineering International, 2018, 14(1): 1-14. |
4 | Jin Liangliang, Zhang Chaoyong, Wen Xiaoyu, et al. A Neutrosophic Set-based TLBO Algorithm for the Flexible Job-shop Scheduling Problem with Routing Flexibility and Uncertain Processing Times[J]. Complex & Intelligent Systems, 2021, 7(6): 2833-2853. |
5 | Tutumlu Busra, Saraç Tugba. A MIP Model and a Hybrid Genetic Algorithm for Flexible Job-shop Scheduling Problem with Job-splitting[J]. Computers & Operations Research, 2023, 155: 106222. |
6 | 张朝阳, 徐莉萍, 李健, 等. 基于改进狼群算法的柔性作业车间调度研究[J]. 系统仿真学报, 2023, 35(3): 534-543. |
Zhang Chaoyang, Xu Liping, Li Jian, et al. Flexible Job-shop Scheduling Problem Based on Improved Wolf Pack Algorithm[J]. Journal of System Simulation, 2023, 35(3): 534-543. | |
7 | 谢锐强, 张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256. |
Xie Ruiqiang, Zhang Huizhen. Two-vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem[J]. Computer Engineering and Applications, 2021, 57(7): 251-256. | |
8 | 陈魁, 毕利. 改进粒子群算法在考虑运输时间下的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. | |
9 | Wu Mingliang, Yang Dongsheng, Liu Tianyi. An Improved Particle Swarm Algorithm with the Elite Retain Strategy for Solving Flexible Jobshop Scheduling Problem[J]. Journal of Physics: Conference Series, 2022, 2173(1): 012082. |
10 | Manas Ranjan Singh, Mahapatra S S. A Quantum Behaved Particle Swarm Optimization for Flexible Job Shop Scheduling[J]. Computers & Industrial Engineering, 2016, 93: 36-44. |
11 | 陈强, 王宇嘉, 林炜星, 等. 改进粒子群算法求解分布式柔性车间调度问题[J]. 电子科技, 2021, 34(10): 63-68. |
Chen Qiang, Wang Yujia, Lin Weixing, et al. An Improve Particle Swarm Optimization Algorithm for Distribution and Flexible Job-shop Scheduling Problem[J]. Electronic Science and Technology, 2021, 34(10): 63-68. | |
12 | Sun Jun, Feng Bin, Xu Wenbo. Particle Swarm Optimization with Particles Having Quantum Behavior[C]//Proceedings of the 2004 Congress on Evolutionary Computation. Piscataway: IEEE, 2004: 325-331. |
13 | 蔡敏, 王艳, 纪志成. 基于多策略融合量子粒子群算法的MOFFJSP研究[J]. 系统仿真学报, 2021, 33(11): 2615-2626. |
Cai Min, Wang Yan, Ji Zhicheng. Research on MOFFJSP Based on Multi-strategy Fusion Quantum Particle Swarm Optimization[J]. Journal of System Simulation, 2021, 33(11): 2615-2626. | |
14 | 李俊萱, 王艳, 纪志成. 基于混合QPSO的模糊柔性作业车间调度问题研究[J]. 系统仿真学报, 2020, 32(10): 2010-2021. |
Li Junxuan, Wang Yan, Ji Zhicheng. Research on Fuzzy Flexible Job Shop Scheduling Problem Based on Hybrid QPSO[J]. Journal of System Simulation, 2020, 32(10): 2010-2021. | |
15 | 张晓星. 生产及能耗多指标优化的柔性作业车间调度方法[D]. 无锡: 江南大学, 2019. |
Zhang Xiaoxing. A Method Applied to Flexible Job Shop Scheduling Problem with Multi-index Optimization of Production and Energy Consumption[D]. Wuxi: Jiangnan University, 2019. | |
16 | Flori Arnaud, Oulhadj Hamouche, Siarry Patrick. Quantum Particle Swarm Optimization: An Auto-adaptive PSO for Local and Global Optimization[J]. Computational Optimization and Applications, 2022, 82(2): 525-559. |
17 | Li Xiaotong, Fang Wei, Zhu Shuwei, et al. An Adaptive Binary Quantum-behaved Particle Swarm Optimization Algorithm for the Multidimensional Knapsack Problem[J]. Swarm and Evolutionary Computation, 2024, 86: 101494. |
18 | Ding Shifei, Zhang Zichen, Sun Yuting, et al. Multiple Birth Support Vector Machine Based on Dynamic Quantum Particle Swarm Optimization Algorithm[J]. Neurocomputing, 2022, 480: 146-156. |
19 | Feng Zhongkai, Niu Wenjing, Tang Zhengyang, et al. Monthly Runoff Time Series Prediction by Variational Mode Decomposition and Support Vector Machine Based on Quantum-behaved Particle Swarm Optimization[J]. Journal of Hydrology, 2020, 583: 124627. |
20 | Qiao Jinghui, Chen Yuxi. Stochastic Configuration Networks with Chaotic Maps and Hierarchical Learning Strategy[J]. Information Sciences, 2023, 629: 96-108. |
21 | Nagata Yuichi. High-order Entropy-based Population Diversity Measures in the Traveling Salesman Problem[J]. Evolutionary Computation, 2020, 28(4): 595-619. |
22 | 李俊萱. 模糊柔性作业车间的调度优化算法研究与应用[D]. 无锡: 江南大学, 2021. |
Li Junxuan. Research and Application of Optimization Algorithm for Fuzzy Flexible Job Shop Scheduling[D]. Wuxi: Jiangnan University, 2021. | |
23 | Zhang Yinxing, Hua Zhongyun, Bao Han, et al. An n-Dimensional Chaotic System Generation Method Using Parametric Pascal Matrix[J]. IEEE Transactions on Industrial Informatics, 2022, 18(12): 8434-8444. |
24 | Shafique Arslan. A Noise-tolerant Cryptosystem Based on the Decomposition of Bit-planes and the Analysis of Chaotic Gauss Iterated Map[J]. Neural Computing and Applications, 2022, 34(19): 16805-16828. |
25 | Nouiri Maroua, Bekrar Abdelghani, Jemai Abderezak, et al. An Effective and Distributed Particle Swarm Optimization Algorithm for Flexible Job-shop Scheduling Problem[J]. Journal of Intelligent Manufacturing, 2018, 29(3): 603-615. |
26 | Gao Jie, Sun Linyan, Gen Mitsuo. A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems[J]. Computers & Operations Research, 2008, 35(9): 2892-2907. |
27 | 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, and Cybernetics, Part C (Applications and Reviews), 2002, 32(1): 1-13. |
28 | Brandimarte Paolo. Routing and Scheduling in a Flexible Job Shop by Tabu Search[J]. Annals of Operations Research, 1993, 41(3): 157-183. |
[1] | Xu Yuze, Zhang Linxuan, Li Hui, Ge Ming, He Wanyi. Modeling and Optimization of Smart Warehouse Order Sorting Considering Splitting Strategy [J]. Journal of System Simulation, 2024, 36(3): 564-577. |
[2] | Chaoyang Zhang, Liping Xu, Jian Li, Yihao Zhao, Kui He. Flexible Job-Shop Scheduling Problem Based on Improved Wolf Pack Algorithm [J]. Journal of System Simulation, 2023, 35(3): 534-543. |
[3] | You Yichen, Wang Yan, Ji Zhicheng. Research on Flexible Job-shop Dynamic Scheduling Based on Game Theory [J]. Journal of System Simulation, 2021, 33(11): 2579-2588. |
[4] | Cai Min, Wang Yan, Ji Zhicheng. Research on MOFFJSP Based on Multi-strategy Fusion Quantum Particle Swarm Optimization [J]. Journal of System Simulation, 2021, 33(11): 2615-2626. |
[5] | Zhang Xiang, Wang Yan, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem Based on Dynamic Interaction Layer [J]. Journal of System Simulation, 2020, 32(11): 2129-2137. |
[6] | Shen Peng, Wang Yan, Ji Zhicheng, Zhang Jianhua. Hyper-heuristic DE Algorithm for Solving Zero-wait Fermentation Process Schedulinge [J]. Journal of System Simulation, 2020, 32(11): 2235-2243. |
[7] | Li Junxuan, Wang Yan, Ji Zhicheng. Research on Fuzzy Flexible Job Shop Scheduling Problem Based on Hybrid QPSO [J]. Journal of System Simulation, 2020, 32(10): 2010-2021. |
[8] | 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. |
[9] | Li Linying, Lu Rui, Li Shaohua, Jing Yu, Diao Jianhua. Online Scheduling Method of Cluster Tools with Residency Time Constraint [J]. Journal of System Simulation, 2017, 29(2): 337-345. |
[10] | Xu Junhui, Wang Yan. Energy Efficiency Optimization for Discrete Manufacturing Workshop Based on Discrete Teaching-learning-based Optimization Algorithm [J]. Journal of System Simulation, 2016, 28(12): 3019-3026. |
[11] | Chen Yan, Wang Yan. Energy Consumption Analysis of Discrete Manufacturing Based on Improved Principal Component Analysis Method [J]. Journal of System Simulation, 2016, 28(12): 3087-3094. |
[12] | Pan Chunrong, Li Liang. Research on Modeling and Scheduling of Cluster Tools with Reentrant Process [J]. Journal of System Simulation, 2016, 28(4): 772-782. |
[13] | Zhang Xiaoxing, Wang Yan, Yan Dahu, Ji Zhicheng. Improved Shuffled Frog-Leaping Algorithm for Solving Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2017, 29(9): 2093-2099. |
[14] | Shan Xin, Wang Yan, Ji Zhicheng. Energy Efficiency Optimization for Discrete Workshop Based on Parametric Knowledge Pigeon Swarm Algorithm [J]. Journal of System Simulation, 2017, 29(9): 2140-2148. |
[15] | Chen Chao, Wang Yan, Yan Dahu, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem for Energy Consumption [J]. Journal of System Simulation, 2017, 29(9): 2168-2175. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||