Improved Particle Swarm Algorithm of Unrelated Parallel Batch Scheduling Optimization

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 14

Table 1

Table 2

Fig. 1

Table 3

Table 4

Fig. 2

Table 5

Problem instance parameters

变量	符号	数值
工件数量	$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$

Table 5

Table 6

Simulation results under different parameter combinations

算例	编号
算例	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

Table 6

Table 7

Fig. 3

Table 8

Table 9

Simulation results

算例	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

Table 9

Fig. 4

Fig. 5

References 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]	Chuanchao Zhao, Rui Zheng, Li Gong, Xiaolu Ma. Particle Swarm Optimization for New Energy Truck Scheduling in Network Environment [J]. Journal of System Simulation, 2023, 35(6): 1337-1350.
[2]	Kui Chen, Li Bi, Wenya Wang. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop [J]. Journal of System Simulation, 2022, 34(3): 461-469.
[3]	Li Zhang, Huizhen Zhang, Dong Liu, Yuxin Lu. Particle Swarm Algorithm for Solving Emergency Material Dispatch Considering Urgency [J]. Journal of System Simulation, 2022, 34(09): 1988-1998.
[4]	Shao Liangshan, Wang Zhen, Li Changming. Optimization Algorithm of Mine Ventilation Based on SA-IPSO [J]. Journal of System Simulation, 2021, 33(9): 2085-2094.
[5]	Lu Jiabo, Cheng Peixing, Huang Yi, Yao Jinqiang, Yang Xuemeng, Ma Xinqiang, Liu Yong. An Intelligent Method for Rapid Construction of Time Sensitive Target Strike Chain [J]. Journal of System Simulation, 2021, 33(2): 346-357.
[6]	Hu Xiaoman, Wang Yan, Ji Zhicheng. Fuzzy Information Granulation and Improved RVM for Rolling Bearing Life Prediction [J]. Journal of System Simulation, 2021, 33(11): 2561-2571.
[7]	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.
[8]	Cao Zhenqian, Yin Jiang, Zhang Jinhua. Identification of Main Steam Temperature System Based on Improved Particle Swarm Optimization [J]. Journal of System Simulation, 2021, 33(10): 2411-2419.
[9]	Li Zhenping, Zhao Yuwei, Zhang Yuwei, Xing Lining, Ren Teng. Joint Distribution Location-routing Problem and Large Neighborhood Search Algorithm [J]. Journal of System Simulation, 2021, 33(10): 2518-2531.
[10]	Qing Dongsheng, Zhang Xiaofang, Li Jianjun, Guo Rui, Deng Qiaoling. Spatial Structure Optimization of Natural Forest Based on Bee Colony-particle Swarm Algorithm [J]. Journal of System Simulation, 2020, 32(3): 371-381.
[11]	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.
[12]	Xuan Hua, Qin Yingying, Wang Xueyuan, Zhang Bailin. Optimization for Unrelated Parallel Machine Scheduling with Deteriorating Jobs [J]. Journal of System Simulation, 2019, 31(5): 919-924.
[13]	Zhao Wenqing, Qin Zhibu. Improved Intelligent Water Drops Algorithm Applied to Power Economic Emission Dispatch [J]. Journal of System Simulation, 2018, 30(8): 3213-3218.
[14]	Liu Wei, Xu Jiaxuan, Wang Peipei, Liu Ruilong, Tang Jingkun. Train Energy Saving Operation Based on Simulated Annealing Algorithm [J]. Journal of System Simulation, 2018, 30(6): 2320-2327.
[15]	Wang Changtao, Sun Xiaotong, Han Zhonghua, Zhu Yi. A Study of Adaptive Simulated Annealing Particle Swarm Optimization (ASAPSO) Algorithm for Building Pipe Routing Design [J]. Journal of System Simulation, 2018, 30(5): 1941-1949.