改进粒子群算法的不相关并行批处理调度优化

doi:10.16182/j.issn1004731x.joss.22-0367

摘要/Abstract

摘要：

针对粒子群优化（particle swarm optimization，PSO）算法在处理不相关并行批处理调度问题中存在的种群多样性丢失、易陷入局部最优等问题，提出了一种改进PSO的调度优化算法，用于最小化最大完工时间求解。采用基于工件序列的实数编码方式进行编码操作；基于该问题的混合整数规划模型，设计了一种J_B局部搜索的新策略；将模拟退火算法的Metropolis准则引入种群粒子的个体极值搜索。通过随机生成的小型、中型和大型实例对该算法的性能进行了测试，并与针对该调度问题提出的元启发式算法和其他3种元启发式算法进行了比较。实验结果和统计测试表明，该算法的性能明显优于对比算法。

Abstract:

To address the problems of population diversity loss and the tendency to fall into local optimality in the PSO (particle swarm optimization)algorithm in dealing with unrelated parallel batch scheduling problems, an improved scheduling optimization algorithm for PSO is proposed for minimizing the maximum completion time solution. A real number encoding based on the sequence of artifacts is used for the encoding operation. A new strategy based on J_B local search is designed based on the mixed integer programming model of the problem. The Metropolis criterion of the simulated annealing algorithm isintroduced into the individual extreme value search of the population particles.The performance of the algorithm is tested with randomly generated small,medium and large instances and compared with proposed metaheuristic for this scheduling problem and three other metaheuristics.The experimental results and statistical tests shows that the algorithm performs significantly better than the comparison algorithm.

Key words: unrelated parallel, batch scheduling, local search strategy, particle swarm algorithm, simulated annealing

中图分类号:

TP391.9

杜利珍, 叶涛, 王宇豪, 张亚军, 宣自风. 改进粒子群算法的不相关并行批处理调度优化[J]. 系统仿真学报, 2023, 35(7): 1549-1561.

Lizhen Du, Tao Ye, Yuhao Wang, Yajun Zhang, Zifeng Xuan. Improved Particle Swarm Algorithm of Unrelated Parallel Batch Scheduling Optimization[J]. Journal of System Simulation, 2023, 35(7): 1549-1561.

图/表 14

表1

表2

图1

表3

表4

图2

表5

问题实例参数

变量	符号	数值
工件数量	$n ∈ {J 1, J 2, J 3, J 4, J 5}$	$20, 50, 100, 200, 300$
工件尺寸	$s j ∈ {S 1, S 2}$	$U [1,20], U [10,30]$
工件加工时间	$p j$	$U [8, 48]$
机器数量	$m ∈ {M 1, M 2, M 3, M 4}$	$2, 3, 4, 5$
机器容量	$H$	$40, 50, 60$
机器速率	$V k$	$1, 1.2, 1.4, 1.6, 1.8, 2.0$

表5

表6

不同参数组合下的仿真结果

算例	编号
算例	LN₁	LN₂	LN₃	LN₄	LN₅	LN₆	LN₇	LN₈	LN₉
J₃M₁S_{1_1}	225.19	232.64	234.60	231.31	229.45	224.17	227.07	221.01	222.06
J₃M₁S_{2_1}	387.03	383.25	387.19	383.97	402.25	382.72	392.28	370.22	376.56
J₃M₂S_{1_1}	160.07	158.85	154.12	158.77	155.25	156.38	159.02	152.27	152.75
J₃M₂S_{2_1}	213.12	230.30	223.40	223.35	227.00	217.55	224.50	220.05	219.16
J₃M₃S_{1_1}	118.39	111.89	110.25	115.40	126.37	111.48	124.48	114.33	114.95
J₃M₃S_{2_1}	179.51	186.81	185.76	183.35	191.31	172.29	189.68	169.48	171.76
$C ¯ m a x$	213.88	217.29	215.89	216.03	221.94	210.77	219.50	207.89	209.54

表6

表7

图3

表8

表9

仿真结果

