资源受限条件下车辆维修工序调度优化

汤润之， 班利明， 钱乐， 雷争军， 宋卫星,3

(1.陆军工程大学 国防工程学院， 江苏 南京 210007； 2.32272部队， 甘肃 兰州 730000；3.陆军工程大学石家庄校区 装备指挥与管理系， 河北 石家庄 050003)

0 引言

车辆维修保障是一个对象繁杂(数量大、种类多、技术标准各异)、要素全面(备件与器材、设施与设备、人员与训练、技术与资料等)的系统化工程[1]。其中维修资源分配、工序调度是关键，其优化效果直接影响了车辆装备的完备性和使用效能[2]。特别是部队在执行任务时，面对维修时间和人力配置受到限制的条件下，如何最大化利用现有资源分配调拨，形成最优维修保障调度方案，显得尤为重要。

资源调度优化问题多视为资源受限项目调度问题(RCPSP)进行求解，即通过合理调配使有限资源在满足要素内部优先关系和资源约束的前提下，对项目内部活动进行合理调度，达到压缩项目工期或减小项目成本等目标。基于RCPSP的研究，有学者提出了抢占式资源受限项目调度问题(PRCPSP)，该问题属于NP难问题，作为RCPSP的重要衍生问题，通过允许任务在进程中灵活中断的方式，暂时释放任务占用资源以满足其他紧前任务执行的需要，提升了任务进程调度与执行的灵活性和可操作性。Sorli[3]总结了无抢占、单抢占和多次抢占3种活动抢占模式，并通过比较大多数实例后得出以下结论：一次抢占相比无抢占能够显著缩短进程时间，而多次抢占相比一次抢占对于缩短进程时间的贡献较小。此外，根据日常经验，反复地停止和重启一项活动，在实际操作过程中较难实现，工程实践意义不强[4]。综上所述，一次抢占式RCPSP(1_RCPSP)对于车辆维修保障系统中的调度任务，具有较好的现实应用价值。

在编码方面，文献[5]在任务进程列表融合优先权值基础方案中插入抢占点，将经典RCPSP升级为1_RCPSP，并针对该抢占式模型设计了新的编码及解码方案；文献[6]利用优先值方法编码求解RCPSP的算法，其编码方式不考虑时序约束。而基于活动列表的编码对每个活动的开始时间[7-8]、完成时间[9]以及活动位置[10]进行解码，得到了相对应的优先权值。此外，一些优先值微小更新并没有改变活动调度的实际顺序[11]，使得其组合不同编码产生相同调度的可能性增大。基于以上分析，在求解质量方面，基于活动列表的编码在某种程度上要优于基于优先权值的编码[12]。

在求解算法方面，RCPSP主要采用元启发式算法进行求解。文献[13]引入了广义优先关系和改进的单代号网络图对项目活动的紧前关系进行描述，并对布谷鸟算法进行改进，以求解该模型。文献[14]对项目调度问题的表示，提出了移动块序列的方案，在问题求解方面，利用多智能体进化算法进行求解。文献[15]研究在最大分割次数和最小连续执行周期的约束下，设计改进的遗传算法，对考虑惩罚时间的RCPSP进行求解。文献[16]针对多工种RCPSP，对禁忌搜索算法进行改进并求解模型。文献[17]基于分散搜索，提出了混合式元启发算法求解RCPSP. 文献[18]提出考虑抢占惩罚时间的多工种PRCPSP，利用改进的蚁群算法求解模型。文献[19]考虑到维修人员掌握的维修技能水平不同问题，建立多目标优化模型，利用两阶段优化算法求解模型。文献[20]提出一种项目活动时间随机的RCPSP，采用预处理和在线调度的两阶段策略，并采用两阶段局部搜索进行优化。近年来又出现了不少新型混合算法，如混合了蚁群和分散搜索的优化模型[21]，它们在解决RCPSP问题时取得了良好的效果。

结合不同算法的优缺点，本文将针对资源受限条件下的车辆维修工序调度问题建立基于人员工种及维修能力的综合模型，以人力资源工种分类、人员等级进行双目标多约束优化，采用1_RCPSP建立抢占式资源调度模型，采用带精英策略的非支配排序遗传算法(NSGA-II)对案例进行求解分析。

1 问题描述

装备维修保障资源调度问题可以转化为抢占式RCPSP进行求解，在考虑人力资源总量和各专业各等级维修人员数量的情况下[22]，兼顾维修工序的紧前约束条件，合理调度维修资源，安排其对各工序进行维修，以达到优化目标。

1.1 问题假设

根据实际情况为简明问题，本文提出以下5个假设说明：1)维修工序在维修过程中，允许对工序进行一次中断，释放维修资源，去维修优先级更高的工序；2)被抢占工序可以在发生额外的时间与费用的条件下重启；3)为提高实际合理性，抢占点只设置在整数时间点上；4)若抢占点发生在工序初始或结束时，或者工序被抢占后瞬间启动，则忽略工序抢占过程；5)关于维修资源，假定维修备件无限供应，仅对维修人力资源进行调度。

1.2 模型建立

每个工序有如下两种约束关系：

