基于禁忌算法的舰载机甲板作业动态调度优化算法

范加利, 黄 葵,*, 朱兴动, 孟杨凯

(1. 海军航空大学青岛校区航空保障与场站管理系, 山东 青岛 266041; 2. 海军航空大学, 山东 烟台 264000)

0 引 言

航空保障作业调度是指在航母甲板提供的有限资源下,多架舰载机、多个部门、多种资源相互协调配合,对各项保障资源进行合理分配,高效完成舰载机的各项保障作业任务[1]。但由于保障任务的执行过程可能存在诸多扰动事件,打破原有调度计划的正常执行[2]。为尽可能减少舰载机保障效率所受影响,需在扰动事件发生的同时,针对当前甲板舰载机及保障组的工序进行状况及各保障任务完成与未完成情况列表,以生成连贯的后续保障调度方案[3-5]。

关于舰载机甲板作业调度问题,国内外学者从不同角度进行了大量研究工作,取得了很多有益成果。苏析超等[2,6-10]从机务保障作业建模的角度研究一体化保障模式的调度优化问题,在该模型的基础上,考虑资源配置、人机匹配等现实问题,尝试了使用多种不同算法对该问题进行求解和分析。文献[11-18]从舰载机勤务保障建模的角度建立了舰载机甲板作业调度模型,并针对典型场景,对比研究了专家调度与智能求解算法的优劣。文献[18]将甲板位置作为一种资源约束,研究了舰载机的甲板调度问题。周晓光等[19]分析了甲板作业对舰载机出动架次率的影响。文献[6,20]介绍了面向舰载机故障扰动、作业时间不确定情形的作业重调度问题,该类研究主要基于对机务作业过程的建模,调度模型较复杂,求解实时性有待提高,且往往只针对某一类扰动或不确定性进行研究,难以与实际作业过程相吻合。

针对舰载机甲板动态调度问题,本文通过建立甲板作业模型与调度数学模型,对调度过程存在的潜在扰动事件进行分析,形成不同的重调度窗口,并制定相应的重调度解决策略,同时设计了动态调度求解算法的具体内容及操作方法。

动态调度求解算法是在调度方案运行的过程中,依据所发生的不同扰动事件,进入预设的对应重调度窗口,触发窗口下的算法执行机制[6,21]。算法依据对该扰动所预设的解决方法,通过所设计的编码方案,记录当前舰载机保障状态、保障组工作状态、各项保障的预计完成时间等信息内容,再生成新的工序调度排班表,按照混合交叉方法,得到邻域结构,并将其作为优化路径,结合解码方法及禁忌方法,计算得到当前状态下的重调度方案。最后,以某型航母为对象,进行动态调度仿真验证。

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

1.1 舰载机甲板作业描述

舰载机保障调度目标是使批次舰载机完成甲板保障后全部起飞的所用时间最小化,记所用时间为C。典型的舰载机甲板作业流程如图1所示。

图1 舰载机甲板作业流程图Fig.1 Flowchart of carrier aircraft flight deck operation

暖机、惯性导航对准等作业属于起飞前必做的作业,调运、滑行、加油、武器加载等作业属于视情开展的作业内容[11]。暖机是利用舰面电源起动飞机发动机,对飞机操纵等性能进行检查[12]。滑行是指从保障机位滑行到起飞机位的过程[13]。

考虑到甲板空间限制、作业安全法规限制等因素,舰载机甲板作业工序约束如下。

(1) 出于安全考虑,舰载机的甲板加油、挂载弹药作业不宜同时进行。对于任一架舰载机,任一保障作业,只要作业开始就不中断执行。

(2) 惯导对准、暖机、滑行3项作业应待舰载机转入暖机位后依次开展,且任一架舰载机的这3道工序顺序是一致的。

(3) 所有舰载机起飞前均需从暖机位滑出,处于其他机位的舰载机必须进行必要的调运作业。该约束决定了舰载机甲板作业工序中是否需加入了调运作业工序。

(4) 飞行甲板加油保障点数量和位置均固定,各保障点所能保障的停机位范围已知,且部分机位可活动2个或2个以上加油点保障。

(5) 暖机位当前被占用的情况下,不能被选择作为其他飞机的目标转运机位。

(6) 对于调运作业而言,必须确保存在可行的转运作业路径。

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

