基于Pareto改进VNS-MMAS的定点修理任务多目标动态调度

doi:10.3969/j.issn.1001-506X.2020.02.14

摘要/Abstract

摘要：

针对战时定点修理任务重、修理时间有限、约束复杂的问题,进行了面向定点修理的战时装备维修任务多目标动态调度研究。提出了战时定点修理装备维修任务调度军事问题,考虑修理时间窗、非遍历性等约束,构建了战时装备维修任务多目标动态调度模型。采取分步求解思路处理修理小组分配以及修理任务排序两阶段优化问题,并从状态转移规则、信息素更新规则、先验信息获取3个方面对最大最小蚂蚁系统(max-min ant system, MMAS)算法进行改进,结合变邻域搜索(variable neighborhood search, VNS)算法增强算法的局部搜索能力,设计了基于Pareto改进VNS-MMAS算法实现模型求解,并通过示例仿真验证了模型及算法的科学性与有效性。

关键词: 定点修理, 多目标, 动态调度, 修理时间窗

Abstract:

To deal with the problem of heavy repair tasks, limited repair time and complicated constraints in wartime, the multi-objective dynamic scheduling of the wartime equipment maintenance tasks for fixed-point repairing is studied. The military problem of wartime fixed-point repairing maintenance task scheduling is proposed. Considering the constraints of repair time window and non-traversal, a multi-objective dynamic scheduling model of the wartime equipment maintenance task is constructed. The step-by-step solution is adopted to deal with the two-stage optimization problem of repair team allocation and repair task sorting. The max-min ant system (MMAS) algorithm is improved from three aspects: state transition rule, pheromone update rule and a priori information acquisition. The local search of the variable neighborhood search (VNS) algorithm is combined with the enhanced algorithm. Based on the ability, the model solving algorithm based on Pareto improved VNS-MMAS is designed. Through example simulation and analysis, the rationality and effectiveness of the model and the algorithm are verified.

Key words: fixed-point repairing, multi-objective, dynamic scheduling, repair time window

中图分类号:

E917

刘彦, 陈春良, 陈伟龙, 郭一鸣. 基于Pareto改进VNS-MMAS的定点修理任务多目标动态调度[J]. 系统工程与电子技术, 2020, 42(2): 356-364.

Yan LIU, Chunliang CHEN, Weilong CHEN, Yiming GUO. Multi-objective dynamic scheduling of fixed-point repairing tasksbased on Pareto improved VNS-MMAS[J]. Systems Engineering and Electronics, 2020, 42(2): 356-364.

图/表 3

表1

表2

图1

参考文献 21

1	昝翔, 陈春良, 张仕新, 等. 多约束条件下战时装备维修任务分配方法[J]. 兵工学报, 2017, 38 (8): 1603- 1609. doi: 10.3969/j.issn.1000-1093.2017.08.019
	ZAN X , CHEN C L , ZHANG S X , et al. Task allocation method for wartime equipment maintenance under multiple constraint conditions[J]. Acta Armamentarii, 2017, 38 (8): 1603- 1609. doi: 10.3969/j.issn.1000-1093.2017.08.019
2	陈伟龙, 陈春良, 史宪铭, 等. 基于变体GA的进攻作战抢修任务动态调度[J]. 系统工程与电子技术, 2017, 39 (3): 577- 583.
	CHEN W L , CHEN C L , SHI X M , et al. Dynamic scheduling of battlefield rush-repair tasks in the offensive operation based on variant GA[J]. Systems Engineering and Electronic, 2017, 39 (3): 577- 583.
3	朱昱, 宋建社, 王正元. 一种基于最大保障时间的战时装备维修任务调度[J]. 系统工程与电子技术, 2007, 29 (11): 1900- 1903. doi: 10.3321/j.issn:1001-506x.2007.11.028
	ZHU Y , SONG J S , WANG Z Y . Scheduling model of the battle equipment maintenance task based on the most support time[J]. Systems Engineering and Electronic, 2007, 29 (11): 1900- 1903. doi: 10.3321/j.issn:1001-506x.2007.11.028
