An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

doi:10.23919/JSEE.2021.000024

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (2): 272-285.doi: 10.23919/JSEE.2021.000024

• INTELLIGENT OPTIMIZATION AND SCHEDULING • Previous Articles Next Articles

An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

Xiuli WU^1,*(), Junjian PENG¹(), Zirun XIE¹(), Ning ZHAO¹(), Shaomin WU²()

¹ School of Mechanic Engineering, University of Science and Technology Beijing, Beijing 100083, China
² Kent Business School, University of Kent, Kent CT2 7FS, UK

Received:2020-12-02 Online:2021-04-29 Published:2021-04-29
Contact: Xiuli WU E-mail:wuxiuli@ustb.edu.cn;18810458661@163.com;xiezirain@163.com;nickzhao@me.ustb.edu.cn;s.m.wu@kent.ac.uk
About author:|WU Xiuli was born in 1977. She received her B.S., M.S. and Ph.D. degrees in mechanical and electronic engineering from Northwestern Polytechnical University, Xi’an, Shaanxi Province, China, in 2000, 2003 and 2006, respectively. Since 2006, she has been with the Department of Logistics, School of Mechanical Engineering, University of Science and Technology Beijing, where she became a professor in 2020. She has authored two books and over 50 refereed papers. Her current research interests include intelligent optimization, production scheduling, and logistic optimization. E-mail: wuxiuli@ustb.edu.cn||PENG Junjian was born in 1992. He received his B.S. degree in industrial engineering from Henan Polytechnical University, Jiaozuo, Henan Province, China, in 2018. He is a master of University of Science and Technology Beijing. His research interests include intelligent optimization, and production scheduling. E-mail: 18810458661@163.com||XIE Zirun was born in 1996. She received her B.S. degree in logistics engineering from University of Science and Technology Beijing, Beijing, China, in 2019. She is a master of University of Science and Technology Beijing. Her research interests include intelligent optimization and production scheduling. E-mail: xiezirain@163.com||ZHAO Ning was born in 1978. He received his Ph.D. degree in mechanical manufacturing and automation from Beijing Institute of Technology, Beijing, China, in 2005. He is a Ph.D. and a professor in University of Science and Technology Beijing. His research interests include applied intelligent manufacturing system, scheduling and simulation decision. E-mail: nickzhao@me.ustb.edu.cn||WU Shaomin was born in 1965. He received his Ph.D. degree in applied statistics from Southeast University, Nanjing, China, in 1995. He is a Ph.D. and a professor in Kent Business School, University of Kent, UK. His research interests include applied stochastic processes, business data analysis, statistical data analysis, data mining, and risk management. E-mail: s.m.wu@kent.ac.uk
Supported by:
This paper was supported by the National Key R&D Plan (2020YFB1712902) and the National Natural Science Foundation of China (52075036).;This paper was supported by the National Key R&D Plan (2020YFB1712902) and the National Natural Science Foundation of China (52075036).

Abstract

Abstract:

In order to solve the flexible job shop scheduling problem with variable batches, we propose an improved multi-objective optimization algorithm, which combines the idea of inverse scheduling. First, a flexible job shop problem with the variable batches scheduling model is formulated. Second, we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method. Moreover, in order to increase the diversity of the population, two methods are developed. One is the threshold to control the neighborhood updating, and the other is the dynamic clustering algorithm to update the population. Finally, a group of experiments are carried out. The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively, and has effective performance in solving the flexible job shop scheduling problem with variable batches.

Key words: flexible job shop, variable batch, inverse scheduling, multi-objective evolutionary algorithm based on decomposition, a batch optimization algorithm with inverse scheduling

Xiuli WU, Junjian PENG, Zirun XIE, Ning ZHAO, Shaomin WU. An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 272-285.

Figures/Tables 20

Table 1

Fig.1

Table 2

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Table 3

Table 4

Table 5

Table 6

Table 7

Fig.10

Fig.11

Table 8

Table 9

References 30

