基于禁忌算法的舰载机甲板作业动态调度优化算法

doi:10.12305/j.issn.1001-506X.2023.10.22

摘要/Abstract

摘要：

针对航母舰载机在保障作业调度过程中出现扰动事件, 并打破原调度方案执行计划的情况, 为及时获得新的优化调度方案, 设计了舰载机动态调度优化算法。在禁忌搜索算法框架下, 采用基于工序的调度排班方式作为优化邻域结构, 并以部分映射交叉与普通映射交叉混合的交叉方式作为编码交叉策略, 以双重禁忌方式作为禁忌表内容, 最终实现实时调度。算法可针对调度过程中舰载机添加、舰载机故障、保障组添加、保障组故障以及某保障工序的完成时间提前或推迟等多种突发扰动事件, 在原调度方案基础上, 对调度方案进行快速、有效的更新。基于对静态甲板保障调度数学模型求解得到静态的调度优化方案, 采用扰动事件模拟方法, 利用动态调度策略获取重调度方案, 验证了所提算法的有效性与可行性。

关键词: 武器装备信息化, 甲板作业调度, 动态调度, 禁忌算法

Abstract:

In response to disturbance events that occur during the support operation scheduling process of carrier aircraft, and the original scheduling plan execution plan is broken. In order to obtain new optimized scheduling plans in a timely manner, a dynamic scheduling optimization algorithm for carrier aircraft is designed. Under the framework of the taboo search algorithm, a process-based scheduling and planning method is adopted as the optimization of neighborhood structure, and a mixed encoding crossover strategy of partial mapping crossover and ordinary mapping crossover is used as the encoding crossover strategy. Double taboo methods are used as the content of the taboo table, which ultimately achieve real-time scaling. The proposed algorithm can quickly and effectively update the scheduling plan based on the original scheduling plan for various sudden disturbance events such as the addition of carrier aircraft, carrier aircraft failures, support group addition, support group failures, and the advance or delay of the completion time of a certain support process during the scheduling process. Based on solving the static deck support scheduling mathematical model, a static scheduling optimization scheme is obtained. The disturbance event simulation method is used to obtain a rescheduling scheme using a dynamic scheduling strategy, which verifies the effectiveness and feasibility of the proposed algorithm.

Key words: computerization of weapon and equipment, deck operation scheduling, dynamic scheduling, tabu algorithm

中图分类号:

V271.4+92

范加利, 黄葵, 朱兴动, 孟杨凯. 基于禁忌算法的舰载机甲板作业动态调度优化算法[J]. 系统工程与电子技术, 2023, 45(10): 3172-3182.

Jiali FAN, Kui HUANG, Xingdong ZHU, Yangkai MENG. Carrier aircraft deck operations dynamic scheduling optimization algorithm based on the tabu algorithm[J]. Systems Engineering and Electronics, 2023, 45(10): 3172-3182.

图/表 13

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

图10

图11

表2

参考文献 29

1	李梦龙. 舰载机保障作业的静态与动态调度研究[D]. 武汉: 华中科技大学, 2019.
	LI M L. Study on static and dynamic scheduling of ship borne aircraft support operations[D]. Wuhan: Huazhong University of Technology, 2019.
2	苏析超, 韩维, 萧卫, 等. 基于Memetic算法的舰载机甲板一站式保障调度[J]. 系统工程与电子技术, 2016, 38 (10): 2303- 2309. doi: 10.3969/j.issn.1001-506X.2016.10.12
	SU X C , HAN W , XIAO W , et al. One-stop support dispatching of shipboard aircraft deck based on memetic algorithm[J]. Systems Engineering and Electronics, 2016, 38 (10): 2303- 2309. doi: 10.3969/j.issn.1001-506X.2016.10.12
3	LIU Q , DENG Q W , GONG G L , et al. An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers[J]. Expert Systems with Applications, 2020, 160 (1): 113721.
4	ZHANG X Y, YIN S W, JIN J C. Hybrid fruit fly algorithm based on bi-objective job-shop scheduling[C]//Proc. of the International Conference on Information, Electronic and Communication Engineering, 2018.
5	MICHINI B, HOW J P. A human interactive course of action planner for aircraft carrier deck operations[C]//Proc. of the Infotech Aerospace, 2011.
6	蒋婷婷, 韩维, 苏析超. 面向故障扰动的舰面保障重调度仿真研究[J]. 兵器装备工程学报, 2017, 38 (11): 93- 98. doi: 10.11809/scbgxb2017.11.021
	JIANG T T , HAN W , SU X C . Simulation of ship surface su-pport rescheduling based on fault disturbance[J]. Journal of Weapon Equipment Engineering, 2017, 38 (11): 93- 98. doi: 10.11809/scbgxb2017.11.021
