面向柔性作业车间调度问题的混沌编码量子粒子群优化算法

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

中图分类号:

TP278

胥远兴,张孟健,王德光 . 面向柔性作业车间调度问题的混沌编码量子粒子群优化算法[J]. 系统仿真学报, 2024, 36(10): 2371-2382.

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.

图/表 14

表1

不同阈值下求解FJSP算例的实验结果

规模

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

表1

图1

图2

图3

图4

表2

表3

图5

表4

4种算法的参数设置

算法	参数设置
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$

表4

表5

4种算法在Kacem数据集上的实验结果

规模 $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

表5

图6

表6

4种算法在Brandimarte数据集上的实验结果

算例	规模 $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

表6

表 7

4种算法在Brandimarte数据集上的平均值对比

算例	规模 $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

表 7

图7

参考文献 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]	蒋权, 魏静萱. 用于动态柔性作业车间调度的实时调度方法[J]. 系统仿真学报, 2024, 36(7): 1609-1620.
[2]	朱宇挺, 苏焕坤, 冯小东, 雷诗洁, 傅妍芳. 基于改进差分算法的数据链时隙分配方法[J]. 系统仿真学报, 2024, 36(5): 1242-1250.
[3]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[4]	徐宜刚, 陈勇, 王宸, 彭运贤. 改进NSGA-III求解高维多目标绿色柔性作业车间调度问题[J]. 系统仿真学报, 2024, 36(10): 2314-2329.
[5]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[6]	焦业峰, 王艳, 纪志成. 基于BLP-ALO-SVM的风电功率短期预测方法[J]. 系统仿真学报, 2022, 34(12): 2535-2545.
[7]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[8]	刘景森, 袁蒙蒙, 李煜. 基于改进樽海鞘群算法求解工程优化设计问题[J]. 系统仿真学报, 2021, 33(4): 854-866.
[9]	李珂, 王艳, 纪志成. 基于混合策略的入侵杂草算法的FJSP问题研究[J]. 系统仿真学报, 2018, 30(5): 1918-1926.
[10]	张新, 李珂, 严大虎, 纪志成. 改进入侵杂草算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2018, 30(11): 4469-4476.
[11]	张晓星, 王艳, 严大虎, 纪志成. 改进的混合蛙跳算法求解柔性作业车间调度[J]. 系统仿真学报, 2017, 29(9): 2093-2099.
[12]	许世鹏, 吴定会, 孔飞, 纪志成. 基于改进鸡群算法的柔性作业车间调度问题求解[J]. 系统仿真学报, 2017, 29(7): 1497-1505.
[13]	郭业才, 马伟伟, 朱赛男. 基于混沌人工蜂群优化的声源定位算法[J]. 系统仿真学报, 2017, 29(6): 1168-1173.
[14]	戴月明, 王明慧, 王春, 王艳. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2017, 29(6): 1268-1276.
[15]	张国辉, 吴立辉, 聂黎, 王永成. 考虑机器故障的柔性作业车间鲁棒调度方法[J]. 系统仿真学报, 2016, 28(4): 867-873.