抢修任务多目标动态调度的动态驱动策略研究

，， ，，

(陆军装甲兵学院 技术保障工程系，北京 100072)

0 引言

机动进攻作战作为未来重要作战样式之一，突显出作战空间广、机动性能强、作战节奏快、持续时间短、战损装备众多、分布地域广、战斗态势多变等特点。在战场抢修过程中，抢修力量十分有限，面对不同时刻、不同地点、不断地出现的、不同损伤程度的故障装备时，若采用定点修理的方式，抢救后送难度大、耗时久，在有限的进攻战斗持续时间内能够修竣的装备极其有限，无法满足作战对装备保障的时效性要求。如何合理运用数字化合成旅的抢修力量，根据决策时刻的作战任务需求、抢修任务的轻重缓急、待修装备的位置远近和维修工作量、抢修单元的修理能力等，快速制定出抢修任务分配方案，明确不同抢修单元间的任务分工以及同一抢修单元内的抢修序列；并根据战场态势发展及不断更新的抢修需求信息，适时、动态地调整抢修任务分配方案，争取在有限作战持续时间内尽可能多地修复或部分修复损伤装备，使其能够再次投入战斗，是亟需解决的一个实际军事问题。目前，在制定抢修任务分配方案时，主要存在以下两个方面问题：1)缺乏定量化测算模型及求解方法，只能依靠决策者的主观经验和定性抢修实施原则进行决策，导致决策主观性过强、风险较高、整体抢修效益不高；2)虽有部分关于维修任务静态分工的研究成果，但其与“抢修需求呈现出的时间、地点的不确定性规律”不符；缺乏关于抢修任务动态调度的研究，忽略了对部分实际约束条件的合理抽象(如恢复状态的不确定性、不同抢修单元间的修理能力差异)，没有考虑不同动态驱动策略对任务分配结果的影响。

针对战时装备抢修任务动态调度及其动态驱动策略问题，国内外学者已取得了许多研究成果。在动态调度方面，研究热点主要集中于动态车辆路径问题[1]、生产调度问题[2]和无人机协同任务规划问题[3-4]，主要约束条件包括：多类型的任务主体[5]、时间不确定性[6]、费用[7]、时间窗[8]、动态需求集合[9]、动态环境[10]等。在战场抢修任务动态调度方面，王正元[11-12]基于战时的定点维修，分别提出了不同约束条件下的动态维修任务调度方法。郭军[13]将证据推理运用于战时多任务的抢修重要度决策。陈伟龙[14]将战场抢修、伴随保障、动态调度结合起来，首次提出了抢修任务动态问题，并以修竣装备获得的二次作战时间总和为目标函数，建立了战场抢修任务单目标动态调度模型及求解算法。昝翔[15]建立了以修竣装备重要度之和最大为目标函数的抢修任务单目标静态分配模型。陈春良[16]考虑诸多约束条件，建立了以修竣装备数量、节点重要度、二次作战时间为目标函数的抢修任务多目标动态调度模型。在动态驱动策略方面，文献[17]将动态驱动策略分为固定时长滚动时域和变时长滚动时域2类。文献[18]提出了“紧急顾客插入+分批驱动”的动态驱动策略，解决了重要客户动态请求的快速响应问题。文献[19]为了有效减少两车间设备的空闲等待时间，提出了两车间设备驱动的动态驱动策略。文献[20]提出了分区灵活分批TSP策略，仿真结果表明该策略能够减少平均行驶距离和平均等待时间。

图1 抢修任务动态调度系统的运行图

现有研究存在以下不足：1)限定于遍历型调度，无法解决非遍历型问题；2)所建立的抢修任务动态调度模型与实际情况趋于接近，但其动态驱动策略采用的是单事件驱动或数量(时间)分批驱动，极易受到“新抢修需求出现时刻的不确定性”的影响，导致抢修力量不能对新抢修需求进行及时响应、抢修力量出现闲置、抢修效益降低；3)部分研究成果中提出了新的动态驱动策略，但并不适用于抢修任务动态调度问题。基于此，本文针对抢修任务动态调度的动态驱动策略开展研究，建立抢修任务多目标静态分配的数学模型，提出“混合分批+基于抢修组状态”的一种新的动态驱动策略，构造基于均匀设计思想的6组测试问题实例，并通过实验分析各种动态驱动策略的优劣性及适用性。研究结果有助于抢修力量对新产生的抢修需求进行及时响应，提高抢修力量的利用率和抢修效益。