舰载机的机务保障作业与甲板保障作业中的加油、惯性导航对准、武器加载等作业环节可以并行实施。为此,在建模过程中,可以不考虑机务保障作业的调度问题,从而降低模型的复杂度。本文研究的甲板作业调度想定是舰载机的多波次循环出动场景。该模型的起点为典型的再次出动准备情况。所谓再次出动准备,是指一批次舰载机的最后一架舰载机完成起飞后,经过战训任务飞行,而后依次着舰,经必要的准备后再次参加下一阶段飞行。对于航母舰载机循环出动而言,再次出动准备时间可以定义为:上一批次舰载机的最后一架舰载机着舰到下一批次最后一架舰载机完成起飞的时间。这个时间与甲板调度效率、参飞舰载机的数量、甲板作业效率等因素有关。

根据约束条件和实际作业过程,建立抽象模型如下[22]。

符号描述:记循环出动过程中,上一次完成舰载机着舰至下一次完成最后一架舰载机起飞所需的最长保障作业时间为Cmax。一批次舰载机完成保障作业时间定义为,批次中最后一架舰载机完成机位停靠到该批次舰载机最后一架舰载机完成起飞所需的时间,也相当于再次出动准备时间。记舰载机i从实施第1道保障作业到完成起飞所用时间为Ci。

批次中包含的舰载机数量定义为I;每一舰载机i对应的甲板作业工序集是Vi,其中Vi={Ji1,Ji2,…,Jij},j表示甲板作业工序数;记飞行甲板作业保障资源集合为R。在所有工序中,Vnr为不需要保障资源的工序集,Vrs为需要特定保障资源的工序集,Vra是需要保障的资源。该资源数量布置一个可进行分配的作业工序集,显然任一工序Jij必需包含在工序集Vi内。舰载机的调运、加油、弹药加载等工序不能同时进行,记类似的工序集合为Vs;VRs为某一保障资源能保障的停机位集合;yijk=1表示第i架舰载机第j项作业开始;dmini是第i架舰载机工序mi、ni开始和结束时间的间隔;舰载机i完成保障作业j所需时间记为Tij;Njk表示时刻k,可用于保障作业j的保障资源总数量;stij为第i架舰载机第j项作业的开始时间,stij≥0;记舰载机i完成第j项作业的完工时刻为edij;记舰载机i完成作业j所花费的时间为dij;记弹药装载组、转运保障组等需进行移动实施保障的保障组在甲板上移动的时间为Ml。

目标函数:

F=minCmax

(1)

约束条件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

sti1jzy≤sti2jzy,∀ZWi1,i2∈Hs;Xzwi1≥Xzwi2

(10)

模型中,式(1)为目标函数;式(2)～式(10)为约束条件。式(2)和式(3)为对舰载机作业工序唯一执行性的约束;式(4)是对舰载机作业工序前后关系的约束,针对作业集中舰载机的导航对准、暖机、滑行、起飞等4项作业;式(5)确保互斥工序不能同时安排执行;式(6)用于表达某一资源在飞行甲板配置的可用总数量的约束,该数量可能因为资源故障等扰动因素而变化;式(9)表达了任一保障资源不可同时服务两架舰载机;式(8)表达了对于同一架舰载机具有紧前紧后关系的保障作业工序,开始与结束时间必须满足的间隔时间约束;式(7)确保对于任一架舰载机的保障,加油作业和弹药加载不能同时进行,调运与其他任何作业不同时进行;式(10)表示舰载机转运需满足的路径可行条件。

2 动态调度方法

2.1 重调度窗口与策略制定

重调度窗口是调度基于突发离散事件进入重调度系统的入口分类,由于采用事件驱动作为重调度策略,因此重调度窗口的预设以及窗口下相应解决办法的预设必不可少,具体内容如下。

(1) 新增舰载机加入保障流程。适用于因作战策略的改变,新增舰载机加入舰载机编队或由于某架舰载机检测出现故障新增其他舰载机代替的情况。当事件触发时,保持甲板全部正在进行保障工序的保障组及舰载机的工作状态不变,把保障组当前正在执行中的工序预计完成时间作为此保障组释放时间,将新增舰载机的全部待保障工序纳入甲板保障未完成部分,根据当前空闲保障组及正在工作保障组的释放时间,结合甲板保障全部未完成部分,进行调度算法计算。

