基于改进PSO 的装备维修任务调度方法*

吕亚娜，田永林，杜秀丽

（大连大学通信与网络重点实验室，辽宁 大连 116622）

0 引言

装备维修的快速性对维修资源、维修人员、维修经费、维修时间等的合理分配提出了更高要求，开展装备维修任务调度方法研究，对提高参战装备的完好率与战斗恢复率，为取得战争最终胜利具有重要意义。

装备维修包含了使装备保持、恢复或改善到规定状态的全部活动，其贯穿于战场服役的全过程，其核心在于装备维修任务调度方法。近年来，学术界开展了大量的装备维修任务调度方法研究，并取得了一定的成果。文献［1］分析了战场装备维修任务特点，以故障装备尽快恢复作战所需状态为目标，提出了动态维修任务调度方法。文献［2］建立了用于评估维修任务调度策略的定点修理过程仿真模型，给出了维修任务执行模式、维修任务选择及维修资源分配中较好的策略。文献［3］提出了一种基于排队论的装甲装备故障维修任务调度方法，实现了任务调度的最优化配置。文献［4］分析了装备维修作业调度工序并行性的特点，建立以最小维修任务时间为目标的作业调度模型，并设计了基于遗传算法的模型求解算法。文献［5］考虑了维修任务调度中时间不确定因素，建立了一种装备维修任务调度模型，并采用改进的最大-最小蚂蚁系统对模型求解。文献［6］提出了一种伴随修理装备维修任务调度的多目标动态调度方法，并设计了基于改进非支配排序遗传算法（NSGA-II）对模型求解。文献［7］提出了一种基于贪婪启发式的本地搜索算法（GHLSA）用于装备多组件的系统维护，旨在最大程度地减少停机时间。文献［8］考虑了装备剩余寿命、重要性和距离等因素，提出了一种基于装备剩余寿命的最优调度模型。

以上研究对于装备维修任务调度问题具有一定借鉴，但方法适应于特定场景，且求解算法效率不高，易造成维修时间过长、维修成本过高等不足。因此，寻求一种更加合理有效的装备维修任务调度方法迫在眉睫。本文以战场环境下故障装备为研究对象，构建以武器装备重要程度、维修时间、维修成本为目标的维修任务调度模型，并设计了改进的粒子群算法对模型进行求解，该方法提高了装备维修任务调度方法的有效性，可为战场维修任务调度提供一定的参考。

1 装备维修任务调度模型

1.1 问题描述

装备维修任务调度是确保战时装备维修保障工作能够合理有效进行的重要组成部分，相对于一般维修任务而言，战时维修任务在维修复杂度、维修方法、维修时限性、维修顺序及装备故障发生范围和频率方面都有很大不同。战时装备维修任务调度的最终目标是能够使战损装备尽快恢复战斗力，及时投入战斗序列。

设有M 个维修保障分队（m=1，2，3，…，M）对N个战损装备（n=1，2，3，…，N）进行维修，装备故障类型有L 种（l=1，2，3，…，L），每个维修保障分队可维修K 个战损装备（k=1，2，3，…，K），每种故障类型装备有S 个（s=1，2，3，…，S），假设：

1）一台战损装备同一时间发生故障的故障类型不变。

2）一台战损装备由一个维修分队进行维修。

3）维修分队通过调度后维修中途不再更换其他分队，直至维修任务结束。

4）故障发生时维修分队即接收相关维修任务指令，忽略不计维修人员在不同战损装备之间的走动时间。

战时装备发生故障后，保障部门接收相关维修指令，维修辅助决策者对维修人员进行任务调度，之后不同分队的维修人员依据任务部署对战损装备进行维修，维修任务调度示意图如图1 所示。

图1 武器装备维修任务调度示意图

1.2 模型建立

根据战时装备维修的特点及装备维修保障的相关要求，本文提出的战时装备维修任务调度问题重点考虑装备重要程度、维修时间、维修成本等指标。

1）装备重要程度。不同作战装备，如指挥装备、信号装备、后勤保障装备等的重要程度不同，重要程度高的装备具有更高的优先级，往往先对优先级较高的装备进行维修，再对优先级较低的装备进行维修。第n 个装备重要程度pn可由战损装备可维修性βn1、装备对作战结果影响程度βn2以及作战任务紧迫性βn3构成，ei为指标权重，可根据战损装备尽快恢复战斗力的重要程度确定。

2）维修时间。指维修分队从开始维修战损装备到维修结束所需时间，最短的维修时间可使较多的火力装备尽快参与战斗。

3）维修成本。指装备从受损到恢复战斗力的停机成本，主要包括了装备维修耗材、维修运输及维修管理等相关费用，合理支配成本支出有助于保障部队维修更多的战损装备。

以装备重要程度、维修时间及维修成本为指标，建立装备维修任务调度模型如下：分别为3 个指标权重值；xn为维修任务调度标志，若对其进行维修，则xn=0，反之，xn=1；tmk表示第m 个维修分队对第k 个战损装备的维修时间；tls表示第l 种类型装备中第s 个战损装备的维修时间；cls表示第l 种类型装备中第s 个战损装备从发生故障到维修结束单位时间损失成本。约束1 表示装备重要程度介于［0，1］之间；约束2 表示不同维修分队中最大维修时间需小于最大保障时间T；约束3 表示维修总时间的平衡性。

