一种航母甲板作业快速调度算法

朱兴动，范加利，王 正，赵宏强

(1.海军航空大学，山东 烟台 265200；2.海军航空大学 青岛校区，山东 青岛 266041)

0 引 言

舰载机在航母甲板上的起降一般分波次循环进行，按循环方式分单周期、双周期等，循环间隔受舰载机制空时间影响，美军历次演习证明，航母航空保障作业中，双周期循环出动能够提高舰载机的出动强度，而双周期连续出动的制约因素主要在于舰载机制空时间和舰载机再次出动准备时间的匹配。在循环出动模型下，留给舰载机进行再次出动准备的时间非常有限，美国海军1997 年对尼米兹级航母进行高强度出动演习表明，当循环周期为1 h 45 min 时，平均可用甲板作业时间仅为57 min。因此，在舰载机和航母设计定型后，如何优化配置和合理安排批次舰载机的再次出动保障工作对于提高航母舰载机出动强度的提高具有非常重要的意义。

受作业完成时间的不确定性、舰载机及保障装设备故障的随机性、作业环节的多态性等因素的影响，涉及多架舰载机、多种保障资源的舰载机再次出动作业的调度问题属于典型的动态调度问题。近年来，国内学者在该领域进行了大量的研究工作，针对该问题常用的方法是建模仿真方法[1-2,6]、最优化方法[3]，以及基于专家方案的逆向强化学习方法等[4]。但多数文献中仍以静态调度为研究基础[5,7]，通过提高调度结果的鲁棒性和自适应性来增强调度系统（算法）对动态、随机环境的响应能力，避免频繁重调度。基于仿真的研究方法计算时间偏长，对于实时重调度的适应能力较弱。

图 1 舰载机再次出动准备作业时序Fig.1 The sequence diagram of carrier aircraft turnaround operations

针对航母舰载机甲板航空保障作业的调度问题，本文在对调度作业指挥人员实际需求分析的基础上，重点研究了双周期出动模式下舰载机再次出动准备的调度问题，建立了舰载机再次出动准备的优化计算模型，并设计一种适用于动态甲板环境的基于启发式禁忌搜索的快速求解算法，最后以库兹涅佐夫航母上8 机双周期再次出动准备作业为例进行验证。

1 舰载机再次出动保障任务调度模型

1.1 舰载机甲板作业描述

俄罗斯 “库兹涅佐夫” 航母是一种采用滑跃方式起飞的中型航母，通常搭载苏-35 飞机作为主战舰载机。航母设计阶段，通常将飞行甲板分为若干功能区域，并在各区域设置多个站位，受空间及站位配置资源的限制，“库兹涅佐夫” 航母上，舰载机着舰后必须先滑行至临时停机位，而在起飞前则必须牵引至暖机位进行惯导对准、暖机、飞控系统自检等作业，随后依次滑行至起飞位起飞。舰载机再次出动准备的作业流程如图1 所示。

对于任一架舰载机，图中作业集 TS1中的加油、挂弹和牵引至暖机位作业的执行顺序可任意调换，但受技术和管理性约束，对于某一架飞机这3 项作业不能同时进行； 作业集 TS2中的惯导对准、 暖机、 滑行、起飞任务必须依次执行；再次出动机务检修（飞机后的检修、视情添加辅助油料、充氧充氮等）作业可与作业集 T S1和 T S2中的部分作业并行执行。

上述诸多作业中按照对甲板资源的需求类型可分为特定甲板资源、不定甲板资源和无需资源作业。对于加油作业，每一停机区能够同时加油的舰载机数量受该区加油站数量的限制；对于挂弹作业，受甲板配置的挂弹小组数约束；对于转运作业，除了受转运小组数量约束外，还受空间路径约束；机务保障受机务保障小组数量约束，因机务作业可与加油挂弹并行作业，此处忽略该约束；惯导对准、暖机等作业受甲板可用暖机位数量的约束；滑行作业可视为不需甲板资源作业类型；起飞作业受起飞站位数量的约束，对于库兹涅佐夫航母，每一时刻只能起飞1 架舰载机。

1.2 舰载机甲板作业调度的数学模型

