定点修理中维修任务调度策略的仿真评估

吕学志，王宪文，范保新，赵新会

（1.总参炮兵训练基地，河北宣化075100；2.南京炮兵学院，南京211100）

定点修理中维修任务调度策略的仿真评估

吕学志1，王宪文1，范保新1，赵新会2

（1.总参炮兵训练基地，河北宣化075100；2.南京炮兵学院，南京211100）

定点修理是一种重要的维修保障形式，合理地调度维修任务将提高定点修理的效率，进而将提高作战单元的作战效能。应用离散事件仿真方法对定点修理中的维修任务调度策略进行了研究。首先，对定点修理及维修任务调度策略进行了探讨。其次，建立了用于评估维修任务调度策略的定点修理过程仿真模型。最后，应用仿真模型对几种维修任务调度策略进行了仿真评估，仿真结果表明：维修任务执行模式选择策略中“最小累积资源（MINCSD）”策略最优；维修任务选择策略中“最短总平均工期（STMD）”策略与“最小平均工作量（MINMWK）”策略较好；子维修任务选择策略中“最早预期完成时间（EECT）”策略与“最早预期完成时间与最少资源需求混合”（EECT&LRD）策略较好；维修资源分配策略中“最少能力数（LC）”策略最好。

定点修理，维修任务，调度策略，离散事件仿真

0 引言

国内许多研究人员开始对维修任务调度进行研究，如文献［1-2］，但存在一些不足，一是维修任务调度多是研究静态模型，对动态模型研究较少；多研究基地级维修任务调度，而对野战维修任务调度研究较少；关于野战维修任务调度的研究，划分较为粗略，其实野战维修还可以划分为随伴修理、巡回修理、定点修理，具有不同的特点与规律，需要分别进行研究。二是研究方法上多采用建立规划模型，求解规划模型的方法，其实根据已有生产调度方面成熟的研究成果与研究经验，对于动态调度问题，一些启发式调度策略往往可以简单快捷地取得最佳的调度目标，也便于实际操作。所以本文主要研究定点修理过程中的维修任务调度问题，旨在通过离散事件仿真方法研究不同启发式维修任务调度策略对定点修理组织实施的影响，尝试一种新的研究途径，为获得最佳维修任务调度策略提供思路，为定点修理的组织实施提供指导。

1 定点修理

定点修理是指在相对固定的地点开设修理机构，对损坏的武器装备进行的修理。主要负责接收、修理当地部队或分队自身难以修复的武器装备和过往部队或分队待修的武器装备。定点修理是一种野战条件下重要的维修保障形式。

定点修理的特点：修理装备类型多样；修理任务更加繁重，通常为伴随、巡回修理组不能修复的装备和需要中修、部分总成大修的装备，维修任务可能包括多个子维修任务，子维修任务之间存在一定时序关系；修理方式多样可以进行原件修理，也可以进行换件修理，即维修任务存在多种执行模式；维修设备器材更加齐全，维修设备可能具有多种功能，人员技术水平较高，可能具有多种技能，即维修资源具有多种能力；在现实的定点修理中存在许多无法预料、无法控制的因素，例如故障装备随机到达，故障单元数不确定，具体哪些单元故障也不确定，因此，故障单元的维修时序关系也不确定，这些方面难以直接用数学模型来解决。因此，需要用仿真来评价系统运行性能。仿真已经成为了解系统运行规律与评估各种控制策略的强有力工具，在柔性制造系统、供应链管理、航空管理得到广泛应用。

定点修理过程从资源有限角度看，可以抽象为一种复杂的排队系统，这也是建立仿真模型的基本依据；从维修任务可以分解为多个子维修任务角度，维修任务有多种执行模式看，它又可以看作是对多执行模式多项目的动态调度，这里对故障装备的修理任务可以看作“项目”，对故障装备的故障单元的修理可以看作“活动”；此外，维修资源具有明显的柔性，所以研究中还必须考虑资源分配问题。

2 定点修理中的维修任务调度策略

