Chaotic-encode Quantum PSO Algorithm for Flexible Job-shop Scheduling Problem

doi:10.16182/j.issn1004731x.joss.23-0740

Abstract

Abstract:

To solve the flexible job-shop scheduling problem (FJSP), a chaotic-encode quantum PSO (CQPSO) algorithm is proposed. Aiming at the premature convergence of particles to local optimum in standard QPSO, the methods for computing the adaptive contraction-expansion coefficient and mean best position using fitness values of associated particles are proposed to improve the global search ability of QPSO. Through chaotic boundary variation strategy, the probability of a large number of particles gathering at the boundary is reduced and the population diversity is increased to enhance the ability of searching the optimal solution. According to the iterative property of QPSO, a chaotic-encode strategy is designed. The proposed CQPSO is applied to solve FJSP and the result is compared with QPSO, PSO, and hybrid genetic algorithm result on several benchmarks to confirm the performance. The experimental results show that CQPSO has the better stability and the stronger optimization ability.

Key words: quantum PSO algorithm, FJSP, chaos mapping, contraction-expansion coefficient

CLC Number:

TP278

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.

Figures/Tables 14

Table 1

Experimental results of solving FJSP benchmarks under different thresholds

规模

n×m

标准QPSO

不同阈值QPSO/

γ

0.005

0.01

0.1

8×8

16.14

18.11

15.87

17.46

10×6

41.91

43.22

40.39

44.06

Table 1

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 2

Table 3

Fig. 5

Table 4

Parameter setting of four algorithms

算法	参数设置
CQPSO	$β m i n = 0.5$ ， $β m a x = 1$ ， $u, k ∈ [0,1]$
PSO	$c 1 = 2, c 2 = 2$ ，
QPSO	$β m i n = 0.5$ ， $β m a x = 1$ ， $u, k ∈ [0,1]$
HGA	$p c = 0.45$ ， $p m = 0.02$ ， $I m = 0.06$

Table 4

Table 5

Experimental results for Kacem benchmarks by 4 algorithms

规模 $n × m$	理论最优值	CQPSO	PSO	QPSO	HGA
8×8	14	14	17	16	14
10×10	7	7	8	9	7
15×10	11	11	14	12	11

Table 5

Fig. 6

Table 6

Experimental results for Brandimarte benchmarks by 4 algorithms

算例	规模 $n × m$	理论最优值	CQPSO		PSO		QPSO		HGA
算例	规模 $n × m$	理论最优值	最优值	相对偏差	最优值	相对偏差	最优值	相对偏差	最优值	相对偏差
MK01	$10 × 6$	36	38	0	41	0.078 9	42	0.105 3	40	0.111 1
MK02	$10 × 6$	24	26	0	26	0	30	0.153 8	26	0
MK03	$15 × 8$	204	204	0	207	0.014 7	220	0.078 4	204	0
MK04	$15 × 8$	48	60	0	65	0.083 3	62	0.033 3	60	0
MK05	$15 × 4$	168	170	0	171	0.005 9	174	0.023 5	172	0.011 6
MK06	$10 × 15$	33	63	0	61	-0.031 7	67	0.063 5	63	0
MK07	$20 × 5$	133	137	0	173	0.262 8	144	0.051 1	139	0.014 6
MK08	$20 × 10$	523	523	0	523	0	526	0.005 7	523	0
MK09	$20 × 10$	299	304	0	307	0.009 9	316	0.019 4	307	0.009 9
MK10	$20 × 15$	165	195	0	312	0.600 0	211	0.024 2	197	0.010 3

Table 6

Table 7

Comparison of average values for Brandimarte benchmarks by four algorithms

算例	规模 $n × m$	CQPSO		PSO		QPSO		HGA
算例	规模 $n × m$	平均值	相对偏差	平均值	相对偏差	平均值	相对偏差	平均值	相对偏差
MK01	$10 × 6$	38.51	0	41.29	0.072 2	43.14	0.120 2	40.21	0.044 1
MK02	$10 × 6$	26.33	0	26.66	0.012 5	30.21	0.147 4	26.79	0.017 5
MK03	$15 × 8$	204.36	0	207.37	0.014 7	220.16	0.077 3	204.48	0.000 6
MK04	$15 × 8$	60.61	0	65.42	0.079 4	62.79	0.036 0	60.96	0.005 8
MK05	$15 × 4$	170.90	0	171.83	0.005 4	174.43	0.020 7	173.12	0.013 0
MK06	$10 × 15$	63.82	0	61.42	-0.037 6	67.41	0.056 2	63.33	0.007 6
MK07	$20 × 5$	137.67	0	173.31	0.258 9	144.52	0.049 8	139.26	0.011 5
MK08	$20 × 10$	523.00	0	523.00	0	526.06	0.005 9	523.00	0
MK09	$20 × 10$	304.81	0	307.14	0.007 6	316.09	0.037 0	307.43	0.008 6
MK10	$20 × 15$	195.33	0	312.63	0.600 5	211.43	0.082 4	197.19	0.009 5

Table 7

Fig. 7

References 28

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.

工件	工序	可选择的加工机器
工件	工序	M₁	M₂	M₃	M₄
J₁	O_1,1	9	5	4	3
	O_1,2	7	8	9	5
	O_1,3	5	8	8	3
J₂	O_2,1	4	6	5	8
J₂	O_2,2	5	4	6	2
J₃	O_3,1	3	8	6	3
J₃	O_3,2	5	5	2	2

工件	工序	优先级
工件	工序	1	2	3	4
J₁	O_1,1	M₄	M₃	M₂	M₁
	O_1,2	M₄	M₁	M₂	M₃
	O_1,3	M₄	M₁	M₂	M₃
J₂	O_2,1	M₁	M₃	M₂	M₄
J₂	O_2,2	M₄	M₂	M₁	M₃
J₃	O_3,1	M₁	M₄	M₃	M₂
J₃	O_3,2	M₃	M₄	M₁	M₂

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