基于Pareto排序法的战时装备维修任务多目标调度方法*

温海骏，李 清，邵延君，刘永姜

（中北大学机械与动力工程学院，太原 030051）

基于Pareto排序法的战时装备维修任务多目标调度方法*

温海骏，李 清，邵延君，刘永姜

（中北大学机械与动力工程学院，太原 030051）

针对战时武器装备维修保障问题，建立了包括最大完工时间、延迟时间和维修单元负荷在内的多目标优化调度模型。为提高解的多样性和收敛性，构建了一种基于Pareto排序法和小生境技术相结合的遗传算法用于模型求解，引入Pareto排序和拥挤距离进行适应度计算，通过混沌系统随机生成权重系数，并使用小生境技术改进选择方式。通过实例验证表明，该方法能够有效地解决装备维修多目标调度问题。

装备维修，多目标调度，Pareto排序法，混合遗传算法

0 引言

高技术战争背景下，武器装备维修是保障军队战斗力迅速恢复的必要条件。当前，武器装备呈现大型化、复杂化的特征，导致装备维修任务难度大大增加。对战时资源配置及维修任务调度都提出了极高的要求［1］。在军队资源有限的情况下，如何缩短维修保障时间，以最低成本、最快速度和最好质量开展对战损、故障装备的维修保障工作，以最大程度发挥维修保障系统效能，成为亟待解决的问题。

对于装备维修保障，传统研究多以保障性分析［2］、能力评价［3］和建立预测方法［4-5］为主，近年来，研究人员围绕战时装备维修调度问题相继展开研究。王正元等［6-7］提出了一种动态维修任务调度的优化方法，实现了战时维修任务的动态调度。朱波等［8］建立了一种通过控制到达时间的维修调度模型。高建军［9］在考虑维修时间与战斗力关系的基础上构建了动态维修调度模型。朱昱［10］从满足最大保障时间角度出发，建立了静态维修调度模型。万明［11］以装备维修效益最大化为目标，建立了维修保障调度模型。然而战时情况错综复杂，维修任务兼具随机多发性、动态全局性、区域分布性等特点［12］，各目标之间相互制约、相互冲突，使得装备维修调度问题呈现多批量、多工艺、多目标、不确定性等特点，缺乏更加符合实际战时状况的维修调度模型。

本文针对这种情况，借鉴生产车间调度问题，建立了多目标柔性维修调度模型。并提出一种基于Pareto排序法的混合遗传算法进行求解。算法使用基于扩展维修工序编码方式，采用混沌加权和小生境技术提高进化过程中解的多样性。以期为快速、高效地进行装备维修保障提供理论支持。

1 问题描述及模型建立

武器装备维修调度优化的目标就是要在保证待维修装备在维修顺序约束的条件下，为每道工序分配合适的维修单元，并确定每个维修单元中待修设备的排列顺序和开始维修时间，使得多个性能指标达到最优。具有柔性特征的武器装备维修调度模型，可描述为：

不同于日常维护，为赢得战争主动权，战时装备维修要求武器装备在有限维修资源条件下尽快修复投入使用，并需要综合考虑多种性能指标的要求。因此，本文选用最大完工时间、延迟时间和维修单元总负荷作为维修调度的优化目标，具体模型描述如下：

其中：

1）最大完工时间

2）最大延迟时间

3）维修单元总负荷

此外，维修调度模型还需满足如下条件：

①即同一时刻同一个维修单元只能进行一道维修工序，维修过程不能中断；②同一个待修装备的维修工序有前后制约关系。③所有维修单元在0时刻均可用，所有故障设备在0时刻都可被维修；④维修工序在维修单元中的维修时间是确定的；⑤维修作业是非抢占式的。

约束条件：

式（5）为决策变量约束；式（6）～式（7）为待修装备在维修单元中的先后顺序约束关系；式（8）为维修单元中各个待修装备的先后顺序约束。

2 模型求解

2.1 多目标遗传算法设计

与车间调度问题类似，超过两个待维修装备的柔性维修调度问题就是NP-hard问题，无法获得求解问题的最优解的多项式时间算法，只能争取用较小的计算量得到问题的近似最优解［13］。遗传算法是借鉴生物进化规律发展而成的随机搜索优化算法，被广泛应用于组合优化、机器学习等工程技术领域。但对于大规模计算问题，易于陷入“早熟”，因此，本文针对多目标维修调度问题，采用基于Pareto排序的小生境混合遗传算法进行求解。