1 问题分析

抢修任务动态调度问题是指，在机动进攻作战过程中，因敌炮火打击，势必造成我方部队在不同时刻和地点、随机地出现战损装备；但抢修力量有限，无法在进攻作战持续时间内完成对修理范围内的所有待修装备的修理。为取得最有利于完成本次进攻作战任务的抢修效益，综合权衡待修装备的优先程度、所需修理工时、距离远近、不同抢修组的修理能力差异、动态驱动策略等因素，通过设计抢修任务动态调度模型及其求解方法，从修理范围内的众多故障装备中迅速地选择部分装备并将其分配给各个抢修组；并根据战场态势发展以及不断变化的抢修需求信息，适时、动态地调整抢修任务分配计划，争取在有限作战持续时间内尽可能多地修复或部分修复损伤装备。

动态驱动策略则是指设定某种驱动策略及其阈值，在战场抢修过程中，当驱动条件满足时，决策者即在该时刻依据抢修任务静态分配模型及求解算法对已有的抢修需求(包括新出现的、非新出现但尚未抢修的)进行再次分配。研究动态驱动策略的核心目的是为了解决何时进行任务动态调度的问题，以期取得更优的抢修效益。

基于系统工程思想，抢修任务动态调度系统的构成要素主要包括：抢修对象及其相关信息、抢修力量及其相关信息、环境信息、决策模型与求解算法、修竣装备与抢修效益。

其中：1)抢修对象的相关信息主要包括：(1)损伤信息，如损伤时刻、坐标位置、装备类型、预计所需维修工作量等；(2)抢修进度信息，如修竣与否、恢复状态、预计修竣时刻、实际修竣时刻、动态调度时刻的剩余修理工作量等。

2)抢修力量的相关信息主要包括：(1)各个抢修组的编制信息，如各抢修组的保障装备的种类和数量信息、保障人员的数量和修理技能水平信息等；(2)在进攻作战持续时间内的任意时刻，所有抢修组的状态信息，如各抢修组在任意时刻的位置信息、人员/装备损失情况信息等。

3)环境信息是指在战场抢修过程中，除却抢修力量和抢修对象的相关信息外，与抢修任务动态调度问题相关的其它所有信息。主要包括：(1)作战起止时刻；(2)各作战单元、武器装备的在任意时刻的任务信息、位置信息；(3)各作战单元、武器装备的相互关系信息；(4)地形、道路、气象水文信息等。

4)决策模型与求解算法是指在战场过程中，为求得抢修任务动态调度问题在各个决策时刻的决策方案(各抢修组间的任务分工和抢修组内的抢修序列)，所需借助的数学模型和求解方法。

5)修竣装备与抢修效益，是指在作战持续时间内，各抢修组通过实施巡回修理，修竣的待修装备及获得的修理效益。

基于控制论思想，从系统输入、系统过程、系统输出、系统限制以及逆向联系5个方面，构建抢修任务动态调度系统的运行图，如图1所示，旨在从整体上呈现出系统各构成元素及其相互关系。

解决抢修任务动态调度问题的难点在于设计合理的决策模型及求解算法。但由于在抢修任务动态调度问题中，抢修需求信息会随时间动态变化(包含随机不确定性和模糊不确定)，直接求解的难度极大。

在任意动态调度时刻t(s)，由于动态抢修需求信息(即新出现的抢修需求)和静态抢修需求信息均己知，引入滚动时域思想，提出“动态问题静态化”的求解思路，即将抢修任务动态调度问题P(t)转化为一系列离散时间点的抢修任务静态分配问题P(t(s))进行求解。其求解思路如图1所示。

图2 求解思路

2 动态驱动策略设计

动态调度驱动策略设计分为两种：基于抢修需求信息和基于抢修组状态。

2.1 基于抢修需求信息的动态驱动策略

2.1.1 单事件驱动策略

