基于HA算法的舰载机出动作业调度方法

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

摘要/Abstract

摘要：

出动离场是舰载机作战效能发挥的基础环节, 本文研究其出动作业优化调度, 将作业过程抽象为柔性车间调度问题, 考虑优先序、资源及空间约束建立了混合整数规划模型, 提出了一种基于种群进化搜索与邻域改进能力的混合遗传-模拟退火算法, 并给出了作业扰动时的重调度策略, 通过引入任务表的生成构建了实际作业调度仿真架构。该架构融合了问题输入、动态扰动与算法, 实用推广性强。仿真结果表明, 所提算法收敛性快、解的准确性好、效率高, 可有效解决任务表驱动下的出动调度问题; 灵敏度分析发现, 保障点-军械加工对全局调度影响最为显著。

关键词: 舰载机, 出动作业, 柔性车间调度, 混合整数规划, 混合算法

Abstract:

The sortie is the fundamental link for the combat effectiveness of carrier aircraft. This paper studies the sortie optimization scheduling of carrier aircraft, abstracting the operation process as a flexible job-shop scheduling problem (FJSP). A mixed integer programming model is established considering priority order, resources, and spatial constraints. A hybrid genetic operator and simulated annealing (HA) algorithm based on population evolution search and neighborhood improvement ability is proposed, and a rescheduling strategy is provided for job disturbance. A simulation architecture for actual job scheduling is constructed by introducing the generation of task tables. The architecture integrates problem inputs, dynamic perturbations, and algorithms, making it highly practical and generalizable. Simulation results show that the proposed algorithm has fast convergence, good solution accuracy, and high efficiency, and can effectively solve the sortie scheduling problem driven by task tables. Sensitivity analysis found that the support point ordnance processing has the most significant impact on global scheduling.

Key words: carrier aircraft, sortie, flexible job-shop scheduling, mixed integer programming (MIP), hybrid algorithm

中图分类号:

V211

刘子玄, 万兵, 苏析超, 郭放, 刘玉杰. 基于HA算法的舰载机出动作业调度方法[J]. 系统工程与电子技术, 2024, 46(5): 1691-1702.

Zixuan LIU, Bing WAN, Xichao SU, Fang GUO, Yujie LIU. Sortie scheduling method of carrier aircraft based on HA algorithm[J]. Systems Engineering and Electronics, 2024, 46(5): 1691-1702.

图/表 15

图1

图2

表1

图3

图4

图5

图6

图7

图8

图9

表2

图10

图11

表3

图12

参考文献 31

1	FENG Q , LI S J , SUN B . A multi-agent based intelligent configuration method for aircraft fleet maintenance personnel[J]. Chinese Journal of Aeronautics, 2014, 27 (2): 280- 290. doi: 10.1016/j.cja.2014.02.016
2	刘翱, 刘克. 舰载机保障作业调度问题研究进展[J]. 系统工程理论与实践, 2017, 37 (1): 49- 60.
	LIU A , LIU K . Advances in carrier-based aircraft deck operation scheduling[J]. Systems Engineering-Theory & Practice, 2017, 37 (1): 49- 60.
