Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm

doi:10.23919/JSEE.2021.000023

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (2): 261-271.doi: 10.23919/JSEE.2021.000023

• INTELLIGENT OPTIMIZATION AND SCHEDULING • Next Articles

Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm

Cuiyu WANG(), Yang LI(), Xinyu LI*()

¹ School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2020-11-23 Online:2021-04-29 Published:2021-04-29
Contact: Xinyu LI E-mail:76325434@qq.com;281366572@qq.com;lixinyu@mail.hust.edu.cn
About author:|WANG Cuiyu was born in 1983. She received her M.S. degree in industrial engineering with the Department of Industrial & Manufacturing System Engineering, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, China, in 2007. She is currently pursuing her Ph.D. degree in industrial engineering with Huazhong University of Science and Technology. Her research interest is scheduling algorithm. E-mail: 76325434@qq.com||LI Yang was born in 1996. He received his B.S. degree in industrial engineering from the School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, China, in 2018. He is currently pursuing his Ph.D. degree in industrial engineering, with Huazhong University of Science and Technology. His research interests include scheduling algorithm and optimization algorithm. E-mail: 281366572@qq.com||LI Xinyu was born in 1985. He is currently a professor with the Department of Industrial & Manufacturing System Engineering, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, China. His research interests include intelligent optimization and scheduling, and intelligent manufacturing system. E-mail: lixinyu@mail.hust.edu.cn
Supported by:
This work was supported by the National Key R&D Program of China (2018AAA0101700), and the Program for HUST Academic Frontier Youth Team (2017QYTD04);This work was supported by the National Key R&D Program of China (2018AAA0101700), and the Program for HUST Academic Frontier Youth Team (2017QYTD04)

Abstract

Abstract:

The flexible job shop scheduling problem (FJSP), which is NP-hard, widely exists in many manufacturing industries. It is very hard to be solved. A multi-swarm collaborative genetic algorithm (MSCGA) based on the collaborative optimization algorithm is proposed for the FJSP. Multi-population structure is used to independently evolve two sub-problems of the FJSP in the MSCGA. Good operators are adopted and designed to ensure this algorithm to achieve a good performance. Some famous FJSP benchmarks are chosen to evaluate the effectiveness of the MSCGA. The adaptability and superiority of the proposed method are demonstrated by comparing with other reported algorithms.

Key words: flexible job shop scheduling problem (FJSP), collaborative genetic algorithm, co-evolutionary algorithm

Cuiyu WANG, Yang LI, Xinyu LI. Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 261-271.

Figures/Tables 14

Fig.1

Fig.2

Table 1

Fig.3

Fig.4

Fig.5

Table 2

Fig.6

Fig.7

Fig.8

Table 3

Fig.9

Fig.10

Table 4

References 48