定义1：单事件驱动策略。在进攻作战持续时间内，如果抢修需求出现的时刻分别为t1,t2,t3,…，且t1

单事件驱动策略的优点在于能够对抢修任务的动态抢修需求进行快速响应，决策出各个时刻的最优分配方案。然而，当动态需求较多时，若采用单事件驱动策略，极有可能出现“某一时刻，各抢修组均正在抢修战损装备，而新的抢修需求在短时间内相继出现，动态驱动策略不断被触发，抢修任务静态分配模型求解得到的任务分配方案始终无法实施，即不断产生无实效的任务分配方案”，带来巨大的计算负荷，大大增加了保障决策指挥中心的工作量和时间耗费，效益极低。与此同时，采用单事件驱动策略求得的“各个时刻最优的抢修任务分配方案”的抢修效果，在绝大部分情况下劣于后文中提出的动态驱动策略。因此，本文中舍弃单事件驱动策略，不纳入研究范畴。

2.1.2 时间分批驱动策略

其中t(s+1)为动态调度时刻，其确定公式为：

(1)

式中，t(s)=ti，t(s+1)=tj。

时间分批驱动策略的优点在于便于保障决策指挥中心进行抢修任务的动态管理。但其阈值难以合理确定，且极易受到抢修需求到达时刻不确定性的影响，进而导致“一个周期内积累了非常多的故障装备，增大了决策难度和时间耗费”、“抢修组处于闲置状态，但动态驱动策略的触发条件不满足，仍然不进行任务分配，不能对抢修需求及时进行响应，极大降低了抢修效益”。

2.1.3 数量分批驱动策略

其中:t(s+1)为动态调度时刻，其确定公式为：

且ti>t(s)}

(2)

数量分批驱动策略的优缺点与时间分批驱动策略相似。

2.1.4 混合分批驱动策略

其中t(s+1)为动态调度时刻，其确定公式为：

(3)

混合分批驱动策略继承了时间分批和数量分批驱动策略的优点，能够在一定程度上缓解“极易受到动态抢修需求到达时刻不确定性的影响”的问题，能够提高对抢修需求的响应速率，但仍存在“抢修组闲置浪费”的问题。

2.2 基于抢修组状态的动态驱动策略

为解决“抢修组闲置”的问题，提高抢修组的利用率和战场抢修效益，提出一种新的辅助策略“基于抢修组状态的动态驱动策略”。

定义5：基于抢修组状态的动态调度驱动策略。在进攻作战持续时间内，如果抢修需求出现的时刻分别为t1,t2,t3,…，且t1

其中t(s+1)为动态调度时刻，其确定公式为：

(4)

基于上述分析，本文将混合分批驱动策略和基于抢修组状态的动态驱动策略结合起来，提出“混合分批+基于抢修组状态”的一种新的驱动策略，旨在既能继承混合分批驱动策略的优点，又能解决抢修组闲置的问题，从而提高整体抢修效益。

3 测试问题实例构造

文中基于均匀设计思想构造测试问题实例，重点考虑如何将具有代表性的设计点均匀地散布在试验范围内，使其能够通过较少的试验点获得最多的信息。首先分析对问题数学特性影响比较大的影响因素，然后在样本空间均匀采样，构造具有代表性的测试问题实例。

3.1 测试问题实例的影响因素设置

3.1.1 进攻作战持续时间

考虑两种情况：1)进攻作战持续时间较短。在这种情况下，抢修组遂行遍历型抢修的概率较大，决策难度相对较小。2)进攻作战持续时间较长。在这种情况下，抢修组遂行非遍历型抢修的概率较大，决策难度较大，且不同决策方案的抢修效果差异也较大，见表1。

表1 3个因素的设置

3.1.2 抢修组数量

抢修组作为抢修任务动态调度模型的任务主体，当任一抢修组的编制已确定时，其数量的多少直接影响着抢修效果；显然抢修组的数量越多，抢修越及时，对维持进攻作战部队的持续进攻能力越有益。考虑2种情况，见表1。

3.1.3 抢修需求的数量