7	苏析超, 韩维, 萧卫, 等. 基于Memetic算法的舰载机舰面一站式保障调度[J]. 系统工程与电子技术, 2016, 38 (10): 2303- 2309. doi: 10.3969/j.issn.1001-506X.2016.10.12
	SU X C , HAN W , XIAO W , et al. One-stop security scheduling of ship-borne aircraft and ship-surface based on memetic algorithm[J]. Systems Engineering and Electronics, 2016, 38 (10): 2303- 2309. doi: 10.3969/j.issn.1001-506X.2016.10.12
8	韩维, 苏析超, 陈俊锋. 舰载机多机一体化机务保障调度方法[J]. 系统工程与电子技术, 2015, 37 (4): 809- 816.
	HAN W , SU X C , CHEN J F . Shipborne aircraft multi-aircraft integrated maintenance support scheduling method[J]. Systems Engineering and Electronics, 2015, 37 (4): 809- 816.
9	SU X C , HAN W , WU Y , et al. A robust scheduling optimization method for flight deck operations of aircraft carrier with ternary interval durations[J]. IEEE Access, 2018, 6, 69918- 69936. doi: 10.1109/ACCESS.2018.2879503
10	苏析超, 韩维, 张勇. 考虑人机匹配模式的舰载机甲板机务勤务保障调度方法[J]. 航空学报, 2018, 39 (12): 222314.
	SU X C , HAN W , ZHANG Y . Scheduling method for maintenance and service support of carrier-based aircraft on flight deck with different man-aircraft matching patterns[J]. Acta Aeronautica et Astronautica Sinica, 2018, 39 (12): 222314.
11	李耀宇, 朱一凡, 贾全, 等. 基于排队网络的舰载机甲板调运优化调度策略生成方法[J]. 海军工程大学学报, 2013, 25 (5): 26- 30.
	LI Y Y , ZHU Y F , JIA Q , et al. Generation method of optimal scheduling strategy for shipborne aircraft deck transport based on queuing network[J]. Journal of Naval Engineering University, 2013, 25 (5): 26- 30.
12	崔博. 舰载机保障人员配置优化仿真研究[D]. 哈尔滨: 哈尔滨工程大学, 2016.
	CUI B. Simulation research on personnel allocation optimization of shipborne aircraft support[D]. Harbin: Harbin Engineering University, 2016.
13	范加利, 朱兴动, 高伟, 等. 基于并行遗传算法的舰载机再次出动作业调度[J]. 兵器装备工程学报, 2019, 40 (11): 139- 143.
	FAN J L , ZHU X D , GAO W , et al. Redispatch of carrier-borne aircraft based on parallel genetic algorithm[J]. Journal of Ordnance Equipment Engineering, 2019, 40 (11): 139- 143.
14	RYAN J C . Comparing the performance of expert user heuristics and an integer linear program in aircraft carrier deck operations[J]. IEEE Trans.on Cybernetics, 2014, 44 (6): 761- 773. doi: 10.1109/TCYB.2013.2271694
15	DASTIDAR R G , FRAZZOLI E . A queueing network based approach to distributed aircraft carrier deck scheduling[J]. American Institute of Aeronautics and Astronautics, 2011, 1515 (12): 1514- 1164.
16	QI C , WANG D . Dynamic aircraft carrier flight deck task planning based on HTN[J]. IFAC-Papers Online, 2016, 49 (12): 1608- 1613. doi: 10.1016/j.ifacol.2016.07.810
17	YU L F , ZHU C , SHI J M , et al. An extended flexible job shop scheduling model for flight deck scheduling with priority, parallel operations, and sequence flexibility[J]. Scientific Programming, 2017, 2463252.
18	刘钦辉, 邱长华, 王能建. 考虑空间约束的舰载机作业调度模型研究[J]. 哈尔滨工程大学学报, 2012, 33 (11): 1435- 1439.
	LIU Q H , QIU C H , WANG N J . Study on ship-based aircraft operation scheduling model considering spatial restriction[J]. Journal of Harbin Engineering University, 2012, 33 (11): 1435- 1439.
19	周晓光, 赵仁厚, 王述运, 等. 飞行甲板作业对航母舰载机出动架次影响分析[J]. 系统仿真学报, 2014, 26 (10): 2447- 2451.
	ZHOU X G , ZHAO R H , WANG S Y , et al. Analysis on the influence of flight deck operation on sortition of aircraft on carrier of aircraft carrier[J]. Journal of System Simulation, 2014, 26 (10): 2447- 2451.
20	刘翱, 刘克. 舰载机保障作业调度问题研究进展[J]. 系统工程理论与实践, 2017, 37 (1): 49- 60.
	LIU A , LIU K . Research progress of carrier-borne aircraft support operation scheduling problem[J]. Systems Engineering Theory and Practice, 2017, 37 (1): 49- 60.