1	AKYOL D E, BAYHAN G M A review on evolution of production scheduling with neural networks. Computers & Industrial Engineering, 2007, 53 (1): 95- 122.
2	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
3	WANG P, REINELT G, TAN Y J Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems. Journal of Systems Engineering and Electronics, 2012, 23 (2): 208- 215. doi: 10.1109/JSEE.2012.00027
4	XU Y, WANG L Differential evolution algorithm for hybrid flow shop scheduling problems. Journal of Systems Engi-neering and Electronics, 2011, 22 (5): 794- 798. doi: 10.3969/j.issn.1004-4132.2011.05.011
5	JIANG E D, WANG L, PENG Z P Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition. Swarm and Evolutionary Computation, 2020, 58, 100745. doi: 10.1016/j.swevo.2020.100745
6	AGARWAL A K, KUMAR D R R Job shop and flexible job shop scheduling problems: scheduling operations. International Journal of Innovations in Engineering Research and Technology, 2020, 7 (5): 334- 350.
7	XIE J, GAO L, PENG K K, et al Review on flexible job shop scheduling. IET Collaborative Intelligent Manufacturing, 2019, 1 (3): 67- 77. doi: 10.1049/iet-cim.2018.0009
8	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
9	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, 106177. doi: 10.1016/j.knosys.2020.106177
10	GAO K Z, CAO Z G, ZHANG L, et al A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems. IEEE/CAA Journal of Automatica Sinica, 2019, 6 (4): 904- 916. doi: 10.1109/JAS.2019.1911540
11	BRUCKER P, SCHILE R Job-shop scheduling with multi-purpose machines. Computing, 1990, 45 (4): 369- 375. doi: 10.1007/BF02238804
12	LI J Q, DENG J W, LI C Y, et al An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. Knowledge-Based Systems, 2020, 200, 106032. doi: 10.1016/j.knosys.2020.106032
13	HOMAYOUNI S M, FONTES D B M M, GONCALVES J F. A multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportation. International Transactions in Operational Research, 2020. DOI: 10.1111/itor.12878.
14	AQEL G A, LI X Y, GAO L A modified iterated greedy algorithm for the flexible job shop scheduling problem. Chinese Journal of Mechanical Engineering, 2019, 32 (2): 157- 167.
15	MASTROLILLI M, GAMBARDELLA L Effective neighbourhood functions for the flexible job shop problem. Journal of Scheduling, 2000, 3 (1): 3- 20. doi: 10.1002/(SICI)1099-1425(200001/02)3:1<3::AID-JOS32>3.0.CO;2-Y
16	AMIRI M, ZANDIEH M, YAZDANI M, et al A variable neighbourhood search algorithm for the flexible job shop scheduling problem. International Journal of Production Research, 2010, 48 (19): 5671- 5689. doi: 10.1080/00207540903055743
17	DING H J, GU X S Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem. Computers and Operations Research, 2020, 121, 104951. doi: 10.1016/j.cor.2020.104951
18	LI X Y, GAO L An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 2016, 174, 93- 110. doi: 10.1016/j.ijpe.2016.01.016
19	RICARDO P R, ARTURO H A A hybrid estimation of distribution algorithm for flexible job-shop scheduling problems with process plan flexibility. Applied Intelligence, 2018, 48, 3707- 3734. doi: 10.1007/s10489-018-1160-z
20	MATI Y, LAHLOU C, PERES S D Modelling and solving a practical flexible job shop scheduling problem with blocking constraints. International Journal of Production Research, 2010, 49 (8): 2169- 2182.
21	BURDETT R L, CORRY P, EUSTACE C, et al A flexible job shop scheduling approach with operators for coal export terminals—a mature approach. Computers and Operations Research, 2020, 115, 104834. doi: 10.1016/j.cor.2019.104834
22	ZHANG C J, ZHOU Y, PENG K K, et al. Dynamic flexible job shop scheduling method based on improved gene expression programming. Measurement & Control, 2020. DOI: 10.1177/0020294020946352.
23	WANG J J, WANG L A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2020, 50 (5): 1805- 1819. doi: 10.1109/TSMC.2017.2788879
24	ZHAO F Q, HE X, WANG L. A two-stage cooperative evolutionary algorithm with problem-specific knowledge for ener-gy-efficient scheduling of no-wait flow-shop problem. IEEE Trans. on Cybernetics, 2020. DOI: 10.1109/TCYB.2020.3025662.
25	PAN Z X, LEI D M, WANG L. A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling. IEEE Trans. on Cybernetics, 2020. DOI: 10.1109/TCYB.2020.3026571.
26	LI X Y, GAO L, ZHANG L P, et al. An effective multi-swarm collaborative evolutionary algorithm for flexible job shop scheduling problem. Proc. of the 15th International Conference on Computer Supported Cooperative Work in Design, 2011: 281–184.
27	GOMES M C, POVOA A B P, NOVAIS A Q Optimal scheduling for flexible job shop operation. International Journal of Production Research, 2005, 43 (11): 2323- 2353. doi: 10.1080/00207540412331330101
28	KACEM I, HAMMADI S, BORNE P Approach by localization and multiobjective evolutionary optimization for flexible job shop scheduling problems. IEEE Trans. on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2002, 32 (1): 1- 13. doi: 10.1109/TSMCC.2002.1009117
29	HO N B, TAY J C, LAI E M K An effective architecture for learning and evolving flexible job shop schedules. European Journal of Operational Research, 2007, 179 (2): 316- 333. doi: 10.1016/j.ejor.2006.04.007
30	YIN L J, LI X Y, GAO L, et al A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem, considering productivity, energy efficiency and noise reduction. Sustainable Computing: Informatics and Systems, 2017, 13, 15- 30. doi: 10.1016/j.suscom.2016.11.002
31	SHI X Q, LONG W, LI Y N, et al Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems. PLoS One, 2020, 15 (5): e0233759. doi: 10.1371/journal.pone.0233759
32	CHEN R H, YANG B, LI S, et al A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Computers & Industrial Engineering, 2020, 149, 106778.
33	LU C, LI X Y, GAO L, et al An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times. Computers & Industrial Engineering, 2017, 104, 156- 174.
34	ALEJANDRO V S, AHMED A, MOHAMMED F B Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility. Journal of Manufacturing Systems, 2020, 54, 74- 93. doi: 10.1016/j.jmsy.2019.11.010
35	ZIRBI N, KACEM I, KAMEL A E, et al Assignment and scheduling in flexible job shops by hierarchical optimization. IEEE Trans. on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2007, 37 (4): 652- 661. doi: 10.1109/TSMCC.2007.897494
36	GAO J, SUN L Y, GEN M A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers and Operations Research, 2008, 35, 2892- 2907. doi: 10.1016/j.cor.2007.01.001
37	WU X L, SHEN X L, LI C B The flexible job-shop scheduling problem considering deterioration effect and energy consumption simultaneously. Computers & Industrial Engineering, 2019, 135, 1004- 1024.
38	ZHANG G H, ZHANG L J, SONG X H, et al A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem. Cluster Computing, 2019, 22, 11561- 11572. doi: 10.1007/s10586-017-1420-4
39	ROU L Y, ASMUNI H A study of cooperative co-evolutionary genetic algorithm for solving flexible job shop scheduling problem. International Journal of Computer and Information Engineering, 2010, 4 (12): 1849- 1854.
40	XING L N, CHEN Y W, YANG K W Multi-population interactive coevolutionary algorithm for flexible job shop scheduling problems. Computational Optimization and Applications, 2011, 48, 139- 155. doi: 10.1007/s10589-009-9244-7
41	BRANDIMARTE P Routing and scheduling in a flexible job shop by taboo search. Annals of Operations Research, 1993, 41 (3): 157- 183. doi: 10.1007/BF02023073
42	PERES S, PAULLI J An integrated approach for modeling and solving the general multiprocessor job shop scheduling using tabu search. Annals of Operations Research, 1997, 70, 281- 306. doi: 10.1023/A:1018930406487
43	FATTAHI P, MEHARABAD M S, JOLAI F. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 2007, 18: 331–342.
44	GAO L, PENG C Y, ZHOU C, et al. Solving flexible job shop scheduling problem using general particle swarm optimization. Proc. of the 36th Conference on Computers & Industrial Engineering, 2006: 3018–3027.
45	HMIDA A B, HAOUAI M, HUGUET M J, et al Discrepancy search for the flexible job shop scheduling problem. Computers and Operations Research, 2010, 37, 2192- 2201. doi: 10.1016/j.cor.2010.03.009
46	YUAN Y, XU H, YANG J D A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing, 2013, 13 (7): 3259- 3272. doi: 10.1016/j.asoc.2013.02.013
47	DEMIR Y, ISLEYEN S K Evaluation of mathematical models for flexible job shop scheduling problems. Applied Mathematical Modelling, 2013, 37 (3): 977- 988. doi: 10.1016/j.apm.2012.03.020
48	BIRGIN E G, FEOFILOFF P, FERNANDES C G, et al A MILP model for an extended version of the flexible job shop problem. Optimization Letters, 2014, 8, 1417- 1431. doi: 10.1007/s11590-013-0669-7