4	陈伟龙, 陈春良, 陈康柱, 等. 考虑不确定性的进攻作战抢修任务动态调度[J]. 兵工学报, 2017, 38 (5): 1011- 1019. doi: 10.3969/j.issn.1000-1093.2017.05.022
	CHEN W L , CHEN C L , CHEN K Z , et al. Dynamic scheduling of battlefield rush-repair tasks under uncertainty in offensive operation[J]. Acta Armamentarii, 2017, 38 (5): 1011- 1019. doi: 10.3969/j.issn.1000-1093.2017.05.022
5	DONG R Y , WANG S S , WANG G Y , et al. Hybrid optimization algorithm based on wolf pack search and local search for solving traveling salesman problem[J]. Journal of Shanghai Jiaotong University (Science), 2019, 24 (1): 41- 47. doi: 10.1007/s12204-019-2039-9
6	YANG J Y , DING R F , ZHANG Y , et al. An improved ant colony optimization (I-ACO) method for the quasi travelling salesman problem (quasi-TSP)[J]. International Journal of Geographical Information Science, 2015, 29 (9): 1534- 1551. doi: 10.1080/13658816.2015.1013960
7	ABDALLAH A M F M , ESSAM D L , SARKER R A . On solving periodic re-optimization dynamic vehicle routing problems[J]. Applied Soft Computing, 2017, 55 (6): 1- 12.
8	CHEN S F , CHEN R , WANG G G , et al. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems[J]. Computers and Electrical Engineering, 2018, 67 (4): 596- 607.
9	ULMER M W , SOEFFKER N , MATTFELD D C . Value function approximation for dynamic multi-period vehicle routing[J]. European Journal of Operational Research, 2018, 269 (3): 883- 899. doi: 10.1016/j.ejor.2018.02.038
10	JIA Y , LI J H . Scheduling rules based on gene expression pro gramming for resource-constrained project scheduling problem[J]. Journal of Donghua University (English Edition), 2015, 32 (1): 91- 96.
11	ZAMANI R . A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2013, 229 (2): 552- 559. doi: 10.1016/j.ejor.2013.03.005
12	AQEL G A , LI X Y , GAO L . A modified iterated greedy algorithm for flexible job shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2019, 32 (1): 21- 32. doi: 10.1186/s10033-019-0337-7
13	PENG J G , LIU M Z , ZHANG X , et al. Hybrid heuristic algorithm for multi-objective scheduling problem[J]. Journal of Systems Engineering and Electronics, 2019, 30 (2): 327- 342. doi: 10.21629/JSEE.2019.02.12
14	LI X , GAO L . An effective hybrid genetic algorithm and Tabu search for flexible job shop scheduling problem[J]. International Journal of Production Economics, 2016, 174, 93- 110. doi: 10.1016/j.ijpe.2016.01.016
15	陈春良, 昝翔, 张仕新, 等. 基于改进MMAS的装备维修任务路径规划方法[J]. 系统工程与电子技术, 2017, 39 (12): 2716- 2720. doi: 10.3969/j.issn.1001-506X.2017.12.13
	CHEN C L , ZAN X , ZHANG S X , et al. Routing plan method for equipment maintenance task based on improved MMAS[J]. Systems Engineering and Electronic, 2017, 39 (12): 2716- 2720. doi: 10.3969/j.issn.1001-506X.2017.12.13
16	MIR J S S , ALI D M . Multigene genetic programming for sediment transport modeling in sewers for conditions of non-deposition with a bed deposit[J]. International Journal of Sediment Research, 2019, 33 (2): 262- 270.
17	AMIN S , MOJTABA B , HOSSEIN S . Optimal setting and placement of FACTS devices using strength Pareto multi-objective evolutionary algorithm[J]. Journal of Central South University, 2017, 24, 829- 839. doi: 10.1007/s11771-017-3485-x
18	KALAYCI C B , KAYA C . An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery[J]. Expert Systems with Applications, 2016, 66, 163- 175. doi: 10.1016/j.eswa.2016.09.017
19	DENG Y , ZHU W H , LI H W , et al. Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows[J]. Journal of Systems Engineering and Electronics, 2018, 29 (3): 625- 638. doi: 10.21629/JSEE.2018.03.20
20	SUJAREE K , KITJARUWANKUL S , BOOONAMNAJ P , et al. Transmembrane helix assembly by max-min ant system algorithm[J]. Chemical Biology and Drug Design, 2015, 86 (6): 1360- 1370. doi: 10.1111/cbdd.12600
21	FAN C L , FU Q , LONG G Z , et al. Hybrid artificial bee colony algorithm with variable neighborhood search and memory mechanism[J]. Journal of Systems Engineering and Electronics, 2018, 29 (2): 405- 414. doi: 10.21629/JSEE.2018.02.20