1	ZHANG M, TAN Y, ZHU J H, et al A competitive and cooperative migrating birds optimization algorithm for vary-sized batch splitting scheduling problem of flexible job-shop with setup time. Simulation Modelling Practice and Theory, 2020, 100, 1- 19.
2	WU X L, PENG J J, XIAO X, et al An effective approach for the dual-resource flexible job shop scheduling problem considering loading and unloading. Journal of Intelligent Manufacturing, 2021, 32, 707- 728. doi: 10.1007/s10845-020-01697-5
3	LI Y J, LI S G Scheduling jobs with sizes and delivery times on identical parallel batch machines. Theoretical Computer Science, 2020, 841 (11): 1- 9.
4	WANG Y, JIA Z H, LI K A multi-objective co-evolutionary algorithm of scheduling on parallel non-identical batch machines. Expert Systems with Applications, 2021, 167, 114145. doi: 10.1016/j.eswa.2020.114145
5	SONG C Improved greedy genetic algorithm for solving the hybrid flow-shop scheduling problem. Systems Engineering and Electronics, 2019, 41 (5): 1079- 1086.
6	OMID S, RASARATNAM L A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect. International Journal of Production Economics, 2018, 195, 227- 248. doi: 10.1016/j.ijpe.2017.10.015
7	MENG T, PAN Q K, LI J Q, et al An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem. Swarm and Evolutionary Computation, 2018, 38, 64- 78. doi: 10.1016/j.swevo.2017.06.003
8	LIU S W, PEI J, CHENG H, et al. Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes. Applied Soft Computing, 2019, 84: 105701.
9	CHANG J H, CHIU H N A comprehensive review of lot streaming. International Journal of Production Research, 2005, 43 (8): 1515- 1536. doi: 10.1080/00207540412331325396
10	NOVAS M J Production scheduling and lot streaming at flexible job-shops environments using constraint programming. Computers & Industrial Engineering, 2019, 136, 252- 264.
11	GENG Z C, YUAN J J, YUAN J L Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost. Applied Mathematics and Computation, 2018, 332, 1- 18.
12	HUANG R H, YU T H An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting. Applied Soft Computing, 2017, 57, 642- 656. doi: 10.1016/j.asoc.2017.04.062
13	DEFERSHA F M Linear programming assisted (not embedded) genetic algorithm for flexible jobshop scheduling with lot streaming. Computers & Industrial Engineering, 2018, 117, 319- 335.
14	HAM A M, CAKICI E Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches. Computers & Industrial Engineering, 2016, 102, 160- 165.
15	ZHOU Y, YANG J J, ZHENG L Y Multi-agent based hyper-heuristics for multi-objective flexible job shop scheduling: a case study in an aero-engine blade manufacturing plant. IEEE Access, 2019, 7, 21147- 21176. doi: 10.1109/ACCESS.2019.2897603
16	BOZEK A, WERNER F Flexible job shop scheduling with lot streaming and sublot size optimization. International Journal of Production Research, 2017, 56 (19): 6391- 6411.
17	JIA Z H, WANG Y, WU C, et al Multi-objective energy-aware batch scheduling using ant colony optimization algorithm. Computers & Industrial Engineering, 2019, 131, 41- 56.
18	REITER S A system for managing job-shop production. Journal of Business, 1966, 39 (3): 371- 393. doi: 10.1086/294867
19	PENG J G, LIU M Z, ZHANG X, et al Hybrid heuristic algorithm for multi-objective scheduling problem. Journal of Systems Engineering and Electronics, 2019, 30 (2): 327- 342. doi: 10.21629/JSEE.2019.02.12
20	DONG Z M, WANG X P, TANG L X MOEA/D with a self-adaptive weight vector adjustment strategy based on chain segmentation. Information Sciences, 2020, 521, 209- 230. doi: 10.1016/j.ins.2020.02.056
21	JIANG E D, WANG L Multi-objective optimization based on decomposition for flexible job shop scheduling under time-of-use electricity prices. Knowledge-Based Systems, 2020, 204, 106- 177.
22	WANG L P, FENG M L, QIU F Y, et al Decomposition multi-objective evolutionary algorithm for recursive replacement optimization strategy. Journal of Chinese Computer Systems, 2018, 39 (6): 1135- 1141.
23	QI Y T, MA X L, LIU F, et al MOEA/D with adaptive weight adjustment. Evolutionary Computation, 2014, 22 (2): 231- 264. doi: 10.1162/EVCO_a_00109
24	BRUCKER P, SHAKHLEVICH N V Inverse scheduling: two-machine flow-shop problem. Journal of Scheduling, 2011, 14 (3): 239- 256. doi: 10.1007/s10951-010-0168-y
25	WU X L, SUN Y J A green scheduling algorithm for flexible job shop with energy-saving measures. Journal of Cleaner Production, 2018, 172, 3249- 3264. doi: 10.1016/j.jclepro.2017.10.342
26	ZHAO Y W, WANG H Y, XU X X A new hybrid parallel algorithm for consistent-sized batch splitting job shop scheduling on alternative machines with forbidden intervals. The International Journal of Advanced Manufacturing Technology, 2010, 48, 1091- 1105. doi: 10.1007/s00170-009-2340-0
27	DEFERSHA F M, CHEN M Y Jobshop lot streaming with routing flexibility, sequence-dependent setups, machine release dates and lag time. International Journal of Production Research, 2012, 50 (8): 2331- 2352. doi: 10.1080/00207543.2011.574952
28	WU X L, YUAN Q, WANG L. Multi-objective differential evolution algorithm for solving robotic cell scheduling problem with batch-processing machines. IEEE Trans. on Automation Science and Engineering, 2000. DOI: 10.1109/TASE.2020.2969469.
29	JAMALI A, MALLIPEDDI R, SALEHPOUR M, et al Multi-objective differential evolution algorithm with fuzzy inference-based adaptive mutation factor for Pareto optimum design of suspension system. Swarm and Evolutionary Computation, 2020, 54, 100666. doi: 10.1016/j.swevo.2020.100666
30	YUE F, SONG S J, JIA P, et al Robust single machine scheduling problem with uncertain job due dates for industrial mass production. Journal of Systems Engineering and Electronics, 2020, 31 (2): 350- 358. doi: 10.23919/JSEE.2020.000012