1)人力资源总约束和各工种各等级维修人员数量约束，即对工序进行维修中任意时刻，正在进行维修的维修人员总数及各种类各等级维修人员数量，不得超过相对应的维修人员数量。

2)紧前约束关系，例如工序ji和工序jk具有紧前约束关系，则工序jk必须于工序ji后发生。

战时车辆维修要求在合理安排人力资源对工序进行维修的同时使得维修时间最短，即合理利用维修资源，尽快完成维修任务。因此，本文将以维修用时最短以及特殊人力资源(维修工时最长的维修人员)总负荷最小为目标函数，建立一次抢占维修工序调度问题的数学模型。用Qg表示第g类维修人员的总负荷，sji表示工序ji的开始时间，vji表示工序ji的紧前活动集合，t表示时间点，eji表示项目最晚结束时间；除工序0和工序n+1外其他工序ji均可被拆分为两部分ji1和ji2，其开始时间分别表示为sji1和sji2，工期分别为非负整数pji1和pji2，且pji1+pji2=pji；此外，t时刻正在进行的工序集合用At表示。

双目标一次抢占模型如下：

minf1=sji+1，

(1)

(2)

s.t.sjk2+pjk2≤sjk1，∀jk∈vji，

(3)

sji1+pji1≤sji2，

(4)

pji1+pji2=pji，

(5)

sj0=0，

(6)

(7)

(8)

以上公式中对工序运行情况进行了限制：(1)式表示第1个目标函数——整个维修任务完成所耗费的总时间最小；(2)式表示第2个目标函数——人力资源总负荷，即所有维修人员的总工作时长最小化；(3)式、(4)式约束确保遵守工序间的优先关系；(5)式确保任务部分工期之和为该项任务的总工期；(6)式表示项目初始时间为0；(7)式、(8)式确保不违背资源约束条件。

2 算法求解

2.1 编码方案

文献[12]指出，优先值表示的方法相对于活动列表的表示，在求解质量和解算效率上都差强人意。因此，对于1_RCPSP，本文采用基于活动列表的编码方案得出一层编码方案，以保证产生的编码方案满足紧前约束关系。工序列表为项目网络图的一个拓扑排序。每个工序被随机产生的抢占点分为两部分，则共有2n个工序。基于工序列表的编码方案如表1所示。基于活动列表的编码为维修工序网络图的一个拓扑排序，即第1重编码为符合时序约束的一个工序排序，一次抢占式维修工序调度将每个工序分为两部分，缩小了维修人员的休息时隙，提高了维修人员的利用率，从而缩短了项目完工时间。以上论述证明，只要对维修资源进行合理合时的调度，安排其对某个子工序在最早开工时间时开始维修，便可以缩小维修人员的等待时间或维修人员的停工次数。

表1 单次抢占编码

对于染色体二重编码，在由第1重编码得出符合紧前约束的子工序序列后，对应每个子工序，在满足人力资源约束和人员种类的情况下，根据每个子工序所需的各种类人力资源，从初、中、高等级中随机选择符合约束条件的人员rji,g次，选择结果串联合并作为染色体的第2重编码。

2.2 算法设计

本文所建1_RCPSP模型为双目标多约束优化模型，对该问题采用适合求解多目标的NSGA-II，并对其改进，以适应实际维修问题对模型进行求解。

2.2.1 选择算子

采用传统的精英保留策略，即首先对当前种群进行非支配排序，其次对等级最高的非支配集合利用二元锦标赛(BTS)选择算子选出最优的二分之一染色体作为精英染色体，直接进入下一代；其余的二分之一染色体并入常规种群进行后续操作。该操作可以使得最优解单调递增逐代提升性能，同时避免庞大集合导致的种群早熟。

2.2.2 交叉算子

交叉算子按照某种交叉方式对常规种群进行重组交叉，产生新的染色体。本文采用基于部分映射策略的两点随机交叉策略，对于常规种群中每一对染色体的第1重编码，随机产生整数τ1和τ2，其中1≤τ1≤τ2≤2n，交换这对染色体中位于[τ1,τ2]区间内的染色体片段。由于抢占点的产生具有随机性，交换完成后可能导致以下两种错误情况：

1)染色体第m个工序的第1、第2部分未被安排维修的同时，导致第n个工序的第1、第2部分重复安排维修；

2)交叉后产生的对第m个工序第1、第2部分进行维修的时间与第m个工序的第2、第1部分进行维修的时间之和,不等于第m个工序所需的总维修时长。

对以上两种错误情况进行修复：

1)将交换后重复安排的维修工序n的第1、第2部分用未被安排维修的第m个工序的第1、第2部分进行替换；

2)以交叉前第m个工序的第1、第2部分为准，调整交叉后的第2、第1部分的维修时间，变更抢占点，使抢占后工序的1、第2部分维修时间之和等于该工序的总维修时间。

交换完成后，结合第1重编码和第2重编码进行染色体合法性检验，即对每个子工序所对应的人力资源种类及总数量约束进行检验，若不合法，则根据交叉后的第1重编码序列及人力资源约束条件，重新产生第2重编码序列。

2.2.3 变异算子

以某一变异概率对染色体进行重新初始化。

