舰载机模块化弹药调度方案优化设计

吕晓峰, 杨东泽, 马 羚

(海军航空大学岸防兵学院, 山东 烟台 264001)

0 引 言

随着军事装备的不断发展,战场形势瞬息万变,战场的打击目标与打击方式也可能会随之改变,原有固定的弹药型号很有可能无法满足实际的作战任务需求。若将舰载机弹药进行模块化设计,每个模块具备统一的对外接口但功能并不一致,在战时便可根据实际情况进行组装[1]。例如美军的GBU-15(V)滑翔制导航空炸弹由导引头、战斗部和尾部组件3部分组成,可装配通用爆破型、侵彻爆破型和集束型3种战斗部,并且可装配红外制导型和电视制导型两种导引头,战时可根据不同任务进行组合[2]。如今模块化技术快速发展,已从部分组件的模块化设计向全模块化转变,即从同一系列不同型号间导引头和战斗部的换装到战时根据实际战场情况与作战需求选择相应的模块进行组装[3],不仅可以横向互换,更能纵向组合[4]。随着该技术的发展,舰载机弹药对于模块化的需求日益凸显,基于作战使用的考虑,使用模块化弹药时贮运,保障部门能够依据任务灵活配置相应类型的舰载机弹药,让舰载机更好地应对作战目标;基于贮存运输的考虑,进行模块化之后,弹药存放更加灵活,在相同容积的舱室能够容纳更多的弹药。

在舰载机的各项保障任务中,舰载机弹药的保障耗时最长[5],目前对于舰载机弹药调度研究大部分都是面向传统整弹调度,对于模块化弹药调度研究很少。对于弹药整体调度,马登武等[6]和张洪亮等[7]建立了以调度结束时间最小化为优化目标的舰载机弹药调度模型,但是其研究对象相较于模块化调度流程并不相同:一是模块化调度需将各模块进行装配,增加了装配环节;二是一个弹药分为多个模块,调度对象呈倍数增加,原有的编码方式已完全不适用;三是约束条件较传统保障更加复杂,在调度时须保证装配区不会发生囤积弹药模块的情况,对各模块的调度次序提出了要求。

虽然目前对弹药模块调度问题研究很少,但其与多工序的配件调度问题有一定的相似之处,可将弹药各个模块看作配件,并且其多个调度流程可看作多个工序,将参与各个模块调度的舱室、升降机和装配线看作机器。对于模块化弹药调度问题,存在同一个工序有多个机器可以调度的情况,比如某个模块在多个舱室内存储,可以由多个舱室进行提供,所以需选择舱室,并且需要计算各模块的调度顺序,是作业车间调度问题(job shop scheduling problem, JSP)的延伸,属于柔性JSP(flexible JSP,FJSP)[8],JSP中每个工序只能由一个机器进行加工,不涉及选择机器的问题。Wang等[9]建立了以最大模糊时间最小化为优化目标的模糊柔性作业车间调度模型,并通过遗传算法求解。Xu等[10]和Yin等[11]等将任务完成时间最小化为目标函数,使用多层编码遗传算法对模型进行求解。Chou等[12]建立以最小化最大任务完成时间为优化目标的配件组装调度模型,提出使用改进灰狼优化算法求解问题。通过对以上文献分析,模块化弹药调度相较于工厂工件调度问题,情况有所差异,对于约束条件,不只是各个模块机器选择和调度顺序的问题,同时还涉及最后各模块装配的情况,在装配环节多个模块需进行组装,模块数量发生变化造成变量变化,在装配区不能堆积过多模块。对于优化目标,结合本文研究对象,在建立任务完成时间最小化的优化目标之外,还需考虑各升降机和各舱室平均工作时间,若不考虑该目标函数,则可能致使某个升降机被频繁使用,从而导致该升降机发生故障的概率增大,对于舰载机弹药调度,若某个升降机发生故障,则会造成该升降机对应的通道发生瘫痪。

