舰载机多机一体化机务保障调度研究*

苏析超，韩 维，史玮韦

（海军航空工程学院，山东 烟台 264001）

舰载机多机一体化机务保障调度研究*

苏析超，韩 维，史玮韦

（海军航空工程学院，山东 烟台 264001）

针对舰载机多机一体化机务保障调度问题，以出树、入树的形式描述实际保障过程中并行工序的约束关系，以最大保障完工时间和资源负载均衡性为目标，构建了舰载机多机一体化机务保障非线性多目标混合流水车间调度模型，并设计了一种结合基于Insert的动态邻域爬山搜索策略和并行工序的同步化修正的Memetic算法求解该模型。最后通过实例仿真验证了模型和所提算法的可行性和有效性。

舰载机机务保障，非线性混合流水调度，多目标优化，Memetic算法

0 引言

作为现代战场上的“海上霸王”，航空母舰集防空、反舰、反潜以及对岸攻击等作战能力于一体，一直是世界各军事强国竞逐的战略性武器。在航母编队中，舰载机是最关键的组成部分，航母全系统和航母战斗群的绝大多数作战使命都需要并且只能由舰载机来承担和完成［1］。其中，舰载机舰面保障作业调度时间跨度长，涉及面广，约束条件复杂，如何对其提供合理的规划或优化对提升舰载机作战效能具有重要作用，相关资料见文献［2-8］。

本文按照舰载机保障流程约束特性对保障工序进行划分整合，以最小化保障时间和保障主体负载均衡为目标，建立了舰载机多机机务保障非线性多目标混合流水调度模型。设计了一种基于Insert邻域爬山搜索的Memetic算法求解该模型。通过实例仿真验证了算法的可行性和有效性。

1 舰载机多机一体化机务保障调度问题

1.1 保障作业流程分析与问题描述

多机一体化机务保障是在保障工序约束下，合理调度保障单元，对多机型机群同时进行保障，以达到较优的出动能力。舰载机机型种类繁多，包括战斗机、攻击机、预警机、反潜机、电子战飞机等，用于执行各类作战任务。各类机型的机务保障内容也不尽相同，按专业可分为机械专业、军械专业、航电专业、特设专业。其中，机械专业主要包括飞机的机械外观检查、发动机润滑油的检查与添加、液压油的检查与添加、补充氮气，添加燃油等；军械专业负责各型导弹的挂载；航电专业与特设专业主要是进行座舱的通电检查、数据的加载及惯导对准、补充氧气等。约束方面：基于安全性考虑，通电检查不能与充氧、加挂导弹同时进行。此外，惯导对准需在所有其他工序保障结束后才能进行。以保障组为主体单元，如军械组以两人为一个单元进行挂弹操作。机械组负责机械专业的工序，由于航电专业与特设专业的共通性，即主要进行通电检查的工作，可合并由航电组进行保障。由此可得到舰载机的保障工序流程图如图1所示。

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

在图1所示的流程基础上，进一步考虑以下约束或假设：①同一时刻一个保障组只能保障一架舰载机；②同一时刻某一工序只能接受一个保障组保障；③保障组在保障某专业内容中过程不可中断，且只能在上一道工序完成后才能进行下一道工序保障；④不考虑突发故障和其他干扰因素。

通过上述分析与假设，舰载机多机一体化机务保障调度问题可描述如下：设J={Ji}1≤i≤n为舰载机集合，n为舰载机数量。一共存在m=4个广义工序，其中工序1为机械专业内容，工序2为通电检查和充氧气，工序3为挂载导弹，工序4为惯导对准，引入虚工序0表示牵引系留。前后工序间存在入树、出树和顺序3种约束类型。每道工序均对应有Mj（j=1，2，…，m）个保障组。