i	t_i/min	δ_i¹	δ_i²	T_i^up/min	$\widetilde T$ _i1	$\widetilde T$ _i2	$\widetilde T$ _i3	i	t_i/min	δ_i¹	δ_i²	T_i^up/min	$\widetilde T$ _i1	$\widetilde T$ _i2	$\widetilde T$ _i3
1	100	0.48	0.37	190	30	20	15	11	207	0.55	0.41	360	35	25	10
2	100	0.57	0.42	190	28	18	12	12	224	0.67	0.52	400	30	20	10
3	100	0.82	0.55	190	32	25	0	13	263	0.48	0.37	400	35	25	18
4	100	0.67	0.52	210	35	0	12	14	282	0.67	0.52	410	28	30	0
5	100	0.74	0.66	210	35	25	18	15	325	0.82	0.55	450	40	30	14
6	128	0.67	0.58	220	0	30	14	16	341	0.67	0.52	450	35	32	18
7	140	0.68	0.42	250	40	30	16	17	387	0.74	0.66	450	28	28	13
8	156	0.59	0.39	280	0	32	0	18	413	0.52	0.38	480	0	20	10
9	168	0.55	0.41	320	36	28	10	19	433	0.48	0.32	480	30	0	16
10	182	0.44	0.36	330	42	0	13	20	456	0.59	0.39	480	35	25	10

调度时刻	参与调度装备	各定点修理组的任务序列及恢复状态								定点修理数据
调度时刻	参与调度装备	组1	组2	组3	组4	组5	组6	组7	组8	F₁	F₂	F₃
100	1, 2, 3, 4, 5	3-2	5-1	4	3-1	2	5	4-1	5-2	5	3.02	1 471
128	1, 2, 6	3-2	5-1	4	3-6	2	5-1	4-6	5-2-1	6	3.69	1 761
140	1, 2, 6, 7	3-7	5-2	4-1	3-7	2-1	5-6	4-6-2	5-7-1	7	4.28	1 925
156	1, 2, 6, 7, 8	3-7	5-2	4-1	3-7-8	2-1	5-6	4-6-2	5-7-1	8	4.87	2 151
168	1, 2, 8, 9	3-7-9	5-2	4-1	3-7-8	2-1	5-6-9	4-6-2-9	5-7-1	9	5.42	2 335
182	1, 2, 8, 9, 10	3-7-10	5-2-9	4-1	3-7-8	2-1	5-6-9	4-6-2-9	5-7-10-1	10	6	2 486
207	1, 8, 9, 10, 11	3-7-10	5-2-9	4-1-11	3-7-8	2-1-11	5-6-9	4-6-2-9-11	5-7-10-1	11	6.41	2 595
224	9, 10, 11, 12	3-7-10-11	5-2-9	4-1-12	3-7-8-12	2-1-11	5-6-9	4-6-2-9-12	5-7-10-1-11	12	7.08	2 709
263	11, 12, 13	3-7-10-11	5-2-9-13	4-1-12	3-7-8-12	2-1-11	5-6-9-13	4-6-2-9-12-13	5-7-10-1-11	13	7.45	2 788
282	11, 12, 13, 14	3-7-10-11	5-2-9-14	4-1-12-13	3-7-8-12	2-1-11-14	5-6-9-13	4-6-2-9-12-13	5-7-10-1-11	14	8.12	2 815
325	11, 12, 13, 14, 15	3-7-10-11-15	5-2-9-14	4-1-12-13	3-7-8-12-15	2-1-11-14	5-6-9-13	4-6-2-9-12-13	5-7-10-1-11-15	15	8.64	2 843
341	14, 15, 16	3-7-10-11-16	5-2-9-14-15	4-1-12-13	3-7-8-12-15	2-1-11-14	5-6-9-13-16	4-6-2-9-12-13-16	5-7-10-1-11-15	16	9.16	2 839
387	15, 16, 17	3-7-10-11-16	5-2-9-14-15	4-1-12-13	3-7-8-12-15	2-1-11-14	5-6-9-13-16	4-6-2-9-12-13-16	5-7-10-1-11-15	16	9.16	2 839
413	17, 18	3-7-10-11-16	5-2-9-14-15	4-1-12-13	3-7-8-12-15-18	2-1-11-14	5-6-9-13-16	4-6-2-9-12-13-16-18	5-7-10-1-11-15	17	9.68	2 886
433	17, 19	3-7-10-11-16	5-2-9-14-15	4-1-12-13	3-7-8-12-15-18	2-1-11-14	5-6-9-13-16	4-6-2-9-12-13-16-18	5-7-10-1-11-15	17	9.68	2 886
456	17, 19, 20	3-7-10-11-16	5-2-9-14-15	4-1-12-13	3-7-8-12-15-18	2-1-11-14	5-6-9-13-16	4-6-2-9-12-13-16-18	5-7-10-1-11-15	17	9.68	2 886