Problem	(LB, UB)	LEGA2008	VNSGA2019	HBFOA2020	PSO2020	SLGA2020	CCGA2010	MPICA2011	MSCGA
MK01	(36, 42)	40	40	40	40	40	41	39	40
MK02	(24, 32)	29	26	26	29	27	27	29	26
MK03	(204, 211)	—	204	204	204	204	204	204	204
MK04	(48, 81)	81	60	60	66	60	62	65	60
MK05	(168, 186)	186	173	172	175	172	173	173	173
MK06	(33, 86)	86	58	57	77	69	64	67	57
MK07	(133, 157)	157	144	139	145	144	140	144	139
MK08	(523, 523)	523	523	523	523	523	523	523	523
MK09	(299, 369)	369	307	307	320	320	328	311	307
MK10	(165, 296)	296	198	205	239	254	225	229	198

Problem	(LB, UB)	IATS	TS	GPSO	DS	MSCGA
01a	(2 505, 2 530)	2 530	2 518	2 539	2 518	2 515
02a	(2 228, 2 244)	2 244	2 231	2 244	2 231	2 231
03a	(2 228, 2 235)	2 235	2 229	2 232	2 229	2 229
04a	(2 503, 2 565)	2 565	2 503	2 523	2 503	2 506
05a	(2 189, 2 229)	2 229	2 216	2 234	2 216	2 216
06a	(2 162, 2 216)	2 216	2 203	2 218	2 196	2 197
07a	(2 180, 2 408)	2 408	2 283	2 361	2 283	2 279
08a	(2 061, 2 093)	2 093	2 069	2 086	2 069	2 069
09a	(2 061, 2 074)	2 074	2 066	2 073	2 066	2 066
10a	(2 198, 2 362)	2 362	2 291	2 362	2 291	2 287
11a	(2 010, 2 078)	2 078	2 063	2 083	2 063	2 060
12a	(1 969, 2 047)	2 047	2 034	2 050	2 031	2 033
13a	(2 161, 2 302)	2 302	2 260	2 342	2 257	2 248
14a	(2 161, 2 183)	2 183	2 167	2 174	2 167	2 167
15a	(2 161, 2 171)	2 171	2 167	2 173	2 165	2 165
16a	(2 148, 2 301)	2 301	2 255	2 324	2 256	2 255
17a	(2 088, 2 168)	2 169	2 141	2 162	2 140	2 142
18a	(2 055, 2 139)	2 139	2 137	2 157	2 127	2 132

