刘 彦， 陈春良， 陈伟龙， 范江波

(1. 陆军装甲兵学院装备保障与再制造系， 北京100072； 2. 中国卫星海上测控部， 江苏 江阴 214431， 3. 66058部队， 天津 301700)

现代战争作战节奏越来越快，作战进程不断缩短，作战空间逐渐变广，使得战损装备多、战时装备保障时间缩短，维修任务繁重，对战时装备维修的时效性提出了更高的要求。巡回修理作为战时装备维修的主要修理方式之一，通过派遣多个巡回修理组对分布在战场的众多待修装备实施抢救修理，实现作战部队战斗力的保持与恢复。

面对众多随机出现的不同损伤程度的待修装备，如何在有限的修理时间内，综合权衡待修装备位置、修理工作量、重要度、各巡回修理组的修理能力及其变化等复杂因素，合理安排巡回修理任务，解决“先修谁”“由谁修”“何时修”“怎么修”的战时装备维修任务调度问题，从而实现维修效益全局最优化，是具有重大意义且亟待解决的军事难题。

由于战场态势复杂、约束条件多、研究难度大，众多学者对装备维修任务调度进行了深入探索，取得了一定成果，具有一定的指导意义。如：张立民等[1]分析了战时装备维修任务调度的特点，建立了基于最大保障时间的维修任务静态调度模型；王正元等[2]以尽快恢复装备战斗力为目标，探究了动态维修任务调度的优化方法；陈春良等[3]考虑时间约束及负载能力约束的影响，将装备维修任务调度问题转化为车辆路径问题，并设计了基于改进最大最小蚂蚁算法(Max-Min Ant System,MMAS)的维修任务规划方法，实现了单修理组的维修任务调度；陈伟龙等[4]提出了进攻作战抢修任务动态调度问题，将其抽象为动态车辆路径问题，以获得的二次作战时间最大为调度目标构造了调度模型，并设计了变体遗传算法(Genetic Algorithm,GA)进行模型求解。

从模型抽象的角度来看，装备维修任务调度问题主要可抽象为车间作业调度问题[1]、资源约束项目调度问题[5]以及车辆路径问题[4，6]，其中前二者适用于基地级修理及定点修理，后者更适用于伴随修理及巡回修理。随着装备维修任务调度研究的不断深入，调度目标根据任务需求(如维修效益[7]、装备重要度[8]、二次作战时间[9]等)不断丰富，但大多数研究仅限于单目标调度；另一方面，约束条件根据战场情况不断细化，但主要聚焦在传统约束，如考虑装备维修流程[10]、维修专业[11]、维修力量休息[5]、不确定性[12-13]等。陈春良等[9]考虑战场抢修时修理能力的限制，提出了非遍历型调度，符合战时修理实际，具有一定指导意义；陈伟龙等[12]虽然考虑了待修装备修复状态，但仅仅停留在对完成任务数的影响，并未考虑修复状态对维修时间及装备重要度的影响。

总体来看，现阶段装备维修任务调度研究尚未针对修理方式的差异进行研究，也未对巡回修理中如何合理规划诸多实际约束下维修任务以及动态处理不确定性信息问题进行深入研究。现有研究大多数是以最大保障时间、最长二次作战时间等作为单一调度目标进行任务调度，难以全面考虑维修任务需求，且约束条件相对较为理想化，忽略了修复状态的不确定性及其对维修时间和装备重要度的影响，也未考虑时间窗约束对维修任务调度的影响。

针对以上问题，笔者以战时装备巡回修理任务调度问题为研究对象，考虑待修装备修复状态的不确定性及其对维修时间和装备重要度的影响，引入待修装备修理时间窗约束及非遍历约束，考虑待修装备的不确定性，构建了多个装备巡回修理组任务动态调度模型，设计了改进的NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm Ⅱ)算法对模型进行求解，并通过示例验证了模型及算法的有效性及合理性。

1 基本描述

1.1 问题描述

随着作战进程的推进及作战任务的遂行，受敌方火力打击的影响，我方作战装备不可避免地会在不同时间、不同地点出现不同程度的损伤。巡回修理力量编成多个巡回修理组，根据待修装备损伤及分布情况，有计划地对分布在战场各地域的待修装备进行巡回修理，既可相对有规律地遂行保障，又可对突然出现的待修装备做出快速反应。在一体化指挥信息平台的支撑下，各待修装备的位置、预计修理时间以及装备重要度等信息可通过相应手段获知。各巡回修理组从初始地域出发，前往各待修装备所在地域实施巡回修理，完成各自修理任务后不返回初始地域，而是根据保障指挥员的安排执行后续任务。在实施修理任务的过程中，保障指挥员会根据不断更新的待修装备及各巡回修理组信息，对各巡回修理组的修理计划进行动态调度。

