基于改进候鸟迁徙优化的多目标批量流混合流水车间调度

doi:10.16183/j.cnki.jsjtu.2020.435

摘要/Abstract

摘要：

针对2+1+1型混合流水车间,研究了多目标不相等批量流混合流水车间调度问题,提出一种基于变邻域搜索的自适应候鸟迁徙优化(AMBO)算法,实现了最小化完工时间与最小平均在制品数量的多目标优化.相比原始候鸟迁徙算法,AMBO算法引入变邻域搜索策略,实现每个算子的权重随迭代次数自适应调整,并提出了时间窗算子,以提升交换算子搜索性能和收敛速度.对随机生成不同规模的订单进行算例研究,结果表明AMBO算法比候鸟迁徙优化算法、遗传算法具有更高的求解质量和收敛性能,从而验证了AMBO算法的有效性.

关键词: 批量流问题, 混合流水车间调度问题, 变邻域搜索, 自适应候鸟迁徙优化, 时间窗算子

Abstract:

This paper proposes an adaptive migrating birds optimization (AMBO) method based on variable neighborhood search to solve the inequal lot streaming hybrid flowshop scheduling problem (ILS-HFSP) for a 2+1+1 hybrid flowshop, which realizes multi-objective optimization of minimizing makespan and minimum average work in process. Compared with the original migrating birds optimization, the AMBO algorithm adopts the variable neighborhood search strategy with an adaptive selection probability of neighborhood operator that is adaptively adjusted with the number of iterations. Besides, a time-window operator is adopted to improve the search performance of exchange operators and convergence rate. Several orders of different scales generated randomly are studied, and the results show that the AMBO algorithm has a higher solution quality and a better convergence performance than the migrating birds optimization algorithm and the genetic algorithm, thereby verifying the effectiveness of the AMBO algorithm.

Key words: lot streaming problem, hybrid flowshop scheduling problem, variable neighborhood search, adaptive migrating birds optimization (AMBO), time window operation

中图分类号:

TH166

汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.

TANG Hongtao, WANG Dannan, SHAO Yiping, ZHAO Wenbin, JIANG Weiguang, CHEN Qingfeng. 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.

图/表 15

图1

图2

图3

图4

图5

表1

表2

图6

表3

图7

表4

表5

表6

表7

当ρ=10,20,30时,GA、MBO与AMBO算法RPI值比较

任务规模	算法	ρ=10		ρ=20		ρ=30
任务规模	算法	$x -$ /%	s	$x -$ /%	s	$x -$ /%	s
60	GA	5.78	4.78	8.15	4.32	13.01	3.81
	MBO	12.21	3.79	11.06	3.64	8.70	3.43
	AMBO	3.37	2.78	2.84	2.57	2.61	2.44
80	GA	3.73	5.24	7.27	4.71	11.42	4.29
	MBO	11.93	4.13	10.38	3.81	7.94	3.72
	AMBO	3.54	3.11	3.13	2.79	2.89	2.58
100	GA	2.41	5.67	5.61	5.12	7.56	4.52
	MBO	12.71	4.85	10.47	4.45	7.46	4.23
	AMBO	5.74	3.43	3.74	3.12	3.31	2.88

表7

表8

参考文献 24

