复杂人力资源约束下的抢占式维修工序调度

　　摘 要: 针对维修保障系统内部工序调度问题具有工序多、维修人员种类不同、维修人员等级不同等复杂特性， 本文建立了以维修工时最短和人力资源总负荷最小为目标函数的多目标多约束优化模型，设计了基于关键路径 算法的优先权值编码对抢占式调度问题进行第一层编码，采用随机产生方案得出第二层人力资源编码，进而针 对混合粒子群遗传算法设计了符合抢占式调度的交叉算子，利用 MATLAB 软件对实例分别进行了无抢占、一 次抢占、多次抢占调度方案仿真，最后对仿真结果进行对比分析。仿真结果得出多工序在多工种和多等级人力 资源约束下的多次抢占式维修工序调度方案，以及无抢占、一次抢占、多次抢占调度所对应的目标函数解，决 策者可根据实际需求设定目标函数权值以得出最佳调度方案.

　　关键词: 抢占式调度;维修调度;优先权值编码;多目标;混合粒子群遗传算法;多等级人力资源

　　0 引 言

　　装备维修保障系统由装备维修所需的各类维修 资源和管理手段组成，该系统装备数量种类复杂 且多，包括维修器材与备件、维修设备以及各种类 个等级维修人员等。维修工序调度优化是建立维 修保障系统的一个关键步骤，决策者需对有限的维 修资源进行合理地分配，制定详细且符合实际的维修调度方案，以达到既定目标。若维修资源分配不 合理、优化方案及算法设计不周，将导致对资源的 利用率过低，产生较长的维修时间。此问题属于资 源受限式项目调度问题 (Resource-constrained project scheduling problem，RCPSP)。如何合理地对工序的 维修流程进行安排，分配维修保障资源，形成所需 时间最短的维修调度计划，使调度方案达到最优，对于提高部队保障能力和装备保障效益都具有重要 意义[1]。

　　维修工程评职知识：工程机械维修师怎么发表论文

　　近年来，对于资源受限式项目调度问题的研 究已有不少。为了更加满足项目的各种需求，可 以将完整的工序划分为若干个子工序，对各个 子工序进行维修。根据在工序维修过程中有无 转移维修资源，将该问题划分为资源抢占式[2] 和 非资源抢占式[3]。抢占式资源受限项目调度问题 (Preemptive Resource-Constrained Project Scheduling Problem，PRCPSP)可以将当前的维修工序设置暂 停并释放其所占用的维修资源对优先级更高的工序 进行维修。理论上，通过工序抢占、设置优先级， 可以更加充分地利用维修资源，从而缩短项目工 期。文献[4] 提出对 PRCPSP 问题，每个工序的计划 维修时间段内的每个整数时刻都可以作为资源抢占 点，也就是说，若工序需要 t 个单位维修时间，则 该工序最多可以被抢占 t-1 次，并将 PRCPSP 划分为 无抢占(0_PRCPSP)，一次抢占(1_PRCPSP)和多 次抢占(m_PRCPSP)三种情况。其中 m_PRCPSP (m 次资源受限抢占式调度问题)允许工序满足各 类约束时，在维修过程中的任意整数间断点被抢 占 m 次。

　　以往的研究结论显示，相对于非抢占式 维修调度，抢占式维修调度可显著缩短工期。对于 工序的优先级编码，主要有基于活动列表的编码[2] 和基于优先权值的编码[5]，文献[6] 设计了允许多次 抢占的基于工序优先级的编码策略，文献[7] 针对 1_PRCPSP，分别设计了基于活动列表的编码方案 和基于优先权值的双重编码方案。 在问题的建模和求解方面，研究人员主要通过 建立多约束规划模型并利用启发式算法对 PRCPSP 进行研究。文献[8] 针对传统的优先关系不能满足描 述事件项目调度优先关系的要求，引入了广义优先 关系(Generalized priority relation，GPRs)和改进的 单代号网络图(Activity-On-Node，AON)来描述任 务的时序关系，并利用改进的布谷鸟算法对问题进 行求解;文献[9] 提出了移动块序列(Moving block sequence，MBS)来表示项目调度问题，使得在满 足优先约束和资源需求的情况下，尽可能早的安排 相应项目中的每个活动，并采用多智能体进化算法 (MAEA)求解问题。