在待修装备不断出现，而修理时间及修理能力有限的前提下，需考虑待修装备修理时间、重要度、修复状态的不确定性、巡回修理组修理能力的变化等因素的影响，从而为各巡回修理组合理分配维修任务，确定各巡回修理组的各待修装备的修理顺序和修复状态，并根据不断出现的待修装备及诸多不确定因素对维修任务进行动态调整，使整体的巡回修理效果达到最优化，最有利于战斗力的快速恢复及作战任务的完成。

1.2 假设描述

为了简化问题，进行如下假设：

1) 参与装备巡回修理任务调度的各待修装备均在巡回修理组的修理能力范围内，不考虑备品备件短缺情况；

2) 研究对象为合成旅巡回修理力量，编成多个巡回修理组对所属部队实施全域巡回修理；

3) 在修理任务实施过程中，各巡回修理组独立完成各自修理任务，相互独立，不存在相互支援；

4) 各待修装备的位置、预计修理时间、修理时间窗、装备重要度等相关信息已通过技术侦察获知；

5) 各修理组修理过程中不会由于任务调整而中止当前正在执行的任务；

6) 各巡回修理组完成修理任务后不返回初始地域，而是等待保障指挥员的后续指挥调度；

7) 待修装备修复后直接归建作战部队并参与作战，忽略归建时间；

8) 不考虑敌方火力打击对待修装备造成的二次伤害。

2 模型构建

2.1 参数定义

为方便研究，对相关参数定义如下：

1)Tsta为战斗开始时刻，Tbeg为巡回修理开始时刻，Tend为战斗结束时刻。

2)E为待修装备集合，且|E|=n，n为待修装备数量，H为始发点集合。

4)ti为待修装备i出现的时刻，(xi,yi)为待修装备i的位置坐标，其修理时间窗为[ti,Tiup]，其中Tiup为修理窗时间上限。

8)pk为第k个巡回修理组的修理能力，即每小时能提供的人时。

10)α为惩罚系数，用以表征时间窗对装备重要度的影响。

14)qk为第k个巡回修理组修理路径中的截点，表示该组最终实际修理的最后一台装备，且有

2.2 多目标参数确定

实施战时装备巡回修理旨在最大可能地修复待修装备，使其能尽快返回战场继续参与战斗，以发挥修竣装备对装备体系的贡献，使作战部队的战斗力能得到最大程度的恢复。因此，可从以下3个方面来综合衡量装备巡回修理任务调度的优劣。

1) 修竣装备总数。修竣装备总数是整个战斗过程中各巡回修理组修复的待修装备数量总和，它反映了巡回修理的快慢程度，直接影响装备的参战率，其表达式为

(1)

2) 修竣装备总重要度。修竣装备总重要度是修竣装备重要度的总和，反映了所修竣装备对整个装备体系的贡献度，是巡回修理重要性的反映，其表达式为

(2)

3) 二次作战总时间。二次作战总时间是指各修竣装备从修竣时刻至战斗结束时刻的时间长度的总和，反映了装备修竣后返回战场参战的有效时长，是修理及时程度的体现，其表达式为

(3)

以上3个参数从不同侧面反映巡回修理效果，且相互影响、相互制约，需要构建多目标优化模型来实现全局的综合权衡。

2.3 调度模型建立

结合巡回修理特点，考虑各巡回修理组修复各待修装备的修理时间关系、遍历与非遍历特点、待修装备修竣与否，确定相关约束条件，构建装备巡回修理任务调度模型如下:

(4)

(5)

(6)

其中，式(4)-(6)表示面向装备巡回修理的任务调度目标分别为修竣装备总数最大、修竣装备总重要度最大、获得的二次作战总时间最长；式(7)表示巡回修理组从初始位置前往并修竣该组计划内第一台待修装备的时间关系；式(8)表示巡回修理组修理计划内相邻2台待修装备的修竣时刻的约束关系；式(9)表示修理时间以及修理能力的约束关系；式(10)表示巡回修理组的遍历与非遍历约束；式(11)表示每个待修装备至多仅由一个巡回修理组修理一次；式(12)、(13)表示任意一条弧线的终点(起点)待修装备有且仅有一个起点(终点)待修装备与之相连。

2.4 调度模型分析

2.4.1 多目标分析