Notation	Definition
m	Amount of the machines
n	Amount of the jobs
l	Machines index,l =1, 2, ···, m
i	Jobs index,i= 1, 2, ···, n
${{J}_{{i}}}$	Sub-batches of job i
j	Sub-batch index of jobi, j = 1, 2, ···, \| ${{{J}}}_{i}}_{i}$ \|
K_i	Operations of job i
k	Operation index, k= 1, 2, ···, \|K_i\|
$ {O}_{ijk} $	The kth operation of the jth sub-batch of job i
$ {t}_{ijkl} $	Processing time of operation $ {O}_{ijk} $ on machine l
$ {t}_{ijk} $	Processing time of operation $ {O}_{ijk} $
$ {b}_{i} $	Batch size of job i
$ {b}_{ij} $	Batch size of the jth sub-batch of job i
$ {b'}_{ij} $	Batch size of the jth sub-batch of job i after adjustment
$ {n}_{ij} $	Actual added batch size of the jth sub-batch of job i
$ {n'}_{ij} $	Virtual added batch size of the jth sub-batch of job i
$ {C}_{\rm{max}} $	The makespan
$ {S}_{ijk} $	Start time of operation $ {O}_{ijk} $
$ {C}_{ijk} $	Ending time of operation $ {O}_{ijk} $
T	Total transportation time
$ {T}_{{l}_{1}{l}_{2}} $	Transferring time from machinel₁ to machine l₂; $ {T}_{{l}_{1}{l}_{2}} $ =0, if $ {l}_{1}={l}_{2} $
$ {x}_{ijkl} $	$ {x}_{ijkl} $ =1 if the operation $ {O}_{ijk} $ is processed by machine l; otherwise $ {x}_{ijkl} $ =0
$ {x}_{ijklt} $	At time t if $ {x}_{ijkl} $ =1, $ {x}_{ijklt} $ =1; otherwise, $ {x}_{ijklt} $ =0
$ {y}_{ij} $	If the jth sub-batch of job i needs to increase the batch size, $ {y}_{ij} $ =1; otherwise $ {y}_{ij} $ =0

Job	Batch size	Operation	M₁	M₂	M₃
1	12	$ {O}_{11} $	10	10	—
		$ {O}_{12} $	2	2	—
		$ {O}_{13} $	—	—	3
2	6	$ {O}_{21} $	2	—	—
		$ {O}_{22} $	—	5	—
		$ {O}_{23} $	—	—	5

Number	Instance	$ n \times m $	Batch size of jobs
Test01	Novas^[10]	3 $ \times $ 3	[32, 48, 31]
Test02	Zhao et al^[26]	3 $ \times $ 4	[54, 58, 49]
Test03	Novas^[10]	3 $ \times $ 5	[21, 39, 36]
Test04	Novas^[10]	4 $ \times $ 5	[9, 20, 25, 6]
Test05	Defersha et al.^[27]	4 $ \times $ 6	[32, 47, 20, 17]
Test06	Defersha et al.^[27]	6 $ \times $ 6	[17, 49, 43, 23, 46, 19]
Test07	Novas^[10]	8 $ \times $ 7	[17, 29, 33, 33, 46, 19, 9, 43]
Test08	Novas^[10]	9 $ \times $ 8	[22, 47, 35, 19, 36, 38, 28, 30, 38]
Test09	Novas^[10]	11 $ \times $ 8	[46, 9, 30, 47, 7, 7, 44, 9, 18, 46, 17]
Test10	Novas^[10]	12 $ \times $ 8	[46, 35, 39, 9, 28, 17, 43, 5, 13, 7, 50, 21]

Indicator	R	pc=0.7			pc=0.8			pc=0.9
Indicator	R	pm=0.1	pm=0.15	pm=0.2	pm=0.1	pm=0.15	pm=0.2	pm=0.1	pm=0.15	pm=0.2
HV	0.05	606.61	1 944.64	1 820.26	2 220.54	944.31	1 429.1	1 970.26	1 273.82	2 396.7
	0.1	1 585.36	1 896.8	639.58	2 204.65	2 059.63	1 506.86	2 115.18	134.93	2 911.07
	0.15	1 499.31	941.59	1 030.54	1 092.39	1 102.42	891.66	564.98	1 716.67	1 110.39
IHV	0.05	441.24	98.63	168.22	209.71	180.28	167.88	108.44	129.01	173.12
	0.1	95.32	91.55	266.91	132.28	258.94	214.67	130.66	74.2	192.6
	0.15	92.85	60.99	191.52	194.12	123.01	224.42	110.2	205.12	137.68
IGD	0.05	1 291.05	1 439.39	1 348.38	1 411.64	1 430.61	1 888.81	1 248.72	1 385.6	1 587.37
	0.1	1 547.89	1 396.05	1 945.29	1 334.35	1 954.2	1 976.07	1 414.73	899.4	1 517.29
	0.15	1 553.3	1 225.08	1 438.2	1 464.17	1 193.79	1 248.57	1 044.2	1 532.24	1 334.99

HV			IHV			IGD
pc	pm	R	pc	pm	R	pc	pm	R
0.7(1 329.41)	0.1(1 539.92)	0.05(1 622.91)	0.7(167.47)	0.1(140.11)	0.05(186.28)	0.7(1 464.95)	0.1(1 367.78)	0.05(1 447.95)
0.8(1 494.61)	0.15(1 334.97)	0.1(1 672.67)	0.8(189.47)	0.15(241.41)	0.1(161.90)	0.8(1 544.69)	0.15(1 384.04)	0.1(1 553.91)
0.9(1 577.11)	0.2(1 526.24	0.15(1 105.55)	0.9(140.11)	0.2(211.61)	0.15(148.87)	0.9(1 329.39)	0.2(1 587.21)	0.15(1 337.17)

An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 20

References 30

Related Articles 1

Recommended Articles

Metrics

Comments

Number	Number of Pareto solutions		HV		IHV
Number	IMOA	MOEA/D	IMOA	MOEA/D	IMOA	MOEA/D
1	11	7	1 392.98	877.17	135.42	143.21
2	9	11	1 384.82	1 175.43	117.44	139.39
3	17	13	3 283.24	1 738.94	119.16	267.15
4	16	11	3 432.73	1 357.31	48.03	323.70
5	20	12	3 056.51	1 722.89	175.76	127.31
6	18	11	3 197.70	1 807.41	222.03	358.76
7	14	12	3 787.31	2 140.67	1 054.95	294.01
8	15	6	2 316.36	201.77	313.59	77.95
9	14	14	1 408.93	2 296.49	128.13	194.86
10	20	12	3 660.51	2 461.24	317.63	364.25

Instance	Variable batching	Rank	Equal batching	Rank
Test01	0.90	17	1.09	20
Test02	0.51	3	0.76	9
Test03	0.59	4	0.85	15
Test04	0.72	8	1.02	19
Test05	0.43	1	0.59	5
Test06	0.67	7	0.80	11
Test07	0.65	6	0.83	13
Test08	0.50	2	0.94	18
Test09	0.78	10	0.85	16
Test10	0.83	12	0.84	14
z = 2.608>1.645	n₁ = 10	T₁ = 70	n₂ = 10	T₂ = 140

Times of test	Makespan		Transferring time
Times of test	BOA-IS	GEM	BOA-IS	GEM
1	119.70	121.20	46.72	68.40
2	119.40	122.20	66.29	88.73
3	115.60	116.00	88.00	81.59
4	117.50	117.70	68.12	98.55
5	116.20	116.50	73.42	86.37
6	120.50	121.20	46.91	50.95
7	118.20	118.20	83.16	109.83
8	120.90	121.80	34.99	41.46
9	117.23	116.20	104.40	139.90
10	117.70	119.20	59.940	108.16

Test	Makespan			Transportation time
Test	IMOEA/ISD	MODE	NSGA-II	IMOEA/ISD	MODE	NSGA-II
Test01	322.70	328.52	326.21	61.27	69.77	65.19
Test02	195.29	188.87	186.19	37.07	41.94	59.92
Test03	348.96	355.56	367.99	71.17	78.72	77.80
Test04	391.89	414.45	383.82	85.68	86.76	94.31
Test05	304.79	356.05	327.18	95.01	88.51	98.35
Test06	832.20	842.26	834.61	496.87	498.05	503.50
Test07	1 244.15	1 214.49	1 248.01	152.24	223.63	177.51
Test08	1 395.91	1 435.80	1 441.40	348.16	376.39	376.33
Test09	1 409.55	1 565.45	1 501.74	518.93	519.10	573.55
Test10	1 516.48	1 556.72	1 579.18	485.99	506.87	487.03