基于工作日志表的舰载机甲板作业优化调度算法∗

朱兴动 孟杨凯 黄 葵 范加利

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

1 引言

航空母舰是以舰载机为主要武器并作为海上活动基地的大型水面战斗舰艇、海军水面战斗舰艇的最大舰种。航母战斗力集中体现在舰载机群的战斗力，航母舰载机起飞前，需经过甲板系列保障工序，但受制于航母甲板保障资源与空间资源有限，保障过程的高度时间紧迫性，甲板保障调度成为影响航母战斗力的重要因素。

针对此类资源受限、作业顺序不确定、工序数量不确定等含多重不确定性因素的保障调度，属车间柔性作业，是典型资源受限项目调度问题（RCPSP）。针对目前航母甲板调度领域研究多具有工位实际约束考虑不足及因工位约束带来的衍生影响考虑不足的缺陷，本文通过对工位约束进行全面分析，包含保障资源服务工位范围限制、基于甲板实时工位状态的作业持续时间不同、机位占用、因初始工位不同而导致的保障工序需求数量不同、保障小组机位间转运调整时间等，形成符合实际作战条件的数学调运模型，设计出适合解决复杂工位约束限制的甲板调度算法。最后以库兹涅佐夫号航母上12机出动准备作业为例进行验证。

2 航母甲板保障作业调度模型

2.1 航母甲板保障作业描述

俄罗斯“库兹涅佐夫”航母舰面共33个停机位，3个滑跃起飞位。航母舰载机出动前，共需进行检修、加油、挂单、牵引至暖机位（由机位可否进行暖机工作决定工序是否存在）、惯导对准、暖机等工序，最后滑行至起飞位，完成起飞，具体过程如图1所示。

图1 舰载机甲板保障工序流程

工序说明:

工序0:舰载机、保障组停靠机位初始状态

工序1:加油

工序2:挂弹

工序3:牵引至暖机位

工序4:惯导对准

工序5:暖机

工序6:滑行

工序7:起飞

工序8:机务检修

其中，工序3牵引至暖机位若因舰载机机位具有可暖机属性，即可无需此工序，由工序1、2完成后进入工序4；受安全管理性约束，舰载机的加油、挂弹和牵引至暖机位三项任务，不可同时进行，但可不分先后，惯导对准、暖机、滑行、起飞四项任务必须依次执行。工序8机务检修伴随勤务保障全程进行。

甲板保障调度作业的目标，即需依据甲板各保障小组初始所在工位、舰载机初始停放工位、甲板工位距离矩阵、各保障小组移动速度、舰载机甲板转运速度（若含此工序）、各保障点可服务机位范围列表、各机位飞机占用，生成基于目前甲板状况的全部飞机起飞完毕的最小化全部保障时间的最优调度方案。

2.2 甲板调度约束分析

1）飞机加油、挂弹、转运三项任务不可同时进行，但可不分先后。

2）惯导对准、暖机、滑行、起飞四项任务必须依次执行。

3）根据机位属性，为可暖机机位/不可暖机机位，若飞机所处不可暖机机位，惯导对准前需由转运小组转运至可暖机机位。

4）甲板共设9个加油保障点，各保障点具有不同数量的可保障机位范围，不同保障点可保障机位可具有重复，保障点对可保障机位范围外的飞机无效（不可保障）。

5）根据飞机转运工序的完成，所在机位产生变化。对后序工序的机位选择产生实时变化、加油保障点可保障范围内的飞机及其所在机位产生实时变化。

6）机位当前占用情况下不可作为转运目标机位。

2.3 调度模型建立

本文研究模型调度初始起点:舰载机均在甲板机位停靠，不考虑机库飞机转出、飞机任务完毕甲板降落。因机务检修工作伴随舰载机多项工作同时进行，无需单独进行工序安排，故不考虑在内。

模型内相关参数定义如下:F为目标函数，Cmax为一波次舰载机完成所有工序的最大所需时间，航母甲板舰载机数量为I，各舰载机表示为i∈｛1，……，I｝，每架舰载机i均有工作集Vi，其中Vi=｛J1，……，Jj｝，j为作业数量；Vnr为非资源需求的工作集，Vrs为特定资源需求工作集，Vra为不定资源需求工序集，任一工作Jj必包含在内。Vs为不可同时执行的作业集，包含加油、挂弹、转运；Tij是舰载机i完成作业工序j的时间，stij为第i架舰载机第j项作业的开始时间，stij≥ 0，edij为第i架舰载机第j项作业的结束时间；dij为第i架舰载机第j项作业的持续时间；作业过程不可中断，edij=stij+dij；Ci为舰载机i完成最后一道作业，即起飞的时间；yijk=1为第i架舰载机第j项作业开始；dmini是第i架舰载机任务mi、ni开始的时间间隔；Njk是在某一时刻k，执行作业j的可用甲板资源数量。