　　文献[10] 研究了在最大分割 次 数和最小连续执行周期的约束下，在离散时间点 上 对每个活动进行分割(考虑分割后的惩罚时 间)的资源约束项目调度问题，设计了一种遗传算法对问题进行求解;文献[11] 建立了多个技能种类 的资源受限式项目调度问题，并对禁忌搜索算法进行改进以 求解该调度问题;针对资源受限式项目调度问题， 文献[12] 提出了分散搜索的混合元启发式算法进 行 求解;文献[13] 针对多技能资源约束项目调度问 题， 规定恢复一个被抢占的活动需要额外的惩罚 成本， 并提出了一种基于蚁群的元启发式算法来 求解模 型;文献[14] 建立了考虑胜任力差异的人 力资源受 限多目标项目调度问题模型，并采用提出 的两阶段 优化算法求解模型;文献[15] 对连续时 间条件下具 有柔性资源配置的资源约束项目调度问 题，即每个任务可以在任何时间点开始、结束或改 变其资源分 配，进行了研究;文献[16] 提出了一种 项目活动时间 随机的资源约束型项目调度问题，采 用预处理和在 线调度的两阶段策略，并采用两阶段 局部搜索进行 优化。

　　现有的人力资源有限项目调度问题多针对工期 最小的单目标函数进行优化求解，或考虑人员多技 能，或考虑人员胜任力差异，但对实际的维修工序 调度问题，需要同时考虑人员多工种类型和人员等 级不同等问题，且单一的目标函数往往难以得出符 合实际的调度方案。基于以上分析，本文对具有人 员多工种类型、人员技能等级不同的双目标—工期 最小和人力资源总负荷最小的多约束问题进行优 化，根据具体问题设计了基于实数编码的双重编码 方案对调度问题进行多次随机抢占，并采用改进的 混合粒子群—遗传算法求解模型，得出更符合实际 需求的维修工序调度方案。

　　1 基本描述

　　1.1 问题描述

　　复 杂 人 力资 源受 限式 工 序 调 度问 题采用 图 G = (V, E) 描述，其中节点集合 V 用以表示项 目中工序集合 J，有向弧集合 E 用以表示工序间的 前后关系。每个项目包含 n + 2 个工序，其中开始 0 节点和结束 n + 1 节点为虚拟工序。对于某维修任 务，工期为 SJ，给定 M 个、K 种维修人员，需要 尽可能快且在工期上限 T 时刻之前完成维修，且维 修消耗的人力资源代价尽可能小。该问题即为复杂 人力资源约束下的工序调度问题，需要针对该问题 中的维修工序进行无抢占、一次抢占、多次抢占式 调度优化，分析并对比结果，得出最符合实际要求 的维修工序调度方案。每个工序需要遵守两种约束 关系：

　　(1)资源约束关系。工序进行维修的任意时 刻，其所占用的维修人员总数必须小于总维修人员 数量。(2)时序约束关系。根据实际工序维修要求，某些工序之间存在紧前约束关系，即若工序维修尚 未结束，则工序不能开始维修。 以往的研究，多是针对单一优化目标—维修工 期最短的调度优化问题，然而，在实际的装备维修 保障过程中，单目标难以评价出一个调度方案的好 坏，决策者必须建立多个优化目标并对其进行协调， 但多个目标通常都相互制约、相互联系，直接对多 个目标进行比较相当困难，因此，需要在这些指标 之间进行衡量，找到最优平衡点。本文建立维修工 期最短和人力资源总负荷最小—双目标模型，在满 足任务时序约束和人力资源约束的条件下，合理地 调度工序和人员，达到既定的维修目标。

　　1.2 问题假设

　　(1)假设不可更新资源(配件、原材料等)充 足; (2)对于可更新资源，本文只考虑人力资源; (3)维修工序所需必要维修时间已给定; (4)不同等级维修人力资源对相应专业的每 项工序进行维修所需的时间由平时经验数据计算已 经得出; (5)每个工序只需要某一种维修人员对其进行维修。

　　2 模型构建

　　2.1 符号定义及说明

　　2.2 建立调度模型 基于以上分析，本文建立以维修工期最短和维 修人员总负荷最小为双目标的 m_PRCPSP(m 次抢 占资源受限项目调度问题)数学模型。工序 j 的开 始时间为 sj，工序 j 的紧前工序集合为 vj，t 表示 时刻;除初始工序 0 和结束工序 n + 1 外，其余的 工序均可被抢占为 W 部分，即 j1，j2，…，jW ，每 一部分的开始时刻分别为 sj1 ，sj2，…，sjW ，工时 分别为非负整数 pj1，pj2，…，pjW 。