算例	HPSO			LSPSO^[14]			PSO			TS			DDE^[16]
算例	Min	Avg	Max	Min	Avg	Max	Min	Avg	Max	Min	Avg	Max	Min	Avg	Max
J₁M₁S₁	25	44	73	38	50	74	37	57	87	33	57	105	34	50	74
J₁M₁S₂	36	66	97	65	72	88	65	103	145	61	98	157	64	95	133
J₁M₂S₁	21	33	56	34	38	45	31	44	62	30	47	76	30	40	56
J₁M₂S₂	36	42	54	40	48	54	49	65	92	43	65	126	43	59	86
J₁M₃S₁	21	26	36	24	30	34	26	34	42	23	34	53	24	29	34
J₁M₃S₂	28	36	55	36	42	50	40	51	67	37	49	76	37	46	59
J₁M₄S₁	20	24	29	24	29	32	22	30	35	22	32	46	21	25	29
J₁M₄S₂	27	33	40	31	36	42	40	45	53	36	45	85	37	41	46
J₂M₁S₁	48	108	152	76	124	178	88	137	188	74	137	263	82	130	173
J₂M₁S₂	127	185	258	145	199	232	187	249	347	172	242	405	185	241	326
J₂M₂S₁	35	61	93	48	78	93	67	96	137	63	93	149	64	90	127
J₂M₂S₂	70	112	147	89	126	154	151	181	225	138	177	248	149	174	210
J₂M₃S₁	26	42	66	41	56	75	61	75	93	54	76	107	56	70	86
J₂M₃S₂	49	71	96	67	78	96	114	130	156	106	128	166	112	125	149
J₂M₄S₁	28	31	42	34	42	53	60	68	77	52	69	100	56	64	72
J₂M₄S₂	24	46	69	44	55	74	91	106	130	87	102	133	88	100	122
J₃M₁S₁	180	242	341	198	278	354	220	282	376	199	279	434	214	273	370
J₃M₁S₂	292	370	463	314	394	475	374	462	548	349	460	665	368	450	534
J₃M₂S₁	113	141	175	120	177	199	153	184	209	143	183	263	145	178	202
J₃M₂S₂	180	237	323	197	256	345	279	337	426	271	333	439	269	328	414
J₃M₃S₁	76	104	129	97	142	168	116	149	183	110	152	194	112	144	176
J₃M₃S₂	124	168	215	135	189	243	212	257	299	204	264	336	205	249	286
J₃M₄S₁	54	76	104	78	98	134	97	117	137	91	115	153	94	112	132
J₃M₄S₂	98	123	144	104	135	189	174	199	233	167	196	251	169	193	224
J₄M₁S₁	410	530	736	452	580	786	485	589	818	462	585	788	476	579	807
J₄M₁S₂	690	889	1 169	742	945	1 224	862	1 070	1 353	835	1 062	1 439	840	1 053	1 326
J₄M₂S₁	262	338	526	354	388	578	309	401	622	301	401	633	307	392	605
J₄M₂S₂	418	551	653	478	610	687	536	697	795	503	679	858	528	684	778
J₄M₃S₁	212	245	314	245	294	382	261	306	380	259	307	386	261	300	372
J₄M₃S₂	309	380	449	354	432	487	422	515	596	410	515	783	426	506	580
J₄M₄S₁	142	188	217	189	240	340	194	249	279	187	249	305	193	244	269
J₄M₄S₂	230	291	327	321	344	371	361	424	488	346	430	575	358	415	476
J₅M₁S₁	646	725	830	702	845	945	682	788	920	674	785	963	553	767	910
J₅M₁S₂	1 087	1 326	1 575	1 124	1 453	1 543	1 257	1 549	1 838	1 220	1 548	2 222	1 241	1 531	1 803
J₅M₂S₁	382	484	642	420	568	741	432	567	731	425	569	752	430	557	716
J₅M₂S₂	706	826	1 072	842	957	1 124	820	989	1 219	806	989	1 306	811	977	1 200
J₅M₃S₁	304	366	423	345	446	512	357	430	502	344	428	515	356	423	489
J₅M₃S₂	484	626	688	524	724	898	665	819	965	658	809	1 050	651	805	929
J₅M₄S₁	250	284	323	250	320	425	299	361	415	298	362	534	304	354	411
J₅M₄S₂	426	461	546	435	513	587	534	621	742	525	621	769	531	610	721