装备巡回修理任务调度模型从修理数量、修理对象重要程度以及修理及时性3个方面权衡维修任务调度方案的优劣，能够克服传统维修任务调度单纯追求某一目标而导致调度方案在其他需求方面存在较大偏差的问题，从而能够更加全面地权衡维修任务调度方案的优劣。

Pareto解集[14]通过支配关系判断调度方案的优劣，能够实现各调度目标间的均衡，是处理多目标调度问题的较好思路。通过在多个目标中协调平衡，可获得一组可接受解(即Pareto最优解集)，从而增加了保障指挥员的决策余地。保障指挥员可根据战场实际需求及决策偏好从Pareto最优解集中选择满意的调度方案。

设定满意方案的决策策略为通过对Pareto最优解集中的解进行规范化处理，采用加权法进行排序优选，从而选择满意解，即

(14)

2.4.2 修复状态的不确定性

巡回修理相对于伴随修理而言，修理开始的时间相对滞后、待修装备相对较多且损伤程度更严重。由于修理时间的限制，为了使待修装备尽快得到修复并返回战场参战，待修装备的修复状态并不全是完全修复，而有可能是仅恢复了部分功能，即待修装备的修复状态分为“能正常作战”S1和“能应急作战”S2。

待修装备修复至不同状态对维修任务调度均产生较大影响，主要是所需的修理工时和修复后获得的装备重要度不同。因此,在制定调度方案时，不但要确定各待修装备的修理顺序，还需确定各待修装备的修复状态，这使得维修任务调度问题更为复杂，求解难度更大，但同时也更贴近实际，具有更强的实用性。

2.4.3 修理时间窗

由于修理能力的限制，难以实现所有待修装备在第一时间均得到修复。随着作战阶段、作战任务的变化，当超过某一时刻待修装备仍未得到修复，该待修装备的重要度将会受到影响。因此借鉴车辆路径问题中的时间窗[15]概念，引入待修装备修理时间窗，对超出修理时间窗而未得到修复的待修装备重要度进行惩罚，其惩罚公式如下：

(15)

2.4.4 非遍历性

巡回修理组负责全域的巡回修理，待修装备多、修理难度大，而受修理时间及修理能力的限制，难以对散布在战场的各待修装备实现全部修复。在调度初期，参与调度的待修装备较少，在任务规划时一般可实现遍历修理(即对全部待修装备进行修理)，但随着作战进程的推进，待修装备不断增多，无法对参与调度的众多待修装备实现全部修复，需采用非遍历型调度。

2.4.5 修理能力变化

战时各巡回修理组的修理能力存在差异，且受战场环境等诸多因素影响，各巡回修理组的修理能力会随着修理任务的遂行而逐渐发生变化。主要体现在随着修理任务的实施，修理人员会产生疲劳，从而影响修理效率，使巡回修理组的修理能力发生变化。

修理人员疲劳所导致的修理能力变化可通过修理效率来度量，其计算公式为

(16)

待修装备的修理时间不但与所承担修理的巡回修理组有关，还受其修理顺序的影响，导致装备维修任务调度更加复杂。

2.4.6 动态驱动策略分析

在处理装备维修任务动态调度问题时，引入滚动时域思想[11]，根据调度需求将整个任务剖面转换为一系列离散时间点的静态调度问题，通过多次维修任务调度，实现动态问题静态处理。而动态驱动策略就是设定某一驱动条件用以判断该时刻是否需要对维修任务进行再次调度，是动态调度的基础。

该动态调度策略在每次重调度时，更新巡回修理组及参与调度的待修装备信息，消除待修装备的实际修理时间与计划修理时间差所产生的调度误差，在实现维修任务动态调度的同时也提升了动态调度的可靠性。

3 模型求解

装备巡回修理任务调度模型是一个存在诸多约束的多目标调度模型，针对模型特点，笔者结合Pareto解集思想，设计了改进遗传算法来求解装备巡回修理任务多目标动态调度问题。

3.1 Pareto最优解集构建

传统多目标优化方法通过线性加权或目标规划等方法处理多目标调度问题，其本质是将多目标问题转化为一个或一系列单目标优化问题进行求解，难以解决多个优化目标之间的冲突关系，存在依赖先验知识、难以处理Pareto最优前端非凸等问题。NSGA-II算法作为最优秀的多目标进化算法之一，在保证种群多样性及保护种群优良个体的同时降低了计算复杂度[16]。因此，笔者通过NSGA-II算法的精英策略，采用非支配排序方法并结合拥挤度比较算子，获得Pareto最优解集，为保障指挥员提供决策依据。保障指挥员可根据战场态势及实际需求，依托决策偏好及决策策略，在Pareto最优解集中选择最满意解。