式（2）表示维修任务调度总目标最优；式（3）表示未维修装备重要程度尽可能低；式（4）表示装备维修工作结束总时间最短；式（5）表示维修任务总成本尽可能最低。

为避免维修时间及维修成本数据量纲的影响，需对多目标进行去量纲化处理。

2 基于改进PSO 的装备维修任务调度算法

2.1 改进PSO 优化算法

粒子群优化算法（Particle Swarm Optimization，PSO）是由美国电气工程师Eberhart 和社会心理学家Kennedy［9］在1995 年最先提出。粒子群算法与其他算法相比具有结构简单、参数设置少、易于操作、搜索速度快等特点，但同时也存在精度低、易发散、易陷入局部最优等缺点。本文提出的改进粒子群算法将从惯性权重w，学习因子c1、c2两方面入手，改进后的w、c1、c2调整公式为：

其中，t 为算法当前迭代次数，tmax为算法的最大迭代次数，A、B、C、D 为常数，由常用测试函数及已有的学习因子调整方法可得A=0.5，B=1，C=0.5，D=2.2。对于惯性权重的调整方法，专家学者对其进行了深入研究，文献［10］表明，当wmin=0.4，wmax=0.9 时，粒子群算法能够快速收敛。改进后的粒子速度更新公式及位置更新公式如下所示：

2.2 改进PSO 算法流程

图2 改进粒子群算法流程图

本文提出的基于改进粒子群的装备维修任务调度方法流程如图2 所示。其主要步骤描述如下：

Step1：初始化种群：初始化种群规模sizepop，最大迭代次数tmax；设置粒子最大更新速度Vmax，最小更新速度Vmin，最大位置边界Xmax和最小位置边界Xmin，根据战场装备维修特点随机产生粒子初始速度和位置。

Step2：计算粒子适应度值：根据式（2）计算每个粒子的适应度值，并将其作为各自粒子个体最优值pbest，继而比较所有粒子的个体最优值，选取出最小值作为全局最优值gbest。

Step3：更新惯性权重、学习因子、粒子速度与粒子位置：根据式（8）～式（11）分别对惯性权重、学习因子、粒子速度和位置进行更新，更新后的粒子速度与位置约束如下：

表3 各装备重要程度

式（12）控制粒子的飞行速度，不但可避免因粒子速度过小算法陷入局部最优，而且同时避免粒子速度过大超出种群区域；式（13）约定了粒子的可行解区域，确保每次搜寻结果的可用性。

Step4：更新个体极值与全局极值：根据式（2）计算出粒子个体适应度值，将其与个体极值，全局极值作比较，由比较结果更新个体极值pbest，全局极值gbest。

Step5：比较当前迭代次数t 与最大迭代次数tmax，若达到最大迭代次数tmax，则输出粒子最优位置，算法结束，得出最优装备维修调度序列，否则，转向Step3。

3 实例验证

以某次战场环境下装备维修保障活动为例，假设有4 个维修保障部队，可对4 种类型的战损装备进行维修，各待维修装备的故障类型、维修时间、重要程度及维修成本如表1～表4 所示，时间以单位时间为准，不同维修保障分队最大保障时间T=25。

综合考虑本文提出的武器装备重要程度、维修时间及维修成本3 个指标，采用层次分析法对各目标权重进行确定，各目标函数两两比较矩阵如表5所示，由表5 可知，CR=0.003 6<0.1，通过一致性检验，故，f1，f2，f3，的权重分别为0.647 9，0.229 9，0.122 2。对本文算法与基本粒子群算法及线性递减惯性权重粒子群算法进行仿真实验，其中参数设置为：种群规模sizepop，最大迭代次数tmax=200，适应度收敛曲线如下页图3 所示，相比于基本粒子群算法与线性递减惯性权重粒子群算法，本文算法收敛速度快，大致在20 代即收敛至最优且精度较高，不易陷入局部最优。图4～图6 分别为基本粒子群算法、线性递减惯性权重粒子群算法，以及本文算法所对应的装备维修任务调度甘特图。

表1 各装备故障类型

表2 各类型装备由各维修分队维修时（单位时间）

表4 各类型装备单位时间损失成本（元）

表5 各目标函数两两比较判断矩阵

图3 适应度收敛曲线

图4 基本粒子群算法装备维修任务调度甘特图

图5 线性递减惯性权重粒子群算法装备维修任务调度甘特图

图6 改进粒子群算法装备维修任务调度甘特图

表6 为以上3 种算法得出的装备维修任务调度方案下维修总时间及维修成本对比表，可以看出，相比基本粒子群算法及线性递减惯性权重粒子群算法，本文算法下维修调度总时间更少，维修成本更低。因此，采用本文算法对装备维修任务进行调度，可有效提高装备维修效率，节省维修成本，有助于故障装备及时投入战斗序列，从而取得战争的最后胜利。

表6 不同粒子群算法维修时间、维修成本对比

4 结论

针对作战装备维修任务调度问题，建立了以装备重要程度、维修时间及维修成本为目标的维修任务调度模型，设计了基于改进粒子群算法的维修任务调度模型求解方法，实例验证了该改进算法的有效性。今后将进一步结合战场装备维修任务调度典型需求，细化模型参数，提高装备维修任务调度方法的适应性。