模型中以一波次舰载机全部着舰滑行至临时停机位为甲板航空保障作业调度起始点，不考虑再次出动机务检修工作所需资源和用时。相关参数定义如下：舰载机 i ∈{1,···I} ， I为当前要需进行再次出动准备的舰载机架数；作业j ∈V，对于每一架舰载机，其甲板作业集，Ji为第i架舰载机需要执行的保障作业数量； Vnr， Vrs和 Vra分别代表非资源需求、特定资源、不定资源作业集。每一任务j 也属于一个任务类型集 Ej，如果是非资源需求任务它等于j，并且包括所有需要同类资源的作业。注意到仅一种特定资源型任务存在于 Vi中，即起飞。 Vs表示由于安全原因不能同时执行的作业集，如对同一架飞机的加油和挂弹作业； Tij是舰载机 i 完成作业工序 j的时间，对于任一飞机的任一作业，因人员作业效率、加油量、挂弹种类及站位分布的不同，其作业时间不完全相同，但可根据统计任务持续时间的均值和3σ 之和作为该时间值，这种取值方法可以提高调度计划的鲁棒性； stij、edij分 别表示第 i 架舰载机第 j项作业的开始时间和结束时间； k ∈{1,···,K} 为调度时间序列； yijk∈{0,1}，当k = stij时 yijk= 1， 表 示 k 时 刻 第 i 架 舰 载 机 第 j项 作 业 开始； Ci为舰载机完成最后一道作业（起飞）的时间；每一飞机的顺序作业型任务用带权图 Gi=(Vi,Ai)表示， 其中dmini是使得任务ni开始的时间间隙， Sni与任务 mi的开始时间相关，Smi满足不等式为本波次再次出动准备时间； Njk是在某一时刻 k，执行作业j的可用甲板资源数量。

调度模型的目标函数取为最小化本波次舰载机的再次出动准备时间：

约束条件为：

式（2）和式（3）联合确保每一作业必须只被每一架飞机启动一次，带有仅单一资源的特定性任务需要额外执行要求的作业通过式（ 3） 强调。 不等式（4）确保作业期间的时序优先级条件，该不等式主要针对作业集 TS2。不等式（5）确保仅有有限数量的甲板资源被用于完成不定资源约束型作业，不等式（6）确保对于每一架飞机没有2 个可以导致安全问题的作业同时进行，不等式（7）表示调运可行路径约束通，其中 ZWi1表 示舰载机在甲板的停机站位， Hs表示舰艏区域站位集合；Xzwp表 示站位的 x坐 标， jzy表示转运作业.

2 求解算法

若将待保障的舰载机视为工件，将保障资源视为加工机器，则舰载机循环出动的再次出动准备作业调度模型可视为具有工序顺序不定、加工时间不确定的柔性车间作业调度问题，该问题属于一类NP-难解问题，时间复杂度为因其解空间搜索量巨大，很难获得精确的全局最优解。禁忌搜索已经被证明是解决该问题的较好算法，但基本禁忌搜索算法容易陷入局部极小，且初始解选取不同，最终得到的优化解的质量也存在差异，为解决该问题，本文采用迭代搜索，在算法中加入简单的摄动策略，来帮助搜索跳出局部最优[8]。

2.1 算法总体框架

迭代禁忌搜索算法从某一局部极小值开始，重复地使用摄动策略使之逃离该局部极小值，并基于禁忌搜索算法去寻找另一局部极小，直到满足停止条件。解的接受标准决定新的局部极小值是否被接受，还是继续从一些以前访问过的解继续搜索。迭代禁忌搜索算法的总体框架如下：

步骤1function ITS（），

步骤2基于启发式规则的初始解→s，

步骤3s←tabuSearch（s），

步骤4for ii = 1，…，maxIT do，

步骤5s′←perturb（s），(s′,i)

步骤6s←tabuSearch ，(ii/maxIT)2s∗

步骤7以概率1- 接受：s← ，

步骤8end for，

步骤9返回搜索中发现的最优解 s∗，

步骤10end function。

在该算法中，在第 ii次迭代结束时，新解以概率1−(ii/maxIT)2被接受。否则搜索继续从当前的 s∗开始，该值在搜索中被更新，并最终返回。接受标准被选择在开始时分散搜索，而在最优解附近强化搜索。

2.2 基于启发式规则的初始解生成

初始解的生成规则基于优先级索引策略、先到先服务和舰首区舰载机优先原则生成，具体规则如下：

1）对于挂弹、转运作业类受限保障资源，优先分配给甲板首区停机位上待保障的舰载机；

2）对于加油作业，按照区域，首先进入该区域停机位的舰载机优先接受加油服务；

3）对于转运作业，每一区域需要转运的舰载机，按照后进先出的顺序依次转运；

4）在满足相关约束条件的前提下，尽量避免长时间占用着舰跑道；