考虑两种情况：1)抢修需求的总数较少。在这种情况下，抢修组遂行遍历型抢修的概率较大，决策难度相对较小；2)抢修需求的总数较多。在这种情况下，抢修组遂行非遍历型抢修的概率较大，决策难度和求解耗时较大，见表1。

3.1.4 抢修需求产生时刻的时间分布

在实际的抢修任务调度中，抢修需求的产生与战场态势密切相关，且在时间轴上是随机出现的；不同的抢修需求产生时刻的时间分布，必然导致不同的任务分配方案。文中将抢修周期划分为前期、中期和后期，并用百分比表示不同时间段内的抢修需求数量的多少。考虑以下两种情况：1)前期多，中期较多，后期少；2)前期和中期较多，后期少。

表2 时间分布的设置 %

3.1.5 损伤状态及预计所需修理工时

由于不同种类的损伤状态及其对应的不同恢复状态，预计所需修理工时是不同的。为确保试验质量且减少试验计算量，将6种损伤状态Ei(i=1,3,…,6)分为两类：第1类为Ei(i=1,2)，仅某一种子系统损伤，其可选恢复状态仅为C1；第2类为Ei(i=3,4,5,6)，有2种或3种子系统损伤，其可选恢复状态为C1或C2，详见文献[16]。考虑以下2种情况：(1)第1类少，第2类多。(2)第1类较少，第2类较多。详见表3。

3.1.6 动态驱动策略

基于“2 动态驱动策略”的分析，在测试问题实例构造中，本文考虑以下3种策略，见表4。

表3 比例设置 %

表4 动态驱动策略的设置

3.2 基于均匀设计思想的测试问题实例构造

借鉴均匀设计的思想，在样本空间进行选择，构造具有代表性的抢修任务动态调度测试问题实例。考虑的主要影响因素及其水平数见表5。

表5 因素及其水平数

表6 均匀设计表 表7 混合均匀设计表

根据混合均匀设计表，构造6个测试问题实例TP1至TP6，见表8。

表8 测试问题实例集

接下来，给定部分边界条件的输入设置：

2)修理水平差异取值θ1=0.8，θ2=1.3。

3)令τ=4，即若将任一故障装备修竣至状态C1，则该修竣装备能执行4种战斗任务。

4)设定初始种群大小pop_size=400,迭代次数num_iter=100。

4 实验结果及分析

4.1 实验结果

1)模型可采用变体遗传算法进行求解，可参见作者的另一篇文献[16]。篇幅所限，此处仅给出TP2在任一动态调度时刻的任务分配结果(见表9)。

2)由表9分析可知，到进攻战斗结束时，经抢修获得的二次作战总时间为3565 min(约60 h)，相当于为进攻部队增添了10辆可以参与6 h进攻作战的战斗装备，也相当于增加了一个战斗连的作战装备；间接证明了实施伴随保障的重要性和建强伴随保障力量的必要性。

3)关于抢修动态调度的更多结果分析，可参见文献[16]，篇幅所限，此处不展开分析。

4.2 动态驱动策略的优劣分析

4.2.1 混合分批驱动策略

对于TP5，其作战持续时间较长(12 h)，抢修组数量(2个)和抢修需求数量(12台)少。由计算结果可知，抢修组最终修竣了10台战损装备，修复率为83.3%，经抢修获得的二次作战总时间为3762 min(约62.7 h)，相当于为进攻部队增添了5辆可以全程参与进攻作战的战斗装备。对于TP6，其作战持续时间较长(12 h)，抢修组数量(3个)和抢修需求数量(24台)较多，且抢修需求在作战前期密集出现。TP6最终修竣了21台战损装备，修复率为87.5%；经抢修获得的二次作战总时间为8137 min(约135.6 h)，相当于为进攻部队增添了11辆可以全程参与进攻作战的战斗装备。

表9 TP2在任一动态调度时刻的任务分配结果