相较于传统舰载机弹药调度问题,本文对多层编码进行优化以解决调度对象的数量和工序增加的问题,同时结合实际保障要求对模型进行约束。相较于工厂工件调度问题,增加舱室和升降机平均工作时间最小化为优化目标,避免出现调度工作分配不均衡的问题,同时通过改进编码方式解决变量变化的问题。随着智能算法的不断发展,近年来众多学者采用遗传算法[13-16]、粒子群算法[17-19]、蚁群算法[20-22]、细菌觅食算法[23]、博弈算法[24-25]、邻域搜索算法[26-27]、禁忌搜索算法[28-29]、启发式算法[30]等求解FJSP。其中，遗传算法优秀的全局寻优能力和较强的鲁棒性使其成为处理全局问题的最佳算法之一[31]。

基于以上分析,本文以任务完成时间最小化和舱室与升降机平均工作时间最小化为优化目标,结合研究对象设立约束条件,根据所建立的模型优化多层编码方式,每层代表含义不同,便可以用一个染色体表示复杂问题的解,运用遗传算法求解问题,最后对实际问题进行验证仿真,表明算法的可行性。

1 模块化弹药调度问题描述及数学模型

1.1 问题描述

根据相关文献[2-3,32],美军福特号航母上的模块化弹药调度流程如图1所示,相较于传统的整弹贮运模式增加了装配环节,共有3个调度流程,并且可将库内转运、垂直转运和装配视作3个工序,调度流程如下:

(1) 库内转运:任务相关舱室工作人员收到下达的保障方案,按照任务指示要求准备弹药相关模块,送至升降机阱口;

(2) 垂直转运:相关模块由舱室工作人员送入升降机阱口后,由垂直转运战位的操作人员控制武器升降机,将其送至水平转运装配室;

(3) 转运装配室装配:弹药模块由升降机送至转运装配室后,将各模块暂存放于装配准备区,装配工作人员在此进行部件安装及模块对接。

图1 模块化弹药调度流程图Fig.1 Modular ammunition scheduling flow chart

1.2 模块化弹药调度模型建立

根据模块化弹药调度流程,其任务的完成主要包括模块的转运和装配。假设有a个舱室,有b个升降机,装配室中有m个装配线,最终需要n枚完整的弹药,一枚弹药分为c个模块。为了降低调度工作的复杂度,同时减少装配区模块的堆积,这里采用逐枚弹药进行调度的方案。对于某枚弹药各模块的调度工作可描述为：首先，c个模块在a个舱室完成库内转运,为第一道工序;其次，c个模块通过运用b个升降机转运至装配室,为第二道工序;最后，c个模块在m个装配线中选择其中一个进行装配,为第三个工序。

问题的求解包括两个方面,其一是为模块选择合适的舱室、升降机和装配线,其二是确定高效的工序顺序以及各个工序的起始时间,需要多枚模块化弹药的任务时使得整个调度工作最快完成,并且得到的调度方案合理,在模型中首先提出以下假设:

一个装配线一次只能装配一枚弹药；在单枚弹药的所有模块调度至装配区之后再进行装配；不同模块在进行同一个工序时没有优先级；模块选择的升降机处于空闲状态时,在该模块完成库内转运之后立即进行升降机转运。

(1)

(2)

(3)

在进行弹药调度时,首先须提高任务完成的效率,即要求任务完成时间最短,根据式(2)得到弹药调度的首要目标函数为

(4)

在保障任务完成速度的同时须使分配到各个站位的任务均衡,这样既使得调度工作更加合理,同时不会使某个升降机相较其他升降机使用频率过高,导致其故障率升高,因此建立次要目标函数为

(5)

在选择方案时首先比较各个方案的首要目标函数值,优先选择首要目标函数值低的方案,若首要目标函数值相同,则比较次要目标函数值,再选择次要目标函数值低的方案。

结合实际情况,为使模型能够得到合理的调度工作分配方案,对模型设置约束条件如下:

(6)

(7)

xekf≤aekf, ∀e,k,f

(8)

(9)

(10)

其中，将3个工序的舱室、升降机和装配线统称为机器。

约束条件中的公式和对模块的工序顺序进行约束,使每个模块按照正确的工序顺序进行调度和装配;公式和对模块的工序机器进行约束,使得各个模块的每个工序只能被分配到可选机器中的一台;公式对工序的结束时间进行约束。

综上,模块化弹药调度的目标函数与约束条件如下:

(11)

2 算法设计

2.1 编码方案