(2) 舰载机故障退出保障流程。适用于舰载机在机务保障伴随勤务保障共同进行的过程中,因发现舰载机部分零部件存在待维修更换、不适宜继续执行飞行任务的情况。当事件触发时,当前保障组及舰载机立即停止工作状态,舰载机停止参与后续甲板保障调度,当前保障组进入空闲释放状态,保持甲板其他正在进行保障工序的保障组及舰载机的工作状态不变,根据当前空闲保障组及正在工作保障组的释放时间,结合甲板保障未完成部分(其中故障舰载机未完成部分不算入内)进行调度运行。

(3) 保障组故障退出保障流程。适用于保障组因人员或设备原因停止后续甲板保障工序。此时分为两种情况,一为保障组退出时可将当前工序执行完毕,二为退出时当前保障工序无法执行完毕,后续需由其他相同工序保障组接替完成。当事件触发时,若工序可执行完毕,则按照当前此保障组预计完成时间对舰载机做释放,对释放时刻的甲板保障组状态及未完成工序状态进入重调度计算;若工序无法执行完毕,则按照故障时间对舰载机立即释放,同时舰载机当前工序的计算机编码不做已完成标记,工序内容继续参与后续重调度,对故障时刻甲板状态进入重调度计算。

(4) 新增保障组加入保障流程。适用于保障组前期因人员或设备原因停止甲板保障参与的后期加入。当事件触发时,保持甲板全部正在进行保障工序的保障组及舰载机的工作状态不变,把工序完成时间作为保障组释放时间,将新增保障组作为空闲保障组,根据当前全部空闲保障组及正在工作保障组的释放时间,对未完成的保障工序进行重调度计算。

(5) 保障工序完成时间发生变化。适用于当前保障工作实际完成时间早于或晚于原调度方案中预计的完成时间,或对工序保障的计划执行所需时间发生改变,如由计划所持的舰载导弹型号发生改变导致工序计划时间改变的情况。该情况下,需设置偏离阀值,首先计算实际情况与原调度计划的偏离程度。若偏离程度超出阀值,则进入重调度系统,根据甲板保障组实际释放时间与改变工序进行的计划所需时间,进入重调度计算。若未超出阀值,则不进入重调度系统。

2.2 时间变化偏离程度计算

在针对保障完成时间变化的重调度窗口中,当保障工作实际完成时间早于或晚于原调度方案中预计的完成时间,或工序保障的计划执行所需时间发生改变时,须首先依据相应编码进行偏离程度计算。在偏离程度大于相应限制情况下进入重调度系统执行重调度方案计算。否则,对原调度方案进行时间平移。偏离程度Δc计算方式具体如下。

(1)若时间延迟情况下,偏离程度计算公式为

Δc=edij(new)-edij

(11)

式中:edij(new)的含义为舰载机在该工序延迟后的工序完成时间;edij是舰载机该工序延迟前的计划完成时间。在完成偏离程度计算后,对偏离程度Δc进行重调度判别计算,判别条件计算公式如下:

Δc≥sti(j+1)-edij

(12)

Δc≥rstm+1-redm

(13)

式中:redm为该保障小组在调度计划中当前任务的计划完成时间;sti(j+1)为保障调度计划中舰载机出现延迟工序的后一保障工序的开始时间;rstm+1为该延迟工序的对应保障组在调度计划中的下一保障任务的开始时间。

依据判别式计算,若满足二者其中之一,则进入重调度算法求解优化重调度方案。

(2)在时间提前的情况下,偏离程度计算公式为

Δc=edij-edij(new)

(14)

对偏离程度Δc进行重调度判别计算,公式如下:

∑NRs+1

(15)

∑NRs=Ns,edij

(16)

式中:NRs+1为在舰载机工序相较于原定完成时间的提前时间段内,保障调度计划内该舰载机所提前的工序的后一工序任务的工序保障种类在该时间段内在甲板的同时进行数量;Ns+1为后一工序任务的工序保障种类的资源总量;NRs的含义为舰载机提前工序的工序保障种类的甲板的同时进行数量;Ns为该工序种类的资源总量。

式(15)用于判别在工序任务提前完成时,该舰载机后一工序任务是否存在可提前进行的可能性。式(16)用于判别该舰载机所提前的任务工序在原调度计划中任务结束时甲板是否处于该资源的供给饱和状态,若饱和,则该保障工序的任务完成时间提前带来了重调度的可操作性。