3.2 编码与解码设计

考虑装备巡回修理任务调度具有多个巡回修理组、非遍历性以及待修装备修复状态不确定性等特点，设计3段式编码以实现相关约束：前段采用顺序编码，用于表示巡回修理组的任务分工；中段采用“1-2”整数编码，用于表示待修装备的修复状态，1表示修复状态为S1，2表示修复状态为S2；后段采用整数编码，表示断点位置，用于划分各巡回修理组。该编码方式能实现多个巡回修理组的非遍历约束以及待修装备修复状态不确定性约束，且染色体与解一一对应，避免了遗传操作中不可行解的产生，大大提高了算法收敛速度。解码时，选取目标函数作为适应度函数，通过相关约束，计算求得截点的信息及相应适应值，从而实现解码。

编码及解码示例如图1、2所示，其中染色体X=(4,8,2,6,3,10,7,5,1,9,1,1,2,1,2,2,1,2,1,1,3,7)，n=10，m=3。经解码可知，共有3个巡回修理组负责10台待修装备的修理任务，任务计划安排为：巡回修理组1的任务安排及修理顺序为4-8-2，修复状态分别为S1、S1、S2；巡回修理组2的任务安排及修理顺序为6-3-10-7，修复状态分别为S1、S2、S2、S1；巡回修理组3的任务安排及修理顺序为5-1-9，修复状态分别为S2、S1、S1。截点信息为(1，5，8)，表明受诸多约束的影响，部分待修装备并未来得及修复，最终实际修理任务完成情况为：巡回修理组1修竣待修装备4，修复状态为S1；巡回修理组2修竣待修装备6-3，修复状态为S1、S2；巡回修理组3修竣待修装备5，修复状态为S2。适应值分别为F1、F2、F3。

图1 编码示例

图2 解码示例

3.3 遗传算子设计

3.3.1 父染色体选择

根据NSGA-II算法中的非支配排序和个体间拥挤距离得到比较算子，采用BTS(Binary Tournament Selection)从上一代染色体中选取20%的个体作为父染色体进行后续交叉变异操作。

3.3.2 交叉变异

由于染色体采取3段式编码，各段编码的编码方式及其实际意义不同，其交叉变异无法采用传统方式进行。为了增大种群多样性，提高收敛速度，针对编码特点，确定“前段只进行变异操作，中段和后段可进行交叉及变异操作”思路，设计了相应遗传算子，对每条父染色体进行如下遗传操作：1)前段、后段均采用随机更新操作；2)前段采取随机更新，后段采取倒置操作；3)前段采用倒置操作，后段采用随机更新操作；4)前段采用倒置操作，后段采用滑动平移操作；5)前段不采取操作，后段采用随机更新操作。

3.4 算法流程设计

模型求解步骤如下：

1) 初始化相关参数。主要是确定种群规模pop_size、最大迭代次数num_gen等，并随机产生初始种群P0。

2) 对种群P0中任一染色体进行解码，计算其适应值和截点信息，得到初始化可行解种群O，并记为pop_chrom。

3) 根据NSGA-Ⅱ算法对可行解种群O进行快速非支配排序，计算非支配集个体间拥挤距离，并令gen=1。

4) 根据BTS从pop_chrom中随机选出数量规模为pop_size的父代染色体种群parent_chrom。通过遗传算子进行遗传操作，产生子代染色体种群offspring_chrom，并计算offspring_chrom中任一染色体的截点信息及其适应值。

5) 采用NSGA-Ⅱ算法对pop_chrom及offspring_chrom进行快速非支配排序，计算非支配集个体间拥挤距离，根据BTS从pop_chrom及offspring_chrom中筛选出规模为pop_size的新一代染色体pop_chrom，从而实现父代优秀个体基因的精英保留。

6) 判断是否gen

7) 判断重调度驱动策略是否满足。若满足，转入步骤1)进行重调度；否则运算终止，输出调度结果。

4 示例仿真与分析

4.1 示例仿真

某合成旅受上级指示执行机动进攻任务，受敌方火力打击，经过一段时间后，陆续出现待修装备，在一体化指挥信息网络的支撑下，经技术侦察，各待修装备相关信息均已获知，保障指挥员根据已知信息，派遣3个巡回修理组对全旅实施全域保障，各巡回修理组遂行巡回修理任务，负责修理120 min内能完成的待修装备。

战斗初期(t≤300 min)，需要更多、更重要的装备及时参战，取μ1=0.2，μ2=0.6，μ3=0.2，战斗后期(t>300 min)，需要提供更多的作战时间，取μ1=0.3，μ2=0.2，μ3=0.5。