定点修理过程中涉及多种维修任务调度策略，其中包括维修任务执行模式的选择策略、维修任务选择策略、子维修任务选择策略、维修资源分配策略。这4类调度策略的应用时机参见仿真模型中的故障事件与修好事件流程图，如图1、下页图2所示。需要说明的一点是，本文中采取这样的策略，即当维修任务到来时首先确定维修任务执行模式，也就是确定修理方式，修理方式在整个修理过程中是不变的，其他策略是建立在修理方式已确定的基础之上的。下面对上述不同策略进行具体介绍。

图1 故障事件的流程图

为了更好地说明这些维修任务调度策略，首先对定点修理系统进行定义：假设故障装备（维修任务）集合I，Ai为维修任务i的到来时间，Pi表示维修任务i的优先级，i∈I；故障单元（子维修任务）集合J，Pij表示维修任务i的子维修任务j的优先级，j∈Ji；M为执行模式集合，Pijm表示维修任务i的子维修任务j的采取执行模式m的优先级，m∈Mij，Mij为维修任务i的子维修任务j的执行模式集合；Sij为维修任务i的子维修任务j按照执行模式选择策略得到的执行模式集合；Dijm为维修任务i的子维修任务j采取执行模式m的平均处理时间；C为能力集合，kijmc为维修任务i的子维修任务j采取执行模式m所需能力（对于人员说是技能，对设备而言是功能）c的数量，c∈C；R表示维修资源集合，Pr表示维修资源r的优先级，r∈R；RCM为维修资源-能力矩阵，表示维修资源与能力之间的关系；定义RCM=［rcrc］|R|×|C|，其中rcrc表示资源r具备技能c的水平，rcrc∈{0，1}，r∈R，c∈C；ASi为维修任务i中所有已经完成的、正在处理的、可以处理的子维修任务构成的集合。

图2 修好事件的流程图

2.1 维修任务执行模式的选择策略

这里采用最短平均工期模式优先、最长平均工期模式优先、最大累积资源需求模式优先，最小累积资源需求模式优先，随机模式选择5种模式选择策略［3］，如表1所示。

最短平均工期（SMD Shortest Mean Duration）策略的应用思想是认为平均处理时间最短的任务执行模式优先级最高（优先级值越小优先级越高）；最长平均工期（LMD Longest Mean Duration）策略正好与最短平均工期策略相反；最小累积资源需求（MINCRD Minimum Cumulated Resource Demand）策略的应用思想是认为累积资源需求最小的任务执行模式优先级最高，尽管计算公式中是对能力的需求，但是对能力的需求其实也是对资源的需求，所以调度策略仍然使用资源需求这一称谓；最大累积资源需求（MAXCRD Maximum Cumulated Resource Demand）策略正好与最小累积资源策略相反。随机选择（RDM Randomly）策略的应用思想是随机选择子维修任务的执行模式。计算公式中，rand（）为在［0，1］区间中均匀分布的随机数。

2.2 维修任务选择策略

这里采用先到先服务、先到后服务、最短平均总工期、最长平均总工期、先到先服务与最少资源混合策略、先到后服务与最多资源混合策略、最小平均工作量、最大平均工作量等8种策略，如表2所示。

表2 维修任务调度策略

先到先服务（FCFS First Come First Serve）策略认为维修任务到达时间越早优先级越高；先到后服务（FCLS First Come Last Serve）策略的应用思想正好与先到先服务策略相反；最短总平均工期（STMD Shortest Total Mean Duration）策略认为维修任务中所有已经处理完毕的、正在处理的、可以处理的子维修任务总的平均工期越短优先级越高；最长总平均工期（LTMD Longest Total Mean Duration）策略的应用思想正好与最短总平均工期策略相反；先到先服务与最少资源混合（FCFS&MINSD First Come First Serve&Minimum Resource Demand）策略考虑了维修任务到来时间与所需资源，认为维修任务的到来时间越早、所需资源越少，则优先级越高；先到后服务与最多资源混合（FCLS&MAXSD First Come First Serve&Maximum Resource Demand）：策略认为维修任务的到来时间越晚、所需资源越多，则优先级越高；最小平均工作量（MINMWK Minimum Mean Work Content）策略认为维修任务中所有已经处理完毕的、正在处理的、可以处理的子维修任务总的平均工期量越小优先级越高；最大平均工作量（MAXMWK Maximum Mean Work Content）策略与最小平均工作量策略正好相反。计算公式中，κ为比例系数，本文中取1×106；PT为维修任务本身的优先级，本文中优先级分为3级，1级最高。

