An Improved Multi-Swarm Migrating Birds Optimization Algorithm for Hybrid Flow Shop Scheduling

doi:10.16183/j.cnki.jsjtu.2022.242

Abstract

Abstract:

An improved multi-swarm migrating birds optimization (IMMBO) algorithm is proposed for hybrid flow shop scheduling with sequence-dependent setup times (HFS-SDST), to minimize the total maximum completion time (i.e., makespan). Permutation-based encoding is adopted to substitute the individual. The modified Nawaz-Enscore-Ham (MNEH) algorithm is employed to generate initial population which are assigned to each sub-swarm according to the makespan. For each sub-swarm, the neighborhood individuals of the leader and followers are generated respectively by performing serial and parallel neighborhood strategies. If the follower is better than the leader according to their makespan, they are exchanged to ensure the information interaction of individuals within the sub-swarm. Moreover, the discrete whale optimization strategy is embedded in IMMBO to optimize the leaders of all sub-swarms to enhance the interaction among them. Furthermore, the local search is designed for the optimal individual to further improve the local search ability of the algorithm. Meanwhile, to avoid algorithm premature convergence, the control strategy for population diversification is designed to the leader of each sub-swarm. Finally, based on adjusting the algorithm parameters experimentally, simulation experiments are conducted on four variants of IMMBO to verify the function of each part by testing an adaptation dataset of Ta. Moreover, the IMMBO is compared with three existing algorithms by testing an adaptation dataset of Ta, and the experimental results demonstrate the effectiveness of the IMMBO algorithm to solve the hybrid flow shop scheduling problem.

Key words: hybrid flow shop scheduling (HFS) problem, improved multi-swarm migrating birds optimization (IMMBO), information interaction among multi-swarm, parallel neighborhood, serial neighborhood

CLC Number:

TP278

ZHANG Sujun, YANG Wenqiang, GU Xingsheng. An Improved Multi-Swarm Migrating Birds Optimization Algorithm for Hybrid Flow Shop Scheduling[J]. Journal of Shanghai Jiao Tong University, 2023, 57(10): 1378-1388.

Figures/Tables 13

Fig.1

Fig.2

Fig.3

Fig.4

Tab.1

Tab.2

Tab.3

Fig.5

Tab.4

Tab.5

Tab.6

Fig.6

Fig.7

References 24

[1]	ZANDIEH M, FATEMI GHOMI S M T, MOATTAR HUSSEINI S M. An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times[J]. Applied Mathematics and Computation, 2006, 180(1): 111-127. doi: 10.1016/j.amc.2005.11.136 URL
[2]	李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程, 2020, 31(23): 2798-2813. doi: 10.3969/j.issn.1004-132X.2020.23.004
	LI Yingli, LI Xinyu, GAO Liang. Review on hybrid flow shop scheduling problems[J]. China Mechanical Engineering, 2020, 31(23): 2798-2813. doi: 10.3969/j.issn.1004-132X.2020.23.004
[3]	SIOUD A, GAGNÉ C. Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times[J]. European Journal of Operational Research, 2018, 264(1): 66-73. doi: 10.1016/j.ejor.2017.06.027 URL
[4]	李俊青, 李文涵, 陶昕瑞, 等. 时间约束混合流水车间调度问题综述[J]. 控制理论与应用, 2020, 37(11): 2273-2290.
	LI Junqing, LI Wenhan, TAO Xinrui, et al. A survey on time constrained hybrid flow shop scheduling problems[J]. Control Theory & Applications, 2020, 37(11): 2273-2290.