在任务时间提前状态下,若据判别式计算满足二者其中之一,则进入重调度算法求解更新优化的重调度方案。

3 求解算法

禁忌优化算法已经被证明具有很强的全局搜索能力,且无需对求解的问题进行编码与解码操作,运算效率高。本文使用该算法对上述模型进行优化求解,可以在保证求解质量的同时,提高算法实时性,以满足瞬息万变的航母甲板作业态势。遗传算法因编码方式灵活,在求解多项目调度和车间调度问题中得到广泛应用[23-29]。本节针对甲板调度作业模型的特殊性,在禁忌搜索算法框架下,设计了一种编码式解结构、构造邻域结构及相应的交叉、变异方法,并采用启发式解码法实现了问题的求解。

3.1 算法流程与描述

针对甲板调度方案优化求解,对其优化研究流程的展示如图2所示。

图2 改进的禁忌优化算法流程图Fig.2 Flowchart of improvement tabu optimization algorithm

算法首先根据启发式规则,生成甲板初始调度方案,以调度排班表及甘特图作为方案结果。然后,基于编码的交叉算法对工作日制进行变换,全部的变换方案构成算法优化的邻域结构,作为下一次禁忌优化算法的路径参考。通过对工作日制的解码计算,从中选取最优且不在禁忌表内的变换作为优化操作。同时,将此次变换计入禁忌表内,以此循环,直至达到目标迭代次数,以最优方案调度结果生成甲板调度甘特图。

3.2 滚动调度算法设计

由于在重调度窗口下进入调度方案计算,是在原调度方案的执行过程中进行的,此时甲板的舰载机及保障组不是初始未工作状态,而是各自均有正在进行的工序保障的状态,且调度的工序内容也仅针对甲板全部舰载机还未进行的部分工序内容。因此,动态调度需要一种在生成调度方案的同时可满足复杂情况约束的调度算法。

滚动调度算法的主要思想是通过连续滚动控制将全部的调度过程细分为连贯的静态区间,通过使每个静态区间的调度达到最优来获得整体的调度方案。由于拆分为不同的静态区间,在进入重调度窗口后,可通过对调度的连续滚动控制,每次针对不同的约束状况,通过对计算机编码的计算,做出符合当下情况的调度步骤。该方法可容纳过程中出现的各类约束限制,如各保障组之间及舰载机之间存在不同的释放时间,在未到达释放时间时不可对其进行工序安排的情况。舰载机之间未完成的工序集各不相同,还可能面临着因舰载机增加或取消导致未完成工序集改变的情况等。

针对滚动调度算法的思想,设计完工时间表矩阵作为滚动调度的计算依据,将甲板各类工序的全部保障组当前任务预计完工时间记录在内,通过对完工时间表矩阵内的数值进行计算,获取可进行任务安排的保障小组,依据对距离编码矩阵、舰载机的任务完成工作集矩阵以及各类其他约束矩阵的数值计算,对其派遣最优任务计划,同时对任务派遣做工作日制矩阵记录,以此循环进行,直至完成全部甲板工序调度。其中,依据完工时间表对保障小组的每一次任务派遣,都可视为连贯的静态区间。通过对每一次派遣做最优选择并滚动进行,从而获取重调度方案,供禁忌优化算法寻优计算。

3.3 编码策略

通过对问题的分析,问题求解的决策包含:各舰载机的柔性工序顺序、各工序所对应分配的保障小组、舰载机转运工序的机位安排等。通过将柔性工序顺序与对应保障小组编码整合,编码部分包含舰载机工序、机位以及约束,共三重编码。

(1) 舰载机工序编码

针对甲板上每一架舰载机i,假设舰载机的甲板作业工序数为n,保障每种工序的资源数量为m,工序编码应当体现其工序顺序及实施该工序保障的是m个保障资源中的哪一个。对保障工序使用1 到n顺序编码,在编码规则中设置约束:∀i≠j,ni≠nj。同样地,顺序编码法也适应于保障资源的编码,且也存在约束:∀i≠j,mi≠mj。

具体的编码构造方法如构造的编码矩阵所示:

(17)