　　3 改进的混合粒子群遗传算法 本章结合资源受限维修调度问题的特点设计了 符合本文模型的双重编码，同时对混合混沌粒子群 算法和遗传算法进行改进以适应调度方案并对其进 行求解，扩大算法的搜索范围，提高优化质量。

　　4 仿真与分析

　　4.1 示例仿真

　　数值试验以某型车辆维修保养的三级保养作业 为例，配置维修人员数量为 15 人，每种(共三种) 维修人员种类分配 5 名维修人员，分别为 2 名初 级维修人员、2 名中级维修人员、1 名高级维修人 员。初始种群数量为 80，迭代次数为 200，变异概 率 0.5。车辆维修保养的三级保养作业数据采用文 献[17] 中表 4-1 的数据，表中的维修工时均为中级维 修人员对该工序进行维修需要的工时，初级维修人 员工时为中级维修人员的 1.1 倍向后取整，高级维 修人员工时为中级维修人员的 0.9 倍向后取整。结 合本文所提出的双重编码方案和改进的混合粒子群 遗传算法，利用 MATLAB 软件对该数值案例进行 求解分析。 4.2 结果分析

　　车辆维修保养的三级保养作业维修调度部分方案。

　　(1)79 个工序根据大工序所需维修时间的比例限定抢占次数，本文中抢占次数为 18min 的整数 倍，例如：大工序 24 所需工时为 60min，则其有60/18=3 个随机抢占点; (2)给出多次抢占式维修调度的第一个 Pareto 解所对应的调度方案，数据第一列表示 79 个 大工序被随机断点被抢占后产生的 158 个子工序的 维修顺序，第二列为子工序所属的抢占前大工序序 号，第三列显示子工序属于大工序的第几部分，第 四列为对该子工序进行维修的维修人员的技术等级 (1,2,3 分别代表初、中、高级人员)，第五列为该维 修人员所属的工种类别(有 A、B、C 三种专业类 别);第六、七列分别代表该子工序的开始维修时 间和终止维修时间。例如：第一行数据表示第 7 个 大工序按照其工时被随机抢占点抢占为三段，第一 段为第 10 个子工序，派两个 B 类初级维修人员对 其进行维修，开始维修时间为 0min，终止维修时间 为 10min; (3)3、4、5 分别为无抢占、一次抢占、多 次抢占维修工序时间图。可以看出，维修全过程， 没有 15 个维修人员同时进行维修的过程，最多为 12 个维修人员同时进行维修，这是由于其他未进行 维修的人员在等待参与下一次维修，这样的调度方 案在短时间内看起来不是最优的，但对于整个维修 过程来说却是最优的。

　　5 结论

　　对考虑维修人员等级和维修人员种类的资源受 限维修工序调度优化问题，本文建立以维修时间最 小和人力资源总负荷最小为目标函数的多约束优 化模型，设计了基于关键路径法的优先权值编码方 案，对混合粒子群遗传算法进行改进，设计了符合 抢占式资源受限项目调度的粒子交叉方案，并结合 实例对无抢占、一次抢占以及多次抢占方案进行对 比，结果显示，在多目标约束下，多次抢占式调度 方案略占优势，但对抢占次数较多的多次抢占式调 度，反而会增加维修时间，因此，设计抢占式工序 调度方案，应根据实际问题考虑多次抢占的次数。 下一步将考虑带有惩罚时间的无限制多次随机 抢占方案在实际维修调度中的应用。

　　参考文献 (References)

　　[1] 李晓宇, 王新阁, 方子立等. 面向任务的装备维修保障 资源优化配置 [J]. 国防科技, 2011, 000(003):48-52. (Li X Y, Wang X G, Fang Z L, etc. Task-oriented equipment maintenance support resource optimization allocation [J]. National Defense Science and Technology, 2011, 000(003):48-52.)

　　[2] Ballestín, F., Valls, V., Quintanilla, S. Pre-emption in resource-constrained project scheduling[J]. European Journal of Operational Research, 2008, 189(3):1136-1152.

　　[3] Kaplan, Lori A. Resource-constrained Project Scheduling With Preemption of Jobs.[J]. Michigan： University of Michigan，1988.

　　作者：孙笑1,† , 宋卫星2 , 班利明2 , 齐小刚1

转载请注明来自发表学术论文网：http://www.fbxslw.com/jzlw/25479.html