3	RYAN J C. Evaluating safety protocols for manned unmanned environments through agent based simulation[D]. Massachusetts: Massachusetts Institute of Technology, 2014.
4	RYAN J C , BANERJEE A G , CUMMINGS M L , et al. Comparing the performance of expertuser 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
5	RYAN J C, CUMMINGS M L, ROY N, et al. Designing an interactive local and global decision support system for aircraft carrier deck scheduling[C]//Proc. of the AIAA Infotech@Aerospace Conference, 2011: 1516.
6	RAJARSHI G D. A queueing network based approach to distributed aircraft carrier deck scheduling[C]//Proc. of the AIAA Infotech@Aerospace Conference, 2011: 1514.
7	MICHINI B, HOW J P. A human-interactive course of action planner for aircraft carrier deck operations[C]//Proc. of the AIAA Infotech@Aerospace Conference, 2011: 1515.
8	张智, 林圣琳, 朱齐丹, 等. 考虑运动学约束的不规则目标遗传避碰规划算法[J]. 航空学报, 2015, 36 (4): 1348- 1358.
	ZHANG Z , LIN S L , ZHU Q D , et al. Genetic collision avoidance planning algorithm for irregular shaped object with kinematics constraint[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36 (4): 1348- 1358.
9	苏析超, 韩维, 萧卫, 等. 基于Memetic算法的舰载机舰面一站式保障调度[J]. 系统工程与电子技术, 2016, 38 (10): 2303- 2309.
	SU X C , HAN W , XIAO W , et al. Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm[J]. Systems Engineering and Electronics, 2016, 38 (10): 2303- 2309.
10	苏析超, 韩维, 张勇, 等. 考虑人机匹配模式的舰载机甲板机务勤务保障调度算法[J]. 航空学报, 2018, 39 (12): 222314.
	SU X C , HAN W , ZHANG Y , et al. Scheduling algorithm for maintenace and service support of carrier-based aircraft on flight deck with different man-aircraft matching patterns[J]. Acta Aeronautica Sinica, 2018, 39 (12): 222314.
11	WANG X W , LIU J , SU X C , et al. A review on carrier aircraft dispatch path planning and control on deck[J]. China Journal of Aeronautics, 2022, 33 (12): 3039- 3057.
12	郑茂, 黄胜, 王超. 优先网络排队的舰载机出动回收能力研究[J]. 北京理工大学学报, 2013, 33 (10): 1051- 1055.
	ZHENG M , HUANG S , WANG C . Research on aircraft sortie generation rate with the use of HOL closed queueing network model[J]. Transactions of Beijing Institute of Technology, 2013, 33 (10): 1051- 1055.
13	杨放青, 王超, 姜滨, 等. 舰载机出动回收调度策略生成方法[J]. 北京理工大学学报, 2018, 38 (10): 1030- 1036.
	YANG F Q , WANG C , JIANG B , et al. A method of policy automated generation for carrier aircraft sortie and recovery scheduling[J]. Transactions of Beijing Institute of Technology, 2018, 38 (10): 1030- 1036.
14	WU Y , QU X J . Obstacle avoidance and path planning for carrier aircraft launching[J]. Chinese Journal of Aeronautics, 2015, 28 (3): 695- 703. doi: 10.1016/j.cja.2015.03.001
15	CUI J P , WU Y , SU X C , et al. A task allocation model for a team of aircraft launching on the carrier[J]. Mathematical Problems in Engineering, 2018, 2018, 7920806.
16	SU X C , HAN W , WU Y , et al. A proactive robust scheduling method for aircraft carrier flight deck operations with stochastic durations[J]. Complexity, 2018, 2018, 6932985.
17	GUO F , HAN W , SU X C , et al. A bi-population immune algorithm for weapon transportation support scheduling problem with pickup and delivery on aircraft carrier deck[J]. Defence Technology, 2021, 22, 119- 134.
18	LIU Y J , HAN W , SU X C , et al. Optimization of fixed aviation support resource station configuration for aircraft carrier based on aircraft dispatch mission scheduling[J]. Chinese Journal of Aeronautics, 2023, 36 (2): 127- 138. doi: 10.1016/j.cja.2022.06.023
19	ZHENG M , YANG F Q , DONG Z P , et al. Carrier-borne aircrafts aviation operation automated scheduling using multiplicative weights apprenticeship learning[J]. International Journal of Advanced Robotic Systems, 2019, 16 (1)
20	LIU J , HAN W , WANG X W , et al. Research on cooperative trajectory planning and tracking problem for multiple carrier aircraft on the deck[J]. IEEE Systems Journal, 2019, 14 (2): 3027- 3038.
21	WU Y , LOW K H , HU X . Trajectory-based flight scheduling for AirMetro in urban environments by conflict resolution[J]. Transportation Research Part C: Emerging Technologies, 2021, 131, 103355. doi: 10.1016/j.trc.2021.103355
22	WU Y , QU X J . Path planning for taxi of carrier aircraft launching[J]. Science China Technological Sciences, 2013, 56 (6): 1561- 1570. doi: 10.1007/s11431-013-5222-5
23	SU X C, LI Z Y, SONG J Y, et al. A path planning method for carrier aircraft on deck combining artificial experience and intelligent search[C]//Proc. of the 4th International Workshop on Materials Science and Engineering, 2018, 381(1): 012194.
24	LIU J , HAN W , LI J , et al. Integration design of sortie sche-duling for carrier aircrafts based on hybrid flexible flowshop[J]. IEEE Systems Journal, 2019, 14 (1): 1503- 1511.
25	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
26	RONALD L R . Optimization in operations research[M]. 2nd ed Upper Saddle River, NJ: Pearson Higher Education, 2017: 5- 15.
27	YUAN Y , XU H . Multiobjective flexible job shop scheduling using memetic algorithms[J]. IEEE Trans.on Automation Science and Engineering, 2015, 12 (1): 336- 353. doi: 10.1109/TASE.2013.2274517
28	DRISS I , MOUSS K N , LAGGOUN A . A new genetic algorithm for flexible job shop scheduling problems[J]. Journal of Mechanical Science and Technology, 2015, 29 (3): 1273- 1281. doi: 10.1007/s12206-015-0242-7
29	姜龙光. 国外航母航空保障系统[M]. 北京: 国防工业出版社, 2016.
	JIANG L G . Foreign aircraft carrier aviation support system[M]. Beijing: National Defense Industry Press, 2016.
30	PEZZELLA F , MORGANTI G , CIASCHETTI , et al. A genetic algorithm for the flexible job-shop scheduling problem[J]. Compu-ters & Operations Research, 2008, 35 (10): 3202- 3212.
31	刘相春. 美国"福特"级航母"一站式保障"技术特征和关键技术分析[J]. 中国舰船研究, 2013, 8 (6): 1- 5.
	LIU X C . Technical features and critical technologies for the "pit-stop" aircraft servicing adopted by ford class aircraft carriers[J]. Chinese Journal of Ship Research, 2013, 8 (6): 1- 5.

工件	工序时间	机器
工件	工序时间	M₁	M₂	M₃
j₁	o₁₁	3	1	-
	o₁₂	2	-	1
	o₁₃	1	1	-
j₂	o₂₁	2	3	2
j₂	o₂₂	2	-	-
j₃	o₃₁	-	3	2
j₃	o₃₂	-	2	-

出动规模/架	保障阶段	离场阶段	作业时间
8	59	8.2	67.2
14	72.5	14.99	87.49
20	99	21.7	120.7

算法	出动规模1架	20次实验性能指标
算法	出动规模1架	最好解	均值	最坏解
HA	8	67.20	67.20	67.20
	14	87.49	87.52	87.64
	20	120.40	120.70	120.90
GA	8	67.20	67.20	67.60
	14	87.49	87.92	88.34
	20	120.84	120.96	121.58
SA	8	67.40	67.60	67.90
	14	88.42	88.68	89.95
	20	121.92	122.75	124.24
MBO	8	67.20	67.30	67.60
	14	87.82	88.24	89.48
	20	121.20	121.90	122.80
DE	8	67.20	67.20	67.40
	14	87.68	87.90	88.96
	20	120.90	121.32	122.56

[1]	刘玉杰, 崔凯凯, 韩维, 李樾. 基于IPSO的舰载机出动离场规划研究[J]. 系统工程与电子技术, 2024, 46(4): 1337-1345.
[2]	李建周, 张海轩, 陈书慧. 基于矩阵降维的MoM-PO电磁散射混合算法[J]. 系统工程与电子技术, 2023, 45(8): 2377-2382.
[3]	韩维, 刘子玄, 苏析超, 崔凯凯, 刘洁. 结合启发式与最优控制的舰载机甲板路径规划算法[J]. 系统工程与电子技术, 2023, 45(4): 1098-1110.
[4]	吕晓峰, 杨东泽, 马羚. 舰载机模块化弹药调度方案优化设计[J]. 系统工程与电子技术, 2023, 45(2): 465-471.
[5]	邓嘉宁, 李海旭, 安强林, 沙恩来, 王泽, 吴宇. 基于指标关联的舰载机出动架次率预测方法[J]. 系统工程与电子技术, 2023, 45(11): 3507-3515.
[6]	崔凯凯, 崔荣伟, 韩维, 郭放, 王毓麟, 刘洁. 基于MGP算法的舰载机回收排序调度技术[J]. 系统工程与电子技术, 2023, 45(10): 3192-3206.
[7]	张勇, 李常久, 苏析超, 崔荣伟. 基于HTLBO算法的舰载机机群机库维修任务调度[J]. 系统工程与电子技术, 2022, 44(9): 2858-2868.
[8]	荘露, 陆中, 宋海靖, 周伽. 一种机载系统研制保证等级分配的优化方法[J]. 系统工程与电子技术, 2022, 44(8): 2688-2698.
[9]	邓嘉宁, 吴宇, 许舒婷, 苟进展. 基于模糊贝叶斯-ANP舰载机出动回收综合评估[J]. 系统工程与电子技术, 2022, 44(11): 3423-3432.
[10]	韩维, 崔凯凯, 刘洁, 王昕炜, 张勇. 基于自校正MPC的舰载机着舰控制技术[J]. 系统工程与电子技术, 2022, 44(1): 250-261.
[11]	曾斌, 陈媛媛, 李厚朴. 考虑保障装备可用度的舰载机作业调度优化[J]. 系统工程与电子技术, 2021, 43(7): 1856-1865.
[12]	崔荣伟, 韩维, 苏析超, 王立国, 刘玉杰. 舰载机甲板机务勤务保障作业调度与资源配置集成优化[J]. 系统工程与电子技术, 2021, 43(7): 1884-1893.
[13]	万兵, 韩维, 梁勇, 郭放. 舰载机出动离场调度优化算法[J]. 系统工程与电子技术, 2021, 43(12): 3624-3634.
[14]	李弘祖, 郭立新, 董春雷, 孟肖. 基于八叉树优化的MoM-PO/PTD混合算法分析目标电磁散射及辐射问题[J]. 系统工程与电子技术, 2021, 43(11): 3033-3039.
[15]	万兵, 韩维, 梁勇, 苏析超. 基于指标函数的舰载机机队回收调度优化研究[J]. 系统工程与电子技术, 2021, 43(10): 2918-2930.