模型中，式（1）为目标函数；等式（2）、（3）为保证每架舰载机同一工序只执行一次，不可重复执行；不等式（4）为工序作业的时序优先级关系，针对作业T中惯导对准、暖机、滑行、起飞四项任务必须依次执行。不等式（5）确保不定资源约束型作业对甲板资源的需求小于甲板资源总量。不等式（6）确保加油、挂弹、牵引至暖机位三项工作中的任意两项不可同时执行。不等式（7）表示机位转运可行性。

3 模型求解算法

保障资源受限，工序数量不确定的柔性资源受限项目调度问题是典型NP难题，当前已证明禁忌算法是解决该类问题最优算法之一。本节阐述求解调度算法主要内容，包含禁忌算法结构思想，编码方案、算法邻域结构设计、初始解优先规则设计及实现过程、算法解的优化方案设计等内容。求解算法侧重于对现有数据数值的调度算法构思、实现，忽略算法数据数值的获取，实际应用中可采用经验数值。

3.1 禁忌算法

模型优化过程采用禁忌算法，禁忌算法具有很强全局搜索能力，并可避免优化结果局部最优。禁忌算法的基本思想是在搜索过程中将近期历史的变换过程放入禁忌表中（Tabu List）中，阻止重复变换，即可有效避免搜索循环。禁忌表模仿了人类记忆功能，为元启发式算法之一。

3.1.1 禁忌算法编码方案

算法编码采用顺序编码方式，由1～n数字组成，分别代表第1至n种工序，此种编码方式优点在于同一染色体内不可出现数字重复，即Xi=｛x1，x2，……，xj｝，xj∈｛1，2……，n｝，且当m≠n时，xm≠xn，编码的不同数值代表不同保障工序，先后顺序代表工序执行顺序。例某架飞机编码为Xm=（2315476），即舰载机甲板保障调度按照各数值所代表工序顺序进行。

3.1.2 禁忌算法邻域结构设计

算法邻域结构是算法寻优过程中计算目标函数值所依据的拓扑结构。算法解由矩阵编码组成，矩阵编码以行为单位成为各调度单位的调度执行方案，如m*n矩阵可代表甲板m架舰载机分别包含的n道工序甲板调度方案，或可代表甲板m个调度小组分别对n架舰载机保障的保障调度顺序。算法邻域结构采用首先获取解的任意两行行排列组合方案，其次完成各行之间任意数字两两交叉变换的策略，组成各算法解的邻域结构。因算法采用顺序编码，针对数字交叉可造成的同一调度单位内数值缺失与数值重复引起的编码非法，如同一舰载机工序调度方案中同时含两个“3”工序或缺少“1”工序等，数值交叉变换采用部分映射交叉（PMX）方式完成。部分映射交叉（PMX）步骤如下:

1）选择A编码的交换数值x与B编码的交换数值y；

2）确定交叉点数值映射关系，即x—y；

3）将A编码的x数值由y替代，同时将A编码原y数值由x替代；

4）将B编码的y数值由x替代，同时将B编码原x数值由y替代。

针对算法解共含m*（m-1）/2个行排列组合方案，邻域结构为完成全部行排列方案的全部两两数字对应变换。例:选取第一行与第二行，完成第一行的第一个数字与第二行的第五个数字交叉，结果如图2所示。

图2 邻域结构算法示意图

3.2 基于优先规则初始解的生成

初始解的生成规则基于优先级索引策略，具体规则如下。

1）对于加油类受资源保障服务范围限制资源，各保障点优先保障服务范围内距离最近舰载机。

2）对于转运工序受目标机位资源空余限制类保障，各转运组优先选择距离最近舰载机及距离舰载机最近暖机位资源。

3）因转运工序消耗时间资源少，加油类资源受保障服务范围限制，舰载机优先进行加油工序。

4）在甲板范围内尽可能保持各类资源均匀分配。

针对此优先规则，算法实现过程具体如下。

1）扫描甲板停放飞机信息，进行飞机编码，并获取停放机位，得到planeinformation表依据停放机位的暖机属性信息可知每架飞机转运需求，得到每架飞机保障工序数量。

2）设计endtime表，记录所有保障小组的当前工作的完工时间，每种保障工序独立成行，表格初始化为0。

3）获得endtime表中当前完工时间最小保障小组。

4）若保障小组有服务飞机，检查该机是否满足完成惯导对准前所有工序，若满足，安排后序工序进行起飞，完成起飞数量FLY+1，并释放当前所在可暖机机位。

5）选择该保障小组保障范围内距离最近的未进行过此项工序且未正在保障作业的舰载机进行工作，若存在满足条件舰载机，have阈值为1，否则为0。若为转运工序，需额外增加选择空余可暖机机位中最近机位步骤，若无空余，have阈值为0。

6）have阈值若为1，进行后续步骤，否则该保障小组endtime+60，进行延迟选择，转步骤3）。

7）对各保障组工序种类完成数量sum+1，对保障飞机编号进行工作日志worklist更新。此表按保障工种成行，依开始时间顺序记录保障飞机编号，如图3所示。

图3 工作日志表worklist示意图

8）更新 endtime=endtime+tmove+twork。tmove为保障小组从上个保障工位到此保障工位的移动时间，twork为此次保障持续时间。

9）若为转运，更新planeinformation表中飞机转运完成后所在机位信息，更新空余可暖机机位信息。