21	CAI S , YANG K , LIU K . Multi-objective optimization of the distributed permutation flow shop scheduling problem with transportation and eligibility constraints[J]. Journal of the Operations Research Society of China, 2018, 6, 391- 416.
22	朱兴动, 范加利, 王正, 等. 一种航母甲板作业快速调度算法[J]. 舰船科学技术, 2019, 41 (10): 180- 184.
	ZHU X D , FAN J L , WANG Z , et al. A fast scheduling algorithm for aircraft carrier deck operatin[J]. Journal of Ship Science and Technology, 2019, 41 (10): 180- 184.
23	LIU Q , DENG Q W , GONG G L , et al. An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers[J]. Expert Systems with Applications, 2020, 160 (1): 113721.
24	ZHANG X Y, YIN S W, JIN J C. Hybrid fruit fly algorithm based on bi-objective job-shop scheduling[C]//Proc. of the International Conference on Information, Electronic and Communication Engineering, 2018.
25	GURKAN O , OZAN B , AYDI T . Extracting priority rules for dynamic multi-objective flexible job shop scheduling problems using gene expression programming[J]. International Journal of Production Research, 2019, 57 (10): 3121- 3137.
26	RAMESH C , KAMALAKANNA R . A lot streaming based flow shop scheduling problem using simulated annealing algorithm[J]. Materials Today: Proceedings, 2021, 37 (1): 241- 244.
27	GONG G L , DENG W Q , RAYMOND C . An effective meme-tic algorithm for multi-objective job-shop scheduling[J]. Know-ledge-based Systems, 2020, 160 (1): 113721.
28	JUNG S W , WOO Y B , KIM B S . Two-stage assembly sche-duling problem for processing products with dynamic component-sizes and a setup time[J]. Computers & Industrial Engineering, 2017, 43 (2): 199- 374.
29	YUAN P , HAN W , SU X C , et al. A dynamic scheduling method for carrier aircraft support operation under uncertain conditions based on rolling horizon strategy[J]. Applied Sciences, 2018, 8 (9): 1546- 1568.

舰载机编号	舰载机位置
P1	28
P2	31
P3	26
P4	7
P5	18
P6	9
P7	16
P8	2
P9	29
P10	30
P11	5
P12	13

重调度事件		算法				全局搜索
重调度事件		禁忌优化算法	模拟退火算法	遗传算法	本文算法	全局搜索
保障组故障	最优解/s	6 020	6 028	5 970	5 860	5 855
保障组故障	耗时	37 s	45 s	50 s	4 s	3 min
新增保障组	最优解/s	5 970	5 891	5 832	5 672	5 672
新增保障组	耗时	36 s	42 s	47 s	3 s	3 min
舰载机故障	最优解/s	5 932	5 873	5 810	5 587	5 587
舰载机故障	耗时	37 s	42 s	49 s	3 s	3 min
新增舰载机	最优解/s	7 341	7 349	7 338	7 183	7 180
新增舰载机	耗时	39 s	44 s	52 s	4 s	3 min
工序时间变化	最优解/s	6 360	6 350	6 234	5 990	5 990
工序时间变化	耗时	52 s	59 s	1 min	3 s	4 min

[1]	刘彦, 陈春良, 陈伟龙, 郭一鸣. 基于Pareto改进VNS-MMAS的定点修理任务多目标动态调度[J]. 系统工程与电子技术, 2020, 42(2): 356-364.
[2]	孙鹏, 武君胜, 王勋, 焦志强, 张杰勇. 基于多目标优化的C2组织平台资源动态调度方法[J]. 系统工程与电子技术, 2019, 41(4): 793-800.
[3]	孙鹏, 武君胜, 廖梦琛, 张杰勇. 基于自适应遗传算法的战场资源动态调度模型及算法[J]. 系统工程与电子技术, 2018, 40(11): 2459-.
[4]	陈伟龙, 陈春良, 史宪铭, 高恒. 基于变体GA的进攻作战抢修任务动态调度[J]. 系统工程与电子技术, 2017, 39(3): 577-583.
[5]	屈巍,汪晋宽,赵旭,刘志刚. 基于遗传算法的无线传感器网络覆盖控制优化策略[J]. Journal of Systems Engineering and Electronics, 2010, 32(11): 2476-2479.
[6]	冯强，曾声奎，康锐. 基于多主体的舰载机综合保障过程建模方法[J]. Journal of Systems Engineering and Electronics, 2010, 32(1): 211-216.
[7]	王军民，王鹏，李菊芳. 成像卫星鲁棒性调度策略研究[J]. Journal of Systems Engineering and Electronics, 2010, 32(1): 109-114.