基于改进多种群候鸟迁徙算法的混合流水车间调度

doi:10.16183/j.cnki.jsjtu.2022.242

上海交通大学学报 ›› 2023, Vol. 57 ›› Issue (10): 1378-1388.doi: 10.16183/j.cnki.jsjtu.2022.242

所属专题：《上海交通大学学报》2023年“机械与动力工程”专题

• 机械与动力工程 • 上一篇

基于改进多种群候鸟迁徙算法的混合流水车间调度

张素君¹, 杨文强¹, 顾幸生²()

1.河南科技学院机电学院, 河南新乡 453003
2.华东理工大学能源化工过程智能制造教育部重点实验室, 上海 200237

收稿日期:2022-06-27 修回日期:2022-07-24 接受日期:2022-07-27 出版日期:2023-10-28 发布日期:2023-10-31
通讯作者: 顾幸生 E-mail:xsgu@ecust.edu.cn.
作者简介:张素君(1978-),讲师,从事生产调度与智能优化算法研究.
基金资助:
国家自然科学基金(61973120);国家自然科学基金(61973209);资助项目,河南省科技攻关(202102110282);资助项目,河南省科技攻关(222102110095)

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

ZHANG Sujun¹, YANG Wenqiang¹, GU Xingsheng²()

1. School of Mechanical and Electrical Engineering, Henan Institute of Science and Technology, Xinxiang 453003, Henan, China
2. Key Laboratory of Advanced Control and Optimization for Chemical Process of the Ministry of Education, East China University of Science and Technology, Shanghai 200237, China

Received:2022-06-27 Revised:2022-07-24 Accepted:2022-07-27 Online:2023-10-28 Published:2023-10-31
Contact: GU Xingsheng E-mail:xsgu@ecust.edu.cn.

摘要/Abstract

摘要：

针对带顺序依赖准备时间的混合流水车间调度(HFS-SDST)问题,以最小化总最大作业完成时间为调度目标,提出一种改进多种群候鸟迁徙优化(IMMBO)算法.算法中个体基于工件加工顺序进行编码,用改进的NEH(MNEH)算法产生初始种群,并按照适应度值分配到各子种群.子种群中领飞鸟和跟飞鸟分别利用串行和并行邻域策略产生邻域个体,如果跟飞鸟优于领飞鸟,二者互换,完成种群内部个体的信息交互;在IMMBO算法中嵌入离散鲸鱼优化策略对各子种群的领飞鸟进行优化,实现子种群之间信息交互;为提高算法的局部搜索(LS)能力,对种群中最优个体执行LS,同时,为了避免算法早熟收敛,针对每个种群的领飞鸟设计了种群多样化控制策略.最后,在实验法调整算法参数的基础上,对IMMBO的4个变体进行了仿真实验,通过测试Ta自适应算例验证IMMBO算法各部分的作用;将IMMBO算法与现有3个算法测试Ta自适应算例,进行实验结果比较,证明了IMMBO算法求解混合车间调度问题的有效性.

关键词: 混合流水车间调度, 改进多种群候鸟迁徙优化, 子种群信息交互, 串行邻域, 并行邻域

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

中图分类号:

TP278

张素君, 杨文强, 顾幸生. 基于改进多种群候鸟迁徙算法的混合流水车间调度[J]. 上海交通大学学报, 2023, 57(10): 1378-1388.

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.

图/表 13

图1

图2

图3

图4

表1

表2

表3

图5

表4

表5

表6

图6

图7

参考文献 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

基于改进多种群候鸟迁徙算法的混合流水车间调度

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 24

相关文章 1

编辑推荐

Metrics

本文评价

水平	N_p	G	a_limit	d	t_max
1	11	2	20	3	300
2	13	3	30	4	400
3	15	4	40	5	500
4	17	5	50	6	600