舰载机个体用矩阵的行代表,矩阵的列排序代表各架舰载机的保障工序顺序,aij的值表示工序内容和实施该工序保障的保障资源编号,编码由“工序种类”+“0”+“同种保障资源编号”组成。例如,a31的编码为“204”,代表编号为3的舰载机,第1个执行的保障作为编号为2的作业,且为该舰载机完成作业2而实施的保障资源为该工序所需资源的第4组。

(2) 机位编码

停机位功能对于舰载机的甲板保障调度的影响极大,通过机位属性,可获得机位间的距离信息及机位对工序的支持性信息等。经分析,甲板上的i架舰载机与n种不同工序所各自对应的m个保障小组均包含机位属性,编码方式如下:

式中:B和C矩阵联合记录甲板机位信息,B矩阵记录舰载机的机位信息,舰载机编号与行序列一一对应,记录舰载机所在机位;C矩阵记录保障组的机位信息,行序列与工序种类编号一一对应,列序列与工序内的每一保障组一一对应,记录各保障组当前所在机位。

(3) 机位约束编码矩阵

约束编码矩阵用于存放甲板全部的约束行为,用于调度模型求解过程中算法从中提取约束信息,从而计算最终作业结束时间,最终目标是剔除违背约束的解,保留可行解。约束编码采用矩阵形式,每个元素只能取值为0或1。用于表示机位属性。1表示机位具备某项作业的保障能力,0则表示不可进行该作业。

3.4 调度排班策略

调度排班策略为每一甲板保障作业工序安排相应的舰载机保障顺序。调度排班策略从工序的角度分配舰载机,这种策略可以提高编码效率和搜索效率,使得调度结果更具体。调度排班表是一个n列m行的矩阵,每一行对应某一个保障工序,行中的n个元素是完成该工序的舰载机的排列顺序。由于各舰载机所要接受的保障作业工序内容不一定相同,所以对于不同工序,它所对应的需实施该工序的舰载机数量不同。表内编码值代表舰载机的机号,针对同一工序,也就是矩阵的同一行,编码值不可能出现重复,这是因为对于任一舰载机,假设同一作业只实施一次。工序调度排班表的解码结果如图3所示。

图3 工序调度排班表编码与解码示意图Fig.3 Schematic diagram of coding and decoding of operation of scheduling tabulation

在工序调度排班表内,仅有各工序相对应的保障顺序,保障顺序内无需对应工序内各保障组。原因在于,在依据调度方案不断寻优解码计算时,遵守左对齐解码规则:首先各工序均依据默认编号从小至大的保障组进行舰载机编号依次选取以进行保障,当完成首轮选取后,再依据工序内各保障组的最早完工时间选取保障顺序内的下一待保障舰载机。

针对规则内同一工序存在默认的保障组选择顺序及各工序在矩阵内的行顺序不同对优化结果可能带来的不利影响,可通过交叉算法在得到优化路径时消除此影响。

调度算法的优化搜索路径应当覆盖调度排班表采取某种变换策略所形成的全部变换方案。对全部搜索解实施解码计算,获取调度的优化结果。

3.5 基于优先规则的重调度初始调度生成

当进入重调度窗口后,针对滚动调度算法,生成初始调度方案的具体步骤如下。

步骤 1创建保障组完工时间表,初始数值为进入重调度窗口的时间数值,创建空白调度排班表,生成甲板当前舰载机、保障组的工序完成状况及相应时间、机位等信息的编码,用于滚动调度仿真计算。

步骤 2在完工时间表内,将正在执行甲板保障工作任务对应的完工时间数值改为工序的预计完成时间。针对不同的重调度窗口,依据其对应策略,对甲板舰载机工序编码、保障组及停机位等信息编码做对应刷新。

步骤 3查询获取加油、挂弹、转运工序完工时间表内的最小值所对应保障小组,对此保障小组进行可保障工作内容检查及派发。在任务派发的同时,以工序为单位,将保障舰载机编号记录于工作日制表。若此保障小组因舰载机工序约束、甲板机位约束或自身保障范围限制等原因没有可进行的工作任务,则跳过此保障组,选择次最小值的保障小组重复上述过程,进行任务派发。

步骤 4在滚动调度仿真过程中,对完成新任务选择的保障组进行编码信息更新,包含所在机位、完工时间、保障舰载机等信息,对被选择的舰载机进行编码信息更新,包含工序进行记录、工序起止时间等信息,根据舰载机涉及的转运机位信息,实时更新停机位占用编码。