在进攻作战持续时间内，抢修组多次处于闲置状态，与此同时，虽已有新的抢修需求出现，但由于驱动策略的触发条件不满足，不会进行任务动态调度，进而导致了抢修组的利用率和抢修效益降低；且相比较而言，TP5比TP6的闲置时间明显更多。例如，对于TP5，在55 min时刻，任务分配方案将待修装备1和2分别分配给抢修1组和抢修2组，其实际修竣时刻分别为104 min和99 min；但由于抢修需求出现的时间间隔较长，导致了“数量分批驱动策略”优先于“时间分批驱动策略”被触发，进而决定了下一次动态调度驱动被触发的时刻为145 min；尽管在98 min出现了新的抢修需求(待修装备3)。换言之，在145 min进行任务动态调度前，不会有新的任务分配给各抢修组，抢修1组和抢修2组分别有41 min和46 min处于闲置状态，大大推迟了待修装备3的修竣时刻，降低了其对本次进攻作战的贡献。

采用“混合分批驱动策略”能够降低抢修任务分工的更新频率和计算负荷，易于进行抢修任务的动态管理。但抢修组可能会多次处于闲置状态，使得抢修组的利用率和抢修效益降低；与此同时，驱动策略的阈值难以事先合理设定，阈值设定过大则问题规模会增大且无法快速响应系统中发生的干扰，过小则调度过于频繁、影响系统的稳定性。适用条件：1)抢修需求的数量很多，任务量较大；2)抢修需求产生时刻的时间分布相对均匀。

4.2.2 基于抢修组状态的动态驱动策略

对于TP3，其作战持续时间较短(8 h)，抢修组数量(3个)较多，抢修需求数量(12台)少，由计算结果可知，抢修组最终修竣了11台战损装备，修复率为91.7%，；经抢修获得的二次作战总时间为2386 min(约40 h)，相当于为进攻部队增添了5辆可以全程参与进攻作战的战斗装备。由于抢修需求数量少而抢修组数量多，导致了各抢修组交替出现闲置状态，但闲置时间明显减少。

对于TP4，其作战持续时间较长(12h)，抢修组数量(2个)较少，抢修需求数量(24台)较多，抢修组最终修竣了19台战损装备，修复率为79.2%；经抢修获得的二次作战总时间为6723 min(约112 h)，相当于为进攻部队增添了11辆可以参与10 h进攻作战的战斗装备。由于抢修需求数量较多而抢修组数量较少，各抢修组的利用率非常高，在572 min以前，其利用率为100%(即没有出现过闲置状态)；而且是因为“非遍历”约束，各抢修组才在572 min以后没有继续进行抢修。

采用“基于抢修组状态的驱动策略”时，各抢修组的利用率非常高，除“非遍历”约束外，不会出现“抢修需求被搁置，而抢修组处于闲置状态”的情况。但调度系统不能对新产生的抢修需求及时进行响应，极大可能会降低整体抢修效益；原因在于：驱动策略仅会在“某一抢修组将所有既定抢修任务完成后”才会触发，当抢修需求较多时，必然会导致响应速度慢、任务分工不甚合理。适用条件：1)抢修需求的数量适中或较少；2)抢修需求产生时刻的时间分布极不均匀(即既有聚集，又有分散)。

4.2.3 “基于抢修组状态+混合分批”的驱动策略

对于TP1，其作战持续时间较短(8 h)，抢修组数量(2个)和抢修需求数量(12台)均较少。抢修组最终修竣了11台战损装备，修复率为91.7%；经抢修获得的二次作战总时间为2015 min(约33.6 h)，相当于为进攻部队增添了4辆可以全程参与进攻作战的战斗装备。对于TP2，其作战持续时间较短(8 h)，抢修组数量(3个)和抢修需求数量(24台)较多。抢修组最终修竣了17台战损装备，修复率为70.8%；经抢修获得的二次作战总时间为3565 min(约59.5 h)，相当于为进攻部队增添了10辆可以参与6h进攻作战的战斗装备。

在TP1的作战前期，由于抢修需求数量较少，在91 min时刻，抢修2组修竣了既定的所有抢修任务(待修装备2)，而混合驱动策略的触发条件仍不满足，因此“基于抢修组状态的驱动策略”优先于“混合分批驱动策略”被触发；之后抢修需求的产生速率高于抢修组的修理速率，“混合分批驱动策略”总是优先于“基于抢修组状态的驱动策略”被触发。