2.3 子维修任务选择策略

这里采用最早可行时间策略、最短平均工期策略、最早预期完成时间策略、最少资源需求策略、最早可行时间与最少资源需求混合策略、最短平均工期与最少资源需求混合策略、最早预期完成时间与最少资源需求混合策略等7种策略［4-5］，如表3所示。

表3 子维修任务调度策略

最早可行时间（FAFS First Available First Serve）策略考虑了子维修任务的可行时间，即最早可以开始的时间，认为子维修任务可行时间越早优先级越高；最短平均工期（SMD Shortest Mean Duration）策略考虑了子维修任务的平均工期，认为子维修任务平均工期越短优先级越高；最早预期完成时间（EECT Earliest Estimated Complete Time）策略考虑了子维修任务的预期完成时间，认为子维修任务预期完成时间越早优先级越高；最少资源需求（LRD Least Resource Demand）策略考虑了子维修任务的资源需求，认为子维修任务资源需求越少优先级越高；最早可行时间与最少资源需求混合策略（FAFS&LRD First Available First Serve and Least Resource Demand）同时考虑了子维修任务的最早可行时间与资源需求，认为子维修任务最早可行时间越早，同时资源需求越少优先级越高；最短平均工期与最少资源需求混合策略（SMD&LRD Shortest Mean Duration and Least Resource Demand）同时考虑了子维修任务的平均工作量与资源需求，认为子维修任务平均工作量越少，同时资源需求越少优先级越高；最早预期完成时间与最少资源需求混合策略（EECT&LRD Earliest Estimated Complete Time and Least Resource Demand）同时考虑了子维修任务的预期完成时间与资源需求，认为子维修任务预期完成时间越早，同时资源需求越少优先级越高。

2.4 维修资源分配策略

这里采用最小能力数、最多能力数、随机选择等3种策略［6］，如表4所示。

表4 维修资源分配策略

最少能力数（LC Least Capability）策略考虑了维修资源的能力数，认为维修资源的能力数越少优先级越高；最多能力数（MC Most Capability）认为维修资源的能力数越多优先级越高；随机选择策略（RDM Randomly）的运用思想是忽略维修资源的能力对资源分配的影响。

3 定点修理过程仿真模型

3.1 模型假设

模型假设：①故障装备的类型有若干种，故障装备到达定点修理机构的时间间隔服从指数分布，到来的装备类型服从某种离散分布，故障装备中的故障单元个数服从某种离散分布，具体哪些单元发生故障则服从均匀分布；②装备类型与单元类型之间存在隶属关系，用装备类型与单元类型的关系表来说明装备有哪些部件等；故障装备具有修理的优先级取1-3，1表示最高级，2表示中级，3表示最低级；同样故障单元的优先级取4-6，4表示最高级，5表示中级，6表示最低级（只有当故障单元从装备上拆卸下来作为单个维修任务的时候才具有本身的优先级）；③修理机构固定于某一位置，不同类型的故障装备不断到来；故障装备的修理任务可以分解细化为若干子维修任务，维修任务与故障装备对应，即故障装备的修复可以看作一项维修任务，维修任务具有本身的优先级；子维修任务与故障装备的故障单元对应，即修复故障装备的故障单元可以看作一项子维修任务，这些子维修任务可能存在时序关系，子维修任务的时序关系可以用活动节点网络图（activity-on-node，简称AON）来描述；每个子维修任务可能存在多种任务执行模式；④维修保障单元中有维修资源包括维修人员、维修设备，以及可更换单元备件；维修人员具备多种技能，维修设备具备多种功能，维修资源所具有的能力可用维修资源-能力矩阵来表示；⑤保障系统只包括定点修理机构，不考虑其他维修保障组织。

