基于改进引力搜索算法的舰载机一站式保障作业优化调度方法∗

朱兴动 赵 洋 范加利 黄 葵

（1.海军航空大学 烟台 264001）（2.海军航空大学青岛校区 青岛 266041）

1 引言

集大量高新技术成果于一体的航空母舰已经成为评价一支现代海军作战能力的核心要素，在其构建的海上大纵深，多层次的攻防体系中，舰载战斗机扮演着一个重要的角色。而舰载机的数量及其出动能力也成为了衡量航母的综合作战性能的关键指标［1］。而航空舰面保障作业效率是影响舰载机出动回收能力的主要因素。制定高效可行的舰载机甲板作业度方案，对于提升舰载机舰面保障能力具有重要意义。

相关研究主要围绕传统的多站位保障与一站式保障两种不同的保障模式展开，而一站式保障模式相较于传统的保障模式极大地提升了保障效率，将会是未来航母所采用的主流保障模式［7］。一站式保障模式对舰载机保障作业的有序管理、分配提出了更高的要求，其中各项保障作业工序对保障资源的争夺冲突消解问题，以及如何对各舰载机的保障工序进行合理规划，避免再次出动准备各项保障作业间的相互干扰的问题尤为突出。但目前舰载机一站式保障调度的相关研究在以上两个方面仍有所欠缺，因此，本文对一站式保障模式的作业流程、资源约束特性以及不同的出动模式下各类舰载机的放飞优先级进行了系统性地分析，建立了舰载机一站式保障调度模型，并设计了一种适用于求解大规模作业调度，消解资源冲突的改进GSA算法求解该模型。最后，通过对“福特”级航母的典型出动案例仿真验证了算法的可行性和有效性。

2 模型建立

美国“福特”级航母首次引入了一站式保障模式的概念［8］，在飞行甲板右舷设置了18 个“一站式保障区”，所有“一站式保障区”的保障模块都进行了系统化的集成设计，集中设置了油、气、电、液等舰面保障设备。舰载机着舰并自主滑入保障站位后，按照作业流程有序开展机务勤务保障作业，主要包括添加燃油、补充氧气、航电检查、特设检查、机械检查以及军械检查等一系列工序，舰载机不需移动即可完成全部保障作业。一站式保障作业的节点活动网络图（Active On the Node，AON）如图1。

2.1 模型假设

假设1：舰载机按照给定的保障流程进行，保障工序之间有串行、并行和柔性关系；

假设2：任意舰载机的保障作业，对其他舰载机工序的完成没有影响；

假设3：进行再次出动准备作业的舰载机均满足一站式保障条件，能够在同一站位完成所有保障工序，不需调运；

假设4：保障人员的保障范围均可覆盖到全体保障站位；

假设5：航母的各类消耗性资源储存总量充足；假设6：不考虑突发故障和其他干扰因素。

2.2 参数设定

I={1，…，i，…，n} ：I表示待保障舰载机机群集合，n为当前需要进行再次出动准备作业的舰载机架数；V={(i，j)|i∊I，j∊Ji} 表示甲板作业集，即所有要执行的工序，其中Ji={1，2，…，|Ji|}为舰载机i(i∊I)的全部保障工序集合，| • |为集合中元素的个数；TX={1，…，i，…，tx} 表示甲板勤务作业调度时间序列；Oij表示舰载机i的第j项保障工序；Hi表示舰载机i(i∊I)的保障停机位；stij表示工序Oij的开始执行时间；edij表示工序Oij的结束时间；INit表示舰载机i(i∊I)在t时刻处于保障作业状态的工序集；Tij表示舰载机i(i∊I)完成第j项保障工序的持续时间；Qi表示舰载机i(i∊I)自主滑抵一站式保障停机位的时间；Wij表示Oij的紧前工序集合；Gp表示机务保障人员专业类型集合；Ge表示勤务保障设备类型集合；Gh表示保障工位空间类型集合；Gr表示航母甲板的供给性资源类型集合；Lrmk表示甲板的第k(k∊Gr) 类供给性资源最多可同时维持Lrmk个固定保障设备的运转；NS表示甲板一站式保障站位的数量。Npijk表示工序Oij所需的第k(k∊Gp)类保障人员的数量；Neijk表示工序Oij所需的第k(k∊Ge)类保障设备的数量；Nrijk表示工序Oij所需的第k(k∊Gr)供给性资源的数量；NHik表示舰载机i(i∊I)的第k(k∊Gs)类工位空间可同时容纳的机务保障人员数量；Lpk={1，2，…，|Lpk|}表示第k(k∊Gp)类机务保障人员集合；Lek表示第k(k∊Ge)类勤务保障设备；Wsij表示工序Oij的保障工位。

2.3 再次出动保障调度模型

甲板航空保障作业的调度起始点为一波次舰载机全部着舰并滑行至一站式保障站位。

2.3.1 目标函数

舰载机机群出动架次率是衡量航母作战及综合保障能力的常用指标［4，9］，而提高舰载机出动架次率的一个直接有效的途径就是缩短单波次甲板机务勤务保障作业完工时间。

