考虑多属性约束的战时装备维修任务动态调度

米巧丽,卢明章,李本威,王永生

(1.中国人民解放军91049部队，山东 青岛 266100；2.海军航空大学，山东 烟台 264001)

1 引言

在现代信息化战争中，武器装备的使用环境、作战任务与保障条件等诸多不确定性因素,使得装备故障的发生及维修保障力量的变化具有突发性、复杂性和频率高等特点，而战时对于装备故障修复的时效性和维修效率要求更高。因此，战时维修任务调度必须有效协调当前待调度的维修任务和可用的维修力量，以快速恢复装备战斗力为目标对维修任务与维修力量进行动态调度。

战时维修任务调度相对于平时来说，所需考虑的约束条件更多、目标要求更高，因此研究难度也更大。针对战时各种特殊情况下维修任务调度的特点，相关领域的学者从调度的属性约束、调度模型的优化目标及模型求解方法等方面展开了理论和方法研究。通过对现有研究成果的分析，可以发现：

1) 由于战时维修任务的增加、维修力量的变化与维修时间等方面具有不确定性，因此需要根据战场态势与维修需求适时、动态地调整维修任务调度方案。如文献[1]中针对维修任务出现的随机性，在考虑维修时间不确定性前提下对维修任务进行优化调度。文献[2]考虑了战时修理能力的变化，对伴随修理任务进行动态调度研究。

2) 战时维修任务繁杂、时效性要求高，且不同维修任务的紧急情况与重要程度不同，调度时需综合考虑维修任务的分类、优先级、维修时间等属性。如文献[3-5]中根据维修任务的重要程度、维修和等待时间等因素确定任务的优先级，以优先级为约束进行维修任务调度。文献[6-7]在考虑维修专业分类基础上构建了基于维修专业的调度模型。

3) 战时维修力量相对平时复杂且多变，分配时需要综合考虑维修力量的类别、调度时的维修资源与维修能力等属性。如文献[8,9]通过考虑战时巡回维修力量的相关约束，规划维修力量派遣路线，实现维修力量与任务的分配优化。

4) 对于复杂的动态调度问题，通过构建实现对应目标的调度模型，采用智能算法可以有效提升模型的求解效率和调度效率。文献[10-15]中，在构建的单目标或多目标调度模型基础上，通过运用和改进遗传算法、蚁群算法、粒子群算法等对模型进行求解，提高求解效率的同时实现了维修任务的优化调度。

由上述分析可知，目前相关研究文献中针对战时维修任务与维修力量均出现突变的动态调度研究较少，且大部分文献在考虑调度的属性约束时侧重于考虑维修任务或维修力量单方面的属性约束，与战时实际情况存在一定的差距。因此，本文中拟针对战时维修任务及维修力量均发生变化的复杂情况，综合考虑维修任务、维修力量的专业分类、优先级和能力负载等属性约束，以快速、有效恢复装备战斗力为目标进行动态调度，以此提高维修任务调度应对战场环境与保障要素随机变化的响应能力。

2 分阶段的动态调度模型构建

2.1 战时维修任务动态调度需求

战时维修任务动态调度是在故障装备随时出现、维修时间和维修能力有限且可能出现变化的情况下，将故障装备所产生的维修任务分配到适合的维修力量，并确定各维修力量所承担的维修任务的维修顺序、修复时间及修复状态，同时还需要根据需求变化进行动态调整，使战斗力得到最及时有效的恢复。可见，维修任务动态调度主要包含2个阶段：一是在出现故障后，依据维修任务的需求及维修力量的能力,将维修任务分配到对应满足能力需求的维修力量上，在此简称为分配阶段；二是依据维修任务的优先级及资源需求等条件，对每个维修力量上所分配维修任务的维修顺序、时间和状态等进行具体规划，简称为规划阶段。