根据本文模型,染色体的编码方式采用整数编码的方式,同时在编码时需体现当前模块所属的弹药序号、当前模块的调运进程以及所选择的机器。为解决保障对象数量变化带来的变量变化的问题,并且需保证模块工序选择与机器选择的编码维度相同,将模块组装工序对应的编码置零以表示多个模块合为一个整体的过程,而以往常用的编码方式并不能实现此结果。改进后的编码方式将染色体的编码分为3层,第1层为目前模块所属的弹药序号,第2层为所有模块在各个机器上的调度顺序,第3层表示模块每个工序选择的机器。如染色体[1 2 1 2 3 1 3 0 2 3 6 1 7 5 9]所示,该染色体的第1位表示当前调度的是第1枚弹药,第2位至第8位表示的是各个模块的调度顺序,依次是模块2的库内转运→模块1的库内转运→模块2的垂直转运→模块3的库内转运→模块1的垂直转运→模块3的垂直转运→3个模块的装配,由于在装配阶段所有模块都需参与,3个模块合为一个整体,所以这里用0表示,第9位至第15位表示执行相应转运工作的机器序列,依次是舱室2→舱室3→升降机6→舱室1→升降机7→升降机5→装配线9。

具体实现过程如下:生成的染色体长度为2×(c×(d-1)+1)+1的整数串,其中c为模块个数,d为调度的工序数量。第1层数值是根据当前弹药序号生成,第2层模块序列的生成是随机生成的,每生成一个数值对应的模块调运次数就减少一次,直至第2层的编码完成,根据第2层的模块序列,第3层随机生成可转运的机器序号。

2.2 适应度值

适应度函数是评价方案优劣的标准,一般情况下会将目标函数的值转化为对应染色体的适应度值,结合本文建立的模块化调度模型,基于弹药调度任务完成时间与各机器平均工作时间得到适应度函数的计算公式如下:

fitness(i)=T1

(12)

fitness(F2)=T2

(13)

根据形成的染色体计算两个适应度函数值,在进行最优解的更新时需判断两个适应度函数值,若第1个适应度值更小则该染色体对应的方案更优,在第1个适应度值相同的情况下比较第2个适应度值。

2.3 选择操作

本文在选择较好的染色体时采用轮盘赌选择法,即适应度值比例法,其中个体选择概率如下所示:

Fitness(i)=1/fitness(i)

(14)

式中:pi(i)表示染色体i在每次选择中被选中的概率。由于第1个目标函数是本文模型的首要目标函数,被选中的概率依据第1个适应度函数。轮盘赌法在选择个体时首先会参考上一代个体的适应度值,让适应度值大的个体有更大概率能被选择作为父代个体来生成新个体。

2.4 交叉操作

交叉操作是染色体进化的主要操作之一,通过父代染色体之间的交叉操作获得下一代新的染色体。根据本文的编码形式,采用整数交叉法,首先在种群中随机选择两个染色体作为父代染色体,并将染色体的第2层和第3层抽取出来,对两个染色体的第2层进行交叉,其次随机选择交叉位置进行交叉，如图2所示。具体方法如下:若随机生成的交叉位置为3,则将父代染色体从起始位置至交叉位置进行交叉。

图2 染色体交叉示意图Fig.2 Chromosome crossing diagram

染色体交叉之后会出现某些模块的工序会发生变化,比如染色体1中的模块2相较于交叉之前多了一道工序,而模块3相较于交叉之前少了一道工序,由于染色体2是与染色体1发生的交叉,染色体2的变化情况正好与染色体1相反。针对交叉后发生的变化需要做出调整,同时根据变化后的工序将其机器调整为交叉前的机器,如图3所示。

图3 染色体调整示意图Fig.3 Chromosome adjustment diagram

2.5 变异操作

种群通过变异操作对染色体的局部基因值做变动获得新的个体,增加种群的多样性,从而使得整个种群向前进化。在进行变异操作时,首先从种群中随机选取一个变异个体;其次随机生成两个变异位置pos1和pos2;最后将染色体pos1和pos2位置的模块及其对应的机器进行调换,产生新的染色体,假设生成的交叉位置为3和5,如图4所示。

图4 染色体变异示意图Fig.4 Chromosome variation diagram

2.6 算法步骤

算法流程图如图5所示。

图5 算法流程图Fig.5 Algorithm flow chart

步骤 1设定遗传算法基本参数,种群数目、最大遗传代数、交叉率和变异率。

步骤 2根据调度模型产生初始种群。

步骤 3根据式(12)计算初代适应度值。