[1]	周炳海, 刘文龙. 考虑能耗和准时的混合流水线多目标调度[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.
[2]	ZHOU X J, YU M Q. Semi-dynamic maintenance scheduling for multi-station series systems in multi-specification and small-batch production[J]. Reliability Engineering & System Safety, 2020, 195:106753. doi: 10.1016/j.ress.2019.106753 URL
[3]	陶辛阳, 夏唐斌, 奚立峰. 基于健康指数的预防性维护与多目标生产调度联合优化建模[J]. 上海交通大学学报, 2014, 48(8):1170-1174.
	TAO Xinyang, XIA Tangbin, XI Lifeng. Health-index-based joint optimization of preventive maintenance and multi-attribute production scheduling[J]. Journal of Shanghai Jiao Tong University, 2014, 48(8):1170-1174.
[4]	李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程, 2020, 31(23):2798-2813.
	LI Yingli, LI Xinyu, GAO Liang. Review on hybrid flow shop scheduling problems[J]. China Mechanical Engineering, 2020, 31(23):2798-2813.
[5]	ZHANG B, PAN Q K, GAO L, et al. An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming[J]. Applied Soft Computing, 2017, 52:14-27. doi: 10.1016/j.asoc.2016.12.021 URL
[6]	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
[7]	ZHANG M, TAN Y T, 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[J]. Simulation Modelling Practice and Theory, 2020, 100:102065. doi: 10.1016/j.simpat.2019.102065 URL
[8]	NADERI B, YAZDANI M. A model and imperialist competitive algorithm for hybrid flow shops with sublots and setup times[J]. Journal of Manufacturing Systems, 2014, 33(4):647-653. doi: 10.1016/j.jmsy.2014.06.002 URL
[9]	LALITHA J L, MOHAN N R, PILLAI V M. Lot streaming in [N-1](1)+N(m) hybrid flow shop[J]. Journal of Manufacturing Systems, 2017, 44:12-21. doi: 10.1016/j.jmsy.2017.04.018 URL
[10]	李航, 章旸, 叶鸿庆, 等. 考虑批量流与换模时间的柔性生产线调度方法研究[J]. 工业工程与管理, 2020, 25(3):179-187.
	LI Hang, ZHANG Yang, YE Hongqing, et al. Research on flexible production line scheduling with lot streaming and setup times[J]. Industrial Engineering and Management, 2020, 25(3):179-187.
[11]	ZHANG B, PAN Q K, GAO L, et al. A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problem[J]. Soft Computing, 2019, 23(17):8101-8129. doi: 10.1007/s00500-018-3447-8 URL
[12]	LI J Q, TAO X R, JIA B X, et al. Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots[J]. Swarm and Evolutionary Computation, 2020, 52:100600. doi: 10.1016/j.swevo.2019.100600 URL
[13]	GONG D W, HAN Y Y, SUN J Y. A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems[J]. Knowledge-Based Systems, 2018, 148:115-130. doi: 10.1016/j.knosys.2018.02.029 URL
[14]	沈倩, 管在林, 张正敏, 等. 面向卷烟生产调度的集成产能过滤算法与仿真技术的优化框架[DB/OL].(2020 -10-26)[2021-02-07]. https://kns.cnki.net/kcms/detail/11.5946.TP.20201026.1016.012.html.
	SHEN Qian, GUAN Zailin, ZHANG Zhengmin,, et al. An optimization framework based on simulation integrated capacity filtering algorithm for cigarette production scheduling[DB/OL].(2020 -10-26)[2021-02-07]. https://kns.cnki.net/kcms/detail/11.5946.TP.20201026.1016.012.html.
[15]	吕洁, 郭婷芳, 韩文民. 虚拟制造单元瓶颈缓冲区容量优化[J]. 组合机床与自动化加工技术, 2016(12):121-124.
	LV Jie, GUO Tingfang, HAN Wenmin. Bottleneck buffer allocation optimization of the virtual manufacturing[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2016(12):121-124.
[16]	ENGEHAUSEN F, LÖDDING H. Managing sequence-dependent setup times—The target conflict between output rate, WIP and fluctuating throughput times for setup cycles[J]. Production Planning & Control, 2020: 1-17.
[17]	DUMAN E, UYSAL M, ALKAYA A F. Migrating birds optimization: A new metaheuristic approach and its performance on quadratic assignment problem[J]. Information Sciences, 2012, 217:65-77. doi: 10.1016/j.ins.2012.06.032 URL
[18]	DINDAR O Z. An improvement on the migrating birds optimization with a problem-specific neighboring function for the multi-objective task allocation problem[J]. Expert Systems With Applications, 2017, 67:304-311. doi: 10.1016/j.eswa.2016.09.035 URL
[19]	EXPOSITO IZQUIERDO C, DE ARMAS J, LALLA RUIZ E. Multi-leader migrating birds optimization: A novel nature-inspired metaheuristic for combinatorial problems[J]. International Journal of Bio-Inspired Computation, 2017, 10(4):1.
[20]	ALMONACID B, SOTO R, CRAWFORD B. Comparing three simple ways of generating neighboring solutions when solving the cell formation problem using two versions of migrating birds optimization [C]//2017 17th International Conference on Computational Science and Its Applications (ICCSA) . Piscataway, NJ, USA: IEEE, 2017: 1-9.
[21]	TONGUR V, ÜLKER E. The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem[C]//The 19th Asia Pacific Symposium. Bangkok, Thailand: Springer, 2015: 1-11.
[22]	ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4):455-472. doi: 10.1287/trsc.1050.0135 URL
[23]	姚妮. 混合候鸟迁徙优化算法求解柔性作业车间调度问题[J]. 华中师范大学学报(自然科学版), 2016, 50(1):38-42.
	YAO Ni. Hybrid migrating brids optimization algorithm for the flexible job shop scheduling problem[J]. Journal of Central China Normal University (Natural Sciences), 2016, 50(1):38-42.
[24]	唐立力. 求解低碳调度问题的改进型候鸟优化算法[J]. 计算机工程与应用, 2016, 52(17):166-171.
	TANG Lili. Improved migrating birds optimization algorithm to solve low-carbon scheduling problem[J]. Computer Engineering and Applications, 2016, 52(17):166-171.

产品数量范围	订单数比例/%	产品总数比例/%
1×10³~3×10³	80	50
3×10³~1×10⁴	15	30
1×10⁴~2×10⁴	5	20

水平	α	ω	m	g
1	0.08283	0.08393	0.08437	0.0818
2	0.08163	0.0813	0.08367	0.08533
3	0.08837	0.0876	0.0848	0.0857
Δ	0.00673	0.0063	0.00113	0.0039
排序	1	2	4	3

序号	AMBO		MBO		GA
序号	最优解均值	标准偏差	最优解均值	标准偏差	最优解均值	标准偏差
1	0.0649	0.00384	0.0653	0.00404	0.0664	0.00684
2	0.0625	0.00335	0.0626	0.00334	0.0642	0.00759
3	0.0683	0.00354	0.0726	0.00369	0.0764	0.00795
4	0.0686	0.00284	0.0784	0.00365	0.0814	0.00718
5	0.0748	0.00321	0.0765	0.00364	0.0787	0.00768
6	0.0646	0.00322	0.0795	0.00342	0.0834	0.00747
7	0.0706	0.00317	0.0796	0.00391	0.0777	0.00734
8	0.0715	0.00336	0.0771	0.00387	0.0804	0.00847
9	0.0673	0.00341	0.0715	0.00405	0.0761	0.00757
10	0.0711	0.00371	0.0826	0.00367	0.0817	0.00754
11	0.0621	0.00315	0.0645	0.00378	0.0794	0.00781
12	0.0733	0.00344	0.0799	0.00363	0.0844	0.00759
13	0.0875	0.00334	0.0884	0.00413	0.0919	0.00763
15	0.0865	0.00325	0.0886	0.00357	0.0884	0.00804
14	0.0686	0.00311	0.0726	0.00398	0.0757	0.00725
16	0.0639	0.00324	0.0709	0.00338	0.0704	0.00737
17	0.0716	0.00315	0.0719	0.00401	0.0717	0.00794
18	0.0639	0.00341	0.0656	0.00387	0.0732	0.00781
19	0.0723	0.00331	0.0695	0.00348	0.0774	0.00765
20	0.0633	0.00345	0.0644	0.00367	0.0706	0.00742
21	0.0643	0.00344	0.0684	0.00379	0.0704	0.00806
22	0.0659	0.00339	0.0724	0.00344	0.0722	0.00774
23	0.0665	0.00338	0.0726	0.00404	0.0719	0.00735
24	0.0649	0.00326	0.0686	0.00367	0.0704	0.00784
25	0.0685	0.00328	0.0699	0.00421	0.0717	0.00785
26	0.0696	0.00285	0.0699	0.00368	0.0707	0.00752
27	0.0724	0.00324	0.0726	0.00354	0.0731	0.00728
28	0.0624	0.00337	0.0679	0.00364	0.0695	0.00838
29	0.0688	0.00315	0.0695	0.00392	0.0714	0.00763
30	0.0691	0.00308	0.0719	0.00390	0.0737	0.00734
均值	0.0690	0.00330	0.0731	0.00375	0.0758	0.00764

算法	最优解均值	解的标准偏差	平均收敛迭代次数	算法平均运行时间/s
GA	0.0758	0.00764	88	263.13
MBO	0.0731	0.00375	76	335.24
AMBO	0.0690	0.00330	56	358.12

任务规模	算法	最优解均值	解的标准偏差	平均收敛迭代次数/次	算法平均收敛时间/s
30	GA	0.0771	0.00798	128	362.24
	MBO	0.0748	0.00384	112	466.25
	AMBO	0.0706	0.00376	87	493.46
40	GA	0.0778	0.00784	167	560.32
	MBO	0.0752	0.00391	154	650.21
	AMBO	0.0714	0.00364	125	708.72
50	GA	0.0806	0.00814	205	780.32
	MBO	0.0766	0.00414	179	920.31
	AMBO	0.0721	0.00385	162	994.63