3 仿真与分析

3.1 示例仿真

实验以某型车辆维修保养的3级保养作业(车辆3级维修保养以维修人员为中心，进行以保为主、保修并重的车辆维修保养制度，维修人员按照车辆的专业对其分配维修作业)为例进行仿真计算并分析结果，配置维修人员数量12人，每个工种(共3类分别为A、B、C)人员分配4名维修人员，分别为2名初级人员、1名中级人员、1名高级人员。本文算法设定80个初始染色体，算法上限迭代200次，变异概率设为0.08. 表2展示了车辆维修三级保养作业关系，该型号车辆维修保养时间按军用标准表中规定为90工时，标准班组作业一般编制员额12名修维修人员，单人作业时间450 min.

表2 某型车辆维修保养的3级保养作业

3.2 结果分析

采用本文算法对表2算例进行计算，得出的部分工序调度结果如表3所示，为方便阅读，表3中只显示下面结果分析1～6出现中的相关数据，对部分过程数据进行了省略。

表3 部分工序调度方案

1～6中重点对关键拆分节点进行分析，并结合维修时间图对比了无抢占和一次抢占的调度方式优劣情况：

1)表3中数据第1列表示79个工序根据随机断点拆分为158个工序后的小工序序号，第2列为小工序所属的拆分前大工序序号，第3列小工序为大工序的第1或第2部分，第4列表示小工序进行维修的维修人员能力等级(1、2、3分别对应初、中、高级)，第5列为对该小工序进行维修的维修人员种类；第6列表示该小工序的开始维修时间，第7列为该小工序的维修完工时间。例如：第1行数据表示第22个大工序被拆分后的第2部分，即小工序的第44个，安排A工种的高级维修人员对其进行维修，开始维修时间为0 min，结束维修时间为9 min.

2)大工序22被拆分为2部分，第2部分为小工序的第44个，第1部分为小工序的第43个，由A工种维修人员中的高级人员在第48 min时开始维修，第73 min时结束维修。

3)抢占发生在整数时间点，开始、结束维修时刻为小数，是因为给定工序的维修人员为初级维修人员时，其维修工时按照中级人员维修工时的1.2倍进行计算，高级人员维修工时按照中级人员维修工时的0.8倍进行计算。

4)大工序共有9个工序，需要2个维修人员同时对其进行维修，因此拆分为小工序后共有18个小工序，需要2个维修人员同时对其进行维修。例如大工序10的第1部分，即小工序的第19个，规划B工种的初级和高级维修人员在125～154 min对其进行维修，在179～230 min由B工种的初级和高级维修人员对大工序10的第2部分，即小工序的第20个进行维修。

5)图1、图2分别为无抢占、一次抢占维修工序时间图。维修过程中，为达到整体目标最优，安排部分维修人员暂时休息，等待参与下一个工序维修，舍弃局部短时间内调度方案最优，从而导致最多有12个维修人员同时进行维修，而不是15人同时进行。

图1 无抢占维修工序调度人员维修图Fig.1 Maintenance personnel and time in non-preemptive maintenance scheduling

图2 一次抢占维修工序调度人员维修图Fig.2 Maintenance personnel and time in one-time preemptive maintenance scheduling

6)图1显示无抢占模式维修很少有12名维修人员同时进行维修，在维修时刻250 min前一直保持7名以上维修人员同时进行维修，但在250 min以后大量维修人员开始进入休息状态，只有少数维修人员继续工作，导致维修总时长较长。由图2可知，一次抢占模式虽没有12名维修人员同时维修的状态，但大致在280 min之前都是7名以上维修人员同时进行维修，同时进行维修的维修人员数量下降趋势缓慢，人员工作与休息时间分布均衡，是导致维修总工期和关键人力资源符合小于无抢占模式的原因。一次抢占模式放弃了局部调度最优，保证了全局调度结果最优。

表4所示为不同模式调度目标值。由表4可见：利用无抢占RCPSP模式安排调度方案，最短工期为358 min，关键人力资源总负荷为306 min；利用1_RCPSP模式安排调度方案，最短工期为339 min，关键人力资源总负荷为302 min；对于战时车辆维修工序调度问题，无论是对于时间优化目标还是人员优化目标，1_RCPSP模式均优于无抢占RCPSP模式。

表4 不同模式调度目标值对比

4 结论

本文采用基于活动列表编码的一次抢占式人力资源调度，结合实际任务中多工种多技术等级的情况，以四要素为约束条件，建立多目标优化模型进行求解，结果表明，对战时多目标车辆维修人力资源进行调度，1_RCPSP方案明显优于无抢占RCPSP方案。同时在传统NSGA-Ⅱ基础上，对等级最高的非支配集合利用BTS选择算子选出精英染色体进入下一代，使得最优解单调递增逐代提升性能，避免了庞大集合导致的种群早熟，提升了传统算法性能。

本文假定维修备件无限供应，仅对维修人力资源进行调度，相较于真实作战的复杂情况目标和约束条件都有待进一步增加，后续工作还需要增加对于经济效益相关因素的考量，近一步提升方法的实用性，在更加有限的资源下提升模型调度效果。