战时装备的维修力量主要包括伴随维修、机动巡回维修以及定点维修等3类维修机构，这3类维修机构的维修能力与备件资源各有特点。通过调研与统计分析可知，依据装备故障部位与类型，针对性地配置专业对口的维修人员及对应的专业器材进行故障维修，可有效地提高维修效率和维修资源的利用率。因此，在进行动态调度时，首先对维修任务依据专业分类得到初始的专业任务集，并将维修机构及对应配置的维修资源整合，并划为若干专业维修小组。由此，在分配阶段可将维修任务快速分配到对应专业的维修小组上，规划阶段则对每个专业维修小组上所分配的维修任务进行进一步调整，在满足约束条件下获得最佳的调度方案。

2.2 问题描述与模型假设

在静态维修任务调度的基础上，动态调度重点考虑维修过程中维修任务、维修力量出现变化后对任务调度的影响。当出现维修任务与维修力量变化时，需要对待调度任务与新增任务在当前维修力量下进行重新调度。在调度过程中，任务的分配与规划均以维修任务集为基本操作对象，而每个任务集的任务数量及操作所需时间均不同。根据调度的阶段划分，对应构建待调度任务池TP1、分配任务池TP2、待规划任务池TP3、规划任务池TP4、已调度任务池TP5。当出现新任务及维修力量变化时，更新TP1，重新调用任务调度算法，更新TP2、TP3、TP4，由此降低任务调度的复杂度。

为明确动态调度过程，做出如下约定：

1) 维修任务不可中途取消，如遇到需要取消的维修小组正在执行某一维修任务的情况，则将该维修任务未完成的任务量按原优先级进行重新调度；

2) 维修小组上维修任务的分配按照优先级高的任务优先，优先级相同以维修时间短的任务优先的原则进行；

3) 每个专业维修小组可对同一专业的若干维修任务进行操作，但每项维修任务不能同时由2个维修小组维修；

4) 每个维修任务的维修时间为维修等待、故障件送修、故障维修等时间的总和；

5) 出现维修任务的增加及维修小组增减等变化时，均按照专业分类进行调度，其他没有变化的专业维修任务和维修小组无需进行重新调度；

6)如某一专业维修小组临时取消，则该小组上未完成的维修任务需要重新调度，其他专业的维修小组及维修任务保持原来的调度安排。

2.3 动态调度模型的构建

假设在t时刻装备出现新故障或维修小组出现增减，通过对维修任务进行专业分类，得到初始维修任务集为：

(1)

记t时刻专业l下待调度任务总数为I(t)，I(t)=I0(t)+Q(t)。将式(1)中的任务合并后，综合任务优先级(从高到低)与维修时间(从小到大)对任务进行排序，得到专业任务集为Ml(t)={Mli(t),i=1,2,…,I(t)}。

记t时刻专业维修小组集合为N(t)={Nlk(t),k=1,2,…,K(t)}。分配阶段的任务即将Mli(t)分配到对应的Nlk(t)上，得到分配方案为：

Π1(t)=[xlik(t)]I(t)×K(t)

(2)

式中: 专业l下的第i个任务被分配到第k个维修小组时，xlik(t)=1，反之xlik(t)=0。

Z=minT(Πopt(t))

(3)

(4)

(5)

(6)

其中，式(4)表示每个维修任务只能由一个维修小组进行维修。式(5)表示所有的维修任务均需要得到维修。记Mli(t)在Nlk(t)上的维修时间为tlik(t)，Nlk(t)的最大能力负载(在此用可承担的最大维修时间衡量)为Qlk(t)，式(6)表示每个维修小组所承担的维修任务不能超出其能力负载。

3 动态调度模型的求解

3.1 基于聚类的任务分配

任务分配的过程就是维修任务的需求与维修机构能力匹配与优化的过程。聚类是将一组对象逐步分解为若干个相似度较高的类或簇的过程[16]。对于维修任务的分配阶段，可以看作将需求相似的任务与能力最匹配的维修小组逐步聚类的过程。将同专业的维修任务Mli(t)与维修小组Nlk(t)作为聚类对象。聚类距离用于衡量任务的需求与维修小组能力之间的匹配程度。聚类距离越小，说明匹配程度越低。基于聚类的任务分配过程主要包括以下几个步骤：

步骤1将承担维修任务的K(t)个维修小组Nlk(t)作为聚类中心。