n架舰载机按入场时序进入保障作业，并以相同的保障工序流程，选取对应的保障组进行保障作业，目的是在优先保证n架舰载机保障完成时间最小化的基础上，使得各个保障组的闲忙比较为均衡。与一般混合流水作业不同［9］，由于保障工序间存在串行和并行的顺序关系，并且工序4与工序1均由同一类型保障组保障，该调度模型可定义为非线性可重入混合流水调度系统。

1.2 模型建立

为了便于描述出、入树的约束关系，分别定义树前集Tl={Tl1，Tl2，…，Tlnt}和树后集Tr={Tr1，Tr2，…，Trnt}，其中nt为树节点数量。对第q个树节点，树前集元素Tlq为包含树节点前端工序的集合，同理Trq为包含树节点后端工序的集合。例如图2所示，对节点q的入树工序约束，Tlq={A}，Trq={B，C，D}，对节点p的出树工序约束，Tlp={b，c，d}，Trp={a}。在本文模型中存在两个树节点，且Tl1={0}，Tr1={1，2}；Tl2= {1，3}，Tr2={4}。

图2 出树、入树工序约束关系图

记Sij和Eij分别为舰载机Ji的第j道工序保障开始时间和保障结束时间；Tijk为舰载机Ji的第j道工序在第k个保障组上的作业时间；Ci为舰载机Ji的最后一道工序的保障结束时间；Xipj为0-1变量，取值为1时表示在第j个工序上第i架舰载机优先于第p架舰载机进行保障，即JiJp，取0则相反；Yijk为0-1变量，取值为1时表示第i架舰载机的第j道工序在第k个保障组上进行保障，否则取0；ObVk为第k个保障组的闲忙比。定义第k个保障组的闲忙比为整个保障过程空闲时间与工作时间的比值，即

保障调度的两个指标分别为最大保障完工时间Cmax=max（Ci）和闲忙比方差

基于上述，建立本文非线性可重入混合流水调度模型如下：

其中，式（3）表示调度的目标，即在保证最小化最大保障完工时间的前提下，使得各保障组闲忙比更为均衡；式（4）表示每个舰载机的任一工序只能在一个保障组上保障；式（5）表示同一舰载机工序保障开始时间与结束时间的关系；式（6）表示同一舰载机工序2和工序3的先后顺序关系；式（7）表示同一舰载机在树前端工序均保障结束后才能开始树后端工序的保障；式（8）中为足够大实数，确保表示对于同一工序，优先级高的舰载机优先进行保障作业。式（9）表示决策变量的属性约束。

2 基于Memetic算法的问题求解

Memetic算法是一种结合遗传算法和局部搜索策略的群智能优化算法，它通过遗传算法来进行种群的全局搜索，通过局部搜索策略来进行个体深度搜索，从而具备较强的全局寻优能力和良好收敛性能。而上文所建立的非线性可重入混合流水调度问题属于NP-hard组合优化问题，传统基本遗传算法（SGA）求解此类问题在全局搜索和收敛性方面存在不足，因此，本文设计了一种基于Insert的邻域爬山搜索Memetic算法如下。

2.1 编码与解码

针对本文模型工序间串并行约束和同一工序多组保障的特点，采用一种基于矩阵的实数编码方式［10］，可避免在遗传操作和局部搜索过程中产生非法解。

如式（10）中的个体Anm，行表示舰载机编号，列表示工序号，任一元素ai，j（i∈{1，2，…，n}，j∈{1，2，…，m}）为区间（1，Mj+1）上的一个随机实数。其中，整数部分Int（aij）表示舰载机i的第j道工序在第Int（aij）个保障组上作业，小数部分表示多个工序在同一保障组上冲突时的优先排序。当Int（aij）=Int（ai'j），i≠i'时，表明不同的舰载机在同一保障组保障同一道工序。如果j=1，2，则按照aij的升序来保障，当j=3，根据第2道工序的保障完成时间，若j=4，则根据第1道至第3道工序的保障完成时间，来确定其保障顺序，即前一级工序先完成的先保障。若前一级工序完工时间相同，则也按aij的升序来进行保障。