根据巡回修理组的实际机动时间、修理时间以及调度策略对装备维修任务进行动态调度，得到调度规划结果如表2所示。

表1 待修装备信息

表2 调度规划结果

此次装备巡回修理任务调度共经历了6次调度过程，在MATLAB软件平台用时分别为11.45、10.87、9.68、9.75、8.32、9.06 s。最终装备巡回修理路径规划如图3所示。

图3 装备巡回修理路径规划

4.2 结果分析

由表2可以看出：

1) 从巡回修理组开始实施巡回修理至战斗结束，共修复装备26台，获得的装备重要度总和为12.17，二次作战时间为6 099 min，约101 h，对恢复部队战斗力提供了较有力的保障，间接证明了战时巡回修理的重要性。

2) 调度时间均在12 s以内，满足战时装备维修任务调度的实效性要求，同时也证明了所构模型和算法的可行性。

3) 在动态驱动策略的影响下，一共进行了6次调度，实现了待修装备不断出现情况下维修任务动态调整，其中前5次调度为遍历型调度，第6次调度为非遍历性调度；待修装备20、28、29、30未纳入最终的巡回修理任务规划中，这主要是由于战时修理时间的限制导致修理任务无法全部完成，反映了巡回修理的非遍历性。

4) 在第105 min进行第2次调度时，待修装备8纳入巡回修理组3的修理计划中，并安排在巡回修理组3的第3顺位，但在第206 min进行第3次调度时，巡回修理组3还在修理第2顺位的待修装备7，待修装备8参与重调度，并最终将其规划到巡回修理组3的第4顺位，并在第335 min得到修竣，类似的还有装备9、16、20、22。这是动态调度的体现，反映了每个巡回修理组的任务序列对其自身而言并不一定是最优的，但是对于整体的巡回修理效益是最优的。这也间接证明了通过动态调度能够更有利于全局的最优化，体现了动态调度的优势。

5) 在第206 min进行第3次调度时，待修装备9被纳入巡回修理组3的第5修理顺位，且计划修复状态为S1，但是在第4、5、6次重调度时，待修装备9均参与了重调度，且最终在巡回修理组1的第7修理顺位得到修复，且修复状态为S2。这反映了在重调度时刻，会根据该时刻的全局信息对各巡回修理组的任务序列及各待修装备的修复状态进行动态调整，以实现全局的最优化，从侧面反映了调度模型的合理性。

6) 前3次调度，待修装备的修复状态以S1为主，因为前期待修装备较少，预计的修理时间相对较充裕，而μ2取值较大，将装备修复至S1状态能获得更多的重要度，且前期修竣装备参战时间相对较长，更高的重要度有利于发挥作战效能。后3次调度，待修装备的修复状态多为S2，因为此时参与调度的待修装备数量多，且在战斗中后期，μ3取值较大，希望能获得更多装备二次作战时间，因此将待修装备修复至S2状态既能节约修理时间以便完成更多修理任务，又能迅速使其返回战场获得更多的二次作战时间。

由图3可以看出：巡回修理组1的规划路径中出现了折线3-6-5以及15-21-9-25-26，前者是因为装备5相较于装备6，修复到相同状态的装备重要度高且修理时间短，因此巡回修理组1在修竣装备3后，舍弃较近的待修装备6，而先修理重要度高且更易修复的待修装备5，这满足“先修重要装备”以及“先修易修装备”的战时修理要求，也从侧面反映了调度模型的合理性。而后者是因为该规划是多次重调度的综合结果，装备15在第4次调度后得到修竣，装备21、9是在第5次调度后得到修竣，而装备25、26是在第6次调度才纳入调度计划并最终得到修竣，这也从侧面反映了动态调度的核心是使整体修理效益最优化，而不是追求某一巡回修理组的修理效益最优。

5 结论

合理高效的装备巡回修理任务动态调度模型，可以为战时保障指挥员的维修决策提供数学支撑，并能根据战时不断变化的维修需求作出及时有效的调整，大大降低了决策工作量和人为决策风险。笔者在提出巡回修理装备维修任务动态调度军事问题的基础上，构建了维修任务的多目标动态调度模型，考虑待修装备修复状态的不确定性，引入待修装备修理时间窗、非遍历性以及修理能力的变化等约束条件，使模型更具现实意义并增强了模型的合理性，通过制定动态调度策略，实现了维修计划的动态调整，设计了NSGA-Ⅱ改进遗传算法求解了模型，并通过示例验证了模型及算法的合理性。下一步将对定点修理中装备维修任务动态调度问题展开研究。