各类甲板资源中，对保障效能具有决定性影响的主要为机务保障人员和保障设备的配置数量及其工作性能［5］，最终体现在保障完工时间的变化上。因此，调度模型的指标函数取为最小化一波次舰载机机群再次出动保障作业时间，即最小化最大完工时间：

依据优化目标定义决策变量：

2.3.2 约束条件

1）机务保障人员约束。任意时刻所有保障作业对某类专业人员的需求量不得大于该类专业保障人员配置数量：

2）甲板勤务保障设备约束：

此外，若同一架舰载机的两相邻工序分配在同一个保障设备上，那么后续工序无需等待前一个工序结束即可开始保障：

3）保障工序流程约束：

舰载机各保障作业开始与结束的时序关系：

4）保障站位数量约束：

5）工位空间约束：

6）资源供给能力约束：

7）资源需求与分配约束：

8）舰载机起飞优先级约束：

3 GSA算法设计

保障作业调度优化的最终目标是最小化一波次保障作业的最大保障完工时间，该问题可以抽象为具有NP-hard 特性的资源受限多项目调度问题（Resource-constrained multi-project scheduling，RCMPSP）［8］，目前解决此类问题的方法主要有引力搜索算法（GSA）、粒子群优化算法（Particle Swarm Optimization，PSO）、遗传算法（Genetic Algorithm，GA）等其他智能优化算法。研究表明，GSA 算法在优化调度［10］、数字辨识［11］等领域具有更好的简洁性和实用性，其寻优精度和收敛速度对比PSO、GA 等算法具有相当的优势［12］。因此，本文选取了GSA作为求解算法，但GSA 存在易早熟收敛，局部搜索能力差的问题［13］，故本文设计了一种改进的引力搜索算法（IGSA）来求解保障作业调度优化问题。IGSA的流程如图2所示。其中δ2表示粒子适应度方差，c为判断阈值。

图2 IGSA算法流程图

3.1 编码与基于SSGS的解码过程

3.1.1 编码

由于舰载机保障作业调度问题是离散的［15］，考虑到本文所研究的调度问题中包含三个子问题，即工序排序、保障设备分配以及保障人员分配，所以引入了二元任务链表，即为满足保障流程约束条件的作业序列编码。它由两部分组成，包括舰载机与工序。图3 给出了一个可行的二元任务链表示意图，其中第一行向量I表示舰载机编号，第二行向量J表示工序号，n、m表示舰载机机群所有工序数量。

图3 舰载机保障作业调度编码示意图

3.1.2 解码

根据资源需求生成调度方案需要利用调度生成机制（Schedule Generation Scheme，SGS）实现食物位置编码向调度方案的映射。SGS 有串联进度生成机制（Serial Schedule Generation Scheme，SSGS）和并联进度生成机制［16］（Parallel Schedule Generation Scheme，PSGS）。

Krüger 在研究中指出，SSGS 是具有活动性的积极的调度计划，而PSGS 生成的只是非延迟性的调度计划，且不考虑有限性资源的分配问题［17］。对于求解多资源约束下的最小化最大保障时间的问题，SSGS 能够较快搜索更为完整的解空间，鉴于此，本文基于SSGS生成调度方案，根据作业调度编码映射到调度方案，输出满足时序关系和资源约束的优化调度任务链表，进而得到各保障工序的最大完工时间即目标函数值、人员和设备的调度方案及其作业时序。在此过程中引入资源冲突消解策略［18］来引导算法产生积极调度计划。SSGS 以时间为阶段变量，共有J 个阶段。定义三个工序集合存在于在每一个阶段g 对应的调度时刻tg中：已完成工序集（Complete group）表示为Cg；可调度工序集（Decision group）表示为Dg；执行工序集（Active group）表示为Ag。在任意阶段g 中，引入了资源冲突消解策略和资源优先分配规则的SSGS算法包括以下步骤：

Step 1选取当前可调度工序集Dg中第一序列的工序，加入到执行工序集Ag中。为当前执行工序集中工序执行三层决策。

Step 2以Ag中当前执行工序的紧前工序的最大完成时间为时间变量的起始值，以1 个时间单位为步长向后步进搜索，直到某一时刻的保障人员、保障设备，工位空间以及消耗资源剩余量满足当前执行工序对保障资源的需求量，将该时刻设定为当前执行工序的开始时间stij，结束时间edij=stij+Tij。

Step 3按照保障人员与保障设备的分配规则为当前执行工序寻找当前时间点中符合规则的人员与设备，将stij至edij时间序列中的与置为零。

Step 4更新保障人员、保障设备、剩余资源和站位空间的信息。

Step 5将当前执行工序加入到已完成工序集Cg中并从Dg和Ag中删除，重复执行Step 1，直至可调度工序集合为空集，然后转入下一阶段，当Dg=∅，调度完成。

3.2 粒子位置更新策略