表9

图4

图5

参考文献 16

1	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
	Chen Kui, Bi Li, Wang Wenya. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop[J]. Journal of System Simulation, 2022, 34(3): 461-469.
2	尤一琛, 王艳, 纪志成. 基于博弈论的柔性作业车间动态调度研究[J]. 系统仿真学报, 2021, 33(11): 2579-2588.
	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.
3	Jia Zhaohong, Huo Siyun, Li Kai, et al. Integrated Scheduling on Parallel Batch Processing Machines With Non-identical Capacities[J]. Engineering Optimization, 2020, 52(4): 715-730.
4	Jia Zhaohong, Yan Jianhai, Leung J Y T, et al. Ant Colony Optimization Algorithm for Scheduling Jobs With Fuzzy Processing Time on Parallel Batch Machines With Different Capacities[J]. Applied Soft Computing, 2019, 75: 548-561.
5	Elias C Arroyo José, Leung J Y T. An Effective Iterated Greedy Algorithm for Scheduling Unrelated Parallel Batch Machines With Non-identical Capacities and Unequal Ready Times[J]. Computers & Industrial Engineering, 2017, 105: 84-100.
6	Jia Zhaohong, Zhang Han, Long Wentao, et al. A Meta-heuristic for Minimizing Total Weighted Flow Time on Parallel Batch Machines[J]. Computers & Industrial Engineering, 2018, 125: 298-308.
7	Tan Mao, Yang Huali, Su Yongxin. Genetic Algorithms With Greedy Strategy for Green Batch Scheduling on Non-identical Parallel Machines[J]. Memetic Computing, 2019, 11(4): 439-452.
8	Kong Min, Liu Xinbao, Pei Jun, et al. A BRKGA-DE Algorithm for Parallel-batching Scheduling With Deterioration and Learning Effects on Parallel Machines Under Preventive Maintenance Consideration[J]. Annals of Mathematics and Artificial Intelligence, 2020, 88(1): 237-267.
9	Zarook Y, Rezaeian J, Mahdavi I, et al. Efficient Algorithms to Minimize Makespan of the Unrelated Parallel Batch-processing Machines Scheduling Problem with Unequal Job Ready Times[J]. Rairo Operations Research, 2021, 55(3): 1501-1522.
10	Graham R L, Lawler E L, Lenstra J K, et al. Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey[J]. Annals of Discrete Mathematics, 1979, 5: 287-326.
11	张源, 王加冕. 改进粒子群算法求解置换流水车间调度问题[J]. 软件, 2020, 41(6): 108-111, 131.
	Zhang Yuan, Wang Jiamian. An Improved Particle Swarm Optimization Algorithm is Proposed to Solve the Displacement Flow Shop Scheduling Problem[J]. Computer Engineering & Software, 2020, 41(6): 108-111, 131.
12	Lee C Y. Minimizing Makespan on a Single Batch Processing Machine With Dynamic Job Arrivals[J]. International Journal of Production Research, 1999, 37(1): 219-236.
13	Cakici E, Mason S J, Fowler J W, et al. Batch Scheduling on Parallel Machines With Dynamic Job Arrivals and Incompatible Job Families[J]. International Journal of Production Research, 2013, 51(8): 2462-2477.
14	Jiang Wei, Shen Yilan, Liu Lingxuan, et al. A New Method for a Class of Parallel Batch Machine Scheduling Problem[J]. Flexible Services and Manufacturing Journal, 2022, 34(2): 518-550.
15	Elias C Arroyo José, Leung J Y T, Ricardo Gonçalves Tavares. An Iterated Greedy Algorithm for Total Flow Time Minimization in Unrelated Parallel Batch Machines With Unequal Job Release Times[J]. Engineering Applications of Artificial Intelligence, 2019, 77: 239-254.
16	Zhou Shengchao, Liu Ming, Chen Huaping, et al. An Effective Discrete Differential Evolution Algorithm for Scheduling Uniform Parallel Batch Processing Machines With Non-identical Capacities and Arbitrary Job Sizes[J]. International Journal of Production Economics, 2016, 179: 1-11.

