基于改进飞蛾扑火算法的集成调度仿真

doi:10.16182/j.issn1004731x.joss.23-FZ0806

摘要/Abstract

摘要：

针对制造型企业成本上升等问题，建立生产与运输集成调度的数学规划模型，提出一种双自适应权重飞蛾扑火算法(double adaptive weights for moth flame optimizer，DAWMFO)进行求解。提出了一种双自适应权重机制；使用螺旋函数更新种群，提高了算法的收敛速度和精度。采用改进算法对基准函数进行了测试，结果表明：DAWMFO不仅能够快速收敛且不易陷入局部最优，寻优能力较其他算法也有所提升。通过对生产与运输集成调度的数据集做仿真实验，验证了改进算法在求解此类问题时可行高效。

关键词: 作业车间调度, 螺旋函数, 双自适应权重飞蛾扑火算法, 生产和运输, 集成调度

Abstract:

Aiming at the rising cost of manufacturing enterprises, a mathematical programming model of integrated scheduling of production and transportation is established, and a double adaptive weights for moth flame optimizer(DAWMFO) is proposed. A double adaptive weight mechanism is proposed. The spiral function is used to update the population, which improves the convergence speed and accuracy of the algorithm. The benchmark function is tested by the improved algorithm. The results show that the improved algorithm can converge quickly and not easily fall into local optimum. Compared with other algorithms, the optimization ability is also improved.Through the simulation experiment on the data set of integrated production and transportation scheduling, it is verified that the improved algorithm is feasible and efficient in solving such problems.

Key words: job shop scheduling, spiral function, double adaptive weights for moth flame optimizer, production and transportation, integrated scheduling

中图分类号:

TP391.9

张天瑞,牛慧媛,谢薇 . 基于改进飞蛾扑火算法的集成调度仿真[J]. 系统仿真学报, 2023, 35(10): 2170-2181.

Zhang Tianrui,Niu Huiyuan,Xie Wei . Integrated Scheduling Simulation Based on Improved Moth Flame Optimizer[J]. Journal of System Simulation, 2023, 35(10): 2170-2181.

图/表 11

图1

图2

图3

图4

表1

表2

图5

图6

表3

表4

表5

参考文献 20

1	Caldeira R H, Gnanavelbabu A, Vaidyanathan T. An Effective Backtracking Search Algorithm for Multi-objective Flexible Job Shop Scheduling Considering New Job Arrivals and Energy Consumption[J]. Computers & Industrial Engineering, 2020, 149: 106863.
2	Firat M, Julie De Meyere, Martagan T, et al. Optimizing the Workload of Production Units of a Make-to-order Manufacturing System[J]. Computers & Operations Research, 2022, 138: 105530.
3	陈魁, 毕利. 考虑运输时间的多目标柔性作业车间调度研究[J]. 小型微型计算机系统, 2021, 42(5): 946-952.
	Chen Kui, Bi Li. Research on Multi-objective Flexible Job Shop Scheduling Considering Transport Time[J]. Journal of Chinese Computer Systems, 2021, 42(5): 946-952.
4	Hidri L, Elkosantini S, Mabkhot M M. Exact and Heuristic Procedures for the Two-center Hybrid Flow Shop Scheduling Problem With Transportation Times[J]. IEEE Access, 2018, 6: 21788-21801.
5	Geismar H N, Laporte G, Lei Lei, et al. The Integrated Production and Transportation Scheduling Problem for a Product With a Short Lifespan[J]. INFORMS Journal on Computing, 2008, 20(1): 21-33.
6	Mohammadi S, Al-e-Hashem S M J M, Rekik Y. An Integrated Production Scheduling and Delivery Route Planning With Multi-purpose Machines: a Case Study From a Furniture Manufacturing Company[J]. International Journal of Production Economics, 2020, 219: 347-359.
7	Gharaei A, Jolai F. A Combinatorial Benders Cut for the Integrated Production Scheduling and Distribution Problem[J]. Journal of Quality Engineering and Production Optimization, 2020, 5(1): 1-18.
8	Moazami Goodarzi R, Ahmadizar F, Farughi H. Integrated Hybrid Flow Shop Scheduling and Vehicle Routing Problem[J]. Journal of Industrial and Systems Engineering, 2021, 13(2): 223-244.
9	梁春华, 周泓, 赵健. 一种求解供应链环境下生产-配送问题的集成优化方法[J]. 控制与决策, 2011, 26(1): 27-36.
	Liang Chunhua, Zhou Hong, Zhao Jian. Integrated Optimization Approach for Production-distribution Planning in Supply Chain[J]. Control and Decision, 2011, 26(1): 27-36.
10	刘玲, 李昆鹏, 刘志学. 生产和运输协同调度问题的模型和算法[J]. 工业工程与管理, 2016, 21(2): 86-91.
	Liu Ling, Li Kunpeng, Liu Zhixue. Model and Algorithms for the Integrated Production and Transportation Scheduling[J]. Industrial Engineering and Management, 2016, 21(2): 86-91.
11	霍思云. 差异容量平行机环境下生产与运输集成调度算法研究[D]. 合肥: 安徽大学, 2019.
	Huo Siyun. Research on Algorithm for Integrated Scheduling of Production and Transportation on Parallei Machines With Non-identical Capacities[D]. Hefei: Anhui University, 2019.
12	吴倩云, 谢乃明, 邵雨婷. 考虑时间窗和装载约束的装配线集成物流调度[J]. 计算机集成制造系统, 2020, 26(3): 806-814.
	Wu Qianyun, Xie Naiming, Shao Yuting. Integrated Logistics Scheduling of Assembly Lines With Time Windows and Loading Constraints[J]. Computer Integrated Manufacturing Systems, 2020, 26(3): 806-814.