2.1.1 初始种群产生

首先产生一组具有维修工序顺序排列的随机染色体，然后在维修工序的可选维修单元集中随机选择两个。若随机数大于0.7则选择维修工时长的单元，否则的话选择维修工时短的单元。通过这种方式产生初始种群，可较好地保持种群多样性。

2.1.2 编码规则

装备维修柔性调度问题中除了要考虑修复工序的排列顺序，还要为每一个修复工序选择一个合适的修复单元。基于这个特点，编码方式采取扩展维修工序编码规则，编码由两阶段组成，第1段为被修复装备顺序码，用来确定待修复工件的修复顺序；第2段为维修单元顺序码，用以将每道修复工序分配给合适的维修单元。以具有4个维修单元和3台损坏装备的维修系统为例，编码方式如图1所示。

解码过程将染色体视为维修工序的有序序列，通过式（7）、式（8）进行解码，把每道工序安排到可用维修单元的尽可能早的时刻进行修复，直至所有工序都安排完成。

2.1.3 适应度计算

适应度的计算采用Pareto排序的适应度赋值机制［14］，将可行解进行Pareto排序，按支配程度将种群划分为不同集合，集合中的个体按其非支配程度给定序号Xj-rank；然后，计算相同非支配性集合中个体之间的相互距离，在本集合中找出距离个体i最近的个体，两者之间的距离就是局部拥挤距离Xk-dis。具体步骤如图2所示。

为提高解的多样性，通过Logisitic映射混沌系统随机生成权重系数，进而将多目标问题转化为单目标问题，即令w1、w2和w3为目标函数权重向量。优化问题中的混沌序列权重系数可由式（10）产生：

其中，μ为控制参数，μ∈（2，4]，多目标权重向量w1和 w2由式（10）产生，w3由给出。

2.1.4 选择

选择操作采用轮盘赌的方式，为了防止群体收敛于单一个体的趋势，迭代过程中采用小生境技术对每一代适应度非常接近的个体进行处理。

式（11）中，r是个体数量，maxlj和 minlj分别为进化到j代时第l个个体的最大值和最小值，P为种群规模大小。式（11）表明小生境域密度越大的个体被遗传下去的概率越小。通过这种选择方式，可以保持解的多样性，避免算法陷入局部最优解。

2.1.5 交叉和变异

交叉的过程分两步进行：

1）代维修装备编码交叉

首先将全部待修装备分成两部分S1和S2；其次随机选择两条父染色体P1和P2，分别在P1和P2中选出包含在S1和S2中的基因，并依次复制到子染色体Q1和Q2中，基因位置保持不变；然后，再次选择在P1和P2中包含在S1和S2中的基因，将其复制到Q2和Q1中的空闲位置，其顺序保持不变，如图3所示。

2）维修单元编码交叉

首先，随机产生一列与维修单元编码染色体长度相等的序列，序列中只包含0、1元素，记为集合H；其次，从P1和P2中选出与集合H中1元素对应的工序，分别复制到Q1和Q2中；然后将P1和P2中剩下的元素依次复制到Q1和Q2中，至此完成全部交叉过程。

变异的过程分两步进行，首先在待修装备编码染色体中随机选择一道工序，随机插入到另一工序之前，并保持对应维修单元的编码不发生变化；其次，在维修单元编码染色体中随机选择两个工序，然后在可选单元集中选择其他单元进行替换。

2.2 算法验证

为了测试模型及算法的正确性，对具有6个待维修装备和8个维修单元的装备维修调度问题进行仿真验证，维修过程中各待维修装备的各道工序对应的维修单元与维修时间（维修时间中包含了运输时间）如表1所示。由于战时的需要，部分损坏装备有限时送达要求，即有维修交货期的要求。

表1 再制造加工过程FGERT网络的活动参数表

根据表1中的数据，使用Matalb2009进行编程求解，设定混合遗传算法的参数为：种群大小Pop_size=100，迭代次数 Giter=2 000，交叉概率 Pc=0.8，变异概率Pm=0.1。求解的结果如表2所示。

表2 实验结果