数组	位置K	工件	数组	位置K	工件
0.11	2	1	0.65	8	5
0.20	4	2	0.45	6	6
0.32	5	3	0.56	7	7
0.05	1	4	0.12	3	8

作业	尺寸	PT₁	PT₂	PT₃
19	3.0	9.3	6.5	7.2
20	8.0	8.0	21.4	15.0
15	17.0	33.6	23.5	26.1
18	14.0	29.3	20.5	22.8
4	6.0	17.9	12.5	13.9
7	13.0	22.1	15.5	17.2
12	10.0	17.9	12.5	13.9
13	7.0	20.0	23.6	16.5
1	20.0	23.6	16.5	18.3
3	6.0	7.1	5.0	5.6
16	8.0	15.0	10.5	11.7
6	10.0	20.7	14.5	16.1
5	16.0	12.9	9.0	10.0
17	7.0	19.3	13.5	15.0
10	14.0	26.4	18.5	20.6
2	16.0	17.9	12.5	13.9
14	11.0	34.3	24.0	26.7
8	13.0	31.4	22.0	24.4
9	15.0	25.0	17.5	19.4
11	4.0	22.9	16.0	17.8

DDE^[16]	HPSO	LSPSO^[14]	TS	PSO
P=40	P=50	P=50	T_max=200	P=50
T_max=100	T_max=100	T_max=100	T_abuL=10	T_max=100
Pc=0.1	ω=0.6	ω=0.6	C_num=10	ω=0.9
P_m=0.5	C₁=2.0	C₁=2.0		C₁=2.05
	C₂=1.0	C₂=1.0		C₂=2.05

[1]	王旭, 季伟东, 周国辉. 基于协同博弈粒子群算法的故障指示器配置优化[J]. 系统仿真学报, 2023, 35(6): 1278-1289.
[2]	赵传超, 郑睿, 龚莉, 马小陆. 网联环境中新能源货车的粒子群调度方法[J]. 系统仿真学报, 2023, 35(6): 1337-1350.
[3]	胡万杰, 董建军, 任睿, 陈志龙. 考虑模糊不确定的地铁货运系统成网布局规划[J]. 系统仿真学报, 2022, 34(8): 1725-1740.
[4]	冯飞波, 闫兴德, 郑宝强, 尹晓峰, 周梦真, 蒋鑫. 蓄电‒氢储混合储能系统的配电网双层优化[J]. 系统仿真学报, 2022, 34(7): 1405-1416.
[5]	马立新, 程颍. 计及可中断负荷的园区综合能源系统优化调度[J]. 系统仿真学报, 2022, 34(4): 817-825.
[6]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[7]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[8]	孙晓安, 栾小丽, 刘飞. 基于智能优化灰色模型的电子固废预测[J]. 系统仿真学报, 2022, 34(3): 536-542.
[9]	张富震, 朱耀琴. 复杂环境中多无人机协同侦察的任务分配方法[J]. 系统仿真学报, 2022, 34(10): 2293-2302.
[10]	张莉, 张惠珍, 刘冬, 陆雨欣. 考虑紧迫度的应急物资调度及粒子群算法求解[J]. 系统仿真学报, 2022, 34(09): 1988-1998.
[11]	朱依婷, 闫云, 何兆成. 公交与社会车辆混合的中观交通建模与仿真[J]. 系统仿真学报, 2022, 34(09): 2019-2027.
[12]	邵良杉, 王振, 李昌明. 基于模拟退火与改进粒子群的矿井通风优化算法[J]. 系统仿真学报, 2021, 33(9): 2085-2094.
[13]	魏腾飞, 潘庭龙. 基于改进PSO优化LSTM网络的短期电力负荷预测[J]. 系统仿真学报, 2021, 33(8): 1866-1874.
[14]	牛侃, 李冰, 付强. 基于混沌扰动机制粒子群算法的战场频率分配方法[J]. 系统仿真学报, 2021, 33(8): 1905-1913.
[15]	孟建军, 王终军, 胥如迅, 李德仓. 基于模糊复合策略的高速列车主动悬挂控制研究[J]. 系统仿真学报, 2021, 33(7): 1554-1564.