3.2 统计参数

仿真的目的是检验不同的调度策略的优劣，所以将故障装备在定点修理维修机构中的加权总逗留时间、加权平均逗留时间、加权通过率作为系统效能度量的主要指标。公式为：

其中，T为加权总逗留时间，表示对具有不同优先级维修任务逗留时间价值的一种度量；Tl为优先级为l的维修任务的逗留时间（l=1，…，6）；βl为优先级为l的维修任务的惩罚系数，在仿真模型中分别取0.530 3、0.242 4、0.121 2、0.060 6、0.030 3、0.015 2（这里采取一种策略，前一优先级的系数要大于后面所有优先级系数之和）；S为加权平均逗留时间；Fl为优先级为l的维修任务完成数量（l=1，…，6）；V为加权通过率；Nl为优先级为l的维修任务到来数量（l=1，…，6）。

3.3 建立仿真模型

本文采用事件调度法进行程序设计［7］，程序结构如图3。仿真程序中非常重要的数据结构是事件表与任务队列。事件表相当于事件构成的队列，事件表中事件的属性包括时间、事件类型（故障事件与修好事件）、所属装备编号、所属单元编号、任务队列编号（记录事件对应的维修任务在任务队列中的编号）。任务队列中维修任务的属性包括编号（按照到来顺序进行编号）、到来时间、优先级、所属装备编号、子维修任务；子维修任务的属性包括执行模式编号、占用备件向量、占用人力向量、状态（包括已经完成、正在进行、可以进行、不可以进行4种状态）、可行开始时间、后继子维修任务编号、紧前子维修任务编号、所属单元编号。任务队列中维修任务的许多信息来自于标准维修任务表，标准维修任务表中包含的信息有：装备类型编号、子维修任务时序关系矩阵、子维修任务（子维修任务的属性包括执行模式数、占用资源矩阵、平均工期向量）。

图3 事件调度法的程序结构

3.4 仿真数据

各类装备损坏单元个数概率分布如表5所示，具体哪些部件故障服从均匀分布。维修资源包括维修人员与各种备件，维修人员总数为20，资源能力矩阵如表5所示，3种装备的各种备件数量均为4。

表5 各类装备损坏单元个数概率分布

图4 装备1中子维修任务执行模式与时序关系图

图5 装备2中子维修任务执行模式与时序关系图

图6装备2中子维修任务执行模式与时序关系图

图4 ～图6分别为3类装备的子维修任务执行模式与时序关系图，其包含的信息与标准维修任务表中的信息对应。这里以图4为例进行说明。在图4中，圆圈中的数字表示子维修任务的编号，子维修任务1与子维修任务10分别为虚拟的开始与结束任务，不需要资源与时间；带有方向的箭头表示了任务之间的时序关系；圆圈下方的矩阵表示执行模式向量，每一行表示一种执行模式，第1个数字如果取表示0表示需要相应装备相应单元的备件，取1表示不需要，第2个～第5个数字依次表示对能力的需要量，第6个数字表示任务执行模式的工期。

4 仿真结果分析

本文用Matlab软件编写了仿真程序，分别对不同的维修任务执行模式选择策略、维修任务选择策略、子维修任务选择策略、资源分配策略进行了仿真试验。在这些试验中，对于每种策略都仿真40次，然后分别对加权总逗留时间、加权平均逗留时间、加权通过率3个统计参数取平均作为评价策略的指标。

表6 人员-能力矩阵

表7 不同维修任务与子维修任务选择策略组合的仿真结果（α=106）