步骤 4运用轮盘赌法选择染色体。

步骤 5按照交叉概率选择染色体,并产生交叉片段进行两两交叉,同时对交叉后不符合实际的染色体进行补缺。

步骤 6进行变异操作。

步骤 7若达到最大遗传代数转步骤8,否则转步骤4。

步骤 8输出最优解。

3 案例分析

本文采用多层编码遗传算法求解模块化弹药调度问题,假设一枚弹药分为3个模块,库内转运与升降机调度分别有4台机器,每个模块都需经过库内转运与升降机调度两个流程,最后3个模块一起进行装配,装配时根据各个装配线状态选择装配线,最终需装配3枚完整的弹药。各个模块在进行各阶段调度工作时可选择的机器如表1所示,其中库内转运的1～4号表示4个舱室,升降机调度的5～8号表示4个升降机。第1行第2列的数据为[1,3],表示模块1的库内转运阶段可选择的舱室有1号舱室和3号舱室。第3行第3列的数据为[6,8],表示模块3的升降机调度阶段可选择的升降机有6号升降机和8号升降机。

表1 工序可选机器表

模块各个阶段工作对应的机器调度时间如表2所示,第1行第2列的数据为[3,4],表示模块1选择1号舱室进行库内转运时转运时间为3 min,模块1选择3号舱室进行库内转运时转运时间为4 min。第2行第3列的数据为[7,8],表示模块2选择5号升降机进行升降机调度时需要时间为7 min,模块2选择6号升降机调度时需要时间为8 min。

表2 各机器调度时间

算法的基本参数设置如下:种群数目设为50;最大遗传代数为50;交叉概率为0.8;变异概率为0.6,各弹药调度完成时的种群适应度值变化如图6～图8所示,分别表示3枚弹药的调度方案求解时适应度值的变化与种群均值的变化。经过50次迭代,计算第1枚弹药调度方案的种群适应度值稳定在20 min,种群均值在23 min左右；计算第2枚弹药调度方案的种群适应度值稳定在27 min,种群均值在30 min左右；计算第3枚弹药调度方案的种群适应度值稳定在33 min,种群均值在37 min左右。

图6 第1枚弹药种群适应度值变化Fig.6 Changes in population fitness value of the first ammunition

图7 第2枚弹药种群适应度值变化Fig.7 Changes in population fitness value of the second ammunition

图8 第3枚弹药种群适应度值变化Fig.8 Changes in population fitness value of the third ammunition

图9为模块化弹药在转运和装配时的甘特图。通过对甘特图中每个单元起点和终点的验证,发现各单元之间不存在重叠的情况,并且次序正确,所得方案可行,表明改进的多层编码遗传算法解决模块化弹药调度问题具备可行性。

图9 模块化弹药调度甘特图Fig.9 Modular ammunition scheduling Gantt chart

图9中的4位数字表示当前调度工作的具体信息,如1011编码中第1位数字“1”表示当前进行的是第1枚弹药的调度工作,第2位和第3位数字“01”表示1号模块,第4位数字“1”表示当前进行的是第1道工序。因此，1011编码代表的完整含义是当前正在进行第1枚弹药中1号模块的第1道工序,即库内转运工作,再结合甘特图纵坐标,该工序在3号舱室进行。同理，2032编码表示当前正在进行第2枚弹药中3号模块的第2道工序,即升降机调度工作,再结合甘特图纵坐标,该工序在4号升降机进行。3003编码表示当前正在进行第3枚弹药的第3道工序,即3个模块的装配工作,由于装配工作是3个模块一起参与的,故编码的第2位和第3位数字都用“0”表示,再结合甘特图纵坐标,该工序是在9号装配线进行的。

4 结 论

本文针对舰载机模块化弹药调度问题,建立了多模块、多工序的舰载机模块化弹药调度模型,主要结论如下:

(1) 针对舰载机模块化弹药调度完成时间问题,提出了递推法计算任务完成时间。

(2) 运用基于多层编码的遗传算法计算以任务完成时间最小化和各舱室与升降机平均工作时间最小化为优化目标的调度方案,并结合本文研究对象在装配工作中数量的变化对多层编码进行改进,用以完整地表达各阶段模块的状态。

(3) 对建立的模型与改进后的算法进行Matlab仿真,验证本文方法的可行性。