将矩阵编码的每一列构成一小段，形成的染色体可以表示为一个长度为n×m的字符串：［a11，a21，…，an1，a12，a22，…，anm］。对于每个染色体，根据上述规则均能映射到一个可行的调度。

2.2 基于多目标的适应度分配

遗传算法在进行进化搜索的过程中仅以适应度函数为依据，种群个体的适应度分布决定了进化搜索的方向。基于排序的适应度分配方法是将种群按个体目标值排序，个体的适应度只取决于它在种群序列中的位序。基于排序的适应度分配法不仅有效克服了适应度计算的尺度问题，表现出较好的鲁棒性，同时也避免了本文的二层多目标优化问题的权值选取困难。对于规模为N的种群，根据目标函数按照先Cmax后的原则进行排序，即Cmax越小排序越高，Cmax相同的情况下，Eob值越小排序越高。设SP为选择压力，表示种群中最佳个体被选中的概率与平均选中概率的比值，pi为个体在种群中的序位，则其基于线性排序的适应度可表示为：

2.3 选择交叉操作

首先将种群中适应度最大的染色体直接复制作为交叉和变异的操作的对象，其余个体按照轮盘赌选择法选取。其次采用两两随机分组均匀交叉方式，对分组后任一对染色体根据交叉概率Pc生成等长的0-1掩码，并按照均匀交叉方式进行交叉互换。为避免种群过早陷入局部最优解而停滞不前，本文采用自适应的交叉概率［11］如下

其中，Pc_max、Pc_min分别为交叉率取值的上限和下限，Fitmax为群体中最大适应度值，Fitavg为每代群体的平均适应度值，Fit为要交叉个体的适应度值。

2.4 变异操作

由于染色体各基因ai，j∈（1，Mj+1），因此，变异操作首先需要考虑变异的范围。文献［8］采用等概率双向变异策略，对于靠近区间边界一侧的基因则表现出双向变异的不对等性，变异向另一侧的概率较低。为使得变异具有指向性，针对目标函数中的闲忙比方差指标，借鉴文献［12］中的变异策略，即在保证个体合法性的前提下，变异操作选择闲忙比最大的保障组加工当前舰载机，即更改当前基因整数位为闲忙比最大的保障组号，小数部分则随机变异。变异概率Pm同样采用自适应机制［11］：

其中，Pm_max、Pm_min分别为变异率取值的上限和下限。

2.5 基于Insert的邻域爬山搜索

局部搜索是Memetic算法区别于传统遗传算法的关键部分，通过局部搜索，在个体周围不断寻找新的优秀的解，从而增加了解的深度。局部搜索的两个主要问题包括搜索机制和邻域的确定。本文采用一种基于Insert的邻域爬山搜索算法，具体过程如下：

Step1：通过遗传算法的全局交叉变异操作后，选取种群中最优个体并随机抽取Nb个其他个体中第2道工序对应的基因段进行局部搜索。

Step2：对选取的任一染色体第2道工序对应的基因段S2g，随机产生自然数pit=Rand{-1，1}、自然数d∈（1，n）。若pit=-1，执行向后搜索，并转入Step4；若pit=1，则执行向前搜索，并转入Step3。

Step3：给定邻域自然数rp，令m=min（rp，d-1），表示从Sg上第d位基因开始向前搜索m位，转入Step3.1。

Step3.1：执行S2g上第d位基因与d-m位基因的Insert操作，即将d位基因从该位取出并插入到第d-m位上得到Stemp，判断若Fit（Stemp）＞Fit（S2g），则更新个体基因S2g=Stemp，并转入Step3.2。

Step3.2：令m=m-1，若m＞0，则返回Step3.1。

Step4.1：执行S2g上第d位基因与d+m位基因的Insert操作，即将d位基因从该位取出并插入到第d+m位上得到Stemp，判断若Fit（Stemp）＞Fit（S2g），则更新个体基因S2g=Stemp，并转入Step4.2。