[1]	肖宇, 邓正宏, 张展. 基于双阶段互信息准则的多目标检测波形设计[J]. 系统工程与电子技术, 2022, 44(9): 2736-2742.
[2]	侯子林, 程婷, 彭瀚. 基于量测转换序贯滤波的GMPHD机动目标跟踪[J]. 系统工程与电子技术, 2022, 44(8): 2474-2482.
[3]	闫世瑛, 颜克斐, 方伟, 陆恒杨. 基于差分进化邻域自适应的大规模多目标算法[J]. 系统工程与电子技术, 2022, 44(7): 2112-2124.
[4]	刘乾, 鲁云军, 陈克斌, 韩梦瑶, 郭亮. 任务主体二元约束下作战任务分解EVA方法[J]. 系统工程与电子技术, 2022, 44(7): 2201-2210.
[5]	梁璞, 范红旗, 付强. 基于投影余角的多普勒雷达几何检测器[J]. 系统工程与电子技术, 2022, 44(6): 1854-1861.
[6]	翟光, 王妍欣, 孙一勇. 基于低轨星网的多目标协同跟踪滤波技术[J]. 系统工程与电子技术, 2022, 44(6): 1957-1967.
[7]	辛怀声, 曹晨. 基于交互多模型的分组δ-广义标签多伯努利算法[J]. 系统工程与电子技术, 2022, 44(4): 1128-1138.
[8]	李洪瑶, 李小强, 韩心中, 谢学立, 席建祥. 基于决策融合的多无人机协同目标检测识别算法[J]. 系统工程与电子技术, 2022, 44(3): 746-754.
[9]	宋子壮, 杨嘉伟, 张东方, 王诗强, 张硕. 基于无锚框的红外多类别多目标实时跟踪网络[J]. 系统工程与电子技术, 2022, 44(2): 401-409.
[10]	唐军奎, 刘峥, 谢荣, 曾波. MIMO雷达稀疏阵列优化设计方法[J]. 系统工程与电子技术, 2022, 44(12): 3661-3666.
[11]	汪瀚洋, 陈亮, 徐海, 白景波. 基于MOEA/D-ARMS的无人机在线航迹规划[J]. 系统工程与电子技术, 2022, 44(11): 3505-3514.
[12]	王宁, 吕晓德, 李苗苗, 刘忠胜. 多频带互相干处理中多目标相位补偿方法[J]. 系统工程与电子技术, 2022, 44(10): 3083-3089.
[13]	来磊, 邹鲲, 吴德伟, 李保中. 交互策略改进MOFA进化的多UAV协同航迹规划[J]. 系统工程与电子技术, 2021, 43(8): 2282-2289.
[14]	崔荣伟, 韩维, 苏析超, 王立国, 刘玉杰. 舰载机甲板机务勤务保障作业调度与资源配置集成优化[J]. 系统工程与电子技术, 2021, 43(7): 1884-1893.
[15]	张佳琦, 陶海红, 张修社. 量测点迹空间聚类的多传感器多帧检测算法[J]. 系统工程与电子技术, 2021, 43(6): 1533-1540.