步骤2非中心与中心的聚类距离用任务Mli(t)在维修小组Nlk(t)上的维修时间tlik(t)衡量，即聚类距离表示为dlik=tlik。

通过计算每个非中心对象(任务Mli(t))与每个聚类中心(维修小组Nlk(t))之间的距离dlik，可构造距离矩阵Dl为：

(7)

步骤3聚类的迭代更新。

将矩阵Dl中每一行元素由小至大排序，从第1行(第1个任务)开始，选取该行的最小值并入该值对应的聚类中心，即如第1行的最小值为dl1k≥0，则将Ml1(t)并入聚类中心Nlk(t)所在的簇，更新各聚类中心。然后依次选取每行最小值进入对应簇，直至最后1行。

3.2 基于约束禁忌搜索的任务规划

(8)

(9)

当Nlk(t)上任务为串并混联时，将并联的所有任务视为一个整体，时间设为其中的最大值，然后再依据串行关系对时间求和。

1) 初始解与适配值函数的确定。

2) 邻域操作的设计。

步骤1基于分配阶段所计算的mlkp(t)在Nlk(t)上的维修时间及排序结果，对应得到mlkp(t)按维修时间从小到大的维修小组序列P。易知P的第1个元素为P[0]=Nlk(t)，选取P的第2个元素P[1]=Nlx(t)，其中，x≠k,1≤x≤K(t)。

步骤2判断Nlx(t)是否超载。如Plx(t)≥Qlx(t)，依次向后选取直至不超载元素Nly(t),(x

步骤3选取不超载元素Nly(t)作为操作目标对象(如Plx(t)

步骤4判断是否到达p[K(t)-1]。如没有则按顺序选取Nlx(t)或Nly(t)的下一个元素，进行插入操作；如到达，则结束该次邻域操作，更新变动向量的分配方案。

max(Tlk(Πlk′(t)),Tly(Πly′(t)))

(10)

通过计算所有邻域解对应的适配值差,并依据适配值差从小到大对邻域解进行排序，选取适配值差最小的邻域解作为当前解，在接下来的邻域操作中即被视为禁忌对象，进入禁忌表中。

3) 禁忌规则与藐视准则。

4) 搜索策略与终止准则。

相对于基本禁忌搜索中对问题元素的选取及邻域操作目标选取的随机性，改进的禁忌搜索方法中的约束主要体现在2个方面：一是在选取超载元素mlkp(t)时按照超载序列Π″lk进行顺序选取；二是在邻域操作中依据mlkp(t)对应序列P中的元素顺序选取操作目标对象。算法的终止条件是维修小组上的所有超载任务得到重新分配。

3.3 综合求解流程

所有的待调度任务只有在经过分配及规划操作后，到达已调度任务池后才能完成整个调度周期。而当时刻t出现新的维修任务时，将新的维修任务经过初始专业分类后，将其与对应的专业下现存待调度的任务共同存储于待调度任务池，通过触发分配与规划时间窗口，对所有待调度任务进行重新调度。在完成现阶段的维修任务调度后，判断下一个时刻是否出现新任务，如出现新任务，则将时间窗口滚动到下个时刻t+Δt，进行重新调度。根据上述分析，维修任务动态调度模型求解算法流程如图1所示。

图1 维修任务动态调度模型求解流程框图Fig.1 Solution flow of flexible task scheduling

4 实例分析

以某型导弹装备战时出现并发故障情况为例，通过对各类故障原因及维修策略的分析，将每个故障相应分解为基本维修任务集合。任务集中各维修任务的任务量与优先级如表1所示。

表1 维修任务的任务量与优先级

依据参战装备的维修策略及相应的维修保障组织设置，将现有的维修力量进行专业分类后，其能力负载(维修时间/h)如表2所示。

表2 维修力量及其能力负载

通过分析该型导弹装备维修策略、各维修任务的类型、能力需求与维修小组职能范畴、能力的对比，得出距离矩阵为：