[5]	NADERI B, ZANDIEH M, ROSHANAEI V. Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness[J]. The International Journal of Advanced Manufacturing Technology, 2009, 41(11/12): 1186-1198. doi: 10.1007/s00170-008-1569-3 URL
[6]	MOCCELLIN J V, NAGANO M S, PITOMBEIRA NETO A R, et al. Heuristic algorithms for scheduling hybrid flow shops with machine blocking and setup times[J]. Journal of the Brazilian Society of Mechanical Sciences and Engineering, 2018, 40(2): 1-11. doi: 10.1007/s40430-017-0921-7 URL
[7]	BURCIN OZSOYDAN F, SAĞIR M. Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: A case study at a manufacturing plant[J]. Computers & Operations Research, 2021, 125: 105044. doi: 10.1016/j.cor.2020.105044 URL
[8]	周炳海, 刘文龙. 考虑能耗和准时的混合流水线多目标调度[J]. 上海交通大学学报, 2019, 53(7): 773-779.
	ZHOU Binghai, LIU Wenlong. Multi-objective hybrid flow-shop scheduling problem considering energy consumption and on-time delivery[J]. Journal of Shanghai Jiao Tong University, 2019, 53(7): 773-779.
[9]	GÓMEZ-GASQUET P, ANDRÉS C, LARIO F C. An agent-based genetic algorithm for hybrid flowshops with sequence dependent setup times to minimise makespan[J]. Expert Systems With Applications, 2012, 39(9): 8095-8107. doi: 10.1016/j.eswa.2012.01.158 URL
[10]	PAN Q K, GAO L, LI X Y, et al. Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times[J]. Applied Mathematics and Computation, 2017, 303: 89-112. doi: 10.1016/j.amc.2017.01.004 URL
[11]	TIAN H X, LI K, LIU W. A Pareto-based adaptive variable neighborhood search for biobjective hybrid flow shop scheduling problem with sequence-dependent setup time[J]. Mathematical Problems in Engineering, 2016, 2016: 1257060.
[12]	KHARE A, AGRAWAL S. Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness[J]. Computers & Industrial Engineering, 2019, 135: 780-792. doi: 10.1016/j.cie.2019.06.057 URL
[13]	DUMAN E, UVSAL M, ALKAVA A F. Migrating birds optimization: a new metaheuristic approach and its performance on quadratic assignment problem[J]. Information Sciences, 2012, 217(24): 65-77. doi: 10.1016/j.ins.2012.06.032 URL
[14]	PAN Q K, DONG Y. An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation[J]. Information Sciences, 2014, 277: 643-655. doi: 10.1016/j.ins.2014.02.152 URL
[15]	HAN D Y, TANG Q H, ZHANG Z K, et al. An improved migrating birds optimization algorithm for a hybrid flow shop scheduling within steel plants[J]. Mathematics, 2020, 8(10): 1661. doi: 10.3390/math8101661 URL
[16]	MENG T, PAN Q K, LI J Q, et al. An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem[J]. Swarm and Evolutionary Computation, 2018, 38: 64-78. doi: 10.1016/j.swevo.2017.06.003 URL
[17]	汤洪涛, 王丹南, 邵益平, 等. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.
	TANG Hongtao, WANG Dannan, SHAO Yiping, et al. A modified migrating birds optimization for multi-objective lot streaming hybrid flowshop scheduling[J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213.
[18]	BÁEZ S, ANGEL-BELLO F, ALVAREZ A, et al. A hybrid metaheuristic algorithm for a parallel machine scheduling problem with dependent setup times[J]. Computers & Industrial Engineering, 2019, 131: 295-305. doi: 10.1016/j.cie.2019.03.051 URL
[19]	HAN Y X, GU X S. Improved multipopulation discrete differential evolution algorithm for the scheduling of multipurpose batch plants[J]. Industrial & Engineering Chemistry Research, 2021, 60(15): 5530-5547. doi: 10.1021/acs.iecr.0c06041 URL
[20]	GAO L, PAN Q K. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem[J]. Information Sciences, 2016, 372: 655-676. doi: 10.1016/j.ins.2016.08.046 URL
[21]	TONGUR V, ÜLKER E. PSO-based improved multi-flocks migrating birds optimization (IMFMBO) algorithm for solution of discrete problems[J]. Soft Computing, 2019, 23(14): 5469-5484. doi: 10.1007/s00500-018-3199-5
[22]	RUIZ R, STÜTZLE T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2007, 177(3): 2033-2049. doi: 10.1016/j.ejor.2005.12.009 URL
[23]	MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67. doi: 10.1016/j.advengsoft.2016.01.008 URL
[24]	VALLADA E, RUIZ R, MAROTO C. Synthetic and real benchmarks for complex flow-shops problems[R]. Valencia, Spain:Universitat Politécnica de València, 2003.

序号	N_p	G	a_limit	d	t_max	平均值
1	11(1)	2(1)	20(1)	3(1)	300(1)	3929.29
2	11(1)	3(2)	30(2)	4(2)	400(2)	3909.13
3	11(1)	4(3)	40(3)	5(3)	500(3)	3926.50
4	11(1)	5(4)	50(4)	6(4)	600(4)	3911.50
5	13(2)	2(1)	30(2)	5(3)	600(4)	3915.21
6	13(2)	3(2)	20(1)	6(4)	500(3)	3901.25
7	13(2)	4(3)	50(4)	3(1)	400(2)	3938.75
8	13(2)	5(4)	40(3)	4(2)	300(1)	3925.88
9	15(3)	2(1)	40(3)	6(4)	400(2)	3928.04
10	15(3)	3(2)	50(4)	5(3)	300(1)	3912.08
11	15(3)	4(3)	20(1)	4(2)	600(4)	3892.96
12	15(3)	5(4)	30(2)	3(1)	500(3)	3915.92
13	17(4)	2(1)	50(4)	4(2)	500(3)	3928.29
14	17(4)	3(2)	40(3)	3(1)	600(4)	3920.92
15	17(4)	4(3)	30(2)	6(4)	300(1)	3914.88
16	17(4)	5(4)	20(1)	5(3)	400(2)	3891.58

水平	N_p	G	a_limit	d	t_max
1	3919.1	3925.21	3903.77	3926.22	3920.53
2	3920.27	3910.84	3913.78	3914.06	3916.88
3	3912.25	3918.27	3925.33	3911.34	3917.99
4	3913.92	3911.22	3922.66	3913.92	3910.15
SD	3.38	5.89	8.45	5.78	3.84
排序	5	2	1	3	4

算法	SSD10_ P3_50	SSD50_ P3_50	SSD100_ P3_50	SSD125_ P3_50
IMMBO_NDC	1511.98	1994.43	2584.83	2871.30
IMMBO_NDWOA	1502.53	1973.93	2553.50	2848.08
IMMBO_NLS	1495.90	1965.15	2536.13	2824.58
IMMBO_NR	1511.20	1992.33	2581.05	2875.90

算法	P13				P3
算法	SSD10_ P13_50	SSD50_ P13_50	SSD100_ P13_50	SSD125_ P13_50	SSD10_ P3_50	SSD50_ P3_50	SSD100_ P3_50	SSD125_ P3_50
ILS_MRLS	2860.13	3887.24	5058.04	5605.45	1163.29	1616.35	2125.87	2389.60
IMBO	2891.37	3882.24	5094.32	5646.12	1178.13	1611.34	2124.73	2390.25
DABC	2857.31	3981.69	5082.48	5627.08	1173.28	1607.95	2113.76	2354.56
IMMBO	2834.60	3856.52	5000.99	5526.81	1110.60	1498.79	1955.79	2170.61

算例	算法	P3
算例	算法	SSD10_P3_50	SSD50_P3_50	SSD100_P3_50	SSD125_P3_50
Ta32	ILS_MRLS	2033.51	1995.49	2015.03	1920.50
	IMBO	1093.25	1099.30	1097.90	1099.67
	DABC	108.93	108.25	108.34	108.14
	IMMBO	3173.05	3134.05	3148.59	3132.99
Ta34	ILS_MRLS	2102.98	1911.52	2009.56	2056.72
	IMBO	1086.26	1097.10	1095.33	1089.54
	DABC	109.96	107.98	108.21	107.21
	IMMBO	3160.43	3143.98	3147.07	3129.43