5）在甲板范围内，尽可能保持各类保障资源的负担均匀。

2.3 约束条件的处理

舰载机再次出动作业调度问题的约束条件比起一般的车间作业调度问题更为复杂，主要体现在 TS1作业集中的任务无固定作业顺序，调运作业存在某些空间约束等。在实施搜索过程中，不判别解的可行性，而是对违反约束的解的工序之间插入时间间隙作为惩罚。以挂弹作业为例，具体算法如下：

步骤1function C aldt （）；

步骤2记录没架飞机第j 到作业工序为挂弹作业的飞机数为tgd，自增；

步骤3取当前舰载机作业工序j 的上一工序结束时间→T empJ；

步骤4若当前为所有飞机的第一道作业工序，且tdg ≤NGD（ 挂弹资源约束），则 d t = 0 ， 否则 d t = tgdd，tgdd为 d 区域的预计挂弹作业时间；

步骤5当前已安排挂弹作业的飞机数量 n gdTask ，并将其预计结束时间按从小到大排序；

步骤6若当前非第一道作业工序，且n gdTask ＜NGD，则 dt = 0 ， 否 则dt = max{tmpTgd(ngdTask −NGD+1)}−tempJ,0。

2.4 领域构造策略

领域结构是对初始解进行一次移动操作而获得另一个解的机制。在禁忌搜索算法中，领域结构直接影响禁忌搜索算法的搜索效率[9-11]。因舰载机再次出动甲板作业中，对于每架飞机集T S2中的作业优先顺序固定，保障作业时间主要受各架机 TS1集中3 个作业工序安排顺序的影响。为了兼顾搜索时间和解的质量，本算法中采用2 种领域，第1 种结构在启发式初始解的基础上，依次对每架飞机 TS1的作业顺序进行交换和插入移动（3 个工序共可进行5 次移动）；第2 种领域结构是在摄动函数中对待保障的所有 I 架舰载机 T S1集的第 j道作业工序进行约束条件检验，并按最小违背原则进行移动。

3 算例仿真

以库兹涅佐夫航母为实例，对8 机双周期连续出动模式下的舰载机再次出动保障进行调度仿真。甲板初始停机数设为16 架，假设连续出动过程中所有舰载机均无故障，舰载机各作业工序的时间取值如下：加油时间tjy= 18 min ； 挂弹时间取为[ tdgstgdztgdzwtgdyw]=min ；转运时间 tzy= 7 min；惯导对准时间 tdz= 8 min ；暖机时间 tnj= 8 min；滑行和起飞时间分别为 thx= 1 min 和 tqf= 1 min。 挂弹小组数NGD= 4； 转运组数 NZY= 3。算法基于MATLAB R2014a实现，计算机配置为2.4 GHz 主频，8 G 内存，Win7系统。文中算法（I-TB) 与模拟退火（SA）算法、普通禁忌搜索（TB）算法以及全局搜索算法的计算结果如表1 所示。表中耗时是指获得优化解的用时，时间差别主要因算法收敛速度引起。文中算法解的收敛曲线如图2 所示，8 机出动模式下的作业调度甘特图如图3 所示。图中矩形内数字表示飞机号×100+作业序号，作业序号1～7 依次表示加油、挂弹、转运、惯导对准、暖机、滑行和起飞。

从仿真结果可以看出， I-TB 算法、 SA 算法、TB 算法较全局搜索算法的搜索效率均有非常显著的提高，其中I-TB 算法搜索时间最短；在解的质量方面，全局搜索算法可获得全局最优解，其他3 种算法均无法保证获得全局最优解，但I-TB 算法与TB 和SA 相比解的质量更高。从调度算法输出的甘特图上看，算法结果能够获得调度专家的认可。

表 1 算法性能对比Tab.1 Performance evaluation of algorithms

图 2 I-TB 算法收敛曲线Fig.2 Convergence curve of I-TB algorithm

图 3 8 机再次出动准备调度时序图Fig.3 Turnaround operations scheduling diagram for 8 carrier aircrafts

4 结 语

本文针对双周期连续出动模式下的舰载机舰面保障作业调度问题，通过分析作业流程和资源约束条件，以优化批次飞机最短再次出动准备时间为目标，建立了优化计算模型。在此基础上，采用迭代禁忌搜索算法框架设计了一种基于启发式初始解的快速求解算法，并给搜素过程中的约束条件处理测量和领域构造策略。通过以库兹涅佐夫航母为背景的仿真计算验证了算法的有效性，且算法获得的调度结果能够被甲板调度专家接受。