兵工自动化
Ordnance Industry Automation 2021-0140(1)
・37・
doi: 10.7690/bgzdh.2021.01.009
王文鹏，邹 冈U，张 玎，马 元，张宇坤
(海军航空大学青岛校区，山东青岛266041)
摘要：为解决舰载机多机保障作业的调度问题，设计一种与之相适应的自适应遗传算法。分析舰载机进行保障 的流程约束，得到单个舰载机的简化流程，以最小化保障时间为目标，建立问题的数学模型，根据舰载机保障调度 作业的特点，采用自适应遗传算法进行求解，通过多机保障任务案例进行验证。结果表明：使用甘特图的方式，可 直观地表示保障作业的计划流程，并验证了自适应遗传算法的有效性。 关键词：舰载机；遗传算法；保障调度
中图分类号：V271.4+ 92 文献标志码：A
Support Scheduling of Carrier-based Aircraft Based on Adaptive Genetic Algorithm
Wang Wenpeng, Zou Gang, Zhang Ding, Ma Yuan, Zhang Yukun
(Qingdao Branch, Naval Aviation University, Qingdao 266041, China)
Abstract: In order to solve the scheduling problem of carrier-based aircraft multi-machine support operations, an adaptive genetic algorithm is designed to suit it. The process constraints of carrier-based aircraft support are analyzed, and the simplified process of a single carrier-based aircraft is obtained. The goal is to minimize the support time and establish a mathematical model of the problem. According to the characteristics of carrier-based aircraft support scheduling operations, an adaptive genetic algorithm is used to solve the problem, which is verified by the case of multi-machine support tasks. The results show that the Gantt chart can intuitively represent the planning process of the guarantee operation and verify the effectiveness of the adaptive genetic algorithm.
Keywords: carrier-based aircraft; genetic algorithm; support operation scheduling
0引言
舰载机是航空母舰系统的重要组成部分，承担 着航空母舰几乎全部的作战任务。舰载机的岀动能 力严重影响着航母的综合作战能力［1］o 在舰载机通 过起飞执行任务之前，必须严格按照预先制
定的甲板作业流程进行舰面保障，舰载机航空保障
作业时间，不仅关系着舰载机的航空保障效率，而 且制约着舰载机岀动架次率［2］o 航空母舰甲板空间
固定，保障资源有限，作业环境多变，作业流程复 杂，作业要求髙效安全，这些也决定了舰载机机务 保障作业调度是舰载机岀动能力的关键影响
因素［3-4］o 舰载机的保障作业调度是在有限的甲板空
间和保障资源等约束条件下，为舰载机提供合理的 保障资源、保障次序和保障人员，以缩短舰载机的
牵引距离并减少保障作业的总时间，从而确保在舰 载机起飞之前完成保障任务［5］o
舰载机保障调度问题可以认为是资源约束的优 化调度问题，国外对该问题的研究经历了人工经验
调度、计算机辅助调度、智能决策和优化调度3个
阶段［5］。目前，对舰载机保障问题的研究主要集中
在计算仿真和智能优化方法。美国麻省理工学院计
算机科学与人工智能实验室开发了航母甲板作业规 划决策支持系统对舰载机保障作业调度进行智能决
策［6-7］。司维超等对9 ］使用智能粒子算法对舰载机
舰面布放调度方法进行求解，还利用多种协作混
沌智能算法对舰载机岀动调度问题进行研究；魏昌
全等［10-11］建立了连续和分波岀动2种方式的舰载机 航空保障调度模型，且认为要考虑航空母舰甲板空
间约束的影响；朱齐丹等［12］采用循环网络模拟技术
对舰载机航空保障资源进行了优化配置；王保乳 等［13 ］利用遗传算法设计了岀动任务下舰载战斗机
舰面布放方案；吕开东等［14］对舰载机航空保障的组
成和需求进行了分析，建立了开环排队网络模型，
获得了相应的目标参量；卞大鹏等［15］建立了甲板停 机位分配模型，利用贪心算法并结合模拟退火算法
进行了求解；韩维等［16］提岀了一种自适应混合差分
进化算法，用来解决舰载机多机一体化保障调度问
题；苏析超等［17-18］建立了舰载机多机舰面一站式保
收稿日期：2020-09-25；修回日期：2020-10-29
作者简介：王文鹏（1991 — ），男，河南人，硕士，从事飞机与发动机故障诊断、装备保障研究。E-mail: *****************。
•38•兵工自动化第40卷
障调度的数学优化模型，并使用文化基因算法求解；石颢等［19］建立了一种基于随机网路的保障流程模型，对舰载机航空保障活动逻辑关系与时间的不确定性进行了相关研究；杨炳恒等［2,20］建立
航空母舰模型了多机岀动甲板作业流程图和舰载机作业流程交通网模型并进行了验证；龙钰洋［21］使用自适应并行遗传算法对保障人员配置优化进行了研究，并通过案例对算法进行了验证；李梦龙等［22］使用改进禁忌搜索算法对舰载机保障作业调度模型进行了求解；李经等［23］建立了保障作业调度系统的数学模型，认为采用遗传算法能够有效地进行求解；宋璟毓等［24］采用单解的贪婪随机自适应搜索算法，对甲板航空保障作业流程进行了优化；范加利等［25］使用岛式并行遗传算法研究了双周期岀动模式下舰载机再次岀动准备的调度，并通过仿真算例进行了验证。
由于舰载机保障作业调度问题的重要性、复杂性和对实际作战的关键性，如何建立调度模型，并求解岀可行、高效的调度方案是十分困难的问题，给调度理论和调度实践带来了极大的挑战［26］o笔者在分析航空母舰舰载机保障作业方式的基础上，建立调度模型，使用基于自适应遗传算法进行求解，以典型多机保障任务进行验证。
1舰载机保障调度问题描述与分析
“尼米兹”级航空母舰，采用的是传统的多站式保障的方法。一个或多个保障工序有不同的保障区域，在保障过程中，舰载机在不同的保障区域进行移动转运，在不同的保障区间内完成保障工作。在保障过程中，舰载机在多个区域转移的时间不可以忽略不计。保障时间随着转移次数的增加而增加，会导致保障人员的工作效率下降，影响保障工作的整个进程。为了减少保障工作的时间，增加舰载机的岀动 架次，美国“福特级”航母采用了“一站式保障”方式。“一站式保障”概念最初来自全美赛车联盟［27］，对航空母舰来说，就是使用集成化的方式，在一站式保障区内完成加油、检测等保障内容，减少舰载机在多个区域转移的时间，从而减少保障时间，提高工作效率。采用一站式保障方式要在一个保障区内完成的保障任务比较多，需要的设备和装置相对集中，而航空母舰甲板的空间有限，在保障区内，装置和设备的紧凑使得保障人员的工作区间比较小，影响了保障人员的舒适度和操作的方便度。一站式保障配套的输油管铺设，设备的安装区间，都需要与航空母舰上其他设备间的位置进行协调和安排。在航空母舰上多个一站式保障区占用了更多的甲板区间，在甲板区间不变的情况下，对甲板调度作业质量的要求更高；因此，与“尼米兹”级航空母舰相比，“福特级”航母增加了甲板面积。
舰载机起飞前的保障作业有飞机的检查、添加润滑油及液压油和挂载导弹等。根据完成保障作业内容的不同，通常将保障人员分为机械、军械、航电、特设4个专业。机械专业人员的主要工作内容有检查添加发动机润滑油、添加液压油、填充氮气、添加燃油等；军械专业人员主要负责军械检查、装填炮弹、挂载导弹等；特设专业人员需要进行通电检查、充氧等；航电专业一般负责航电检查、设备通风等。每个保障专业下有一个或多个保障组，根据实际工作情况设置各专业的保障组的数量。每个保障组由可以完成相关专业任务的保障人员和相关的保障设备组成，每个保障组都可以完成所属保障专业的工作。结合保障模型的约束条件，单个舰载机保障流程如图1所示。
（人员密备就位）
加润滑油11军械检查］|通电检查］|航电外观检查］
加液压油11装填炮弹1111设备通风除潮|
T~~r^'_"I.....
\^\j j
|+「左翼屋载导弹||右翼屋载导弹|
加磁油|I「I
（检查验收）
图1单个舰载机保障流程
为避免在保障的过程中岀现混乱，考虑到安全问题，舰载机的各保障工序有一定的先后顺序。保障过程中，保障人员可能需要在不同的保障区中移动以完成任务，保障组的移动时间不能忽略不计。各保障工序的保障时间如表1［28］所示。
表1各保障工序作业时间
工序号工序名称
紧前
工序号
保障专业
保障时间/
min 1加润滑油—机械4
2加液压油1机械4
3充氮2机械3
4加燃油3机械18
5军械检查—军械6
6填装炮弹5军械8
7左翼挂载导弹6,10军械6
8右翼挂载导弹6,10军械6
9通电检查—特设7
10充氧9特设4
11飞机外部检查—航电10
12设备通风除潮11航电3
第1期王文鹏等：基于自适应遗传算法的舰载机保障调度•39•
2舰载机保障调度模型
为了建立舰载机保障调度模型，假设如下：一个保障组在同一时刻可以多个工序并行保障，一个工序在同一时刻只能接受同一个保障组；在保障组对保障工序进行作业的过程中不能停止；各个舰载机之间相互独立，各工序除流程图中先后工序外互不影响；保障组进行作业的时间是确定的，不考虑随机情况；不考虑突发故障和干扰因素的影响。将保障第一个工序开始的时间到最后所有舰载机工序完成的时间称为完工时间。保障调度的目标是将完工时间最小化，公式如下：
C=max(E#),1W i W m，1W j W n。(1)式中：C为完工时间；m为舰载机的数量；n为工序的数量；E ij为第i架舰载机第j个工序的完成时间。
F=min(C m a x)o(2)式中：F为优化目标；C max为最大完工时间。
用P’j表示第i架舰载机第j个保障工序，每个工序在同一时刻只能由一个保障组进行作业，每个工序都有保障组进行作业，公式如下：
M
工Y yt=1，W i W m，1W j W n。(3)
k=1
式中：Y jk为工序分组标记，当工序P j由第k个保障组进行保障时为1，其他为0；M为保障组总数量。
对于保障工序来说，开始时间加上保障作业持续的时间等于保障结束的时间，公式如下：
M
E v=S v+^Y j W i W m,1W j W n。⑷
k=1
式中：S j为第i架舰载机第j个工序的开始时间；T jk为由第k个保障组对工序P j进行作业所需要的时间。
保障组的作业顺序应该按照流程图中的先后约束进行，公式如下：
max(E#)W S tj，1W i W m,1W j W n,V h e B tj。(5)式中：B j为第j个工序的前序工序集；h为变量。
保障组在不同的保障区间进行转移需要的时间需要考虑，分配在同一保障组的工序要按优先级进行，公式如下：
E ij+W ie+R・X ijeg W E j+R1W i,e W m，1W j,g W n。⑹式中：W ie为舰载机i和舰载机e之间保障组转移时间；X ijeg为工序顺序标记，当工序P,J与工序P eg由同一保障组作业时，P j在P eg之前为1，之后为0；R是大于保障组转移时间的实数。
3基于自适应遗传算法的问题求解
舰载机多机保障调度作业具有复杂的流程约束、资源约束，保障工序比较多。舰载机的数量越多，问题的规模越大，导致传统的人工调度的效率越低，使用智能算法进行求解是一个值得考虑的途径。遗
传算法是通过交叉、变异、选择3个操作去除低适应度的个体，从而求得较优解，适合于求解复杂的优化问题，可以全局搜索和并行计算。传统的遗传算法采用了相同概率的交叉和变异操作，自适应遗传算法考虑到搜索和随机性之间的权衡，根据适应度值的不同动态改变交叉和变异的概率，从而实现快速到最优解，提高算法效率[29]o
根据舰载机保障调度作业的特点，避免产生非法解，降低编码的冗杂性，采用基于矩阵的实数编码的方式，如下式所示：
a11a12 (1)
a a21
a22…a2n A.q,1\(7)
A m,n=:::，
a i列1,Q+1)。(7)
_a m1a m2…a mn_
式中：如*”是编码矩阵；Q是可以对工序P ij进行作业的保障组的数量；矩阵元素a1｝的整数部分是完成工序P j对应的保障专业的第几个保障组。当不同的工序分匹配到同一个保障组时，在满足约束的条件下，根据矩阵元素a1｝的小数部分大小安排保障工序顺序。为了便于将染体进行交叉、变异等，将矩阵展平后的列表作为染体，染体的形式如[a11%2…a n a21a22…a2”…a m1a”2…％]。将每个染体作为行组合成种矩阵。
解码过程与编码相反，是将染体向调度方案进行映射的过程，可以将解码当作是对调度系统进行的仿真。在解码过程中，不单要考虑染体所携带的信息，还要满足保障工序前后的约束关系。每个保障组都生成一个保障表，根据染体携带的基因信息，将工序放入到相应保障组的保障表，并将保障表内的工序按基因的小数部分进行排序。采用离散时间仿真的事件调度策略，将保障工序分成正在保障工序集合、己完成保障工序集合和待保障工序集合。通过基于最早发生事件的时钟推进机制，更新3个集合，从而获得各工序的相关调度信息。相关步骤如下：1)将所有工序的保障表编号加入到待保障工序集；2)对待保障工序集中保障表的工序
• 40 •兵工自动化
第40卷
进行分析，如果无前序工序或前序工序则称为可进 行，将保障表中第一个可进行的工序加入到正在保
障工序集；如果该工序和保障表上一个取岀的工序
是同一架飞机，则将开始时间记为现在时间；如果 不是同一架飞机，则将现在时间加上飞机间的转移
时间记为开始时间，将该工序的结束时间记为开始
时间加上保障时间，将该工序加入正在保障工序集;
3）将现在的时间更新为正在保障工序集中所有工
序的最小结束时间，将保障工序集中结束时间早于
或等于现在时间的工序加入到己完成工序集，如果 该工序所在保障表为空，将保障表从待保障工序集
中弹岀，重复2）、3）直到所有工序保障完成。
初始种随机生成，将目标函数的倒数作为适
应度函数。使用赌策略和精英策略相结合的方
式来选择交叉和变异步骤所需的候选染体。使用
单点交叉的方法对染体每一基因进行处理，生成 一个随机数，当该数小于交叉概率时，对染体随
机配对，将随机生成的一个位置后的基因交换。生
成一个随机数，当小于变异概率时，染体进行变 异操作，选择一个随机位置，然后对该位置重新随
机生成符合编码要求的实数。为了不让遗传算法陷
入局部最优解，使低于平均适应度的个体去搜索空 间中查包含最优解的范围，将交叉概率和变异概
率设置为适应度相关的函数，如下式所示：
k 2
，
⑻
式中：代为交叉概率；/max 为种适应度最大值；仏 为种适应度平均值；k 1, k 2为参数，根据经验都设
置为1；广为交叉父亲母亲染体适应度最大值。
k f max f f > f
P _』k 「f ■―~f~~, f -人用。
（9）
厂m —〔 丿 max J avg
' 丿
|k 4, f V f avg
式中：P m 为变异的概率；f 为染体的适应度值；
k 3, k 为参数，根据经验均设置为0.5。
4计算结果分析
为了验证自适应遗传算法对舰载机保障调度模
型的求解效果，使用Python 3.6对基于自适应遗传
算法舰载机保障调度优化进行编程求解，并用实例
进行验证。在一次保障作业任务中，有10架舰载机
在等待进行起飞前的保障，可执行保障任务的有4 个机械保障组，4个军械保障组，2个特设保障组， 2个航电保障组，保障组在保障区之间的移动所需
时间为2 min ，保障工序、保障工序之间的约束关
系及每个保障工序的时间如上所述。
在进行自适应遗传算法求解的过程中，种规
模比较大，全局搜索能力好，但计算量大，收敛的 速度就越慢；种规模太小，容易收敛到局部最优
解。在编程中将种数量的大小设置成 100，交叉 概率和变异概率随适应度变化，迭代次数取500次。
对实例求解得到的调度方案保障全部完成时间为
79 min ，保障组调度计划甘特图如图2，飞机保障
计划甘特图如图3所示。
舰载机10舰载机9舰载机8
舰载机7舰载机6
舰载机5舰载机4
舰载机3舰载机2
舰载机1
f f
0 10 2030
40
时间/min
506070 80
图2保障组调度计划
甘特
第1期王文鹏等：基于自适应遗传算法的舰载机保障调度•41•
在图2中，甘特图上的编号为“舰载机编号-工序编号”，如“9-6”表示舰载机9的第6号保障工序。从图中可以看到：在该保障任务中，每组保障人员的工作时间相差不大，工作密度安排较合理，保障组在保障区间转移的平均次数为3.75次，转移次数较少，各保障组的工作安排可由图中得到。在图3中，甘特图中的数字表示舰载机的工序编号。从图中可知：舰载机的保障任务均全部完成，单个舰载机保障完成的时间梯度比较合适，有利于飞机次序进行接下来的起飞等任务。总之，自适应遗传算法获得结果符合设置的约束条件，方案可行。
5结论
针对舰载机多机保障作业的调度问题，笔者以最小化保障时间为目标，设计一种与之相适应的自适应遗传算法，采用甘特图的方式，直观地表示了保障作业的计划流程，通过对典型的多机保障任务案例进行分析，验证了自适应遗传算法在解决保障调度问题的可行性和有效性。该设计为航空母舰多机保障调度合理规划、快速编制舰载机保障调度方案提供了思路和参考。
参考文献：
[1]周晓光，赵仁厚，王述运，等.飞行甲板作业对航母舰
载机出动架次影响分析[J].系统仿真学报，2014, 26(10):2447-2451.
[2]杨炳恒，毕玉泉，张彪，等.航母多机出动甲板作业流
程研究[J].舰船电子工程，2016,36(8):150-152.
[3]US Naval Air Systems Command.CVN flight-hanger
deck NATOPS manual[R].Washington:NACYAIR
00-80T-120,2008.
[4]JEWELL A,WIGGE M A,GAGNON C M.USS Nimitz
and carrier airwing nine surge demonstration[R].US Navy:Center for Naval Analyses,1998.
[5]刘翱，刘克.舰载机保障作业调度问题研究进展[J].
系统工程理论与实践，2017,37(1):49-60.
[6]RYAN J C,CUMMINGS M L,ROY N.Designing an
interactive local and global decision support system for aircraft carrier deck scheduling[C].Proceedings of AIAA Information Technology,2011.
[7]MICHINI B,HOW J P.A human-interactive course of
action planner for aircraft carrier deck operations[Z].
AIAA,2011:1-11.
[8]司维超，韩维，史玮韦.基于PSO算法的舰载机舰面布
放调度方法研究[J].航空学报，2012,33(11): 2048-2056.
[9]司维超，韩维，宋岩，等.基于多种协作混沌智能算
法的舰载机出动调度[J].计算机应用研究，2013,30(2): 454-457.
[10]魏昌全，陈春良，王保乳.基于出动方式的舰载机航空
保障调度模型[J].海军航空工程学院学报，2012,27(1): 111-114.
[11]魏昌全，陈春良，王保乳.基于空间约束的舰载机航空
保障调度研究[J].控制工程，2013,20(4):699-702. [12]朱齐丹，吕开东，李新飞.舰载机航空保障资源优化配
置的循环网络模型[J].计算机应用，2013,33(11): 3276-3279.
[13]王保乳，司维超，薛建海.基于GA算法的舰载机甲板
布列方法[J].海军航空工程学院学报，2013,28(5): 571-576.
[14]吕开东，朱齐丹，李新飞.舰载机航空保障需求及排队
网络模型研究[J].飞行力学，2014,32(1):88-92. [15]卞大鹏，栾添添，米青超，等.
舰载机甲板停机位分配
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议