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

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

Abstract

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

CLC Number:

E917

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.

Figures/Tables 3

Table 1

Table 2

Fig.1

References 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]	Shiying YAN, Kefei YAN, Wei FANG, Hengyang LU. Large-scale multi-objective algorithm based on neighborhood adaptive of differential evolution [J]. Systems Engineering and Electronics, 2022, 44(7): 2112-2124.
[2]	Qian LIU, Yunjun LU, Kebin CHEN, Mengyao HAN, Liang GUO. Combat task decomposition EVA method based on binary constraints of task subject [J]. Systems Engineering and Electronics, 2022, 44(7): 2201-2210.
[3]	Hongyao LI, Xiaoqiang LI, Xinzhong HAN, Xueli XIE, Jianxiang XI. Cooperative object detection and recognition algorithm for multiple UAVs based on decision fusion [J]. Systems Engineering and Electronics, 2022, 44(3): 746-754.
[4]	Junkui TANG, Zheng LIU, Rong XIE, Bo ZENG. Optimal design method for sparse array of MIMO radar [J]. Systems Engineering and Electronics, 2022, 44(12): 3661-3666.
[5]	Hanyang WANG, Liang CHEN, Hai XU, Jingbo BAI. UAV online trajectory planning based on MOEA/D-ARMS [J]. Systems Engineering and Electronics, 2022, 44(11): 3505-3514.
[6]	Rongwei CUI, Wei HAN, Xichao SU, Liguo WANG, Yujie LIU. Integrated optimization of carrier-based aircraft flight deck operations scheduling and resource configuration for pre-flight preparation stage [J]. Systems Engineering and Electronics, 2021, 43(7): 1884-1893.
[7]	Bin ZENG, Quanxian ZHANG, Houpu LI. Optimal scheduling for cooperative support chain of logistics and equipment under uncertainty [J]. Systems Engineering and Electronics, 2021, 43(5): 1277-1286.
[8]	Boyuan XIA, Kewei YANG, Zhiwei YANG, Xiaoke ZHANG, Danling ZHAO. Multi-objective optimization of equipment portfolio based on kill-web evaluation [J]. Systems Engineering and Electronics, 2021, 43(2): 399-409.
[9]	Chunming TIAN, An YANG, Le YE, Jianxing LI, Yuchen HE. End-to-end antenna optimization based on Bayesian optimization algorithm [J]. Systems Engineering and Electronics, 2021, 43(12): 3413-3419.
[10]	Lei LAI, Dewei WU, Kun ZOU, Kun HAN, Hailin LI. Three dimensional route planning of UAV based on the multi-criterion interactive membrane evolutionary algorithm [J]. Systems Engineering and Electronics, 2021, 43(1): 138-146.
[11]	Yunfei MA, Xisheng JIA, Huajun BAI, Chiming GUO, Shuangchuan WANG. Fault diagnosis of compressed vibration signal based on 1-dimensional CNN with optimized parameters [J]. Systems Engineering and Electronics, 2020, 42(9): 1911-1919.
[12]	Qingguo LIU, Xinxue LIU, Jian WU, Yaxiong LI, Hao CHEN. Optimization of fire distribution for multiple SGSW based on improved NSGA-Ⅲ [J]. Systems Engineering and Electronics, 2020, 42(9): 1995-2002.
[13]	Yadong WANG, Quan SHI, Wei XIA, Cai CHEN. Structure optimization of spare parts supply network based on hyper heuristic algorithm [J]. Systems Engineering and Electronics, 2020, 42(3): 620-629.
[14]	Zhifei XI, An XU, Yingxin KOU, Zhanwu LI, Aiwu YANG. Decision process of multi-aircraft cooperative air combat maneuver [J]. Systems Engineering and Electronics, 2020, 42(2): 381-389.
[15]	Chunshan DING. Survey on progress and prospect of sensor management [J]. Systems Engineering and Electronics, 2020, 42(12): 2761-2770.

Multi-objective dynamic scheduling of fixed-point repairing tasksbased on Pareto improved VNS-MMAS

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 21

Related Articles 15

Recommended Articles

Metrics

Comments