步骤 5对完成加油、弹药加载、调运保障作业的舰载机,直接依次安排惯导对准、暖机、滑行作业。视起飞位可用情况安排起飞作业。

步骤 6循环执行步骤2至步骤5,直至完成所有舰载机的保障作业安排。

完成上述计算,便可获取重调度的初始优化调度方案及所对应工作日制记录。

3.6 邻域结构设计

由于动态调度算法与静态调度算法在运行时的甲板状态不同,因此产生的调度排班表编码内容不同。静态调度在甲板初始状态下运行,因此在初始调度方案生成的调度排班表中,各项工序的保障编码包含甲板全部对此工序有需求的待保障舰载机的编号。动态调度是在调度的进行过程中进行的,部分舰载机已完成了部分保障工序,因此在初始调度方案生成的调度排班表中,各行之间编码的数量及内容各不相同。若采用原交叉方式,由于舰载机编号可能仅在矩阵的某一行内出现,无法与其他行的编码进行部分映射交叉,所产生的邻域结构无法充分体现全部的优化路径方向,从而导致优化算法无法取得最优结果。对此,算法对调度排班表采用部分映射交叉与普通交叉的双重交叉结合的方式,以产生优化所需要的邻域结构。

(1) 部分映射交叉

部分映射交叉的操作方式是在确定两行之间的数值映射关系后,将两行的对应数值做映射变换。部分映射交叉方法与文献[30]中交叉方法类似,在因动态调度所产生的调度排班表中,各行之间编码的数量及内容各不相同,部分映射交叉方案的记录必须满足其交叉合法条件,即在两行之间分别选取编码作为彼此的映射关系时,两个编码的所在行内也必须包含映射对象的编码。如图4所示,在第1行选取编码数值1、第2行选取编码数值4作为映射关系时,因第1行存在映射对象4,第2行也存在映射对象1,即映射交叉方案合法。对满足合法条件的交叉方案,进行行排列关系及映射关系的记录。

图4 动态调度部分映射交叉示意图Fig4 Schematic diagram of dynamic scheduling partial mapping

(2) 普通交叉

普通交叉是对调度排班表的全部矩阵行的每一行进行单行内两数值的位置交叉变换操作。通过获取各行内编码的两两排列组合方案得到其全部交叉方案,并对其进行记录,如图5所示。

图5 动态调度普通交叉示意图Fig.5 Schematic diagram of dynamic scheduling common intersections

邻域结构由调度排班表编码矩阵内全部可行的映射交叉方案(方案A)以及全部的普通交叉方案(方案B)共同组成。通过对其全部邻域结构的解码、择优,完成其甲板重调度方案的优化。

其中,由交叉方案A组成的邻域结构,是为了在舰载机待保障的工序有两个及以上的情况下,实现对舰载机工序的保障顺序交叉互换寻优,而又不引起行内编码重复的不合法性。由交叉方案B组成的邻域结构,是为了在同一工序中有多架待保障舰载机情况下,实现工序对舰载机的选择顺序的交叉互换寻优。通过将两种交叉方案结合,共同组成邻域结构,扩大解的搜索范围,提高解的质量。

3.7 双重禁忌表策略

在普通调度算法中,由于邻域结构由单一的部分映射交叉方案组成,禁忌优化算法在优化过程中,也仅需单一的禁忌表实现对优化过程中被选择的交叉方案的禁忌记录。而由于动态调度算法的邻域结构由两种不同的交叉方案组成,不同的交叉方案所产生的方案记录矩阵不同,因此在优化的过程中,需要两个禁忌表分别记录两种交叉方案中被选择的方案的禁忌值。

3.8 解码策略

解码的目的在于获取问题的调度解。通过将调度排班表按照邻域结构中的每一个交叉变换方案逐一做变换,对变换后的调度排班表按照解码策略进行甲板仿真,得到相应调度结果。对比完成甲板全部保障的最短时间,若时间优于当前最优目标值(初始记录为原调度排班表未交叉变换时所对应的甲板最短保障时间),则记录此变换方案,更新最优目标值,以此循环进行,直至完成全部的邻域结构解码计算。其中,在对邻域结构全部变换方案进行逐一变换计算的过程中,变换操作不累计,每一次变换操作都针对于原调度排班表,而不是针对于在邻域结构上进行一个变换方案操作后的调度排班表。