图4为采用混合优化算法得到的装备维修多目标调度问题的Pareto解集三维分布图，图5为该三维分布图对应的平面投影图。从图中可以看出，多目标优化算法能够有效解决具有柔性特征的维修任务调度问题，该算法能够得到一组分布均匀的Pareto前端，表明其Pareto解有较好的分布性。

通过得到的一组Pareto解，决策者可根据主观经验或多属性决策方法进行评估。限于篇幅，此处只给出第1个Pareto解对应的维修调度甘特图，图中第1位数字表示待维修装备，第3位表示维修工序。

3 结论

本文针对具有柔性特征的战时装备维修问题，建立了多目标优化调度模型，并提出了一种基于Pareto和小生境技术相结合的混合遗传算法用于模型的求解，深入研究了混合算法的编码方式、初始种群生成方式、适应度值计算方式、交叉和变异方式等。并应用具有6个损坏装备、8个维修单元的维修系统对该算法进行验证，验证结果表明，本文提出的模型能够较好地描述装备维修的柔性调度问题，算法能够得到多目标最优解，证明了算法的合理性和有效性。

［1］朱亚红，曹继平，王正元，等.变精度粗糙集的战时装备维修保障资源优化配置［J］.火力与指挥控制，2014，39（6）：40-44.

［2］于维铭.保障性分析在现役装备维修资源确定中的应用［J］.装甲兵工程学院学报，2003，17（1）：55-59.

［3］郭玉明，陈东林，李志刚，等.航空装备战时维修保障能力评价模型［J］.火力与指挥控制，2010，35（10）：166-170.

［4］王亚彬.仿真技术在维修资源预测中的应用研究［J］.计算机仿真，2005，22（7）：249-251.

［5］张申，徐豪华.基于仿真的战时维修保障力量需求预测方法研究［J］.系统仿真学报，2013，25（S1）：386-389.

［6］王正元，朱昱，宋建社，等.动态维修任务调度的优化方法［J］.机械工程学报，2008，56（1）：92-97.

［7］王正元，严小琴，朱昱，等.一种考虑专业的动态维修任务调度的优化方法［J］.兵工学报，2009，31（2）：252-256.

［8］朱波，宫俊，唐加福，等.分布式到达时间控制器装备维修任务实时调度方法［J］.火力与指挥控制，2011，36（8）：126-128.

［9］高建军，蒋里强，郭强，等.基于战斗力的维修调度模型优化研究［J］.火力与指挥控制，2014，39（3）：95-98.

［10］朱昱，宋建社，王正元.一种基于最大保障时间的战时装备维修任务调度［J］.系统工程与电子技术，2007，39（11）：1900-1903.

［11］万明，张凤鸣，樊晓光.战时装备维修任务调度的两种新算法［J］.系统工程与电子技术，2012，34（1）：107-110.

［12］牛天林，王洁，杜燕波，等.战时维修保障资源优化调度的μPSO算法研究［J］.计算机工程与应用，2011，38（9）：210-213.

［13］王晓娟.多目标柔性作业车间调度方法研究［D］.武汉：华中科技大学，2011.

［14］张师，博华，车阿大，等.基于Pareto排序和混沌加权的多目标项目调度［J］.计算机集成制造系统，2012，18（6）：1215-1222.

Multi-objective Scheduling Method of Wartime Equipment Maintenance Task Based on Pareto Sorting

WEN Hai-jun，LI Qing，SHAO Yan-jun，LIU Yong-jiang
（School of Mechanical and Power Engineering，North University of China1，Taiyuan 030051，China）

For the problem of weapons and equipment maintenance during wartime，this paper built a multi-objective scheduling model considering of the maximum completion time，delay time and maintenance unit load.In order to improve the diversity and convergence of solutions，a genetic algorithm combined Pareto sorting method and the niche technology was developed to solve the model.The fitness was evaluated by Pareto sorting and crowding distance，the weight coefficients was generated randomly by chaotic system，and the niche technology was used to improve the way of choice.The application results show that the proposed method can solve the multi-objective scheduling problem during equipment maintenance process effectively.

equipment maintenance，multi-objective scheduling，pareto sorting，hybrid genetic algorithm

TJ07

A

10.3969/j.issn.1002-0640.2017.11.31

1002-0640（2017）11-0146-05

2016-10-05

2016-11-07

山西省自然科学基金资助项目（2015011060）

温海骏（1975- ），男，山西太原人，博士，讲师。研究方向：制造过程监测与控制、生产系统建模优化与仿真等。