“基于抢修组状态+混合分批”的驱动策略，能够对新产生的抢修需求进行及时响应，且各抢修组不会出现闲置状态，有利于取得更好的抢修效益。缺点：“数量分批驱动策略”和“时间分批驱动策略”的阈值难以事先合理设定；当抢修需求的数量极少时，可能出现无效的任务动态调度。适用条件：1)抢修需求的数量不受限制；2)修需求产生时刻的时间分布不受限制。

5 结束语

本文针对“采用时间(数量)分批驱动策略时，由于新的抢修需求出现时刻的不确定性，会导致抢修力量不能对新产生的抢修需求进行及时响应、抢修力量会出现闲置等”问题，设计了基于抢修需求信息和抢修组状态的2种动态驱动策略，提出了“混合分批+基于抢修组状态”一种新的动态驱动策略，该策略既能继承混合分批驱动策略的优点，又能解决抢修组闲置的问题，有利于提高整体抢修效益。

参考文献：

[1] Victor P, Michel G, Christelle G, et al. A review of dynamic vehicle routing problems[J]. European Journal of Operational Research, 2013, 225: 1-11.

[2] Cheng H L, Cheng I H. Dynamic job shop scheduling with fixed interval deliveries[J]. Production Engineering, 2015, 9(3): 377-391.

[3] Sangwoo M, Eunmi O, David H S. An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments[J]. Journal of Intelligent and Robotic Systems, 2013, 70(1): 303-313.

[4] 齐 骥,王宇鹏,钟 志.无人机多阶段航迹预测协同任务规划[J].计算机测量与控制,2016,24(6):189-194.

[5] Víctor Y,Josep M. Economic heuristic optimization for heterogeneous fleet VRPHESTW[J]. Journal of Transportation Engineering, 2015, 132(4): 303-311.

[6] Lorini S, Potvin J Y, Zufferey N. Online vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research, 2011, 38(7): 1086-1090.

[7] Letchforda A N, Nasiri S D. The steiner travelling salesman problem with correlated costs[J]. European Journal of Operational Research, 2015, 245: 62-69.

[8] Michael S. The vehicle-routing problem with time windows and driver-specific times[J]. European Journal of Operational Research, 2016, 250(1): 101-119.

[9] Briseida S, Karl F D, Verena S, et al. Variable neighborhood search for the stochastic and dynamic vehicle routing problem[J]. Annals of Operations Research, 2016, 236(2): 425-461.

[10] Engin A, Haluk R T, Murat E. Hyper-heuristics for online UAV path planning under imperfect informationJ].Lecture Notes in Computer Science ,2014, 1(1):741-752.

[11] 王正元,朱 昱,宋建社,等.动态维修任务调度的优化方法[J].机械工程学报,2008,44(1): 92-97.

[12] 王正元,严小琴,朱 昱,等.一种考虑专业的动态维修任务调度的优化方法[J].兵工学报,2009,30(2):252-256.

[13] 郭 军,宋建社,杨 檬,等.基于证据理论的多任务抢修重要度决策[J].系统工程与电子技术,2011,33(3):581-584.

[14] 陈伟龙,陈春良,史宪铭,等.基于变体GA的进攻作战抢修任务动态调度[J].系统工程与电子技术,2017,39(3): 577-583.

[15] 昝 翔,陈春良,张仕新,等.多约束条件下战时装备维修任务分配方法[J].兵工学报,2017,38(8):1603-1609.

[16] 陈春良,陈伟龙,陈康柱,等.考虑非遍历的抢修任务多目标动态调度[J].兵工学报,2017,38(8):1593-1602.

[17] 王艳玲.取货车辆动态调度问题研究[D].北京:北京交通大学,2010:36-37.

[18] 王 君. 不确定因素下车辆路径问题建模及优化方法研究[D]. 天津: 天津大学, 2011: 106-108.

[19] 谢志强,王有为,辛 宇,等.利用工序迁移时间的两车间设备驱动综合调度算法[J].上海交通大学学报,2016, 50(6): 929-935.

[20] 熊 浩.动态车辆路径问题的分区灵活分批TSP策略[J].控制与决策,2013,28(10):1454-1458.

[21] 李云雁,胡传荣.试验设计与数据处理[M].第二版. 北京:化学工业出版社,2008.