详细的解码算法步骤如下。

步骤 1创建与调度排班表对应维度的工序完工时间表,令其所有元素均为0。

步骤 2在调度排班表中,依照舰载机的加油、弹药装载、调运的顺序查询作业完工时间,工序对应行元素按从小到大顺序排列(顺序的制定是针对初始状态下完工时间表数值均为0以及过程中可能出现相同最小值情况下,有固定的解码规程,且此顺序与初始调度方案计算过程相同,以免产生误差),完工时间最小值将通过该步骤获取,同时记录该值对应的保障资源(小组)的编号。

步骤 3获取步骤2查询所得的保障(资源)小组序号,根据所属工序,按照调度排班表中该工序的元素排列顺序选取对应编号的舰载机,并赋予其该项作业作为开始。判断该工序的所需保障资源是否属于固定点保障多个停机位的资源,若是,则按照编码顺序选取在该保障点服务范围内的舰载机进行保障;因式(2)中的约束条件中对作业工序不能中断约束,当前工序开始时间取值应为被选飞机正在执行保障作业的完工时间。

步骤 4实时更新作业工序选择信息,包含所在机位编码、完工时间编码、保障舰载机编码等信息,同时对进行任务安排的舰载机进行编码信息更新,包含工序记录编码、工序起止时间编码等信息,若涉及机位转运,则还需更新停机位占用的信息编码。

步骤 5对完成加油、弹药加载、调运保障作业的舰载机,直接依次安排惯导对准、暖机、滑行作业。视起飞位可用情况安排起飞作业。

步骤 6循环执行步骤2～步骤5,直至完成所有舰载机的保障作业安排。

按上述算法解码后,对调度排班表对应的调度解执行领域变换操作,同时在禁忌表内记录该变换方案,在禁忌算法框架下循环搜索,至此则完成优化过程中的一次优化前进。在总的优化算法框架下多次迭代直至收敛,取最小值作为目标调度方案。

4 算例仿真

为充分验证禁忌算法框架下多重编码策略的重调度算法的有效性,在PC机上,采用Matlab 2014a软件实施仿真。调度模型以某型航母为例,考虑舰载机多机多波次循环出动等典型场景,在仿真过程中假设所有参与飞行的舰载机不发生故障。各工序保障时间取值来源于实践经验平均值,参数取值如下:弹药加载时间25 min,暖机时长5 min,舰载机滑行用时1 min,惯导对准作业时间13 min,加油时长取26 min(该值随加油量变化,此处采用固定值仿真)。保障资源移动速度方面,加油保障组的甲板移动速度取为1 m/s,弹药保障组的甲板移动速度为1.5 m/s,转运组空载和牵引时的速度分别为1.5 m/s和0.7 m/s。

仿真研究基于飞行甲板12架舰载机的想定而进行,弹药加载保障组数量NGD=5、转运小组数量NZY=3,完好情况下飞行甲板加油保障点数量NJY=9。初始状态下,甲板舰载机停放信息如表1所示,飞机站位数字依一定规律标号,分别与甲板停机位一一对应。

表1 甲板舰载机初始位置信息Table 1 Aircraft initial position status on flight deck

续表1Continued Table 1

根据舰载机在甲板上的停放位置,按启发式规则和禁忌算法结合的方法产生静态甲板调度方案,如图6所示,用于后续对算法结果的对比分析。

图6 12机动态调度初始调度甘特图Fig.6 Gantt chart of 12 aircraft dynamic scheduling initial schedule

(1) 对原调度方案在执行过程中,在1 000 s时刻下,模拟挂弹保障第3组出现故障但可完成当前正在执行任务的情况。进入动态调度算法后,基于当前各舰载机、保障组工序执行情况,生成动态调度方案如图7所示。

图7 保障组故障动态重调度甘特图Fig.7 Gantt chart of support group failure dynamic rescheduling

通过调度甘特图图6可发现,在1 000 s时刻进入重调度算法时,由于编号为P2至P11的舰载机当前有正在执行的工序,故所生成的重调度甘特图图7中该部分舰载机的当前工序未受影响,而当前工序的后续工序调度安排产生了变化。编号为P1和P12的舰载机由于在1 000 s时刻下没有正在执行的工序,因此在进入重调度算法后立即产生了新的调度方案。由于保障组203故障,通过重调度甘特图图7可见后续保障中无该保障组参与,通过对比分析可证实算法的有效性。