由于篇幅限制，本文只给出当α取1×106时在不同平均到达间隔时间下不同维修任务与子维修任务选择策略组合的仿真结果，如表7所示。其中维修任务执行模式选择策略为“最短平均工期”，维修资源分配策略为“最小能力数”。仿真试验中，维修任务调度策略取了“最短总平均工期”与“最小平均工作量”两种策略，子维修任务调度策略取了“最早预期完成时间”、“最少资源需求”与“最早预期完成时间与最少资源需求混合策略”三种策略。从结果可以看出，“最短总平均工期（STMD）”策略与“最早预期完成时间与最少资源需求混合策略（EECT&LRD）”组合最优，其次为“最小平均工作量（MINMWK）”与“最早预期完成时间与最少资源需求混合策略（EECT&LRD）”组合。

5 结束语

本文应用离散事件仿真方法对定点修理中的维修任务调度策略进行了研究，探讨了定点修理及其维修任务调度策略，建立了定点修理过程的仿真模型，应用仿真模型对维修任务执行模式选择策略、维修任务选择策略、子维修任务选择策略、维修资源分配策略进行了评估，仿真结果表明：维修任务执行模式选择策略中“最小累积资源（MINCSD）”策略最优；维修任务选择策略中“最短总平均工期（STMD）”策略与“最小平均工作量（MINMWK）”策略较好；子维修任务选择策略中“最早预期完成时间（EECT）”策略与“最早预期完成时间与最少资源需求混合”（EECT&LRD）策略较好；维修资源分配策略中“最少能力数（LC）”策略最好。

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

［2］喻春明，迟玉红，方艳东，等.排队系统的非平衡动态指派模型及战时维修应用［J］.东北大学学报（自然科学版），2008（11）:1617-1620.

［3］吴兵.柔性资源受限的多模式项目调度问题研究［D］.武汉:武汉理工大学，2008.

［4］赵峥，刘德刚，段炼，等.模糊Petri网在装备维修任务调度中的应用［J］.四川兵工学报，2010，31（8）：16-19.

［5］Kurtulus I，Davis E W.Multi-Project Scheduling:Categorization of Heuristic Rules Performance［J］.Management Science，1982，28（2）:161-172.

［6］HartmannS，KolischR.ExperimentalEvaluationof State-of-the-art Heuristics for the Resource-constrained Project Scheduling Problem［J］.European Journal of Operational Research，2000（127）:394-407.

［7］Huang H C，Lee L H，Song H Q，et al.SimMan-A Simulation Model for Workforce Capacity Planning［J］.Computers& Operations Research.2009（36）:2490-2497.

［8］Law M A.Simulation Modeling and Analysis（Fourth Edition）［M］.Beijing:Tsinghua University Press，2009.

Simulation-based Evaluation of Maintenance Task Scheduling Strategies in Fixed Point Repairing

LüXue-zhi1，WANG Xian-wen1，FAN Bao-xin1，ZHAO Xin-hui2
（1.Simulation Training Center，Artillery Training Base of General Staff，Xuanhua 075100，China；
2.Nanjing Artillery Academy，Nanjing 211100，China）

Fixed point repairing is an important maintenance support form，optimally scheduling maintenance task will improve the maintenance efficiency，moreover the combat effectiveness for combat unit is increased.In the paper，maintenance task scheduling strategies in fixed point repairing are researched with discrete event simulation methods.Firstly，discussions about the fixed point repairing and maintenance task scheduling strategies are presented.Secondly，simulation model of fixed point repairing process for assessing scheduling strategies is formulated.Then，maintenance task scheduling strategies is evaluated with the simulation model.The simulation results are as following:“MINCSD（Minimum Cumulated Resource Demand）”is optimum among the maintenance task execute mode selecting heuristics.“STMD（Shortest Total Mean Duration）”and“MINMWK（Minimum Mean Work Content）”are better than other maintenance task scheduling strategies.In the maintenance subtask scheduling strategies，“EECT（Earliest Estimated Complete Time）”and“EECT&LRD（Earliest Estimated Complete Time and Least Resource Demand）”are better.When assign the maintenance resource，you’d better choose the resource with“LC（Least capability）”firstly.

fixed point repairing，maintenance task，scheduling strategies，discrete event simulation

E92

A

1002-0640（2015）01-0070-07

2013-11-10

2014-02-20

吕学志（1979-），男，河北宣化人，讲师。研究方向：建模与仿真。