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

所属分类：建筑论文阅读次时间：2021-01-12 10:34

本文摘要：摘要: 针对维修保障系统内部工序调度问题具有工序多、维修人员种类不同、维修人员等级不同等复杂特性，本文建立了以维修工时最短和人力资源总负荷最小为目标函数的多目标多约束优化模型，设计了基于关键路径算法的优先权值编码对抢占式调度问题进行第一层

高端学术服务项目

　　摘要: 针对维修保障系统内部工序调度问题具有工序多、维修人员种类不同、维修人员等级不同等复杂特性，本文建立了以维修工时最短和人力资源总负荷最小为目标函数的多目标多约束优化模型，设计了基于关键路径算法的优先权值编码对抢占式调度问题进行第一层编码，采用随机产生方案得出第二层人力资源编码，进而针对混合粒子群遗传算法设计了符合抢占式调度的交叉算子，利用 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