Step4.2：令m=m-1，若m＞0，则返回Step3.1。

其中，搜索邻域rp采用动态调整策略，在搜索初期，局部搜索范围设置较大，有助于全局搜索快速收敛到各局部极值；搜索后期，局部搜索范围缩小，在极值附近更深一步搜索，并减小计算的复杂度。则搜索邻域范围的动态取值可表示为：

其中，［］为四舍五入取整操作。rpmax、rpmin分别为搜索邻域范围取值的上限和下限。gh为指定的最小邻域搜索迭代阈，且小于种群最大迭代次数，g为当前迭代次数。

2.6 并行工序的同步化修正

并行工序的存在是本文模型区别于一般混合流水调度问题的显著标志，并行工序调度不协调将直接影响后续工序的保障。例如：在某次调度分配中，机械加油组保障第1道工序所属的舰载机编号按时间前后排列为π1={1，2，3，4}，而挂弹组k2保障的舰载机序列为π2={4，3，2，1}，并假设两者同时开始，各工序保障时间均为一个时间单元，则通电检查组只能等到第3个时间单元后才能开始保障。反之，若k2保障的舰载机序列为π2=π1={1，2，3，4}，由于并行工序加工的同步性，通电检查组在第一个时间单元后即可开始保障，大大缩短总体保障时间。基于上述分析，在对种群进行交叉变异和局部搜索后，对所有个体进行并行工序的同步化修正，具体步骤如下：

Step1：对染色体Sg，将其第2道、第3道工序的基因段解码得到各舰载机第3道工序的保障结束时间e3i（i=1，2，…，n），按其时间大小排序即可得到舰载机第3道工序完工编号序列π={π（1），π（2），…，π（n）}。

Step2：同理，对染色体Sg第1道工序基因段解码得到第k（k=1，2，…，M1）个保障组的保障序列πk={πk（1），πk（2），…，πk（n）}。

Step3：对πk中的元素按照π的序列进行重排。对种群所有个体进行以上操作。

例如：对某一染色体解码获得π= {4，2，5，1，3，6}和π1={1，2，3，4}，将π按照π1的序列重排可得同步化的新序列π1={4，2，1，3}。

3 仿真研究

由于任务、机型等因素的差异，不同舰载机各道工序的保障时间不尽相同；而对于同一舰载机，不同保障组的经验和配合度等因素的差异也会造成保障时间的差异。假设某任务波次需要出动各型舰载机12架，保障组保障舰载机各道工序的时间矩阵如表1所示，入场保障时间如表2所示。

表1 舰载机及各工序保障时间表（单位：min）

表2 舰载机入场保障时间（单位：min）

设定初始参数为：染色体种群规模100，迭代次数取100，交叉率上、下限Pc_max=0.9、Pc_min=0.7，变异率上、下限Pm_max=0.1、Pm_min=0.01，选择压力SP=2，Nb=20，rpmax=8，rpmin=3，gh=40。利用Matlab7.6软件分别采用本文Memetic算法和标准SGA算法进行编程求解，提取30次独立运算得到的最大保障时间和闲忙比方差，计算其平均值，分别绘制其收敛曲线图如图3、图4所示。

图3 平均最大保障时间变化图

图4 平均闲忙比方差变化图

由图3和图4的仿真结果可得，本文设计的Memetic算法经过30次独立运算的平均最大保障时间=124.4，平均忙闲比方差为=0.240，均优于SGA算法的运算结果，具有更强地寻优能力和收敛速度。

通过Memetic算法获得的一个最优调度甘特图如图5所示，其中每一个条状框图的前一个字母数字组合表示正在保障的舰载机Ji（1≤i≤10），后一个数字表示舰载机的第j（1≤i≤4）道工序。所求得最优目标值Cmax=124.4 min，Eob=0.234。图6为原最优调度未经过工序同步化修正的调度甘特图，其目标值Cmax=140 min，Eob=0.300。通过图5和图6的比较可以看出，经过并行工序同步化修正后，工序1和工序3基本实现同步化保障，从而加快了出树工序4的保障进度，缩短了最大保障时间。