Problem	AIA	HHS	M2	MILP	MIG	MPGA-ER	MSCGA
SFJS01	66	66	66	66	66	66	66
SFJS02	107	107	107	107	107	107	107
SFJS03	221	221	221	221	221	221	221
SFJS04	355	355	355	355	355	355	355
SFJS05	119	119	119	119	119	119	119
SFJS06	320	320	320	320	320	320	320
SFJS07	397	397	397	397	397	397	397
SFJS08	253	253	253	253	253	253	253
SFJS09	210	210	210	210	210	210	210
SFJS10	516	516	516	516	516	516	516
MFJS01	468	468	468	468	462	468	468
MFJS02	448	446	446	446	446	446	446
MFJS03	468	466	466	466	450	466	466
MFJS04	554	554	564	554	554	554	554
MFJS05	527	514	514	514	514	514	514
MFJS06	635	634	634	634	634	634	634
MFJS07	879	879	928	879	881	879	879
MFJS08	884	884	/	/	889	884	884
MFJS09	1 088	1 055	/	/	1 059	/	1 055
MFJS10	1 267	1 196	/	/	1 214	/	1 196

Benchmark		MK data	Peres data	Fattahi data
Number of optimal solutions	MSCGA	9	13	18
Number of optimal solutions	Optimal comparison algorithm	9	12	16
Average error	MSCGA	0.147 3	0.019 1	—
Average error	Optimal comparison algorithm	0.151 0	0.019 3	—

Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 14

References 48

Related Articles 0

Recommended Articles

Metrics

Comments