(2) 在原调度方案执行过程中,在1 000 s时刻下,增加挂弹保障第6组,所在甲板机位为12号,动态调度方案如图8所示。

图8 增加保障组动态重调度甘特图Fig.8 Gantt chart of increased support group dynamic rescheduling

新增加挂弹保障组第6组,依据编码规则,保障组对应编号为206,通过对比调度甘特图图6可发现,舰载机P2至P11的当前工序无影响,在当前工序完成时刻后,后续调度方案产生变化,舰载机P1和P12在1 000 s时刻下无正在执行工序,则在重调度时刻产生新的调度方案,且在后续调度方案中,保障组206参与调度任务安排,如图8中红色方框所示。通过对比分析可证实算法的有效性。

(3)在原调度方案执行过程中,在1 000 s时刻下,编号为P5的舰载机机务检查出现故障,动态调度方案如图9所示。

图9 舰载机故障动态重调度甘特图Fig.9 Gantt chart of aircraft failure dynamic reschedule

通过重调度甘特图图9可发现,在1 000 s时刻下舰载机P5发现故障,立即停止了当前工序的进行,101保障组即刻释放,且舰载机P5不再参与原定的后续调度。通过对比静态调度甘特图图6可见,P5舰载机原定在加油保障工序完成后进行转运工序,由保障组302进行。在1 000 s时刻下产生的新调度方案中,302保障组负责在舰载机P11完成当前加油工序后对其进行转运工作,通过对比分析可证实算法的有效性。

(4) 在原调度方案执行过程中,在2 200 s时刻下,增加编号为13的舰载机,机位在9号,动态调度方案如图10所示。

图10 新增舰载机动态重调度甘特图Fig.10 Gantt chart of increased aircraft dynamic reschedule

由于舰载机P13所在9号机位可进行发动机的启动、暖机工序,因此起飞前保障无需进行转运工序,产生重调度甘特度图图10。虽然在2 000 s时刻下进行重调度计算,但由于当前工序执行的饱和状态,舰载机P13加油工序由加油保障组103完成对舰载机P4的加油作业后进行,如图10内红色方框及对应虚线所示,通过对比分析可证实算法的有效性。

(5)在原调度方案执行过程中,在1 000 s时刻下,舰载机P11号加油任务由原定25 min延迟至40 min,动态调度方案如图11所示。

图11 任务延迟动态重调度甘特图Fig.11 Gantt chart of task delay dynamic reschedule

由图11可见,在1 000 s时刻重调度算法所生成的重调度甘特图中,舰载机P11的当前加油工序时间由初始静态调度甘特图图8中的25 min延迟至40 min,如红色方框内所示,且各舰载机当前正在执行的工序未产生影响。在各舰载机当前工序的释放时刻以后,产生新的调度方案,通过对比分析可证实算法的有效性。

通过对比其他算法执行结果,算法运行的最优解与消耗时间汇总如表2所示。

表2 算法性能对比Table 2 Algorithm performance comparison

通过仿真结果可以看出,本文算法最终所得结果近似趋同于全局搜索,得到当前状态下的最佳保障调度方案,且所消耗时间远小于其他算法求解所需时间,因此本文所设计的动态调度优化算法可在较短的时间内提供一个较优的甲板舰载机调度方案,是获得甲板保障调度方案的有效算法。

5 结 论

针对多种扰动下的舰载机多机循环批次出动甲板作业的动态调度问题,从甲板勤务作业视角建模,降低调度复杂性。采用基于禁忌优化算法框架下的多重编码、工作日志表搜索等策略,获得了一种考虑资源分配、机位分配等因素的调度问题求解算法。

该算法不仅可用于航母保障作业调度,也可适用于器械加工、路径选择等扰动事件频发且对总消耗时间较为敏感的调度领域。由于算法执行消耗时间少,可适用于工序时间短、前后工序紧密相连的密集型调度领域。

算法在拓展运行至不同调度环境的过程中,需要对编码部分及调度排班表的具体设计进行更改,做出适合目标运行环境的设计。算法的总体结构大体一致,难点在于算法的编写人员需充分理解该算法在执行过程中的算法设计内容及原理。该算法的优点在于算法的通用性较强,无需做出较大改动,因此研究结果实现的可能性较大。