假定每个维修小组能够连续执行维修任务，中间无需停休。通过维修任务分配，得到初始调度方案。初始调度方案中所有维修任务的完成时间为13.7 h。在初始调度方案的基础上，采用Matlab 7.1编程实现改进禁忌搜索的任务规划算法，以初始调度方案为初始解，实现维修任务调度方案的规划调整。为验证本文中模型及算法的正确性及求解性能，应用精确求解的匈牙利法，对上述案例中的维修任务优化调度模型进行求解，本文中方法求解的最优值为与匈牙利法的精确求解最优值一致，均为10.9 h，由此说明了本文中所建模型的正确性及所提出的模型求解方法对于维修任务优化调度模型求解的有效性。

为验证本文中的算法对维修任务动态调度的求解效果及效率，假设在当t=5时，导弹装备突发新的故障，并且维修分队N13被临时调离。假定执行过程的维修任务不会中途停止。因此，维修小组数量减少1，同时，N13上正在执行的任务及已分配的任务需要被重新调度。对新产生的故障进行分析，按专业分解为基本维修任务集，与现存的任务进行重新调度。为对比本文中的动态调度方案，同时采用2个传统调度方案进行分析。方案1中采取先到先维修的方法，方案2中采取优先级高先维修的方法，方案3为本文中考虑的多属性约束动态调度方案。通过调用分配算法得出初始调度方案，在此基础上分别设置规划阶段算法参数。通过求解，方案1所有任务完成时间为54.6 h，方案2任务完成时间为49.7 h，方案3最优目标值为37.2 h。其中，方案3的维修任务调度方案如图2所示(图2中数字编号代表“专业-任务序号”)。

图2 维修任务动态调度甘特图Fig.2 Gantt chart of dynamic optimization scheduling for maintenance tasks

为验证模型在多次复杂动态变化下的适用性，在某型导弹维修保障过程仿真中，进行50次随机故障扰动，增加维修任务数量，设定4个专业，每个专业维修任务产生概率分别为0.15，0.38，0.27，0.20，在每个维修小组维修时间取值范围为[2.5,25.5]，且每次随机增加或减少一个维修小组。每次扰动后对新产生及原待调度的维修任务进行重调度，对维修小组的选择及维修时间进行随机抽样。同样采用3种调度方案进行动态调度，对3种方案进行仿真计算，所得目标函数值即所有维修任务完成时间如图3所示。

为验证本文中考虑的分阶段动态调度方法及改进的禁忌搜索方法的求解性能，在不考虑维修任务关联性的基础上，同时采用迭代启发式算法中的NEH方法、经典禁忌搜索方法对相同数据扰动下的维修任务进行重调度与求解，3种方法在同一计算机上的运行时间如图4所示。

由图3可知，相对于传统的和只考虑单一约束条件的维修任务调度方案，采用本文中动态调度方法的维修任务完成时间平均提前约30%，且随着重调度次数的增加，优势更加显著。图4表明，改进的禁忌搜索任务规划方法相比其他2种方法在求解效率上具有明显的优势。

图3 不同方案的目标函数值曲线Fig.3 Objective function values under different schemes

图4 不同方法的运行时间曲线Fig.4 Running time of different methods

5 结论

1) 在战时装备维修任务调度研究中，同时考虑维修任务与维修力量的变化更贴近战时的实际情况与需求；

2) 相对于传统的先到先维修与单纯只考虑优先级的调度方案，综合考虑维修任务的专业分类、优先级、任务量及维修小组的专业和负载等各方面属性约束的调度方案，有效提高了将维修任务匹配到具有对应维修能力的维修力量的准确度和速度，明显缩短了维修任务完成时间；

3) 在发生维修任务和维修力量变化的时刻，进行维修任务重调度，可以将复杂的动态问题简化为每个变化时刻的静态调度问题，并生成近实时的调度方案；

4) 实例表明，在考虑多属性约束的基础上，将维修任务的动态调度过程划分为分配和规划2个阶段，可以降低调度过程的复杂性和冗余性，提高维修任务的调度效率；

5) 实例验证了改进禁忌搜索方法在维修任务动态调度模型求解中的有效性和可行性，且在实现全局优化的同时，能够保证针对性有效搜索范围及相对较少的计算量，模型的求解效率得到提高。