13	Mirjalili S. Moth-flame Optimization Algorithm: a Novel Nature-inspired Heuristic Paradigm[J]. Knowledge-Based Systems, 2015, 89: 228-249.
14	李志明, 莫愿斌. 基于Lévy飞行的飞蛾扑火优化算法[J]. 计算机工程与设计, 2017, 38(3): 807-813.
	Li Zhiming, Mo Yuanbin. Moth-flame Optimization Algorithm Based on Lévy Flights[J]. Computer Engineering and Design, 2017, 38(3): 807-813.
15	李唐兵, 胡锦泓, 周求宽. 基于Lévy飞行的改进飞蛾扑火算法优化红外图像分割[J]. 红外技术, 2020, 42(9): 846-854.
	Li Tangbing, Hu Jinhong, Zhou Qiukuan. Improved Moth-flame Optimization Algorithm Based on Lévy Flight to Optimize Infrared Image Segmentation[J]. Infrared Technology, 2020, 42(9): 846-854.
16	Zhang Zhendong, Qin Hui, Yao Liqiang, et al. Improved Multi-objective Moth-flame Optimization Algorithm Based on R-domination for Cascade Reservoirs Operation[J]. Journal of Hydrology, 2020, 581: 124431.
17	Zhao Huiru, Zhao Haoran, Guo Sen. Using GM (1,1) Optimized by MFO With Rolling Mechanism to Forecast the Electricity Consumption of Inner Mongolia[J]. Applied Sciences, 2016, 6(1): 20.
18	Mirjalili S. SCA: A Sine Cosine Algorithm for Solving Optimization Problems[J]. Knowledge-Based Systems, 2016, 96: 120-133.
19	Yang Xinshe. Firefly Algorithms for Multimodal Optimization[M]//Watanabe O, Zeugmann T. Stochastic Algorithms: Foundations and Applications. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009: 169-178.
20	王彤. 低碳经济下考虑配送时间需求的生产调度优化研究[D]. 重庆: 重庆大学, 2019.
	Wang Tong. Study on Production Scheduling Optimization Considering Delivery Time Demand in Low Carbon Economy[D]. Chongqing: Chongqing University, 2019.

函数	DAWMFO		MFO		SCA		FA
函数	均值	标准差	均值	标准差	均值	标准差	均值	标准差
F1	1.2E+04	1.1E+04	4.2E+10	2.4E+10	1.2E+10	2.0E+09	1.4E+10	1.5E+09
F2	1.8E+90	1.0E+91	1.8E+172	6.6E+04	1.9E+35	6.7E+34	1.0E+34	1.6E+40
F3	1.5E+05	1.6E+04	5.4E+05	1.9E+05	3.7E+04	6.3E+03	6.0E+04	1.1E+04
F4	6.7E+02	4.4E+01	2.5E+04	1.2E+04	1.4E+03	2.3E+02	1.4E+03	9.7E+01
F5	1.6E+03	2.4E+02	1.8E+03	1.4E+02	7.8E+02	1.9E+01	7.6E+02	1.2E+01

机器	FT1	FT2	FT3	FT4	FT5	FT6	机器	FT1	FT2	FT3	FT4	FT5	FT6
M1	140.97	200.47	247.31	276.37	316.67	367.45	M4	179.23	215.23	297.36	314.03	343.17	395.14
M2	74.00	125.00	164.00	245.27	317.56	362.63	M5	29.00	102.45	152.32	243.68	321.37	398.46
M3	43.00	79.00	140.38	226.23	268.23	409.14	M6	60.00	87.77	155.77	221.76	195.76	280.43

机器	工序	完工时间	工序	完工时间	工序	完工时间	工序	完工时间	工序	完工时间	工序	完工时间
M1	4-3	140.97	6-3	200.47	2-4	247.31	1-5	276.37	5-5	316.67	3-5	367.45
M2	4-1	74.00	6-1	125.00	1-2	164.00	5-3	245.27	3-4	317.56	2-6	362.63
M3	1-1	43.00	5-1	79.00	3-3	140.38	4-5	226.23	6-4	268.23	2-5	409.14
M4	4-4	179.23	2-3	215.23	5-4	297.36	1-6	314.03	6-6	343.17	3-6	395.14
M5	2-1	29.00	3-2	102.45	6-2	152.32	1-4	243.68	4-6	321.37	5-6	398.46
M6	3-1	60.00	4-2	87.77	2-2	155.77	1-3	221.76	5-2	195.76	6-5	280.43

机器	工序	实际完工时间/min	距离/km	客户需求产品时间				偏差/min
机器	工序	实际完工时间/min	距离/km	提前惩罚时间/min	延迟惩罚时间/min	Dm/min	Dn/min	偏差/min
M1	1-6	314.03	30.41	345.35	375.35	350.35	370.35	0.91
M2	2-6	409.14	21.24	395.40	435.40	400.40	430.40	0
M3	3-6	395.14	44.72	365.20	405.20	370.20	400.20	-34.66
M4	4-6	321.37	8.21	305.00	335.00	310.00	330.00	0
M5	5-6	398.46	33.97	385.50	445.50	390.50	435.50	0
M6	6-6	343.17	36.72	325.57	385.57	330.57	380.57	0

成本项目	未考虑运输时间成本/元	考虑运输时间成本/元	优化率/%
合计	1 269.18	1 070.15	15.68
运输	255.21	246.31	3.49
惩罚	343.13	153.00	55.41
生产	670.84	670.84	0