10）更新保障小组当前所在机位、正在保障服务飞机编号，更新各飞机各工序开始时间、结束时间。

11）转步骤3），直至甲板所有舰载机完成起飞。

3.3 基于邻域结构解的目标函数值计算

在得到算法优先规则初始解或基于邻域结构算法解后，需对算法解进行目标函数值计算，作为算法优化过程优化依据。算法解的目标函数值计算依据甲板信息（含飞机编号及停靠机位、机位属性）、保障小组信息（含所在机位及当前工序结束时间endtime，初始化为0），依照工作日志worklist安排工序进行，具体算法如下。

1）获得endtime表中当前完工时间最小保障小组。

2）若保障小组有服务飞机，检查该机是否满足完成惯导对准前所有工序，若满足，安排后序工序进行起飞，完成起飞数量FLY+1，并释放当前所在可暖机机位。

3）保障小组从工作日志中当前工种的第一个飞机编号开始，选取未进行过此项工序的保障飞机进行保障工序安排，have阈值为1，否则为0。若工种为加油，则需添加额外条件满足此加油保障点保障范围内机位。若为转运，需添加额外有空余暖机位条件。

4）若have阈值为1，进入后续保障工序安排，否则转步骤2）选下一最小endtime保障小组。

5）计算保障前保障小组工位间转移所需时间tmove，TSij=endtime+tmove，TEij=TSij+tij，endtime=TEij，若飞机当前有正在进行保障工序，TSij=TEij-1，TEij=TSij+tij。

6）更新保障小组当前所在机位、正在保障服务飞机编号，更新各飞机各工序开始时间、结束时间，记录各飞机各工序执行记录，若为转运，更新planeinformation表中飞机转运完成后所在机位信息，更新空余可暖机机位信息。

7）转步骤2），直至甲板所有飞机完成起飞。

3.4 解的优化方案设计

算法解在完成目标函数值计算后，需对算法解按算法邻域结构生成新的算法解方案，用于计算新的目标函数值，成为算法迭代中算法解自适应优化的过程。甲板保障小组依靠worklist调度，直至全部保障流程完成。因此工作日志成为算法目标函数值计算依据及算法解及算法解优化过程依据。故优化方案针对工作日志worklist执行。worklist各行数值分别代表不同工序种类依次进行保障服务飞机的顺序。解的历代优化通过实现对工作日志worklist按3.1.2邻域结构算法完成数值对应变换。

依工作日志worklist生成优化算法邻域结构过程中，针对工作日志出现两行数量不一致情况，如10号飞机需加油工序却无需转运工序，则加油一行中含10编号，转运无10编号，实行如下解决方案:选取两行各自交叉编号时，检查对立行有无该编号，若无或两行选取编号相同，则跳过。

通过此邻域结构算法完成解的优化方案迭代可解决加油、挂弹、转运等工序在初始解中优先安排顺序对整体方案的影响，同一工序不同小组在优先规则中的选择对优化方案的影响、调度过程可能出现的保障小组暂时等待对整体调度方案的优化，不同舰载机因转运时序不同而选择的不同暖机位对整体优化调度的影响等问题，实现完全依靠算法自动寻优，实现调度算法的优化。

4 案例仿真

以库兹涅佐夫号航母为例。对航母甲板舰载机出动调度仿真，设舰载机以双周期连续出动为背景条件。设甲板初始停机数量为12，对全部舰载机进行调度运算。仿真过程中假设所有舰载机均无故障、保障点均无故障。工序保障时间取值如下:加油26min，加油保障小组甲板移动速度1m/s、挂弹25min、挂弹保障小组甲板移动速度1.5m/s、转运保障小组甲板移动速度1.5m/s，加车后舰载机甲板转运速度0.7m/s、惯导对准13分钟、暖机5min、滑行1min、起飞1min，加油保障小组NJY=9，挂弹保障小组NGD=3、转运保障小组NZY=4。

初始状态甲板舰载机停放信息如表1所示。

表1 甲板舰载机初始状态信息

图4 甲板舰载机优化调度方案甘特图

仿真通过Matlab 2014a实现基于表1信息的航母甲板12机出动进行调度方案优化，优化调度方案结果甘特图如图4所示，甘特图中，灰色部分为当前舰载机工序进行前，保障小组由前一舰载机完成后转移至当前机位所需移动时间。1～7数字代表相应保障工序。

优化后执行结果各舰载机转运记录如表2所示，其中2、10、12号舰载机初始机位具有可暖机属性，无需转运。

表2 甲板舰载机优化调度方案执行完成转运记录

5 结语

本文针对库兹涅佐夫航母舰载机以连续出动模式进行批次出动的甲板舰载机保障作业调度问题，通过分析甲板作业流程、资源约束条件和工位约束限制，以出动的最短准备时间为目标，建立了优化计算模型。在此基础上，采用禁忌算法框架设计了考虑充分工位约束限制的调度求解算法，通过以库兹涅佐夫航母为背景的仿真计算验证了算法的有效性，且算法获得的调度结果能够被甲板调度专家接受。