通过先例保全交叉法（Modified Precedence Preservative Crossover，MPPX）对当前全局的粒子位置进行扰动［19］。首先产生一个长度为n 的随机二进制矢量，其维数相当于任一粒子位置全部工序矢量的长度，用于选择。粒子元素以生成新的粒子位置。其中0和1分别代表第一个和第二个粒子位置。这些数字代表元素从食物位置中移除并放入新粒子位置向量的顺序。从左边开始，根据随机矢量的顺序选择一个元素，并从两个食物位置矢量中移除，然后放入一个新的食物位置，直到两个食物位置向量都为空。

其次，针对保障作业调度这种大规模RCMPSP问题难以跳出局部最优的特性，引入一种基于子拓扑工序网的变异策略［20］，以产生更大的邻域变换范围，防止算法早熟收敛，提高种群的多样性。变异策略主要步骤如下：

Step 1在当前种群中按概率Pm 选取执行变异操作的食物位置向量集合，提取单一向量Re-Chrom执行步骤2；

Step 2在ReChrom 中随机选择一个操作点P∊[1，|Ji|-len]，其中len 为重排子向量（即子任务链）的长度，选取P 至P+len 位的向量记为nC，并记录P 和P+len 位在ReChrom 中位置LocP与LocP+len；

Step 3将nC 中的工序按照舰载机保障流程AON 图的作业工序约束关系构造所选取子向量的AON 子图，依照子图的约束对子向量进行随机重排；

Step 4用重排后的子向量（即子任务链）替代ReChrom 中[LocP，LocP+len]区间内的向量，构造出新的食物位置向量。

为进一步减少算法迭代的时间，提高算法收敛速度，在执行完交叉、变异扰动后，计算当前所有粒子的适应度值，并选取部分最优解作为初始解执行禁忌搜索［21］，算法主要流程如下。

步骤1接收初始解，作为当前解，将该粒子位置加入禁忌表；

步骤2创建当前解的候选解解集（邻域解解集）；

步骤3在候选解解集中选择目标函数值最优且不在禁忌表中的解，作为新的当前解；

步骤4新的当前解加入禁忌表，并更新禁忌表，判断此时是否满足终止条件，若是，则继续执行下一步，反之则转至步骤2；

步骤5输出搜索到的最优解，即最优粒子位置。

4 仿真分析

4.1 案例构建

本文基于“福特”号航母甲板保障资源配置情况构建舰载机机群保障仿真案例，航母右舷的一站式保障区最多可停放20多架舰载机并能同时为18架舰载机提供各种保障，其中一站式保障站位编号分别为1～18，本文构建了一个舰载机机群双周期连续出动保障案例，对8机和12机轮转两种出动模式进行调度仿真，表2 给出了不同作战模式下的各类型舰载机的起飞优先权；作战任务需求设定为预警机、电子战飞机、空对地打击战斗机以及护航机。舰载机编号为1～12，只采用甲板的一站式保障区。任一舰载机i的单机保障工序流程如图1所示，其中编号1 和编号19 为虚拟开始/结束工序。各保障工序对保障资源的需求和执行工序的时间参数情况以及保障设备的覆盖范围由于篇幅限制，未在文中给出。

表2 不同作战任务下的舰载机起飞优先权

4.2 仿真结果

仿真案例采用的硬件平台为Windows11 操作系统，Intel（R）Core（TM）i7-12700K CPU，3.61GHz主频，32G 内存，Matlab R2022a 仿真软件。经多次实验对比分析，最终设定的算法参数为算法的种群规模N2=50，引力系数G0=50，粒子加速度α=10，迁移因子MF=15，变异概率Mutation（m）=0.2，交叉概率Crossrate（c）=0.2，贪婪搜索概率TSrate（s）=0.4，算法整体最大迭代次数T=300。

12 机轮转模式下任务C 的最大保障完工时间随下层迭代的曲线如图4 所示。最终求解得到的任务C 的再次出动保障作业的保障人员和保障设备的最优调度方案如图5 和图6 所示。其中，横坐标表示再次出动准备作业中一波次保障过程的时间轴，图5 纵坐标Gpk-l代表第k 类专业中第l 个保障人员。图6 纵坐标Gek-l代表第k 类第l个保障设备。

图4 最大保障完工时间收敛图

图5 任务C的保障人员最优调度甘特图

图6 任务C的保障设备最优调度甘特图

5 结语

针对一站式保障模式下舰载机保障作业调度问题，对舰载机再次出动保障任务的流程、保障资源约束进行了系统性的分析，建立了一站式保障调度优化模型，进而设计了一种改进的引力搜索算法用于该问题的求解。引入了融合资源冲突消解策略的串行进度生成机制来生成调度方案并解决作业调度过程中的资源争夺问题；采用MMPX 交叉法、基于子拓扑网络的变异策略以及禁忌搜索，提高算法的寻优能力。

最后通过对“福特”级航母舰面保障调度典型案例的仿真分析，验证了本文所提模型和求解算法在一站式保障作业调度优化问题中具有良好的求解性能，表明了算法的有效性和可行性。