图5 最优保障调度方案Gantt图

图6 未经过工序同步化修正的调度方案Gantt图

4 结论

本文在分析舰载机单机机务保障流程的基础上，以出、入树的形式描述了并行工序间的约束关系，建立了多机一体化机务保障非线性多目标混合流水调度模型，并采用Memetic算法进行求解。算法在局部搜索环节设计了一种基于Insert的邻域爬山动态搜索策略，通过对染色体中并行工序的同步化修正加快了收敛速度。最后通过实例仿真与标准遗传算法进行对比，验证了模型和算法的可行性与有效性。该智能化方法为航母上的多机一体化机务保障调度提供了新的思路和决策参考。下一步的研究方向是建立更为细化的保障工序约束模型，并进一步改进优化算法以达到更好地优化效率。

［1］韩维，王庆官.航母与舰载机概论［M］.烟台:海军航空工程学院出版社，2009.

［2］司维超，韩维，史玮韦.基于HPSO和GA算法的舰载机甲板布放方法比较［J］.系统工程与电子技术，2013，35（2）:338-344.

［3］刘钦辉，邱长华，王能建.考虑空间约束的舰载机作业调度模型研究［J］.哈尔滨工程大学学报，2012，33（11）: 1435-1439.

［4］Michini B.A Human-Interactive Course of Action Planner for Aircraft Carrier Deck Operations［C］//AIAA，2011.

［5］Dastidar R G.A Queueing Network Based Approach to Distributed AircraftCarrierDeck Scheduling［C］//AIAA，2011-1514.

［6］李静龙，陶勇刚.飞机及无保障系统的优化设计［J］.工业工程，2009，12（3）:85-88.

［7］栾孝丰，谢君.基于仿真优化的多机机务准备流程研究［J］.计算机与数字工程，2010，38（12）:50-53.

［8］魏昌全，陈春良，王保乳.分波出动舰载机航空保障调度研究［J］.控制工程，2012，19（S0）:831-834.

［9］Liao C J，Tjandradjaja E，Chung T P.An Approach Using Swarm Optimization and Bottleneck Heuristic to Solve Hybrid Flow Shop Scheduling Problem［J］.Applied Soft Computing，2012（12）：1755-1764.

［10］王凌.车间调度及其遗传算法［M］.北京:清华大学出版社，2003.

［11］王小平，曹立明.遗传算法——理论、应用与软件实现［M］.西安:西安交通大学出版社，2002.

［12］丁帅，李铁克，施灿涛.考虑机器故障的HFS重调度研究［J］.计算机工程与应用，2012，48（23）:234-238.

Research on Integrated Maintenance Scheduling of Multi-carrier Aircrafts

SU Xi-chao，HAN Wei，SHI Wei-wei
（Naval Aeronautical and Astronautical University，Yantai 264001，China）

To solve integrated maintenance scheduling problem of multi-carrier aircrafts，the parallel constraint relationship between process in the course of actual maintenance is described in the form of in-tree and out-tree，and a multi-carrier aircrafts integrated maintenance nonlinear multiobjective hybrid flow shop scheduling model based on maximum support time and resource load balancing is built in this paper.Then a Memetic algorithm combines an Insert-based dynamic hillclimbing local search strategy and a synchronization modification of parallel process.The result of the model and the algorithm is proved feasible and effective by the results of simulation.

carrieraircraftmaintenance，nonlinearhybridflowscheduling，multi-objectiveoptimization，Memetic algorithm

TJ760.7；V271.4+92

A

1002-0640（2015）06-0026-05

2014-04-21

2014-05-30

国家自然科学基金（51375490）；航空科学基金资助项目（20115184005）

苏析超（1989- ），男，广西南宁人，硕士。研究方向：舰载机技术研究及应用。