杨杰,余明晖*,彭雅欣,苏厚胜,杨大鹏
1 华中科技大学 人工智能与自动化学院,湖北 武汉 430074
2 中国舰船研究设计中心,湖北 武汉 430064
航空母舰(以下简称“航母”)是当前乃至未来海上作战中最重要的力量,而舰载机作为航母的主要武器,承担着绝大多数的作战任务[1],因此,舰载机的出动能力成为影响航母综合作战能力的重要因素。由于航母甲板空间有限,环境多变,作业流程复杂且资源约束多[2],特别是在舰载机连续波次出动方式下,如何在有限的时间内对舰载机机群以及相关保障人员进行科学、合理的资源分配和时序规划,缩短机群保障完成时间,提高保障人员利用率,实现作业间的安全有序,是制约舰载机机群出动效能的关键性问题。
在舰载机作业调度方面,国内外学者开展了大量研究。2011年,Ryan和Michini等[3-4]开发了基于人机交互的舰载机甲板作业规划决策支持系统(deck operations course of action planner,DCAP),其利用甲板上舰载机、阻拦索和弹射器等装置的状态信息,设计了基于逆强化学习的自动规划算法,不断学习专家经验直至给出指挥人员满意的规划调度方案;Ryan等[5]基于线性整数规划的重调度模型,以人机交互的方式与计算机协作完成了调度规划,仿真结果显示,计算机调度与人工经验调度相比更加快速、有效。魏昌全等[6]针对舰载机的连续出动方式和分波出动方式,分别建立了保障资源调度模型。韩维等[7]针对单机机组保障模式的不足,建立了多目标的多机一体化机务保障调度模型。
在舰载机作业保障人员的调度方面,孙长友[8]将保障组分为航电、特设、军械和机械4个小组,研究了不同舰载机数量和保障组配置下的静态调度问题;苏析超等[9]以保障完成时间和资源复杂均衡性为指标,构建了舰载机多机机务保障混合流水调度模型;蒋婷婷等[10]针对舰载机集中式保障,在考虑各类资源约束条件的基础上,建立了基于保障调度时间和人员负载均衡性的动态分层双目标优化模型。
现有的研究虽然取得了一些成果,但仍缺乏以下几个方面的研究:1)当前研究大多将不同专业的人员按小组划分,没有细致到个人,在实际过程中会造成小组内与作业无关人员的无效移动,而对于保障人员的跨专业复用问题,现有研究也未给予充分考虑;2)当前研究假设保障人员可以进行全甲板域的保障作业,而实际上在连续出动模式下,舰载机的起降和保障作业是同时进行的,可以提供给人员流动的通道少且隐藏着危险,因而限定保障人员的流动范围十分有必要;3)针对保障资源调度研究,大多是以机群保障完成时间和资源负载均衡性为目标,然后再给出权衡两者后的最优方案,但在实际舰载机调度作业中,由于人员流动存在潜在的危险,应当考虑保障人员在不同舰载机站位之间切换保障的转移时间,并根据战场环境选择不同侧重点的保障方案。
为此,本文将以舰载机甲板保障调度为研究对象,引入甲板上保障人员累计转移时间,基于舰载机保障的流程和资源约束,研究建立考虑多技能保障人员的舰载机甲板保障调度模型与优化算法,然后面向保障作业完成时间、保障人员累计转移时间和负载均衡性指标,实现对舰载机机群甲板保障时序的调度优化、保障人员数量配置和保障技能的分配,从而提升机群甲板的作业效率与利用率,进一步助推航母舰载机出动回收的综合效能。
美国“尼米兹”级航母[11]采用的是传统的“多站式”保障模式。舰载机着舰后,需要由牵引车依次牵引到维修站位进行维修,或牵引到加油站进行加油,或到弹药挂载区进行挂弹等保障作业,但由于甲板环境本身狭窄且拥挤,而调运舰载机又要经过多个工作区域,这就增加了意外事故的风险,故而也降低了人员的作业效率。美国“福特”级航母采用的“一站式”保障模式可以大大提高舰载机保障作业的效率[12]。其通过在同一保障区内集中放置各类舰面保障设备并配备相应的保障人员,来保证着舰舰载机在移动到保障区后就在原位即可完成加油、通电、挂弹、维修作业等所有的保障工作,离开保障区后,即可滑行至弹射起飞位待命,准备下一轮的飞行作业,从而显著减少了舰载机的保障用时,提高了舰载机的出动架次率。
在“一站式”保障模式下,根据保障人员的作业范围,可以划分为单机机组保障模式、大机组模式和一体化联合保障模式3种[13]。在单机机组保障模式下,保障人员只能给某一个固定的舰载机进行保障作业,导致人员利用率低,保障人员数量增加;在一体化联合保障模式下,保障人员可以给甲板上任意一架舰载机进行保障,但加大了保障作业之间的转移距离,导致甲板作业环境潜在的危险较多且管理复杂度高;在大机组模式下,保障人员为某一范围内的舰载机提供保障作业,相比单机模式不仅增加了保障效率和保障质量,而且避免了一体化保障模式下组织管理的高成本,更贴合实际作业环境。
本文将以“福特”级航母的“一站式”保障模式为研究对象,采取大机组模式进行保障作业,如图1所示。在连续波次出动模式下,由于连续出动舰载机,其出动的飞行周期首尾交错重叠,在舰载机保障作业过程中会存在其他舰载机正在着舰和起飞的情况,从而给甲板上流动的保障人员带来了潜在风险。而让保障人员只在局部范围内移动,则可以规避有很多人员流动的情况下面临的潜在危险,所以引入保障人员在舰载机作业之间切换时消耗的累计转移时间,并将其作为评价舰载机保障方案的指标具有重要意义。
图1 大机组保障模式示意图Fig.1 Schematic diagram of large unit support pattern
舰载机着舰并入位系留后,将进行外观检查、加油、通电、充电、挂弹等一系列保障作业。保障作业可以根据保障的内容划分为不同的专业,每种专业作业要求一项对应的专业技能,只有拥有该专业技能的人员才可以从事此项工作。根据保障作业的性质和工作强度的不同,可能同时需要多名保障人员共同完成,而如果有些保障人员具备满足多个需求的技能,能够完成不同的保障作业,则会极大地增加作业指派的灵活性。此外,受作业性质的约束,不同的保障作业之间存在串行或者并行的约束关系,每项作业只有在其紧前作业完成后才能开始执行。。
此外,战场环境瞬息万变,舰载机的作战任务也会随之变化,从而对舰载机保障作业提出了不同的要求。这时,就不能仅考虑诸如最小化保障完成时间这样的单一目标,还应考虑保障人员的负载均衡性和切换作业时的转移时间,并且这三者的优先级顺序也非一成不变,通常随战场环境的改变而改变,指挥人员需根据战况在三者之间寻找一个合适的平衡点。因此,给出最优的舰载机保障方案Pareto集合,由指挥人员因地制宜地采用方案将极大地增加灵活性和人员利用率。
1.2.1 假设条件
为建立舰载机机群保障作业人员调度模型,提出以下假设:
1) 保障期间,不考虑飞机故障、人为差错、设备故障等不确定的突发情况和其他干扰因素;
2) 保障人员在保障作业的过程中,不考虑中途换人或者作业暂停的情况,并且只能在上个保障作业完成后才能进行下一项保障作业;
3) 每个保障作业只对应一项专业技能,对于具备多项技能的保障人员,同一时刻只能进行一项保障作业;
4) 各舰载机之间的保障作业互不干扰;
5) 执行保障作业前,需要满足3个条件(即对应的技能需求、人员数量需求以及前置作业均已完成),且保障作业时间为固定标准作业时间,不会发生变化;
6) 舰载机在任意站位都可以接受“一站式”资源保障,不用转移;
7) 保障人员只能对大机组保障模式下指定范围内的舰载机进行保障作业。
1.2.2 调度模型参数及决策变量定义
调度模型参数定义为:
I={1,2,···,IM},为参与保障的舰载机集合,其中IM为舰载机数量;
G={1,2,···,MM},为保障人员集合,其中MM为人员数量;
Ji={1,2,···,JM}, 为舰载机i的作业集,其中JM为舰载机作业数量;
S={1,2,···,S M},为舰载机所有作业需要的技能集,其中SM为作业数量;
D={1,2,···,ZM},为时间离散化集合,其中ZM为所有作业的串行执行时间之和,d∈D为离散时间节点;
ags为每名保障人员对于技能的匹配关系,其取值范围为1或者0,其中ags=1表示g保障人员具备技能s。人员技能矩阵SKL为
T=[t1,t2,t3,···,tJM],为舰载机所有作业标准作业时间集;
TSi为 舰载机i的入场保障起始时间;
STji为 舰载机i的 第j项作业保障开始时间;
ETji为舰载机i的 第j项作业保障结束时间;
Pji为 舰载机i的 第j项作业的紧前作业集合;
HS ji为 舰载机i的 第j项作业的紧后作业集合;
Ci为舰载机i最后一项作业的保障结束时间;
Cji fe为保障人员从舰载机i的 第j项作业保障结束至舰载机e的第f项作业开始保障的转移时间;
Avu为所有保障人员的工作负载均衡性;
Mov为所有保障人员的累计转移时间;
Tin为舰载机机群保障完成时间。
决策变量定义为:
1.2.3 目标函数
1) 最小化机群保障完成时间。
舰载机的出动回收能力受限于航母甲板上舰载机的作业效率,舰载机机群的保障完成时间越短,舰载机出动架次率越高。因此,最小化机群保障完成时间是重要的优化目标之一。
2) 最小化保障人员负载均衡性。
舰载机保障作业主要是由保障作业人员操作保障设备完成,保障人员的工作状态决定了保障作业的工作效率。如果某些保障人员承担过多的作业,而另外的人员又过于空闲,此种失衡的人员工作负载就会影响到作业的持续高效开展。因此,本文考虑将保障人员的作业时长作为衡量负载均衡性的指标,且模型的优化目标使保障人员负载的偏差最小。
保障人员的负载均衡性计算:
3) 最小化保障人员累计转移时间。
通常,甲板人员在移动时可能会遇见各种潜在的危险,例如,因甲板转运及滑行而产生的高温尾焰或是失足掉入海中。同时,人员的移动也会给舰载机或者其他设备的转运带来干扰,因此限制保障人员的移动十分有必要。模型的优化目标取保障人员的累计转移时间Mov最小化。
1.2.4 约束条件
有关保障人员配置的数学模型需要考虑以下几个方面的约束:1)保障流程的时序约束,即舰载机入场时序约束和保障流程中作业的串、并行约束;2)保障人员的转移约束,即保障人员的作业切换受转移时间的限制;3)资源保障能力和分配约束;4)布尔变量约束。具体的约束条件如下:
其中,式(6)表示舰载机降落后移至保障区且系留完成后才能进行保障作业;式(7)表示舰载机作业的保障开始时间、标准保障时间和保障结束时间三者之间的关系;式(8)表示任一项作业都有紧前作业的约束关系,必须保证所有紧前作业均保障完成才能开始作业;式(9)表示每名作业保障人员在某个时刻只能使用一种技能,同时只能执行一项作业任务;式(10)表示需要满足舰载机作业对技能的需求量,作业才能开始;式(11)表示保障人员只能同时对一项作业进行保障,若分配多项作业,则按保障按优先级进行,为了确保不等式始终成立,设置INF为足够大的实数;式(12)表示决策变量的0~1属性约束。
舰载机机群保障作业的人员配置问题具有约束多和目标多的特性,并且还属于NP-hard(nondeterministic polynomial-time hard)问题。舰载机的保障作业随着舰载机数量的增加而急剧增多,导致算法在庞大的解空间中只能找到局部最优解,而保障作业人员配置问题中的多个目标通常没有办法找到理想的统一标准来转化成单一目标问题求解。Deb等[14]提出了一种非支配排序遗传算法NSGA2,该算法在多目标优化问题中具有运行速度快、鲁棒性好、收敛性好等优点。NSGA2算法的整体思想为:对每个父代Pt都通过遗传算子(交叉、变异和迁移操作)生成子代Qt,然后合并为集合Rt,之后,通过非支配排序和拥挤距离排序来选择下一代Pt+1中的个体,重复整个过程直至结果收敛。
对于资源受限项目调度问题,常采用作业列表的编码方式,但这种方式只能表示作业之间的执行顺序,无法体现保障人员对作业的分配关系,若再增加一层编码列表来表示分配关系,会极大地增加算法复杂度,并且由于本文研究的舰载机作业与保障人员的关系可能是一对多。因此,为了满足需求并降低编码的冗余度,本文采用基于矩阵的整数编码方式[15]来表示作业与人员的分配关系,在解码时利用优先规则约束各舰载机作业的保障顺序。染色体某一段的编码方式如图2所示。
图2中,白色方框代表保障人员单独完成舰载机作业,例如1号作业由28号保障人员完成;连续的红色方框则代表保障人员共同完成舰载机作业,例如2号和3号作业实际上为同一项舰载机作业,由1号和8号人员共同完成。具体的染色体编码如下式所示。
图2 染色体编码方式Fig.2 Chromosome coding
式中,个体An×m中 的aij的i为 舰载机编号,j为该舰载机的作业编号,aij的取值为区间 (1,MM)上的一个随机整数,表示舰载机i的 第j项作业由人员编号aij进行。将上述多维的编码矩阵展开为一维的矩阵,可以形成一个长度为n×m的字符串,即[a11,a12,···,a1m,···,an1,···,anm]。这 样 编码的好处在于,可以解决舰载机作业与保障人员一对多编码困难的问题,并且增加保障人员团队数量只需增加元素的取值范围即可,不会影响到染色体的长度,这不仅能降低经历过交叉和变异环节后会出现不合法染色体的情况,还可提高算法收敛的速度。
染色体的解码过程是由染色体的字符串到舰载机保障方案的转换过程。舰载机保障方案的仿真除了要在染色体上表示舰载机作业与保障人员的分配关系,还需要考虑舰载机作业的紧前/紧后约束、舰载机作业之间的保障顺序及转移距离。在此,采用离散事件系统仿真策略中常用的事件调度策略,基于遍历事件集合中某个事件的状态变化来推动仿真时钟,从而得到各个舰载机作业的起止时间以及保障人员完成工作的总时间和转移时间等信息。
首先,定义3类事件集合:作业准备(FEL1)、作业工作(FEL2) 、作业结束(FEL3) 。其中,FEL1表示当前作业未满足紧前作业约束或保障人员需求约束,一旦作业满足这2类约束,就可以将作业移至表示作业已经开始工作的FEL2中,再次等待作业完成后,便移至表示作业结束的FEL3中。每名保障人员都有这3类事件集合,染色体按照图2所示的编码方式解码后,所有作业会依次下放到对应保障人员的FEL1中,整个仿真过程也就是每项作业都完整经历3个事件集合的过程。解码算法流程图如图3所示。
图3 解码算法流程图Fig.3 Flow chart of decoding algorithm
由于本文采用的是NSGA2算法,算法结果为Pareto集,而不同保障作业人员数量下的Pareto集必然不同,因此,指挥人员就有了更多可供选择的方案来应对变化莫测的作战环境。对保障作业人员数量的研究旨在通过保障作业人员数量的变化来改变技能组合关系。例如,增加人员数量后是否对目标值有明显的提升,或是减少人员消耗依旧能符合预期效果,只需改变2.1节中的染色体基因选择范围便可进行进一步的研究。
在本文中,选择算子采用二元竞赛选择法,以非支配排序等级高和拥挤距离大为优先选择原则;交叉算子采用离散型多点交叉方式[16];变异算子采取基本位变异,若出现作业需求人员数量与实际分配人员数量不匹配,进行染色体合法性矫正,矫正的规则是将该作业或人员重新随机分配,直至符合要求;迁移算子采用环形连接的拓扑结构来作为子种群迁移路径,使用轮盘赌方法选择迁移个体,在非劣排序中,等级越高的个体更容易被选中。
与普通的遗传算法相比,并行遗传算法的全局搜索能力更强。本文采用岛式模型[17]的并行算法,整个初始种群分为多个子种群,由各个处理器独自运行进化过程,并对独立的搜索空间进行探查,在满足迁移条件后,通过迁移机制交换信息。算法具体流程如图4所示。
图4 基于改进的NSGA2的人员优化配置算法流程图Fig.4 Flow chart of optimization algorithm for personnel configuration based on improved NSGA2
步骤1:初始化算法参数,包括种群规模N、子种群数量m、迭代次数It、交叉和变异因子概率、迁移代数和迁移因子概率、大机组保障模式下待保障舰载机数量、位置和作业集,以及可提供的保障人员数量范围、舰载机作业集中作业之间的并行约束关系。
步骤2:从可提供的保障人员数量范围的最小值开始确定保障人员数量MM,对种群各染色体基因位按照aij=1+MM·rand(0,1)进行初始化。
步骤3:根据2.2节解码操作对染色体字符串进行解码,得到舰载机机群保障完成时间、保障人员负载均衡性和保障人员累计移动时间。
步骤4:对各岛内父种群Pt按 照3个目标值进行对个体非劣排序,然后进行遗传操作得到子种群Qt,随后 针对父种群Pt和 子种群Qt合并的Rt计算拥挤距离并排序,从Rt中 选取排序靠前的N/m个体作为精英保留下来参与下一代的进化。
步骤5:各岛内迭代次数到达迁移代数后,采用迁移策略生成新的初始种群。
步骤6:判断是否满足最大迭代次数It的终止条件,若满足,继续步骤7,否则,回到步骤3。
步骤7:判断数量MM+1是否超过可提供的人员数量范围,若超过,则退出,否则,返回步骤2。
为了验证在连续出动模式下本文模型的可行性和算法的有效性,以美国“福特”级航母为实例,对连续出动模式下的舰载机保障方案进行仿真。在大机组保障模式下,有3架舰载机已经降落滑行到同一保障范围内并系留结束,优化目标为最小化机群保障完成时间、最小化保障人员负载均衡性和最小化保障人员累计转移时间,给出的保障人员数量范围为18~28人,并假设舰载机类型都相同且使用一套舰载机作业集,每项作业需求单独的专业技能。舰载机作业集的串/并行约束如图5所示,保障作业标准时间和人员需求[18]如表1所示。例如,挂弹作业时长1 200 s,需要2名作业人员,该作业只有在补充氧气及氮气作业完成后方可开始,且在挂弹作业结束后才能进行弹药加载及联合自检作业。
表1 舰载机甲板保障作业标准时间及人员需求Table1 Standard time and personnel requirements of the carrier-based aircraft flight-deck support operation
图5 航母飞行甲板舰载机作业集串/并行约束Fig.5 Serial and parallel constraint of flight-deck operation set for the carrier-based aircraft
NSGA2算法参数设置为:共有4个种群进行并行计算,种群数量为100,最大迭代次数为400,交叉概率为0.8,变异概率设为0.1,迁移代数为50,迁移率为0.1,所有算法采用C++编程,在Inter Core i5-8250U 1.6 GHz Windows10.0上运行。
图6所示为保障人员数量为22人时机群保障完成时间、保障人员负载均衡性和保障人员累计转移时间这3个目标平均值在种群进化过程中的变化趋势。由图可以看出,3个目标值均呈单调递减的趋势,收敛速度较快,最终趋于稳定。多次仿真实验证明,各目标值均能收敛至最优值,说明算法具有较强的鲁棒性。
图6 优化目标在种群进化过程中的变化趋势Fig.6 The changing trend of optimization goals in the process of population evolution
图7所示为改进NSGA2算法获得的Pareto最优解集,图8为图7所示Pareto最优解集中A5这一解的舰载机作业保障方案甘特图。选取的保障人员数量为22,其中每个方块中的第1个数字表示舰载机编号,第2个数字表示舰载机作业的编号;甘特图中黑色部分表示保障人员的转移时间,相同颜色的方块表示同类型的舰载机作业;求得的机群保障完成时间为2 533 s,保障人员负载均衡性为299,保障累计转移时间为132 s。由图可见,每名保障人员分配的作业表示该人员应当具备的作业技能,作业执行顺序满足给定的作业串/并行约束,每名保障人员的工作总时间基本达到均衡,且切换作业所需的转移时间也较短。结果显示,算法能获得满意的人员配置结果,作业逻辑符合实际作战环境,方案可行。
图7 Pareto最优解集Fig.7 Pareto chart of optimal solution set
图8 航母飞行甲板舰载机作业保障方案甘特图Fig.8 Gantt chart of flight-deck support operation scheduling plan for the carrier-based aircraft
为进一步验证算法的有效性,取保障人员数量作为输入,将不同保障人员数量下得到的不同Pareto最优解集合按照机群保障完成时间、保障人员负载均衡性和保障人员累计转移时间,依次按从高到低的优先级顺序从中选取保障人员配置方案,得到如图9所示的仿真结果。
图9 航母飞行甲板舰载机作业保障人员数量配置Fig.9 Personnel allocation in support of the carrier-based aircraft flight-deck operation
由仿真结果可以看出:
1) 随着保障人员数量的增加,机群保障完成时间在初始阶段下降明显,后面逐渐趋于稳定。这说明在初始阶段原本执行多份串行作业的人员可以把作业交给其他人负责,这样可以有效减少总的保障时间。随着人员数量的增加,保障完成时间波动不大,这是因为每名保障人员分配的作业变少了,不过作业间的串行约束关系依旧存在。仿真结果说明保障人员数量在一定范围内增加可以给保障时间带来显著收益,但超过该范围后收益就不大了。
2) 随着保障人员数量的增加,保障人员负载均衡性的总体趋势较为稳定。因为无论保障人员数量是否增加,在保证最小化舰载机保障完成时间的前提下,每名保障人员的工作时间均相差不大,这样才会有更好的人员利用率。为了直观地体现人员数量增加给人员负荷带来的影响,引入了人员平均工作时间与机群保障完成时间的比值,称为人员平均负荷水平Avr,其计算方法如式(13)所示。从图9中可以看出,保障人员平均负荷水平在前期随着人员数量的增加呈逐渐上升趋势,到后期变化较平稳,其原因在于因保障作业的时间和需求已固定,如式(13),分子中的保障作业总时长就是固定值,而分母中机群保障完成时间下降的幅度足以抵消人员数量增加的幅度,因此人员平均负荷水平呈上升趋势,到后期机群保障完成时间趋于稳定,人员数量增加的效果也就不明显了,符合实际情况。
3) 保障人员累计转移时间总体呈下降趋势,但在小范围内存在波动。其原因在于在选取Pareto最优解集方案时,是以机群保障完成时间和人员负载均衡性作为第1和第2优先目标,因而增加保障人员数量会给保障人员累计转移时间带来不确定的影响。但随着保障人员数量的增加,保障人员分配的保障作业会更少,在甲板上转移的时间也就会相应减少,这与实际保障状况吻合。
本文分析了舰载机保障作业中保障人员流动的局限性和有效性,引入了保障人员累计转移时间最小化概念,结合最小化机群保障完成时间和保障人员负载均衡性,建立了多目标的保障人员调度模型,并对保障人员团队数量和人员技能配置进行了研究。设计了一种基于改进NSGA2的人员优化配置算法来求解该模型,最后通过实例进行了仿真验证,主要得到如下结论:
1) 建立的保障人员配置数学模型,可以结合实际保障需求,更好地兼顾保障完成时间、人员负载均衡性和累计转移时间三者之间的关系,有利于实际调度分配。
2) 基于改进NSGA2的人员优化配置算法,针对舰载机不同作业需求及其所需专业技能不同的特点,采用基于矩阵的整数编码方式,将人员编号作为基因值,而基因位置则指定相应的舰载机作业,然后基于事件调度策略对染色体解码,最后基于改进NSGA2算法并引入迁移策略提高解空间的搜索能力。仿真结果显示,对于本问题,该算法具有很好的优化性能和鲁棒性。
3) 舰载机保障方案甘特图清晰地展现了每架舰载机不同保障作业的起止时间和所分配人员编号,以及保障人员的技能分配,可为航母舰载机保障人员技能培训、团队配置和方案评估提供一定的理论基础。
由于舰载机保障作业涉及的因素复杂,本文主要针对保障人员数量和技能的配置进行了研究,而在实际保障作业中,还应涉及保障设备的数量和范围约束。本文算法给出了舰载机保障方案中保障人员应当具备的技能,但在实际情况中可能不存在这样的人员,或是分配多项作业的人员需具备的技能差距较大。对此,有如下改进方向:一是用相同时长的作业进行替换;二是培训少数全能型作业人员;三是增加作业属性,以及增加人员分配的作业属性不能差距过大的约束。此外,还可在给出的保障方案集与实际作业团队之间建立匹配机制,给出有效的保障人员配置,并在后续的工作中继续予以丰富。