通航维修资源调度分配方法及应用研究

蒋陵平，徐文强，葛 杭，沈 峰

(中国民用航空飞行学院 航空工程学院，四川 广汉 618300)

0 引言

通航产业高速增长的同时，不可避免地存在着一些安全隐患问题，较为突出的就是现阶段通航维修资源保障能力不足造成的通航事故频发，而通航维修资源保障能力不足主要表现在在修资源需求关系冲突造成的库存备件不足[1]。通航维修的目的是合理、有效地利用各种维修资源，即用最短的时间恢复飞机至适航状态，保证通航飞行任务的安全实施。不难发现通航维修保障能力不足的根本原因是通航作业特点导致的维修资源调度分配不合理。

通航维修资源调度是将维修资源在规定的时间内分配到具体的随机维修作业队(一般通航企业的随机作业队由1至2名飞行员和若干名机务人员组成)。飞机故障具有随机性、作业地点具有任意性、作业时间具有不确定性，飞机一旦发生故障需要根据飞机所处环境，按照适航法规等要求，对具备该维修故障等级及以上的维修资质人员、所需航材以及专门的维修工具进行调度，因此通航维修资源调度作业是一个典型的离散过程。若对一架飞机进行排故资源分配调度，其调度分配方法较为简单，但实际情况往往是需要同时对多架飞机进行排故资源分配调度，其调度先后顺序交叉，容易引起维修资源的冲突，因此对有限的维修资源进行调度分配计划显得尤为重要。

通航维修资源调度复杂性表现在其存在众多影响维修资源调度的因素上[2]，且各需求关系之间存在同步、并发、冲突、互斥、死锁等情况。现阶段关于通航维修资源调度的研究较少，针对离散事件动态系统的研究方法主要有语言与自动机、马尔科夫链、排队论、Petri网等。通航资源调度分配的难点是由于飞机排故时间、地点、飞机故障原因等的不确定性而造成的飞机排故维修资源分配的冲突、互斥等，而Petri网[3-5]能较好的解决此类问题，且Petri网已经被成功应用于物流分配、电力排故等多个领域，因此本文选用Petri网来解决通航维修资源调度分配问题。在选用Petri网的基础上将时间概念引入着色Petri网，可以更有针对性的解决通航维修资源调度分配问题。

1 模型建立

1.1 Petri网模型关系确立

对通航维修资源调度分配进行建模，首先要对整个通航运营做深入的了解，梳理清楚维修资源需求调度各状态之间存在的并发、顺序、竞争等关系，然后明确各个状态及状态之间的消息传递关系[6]，确定状态和事件驱动的状态改变所持续的时间(由于通航维修资源调度很难给定某一工序具体时间，所以本文均采用其工序的上下限时间为计算标准)，然后建立仿真系统的模型并优化调度分配方案。

图1 通航维修资源保障系统发动机拆装工艺与资源调度关系

通航维修资源保障系统发动机拆装工艺与资源调度关系为图1所示，发动机拆装维修任务按照工卡维修任务又可以细划分为A、B、C、D、E、F六大工作内容，其中A、B、C、D、E、F分别代表准备工作、发动机油封及润滑油、拆卸发动机、拆卸发动机上的飞机附件、安装发动机、发动机安装后的操作检查。发动机拆装任务计划维修工时为60～80工时，图示[x，y]为执行A、B、C、D、E、F中某一维修任务所需要的维修工时，x为维修工时下限，y为维修工时上限。发动机拆换过程中会出现某两个工艺同时需要某一维修资源，调度时间会有所不同，由于Petri网模型采用延时预估调度时间，类似于栈数据存储方式，“先进后出，后进先出”，因此以调度用时短者为准。在详细分析通航维修资源保障系统的基础上，以飞机排故维修工作所需维修资源为输入条件，输入信号分别进入航材调度子模型、维修资质人员调度子模型、法规维护手册等调度子模型、维修工具调度子模型作为输入信号，以库存数量作为库所中的托肯数，当满足公式(1)变迁激发条件时，变迁激发，前置库所中的托肯销毁，经过规定时间的变迁延时，在后置库所中产生新的库所，此过程代表一个最小事件的状态改变。通过模拟维修资源之间的状态变迁来仿真整个维修资源调度过程，实现对相关维修资源的调度时间预估、可视化调度状态查询。

1.2 Petri网模型的定义

通航维修调度分配作为一个状态空间离散，且状态的转移是事件作为驱动的复杂离散事件动态系统(DEDS)。该系统调度航材、维修工具等过程中存在着库存调度、采购调度、其他基地跟随机作业队调度等多种调度状态，故选用着色Petri网(Coloured Petri Net，CP-Nets)，着色Petri网[7]中托肯以不同颜色来对各调用状态进行分类，且可以实现对网系统的折叠、简化。着色Petri网的使用的确可以较为方便的查询通航维修调度分配过程中的状态，但对于状态的停滞时间和事件发生所经历的时延问题没有得到有效解决，导致Petri网模型输出结果难以达到预期的效果，给后期的动态规划调度分配造成了困难。因此在着色Petri网的基础上于变迁节点处引入表现时间Petri网(Time Petri Net，TPN)的时间参量[8-11]，因此Petri网模型名称定义为CTPN(Coloured Time Petri Net)，该Petri网模型不仅能够对系统状态/事件进行查询，而且还能实现对维修资源调度时间的预估。

对CTPN进行定义：设N={1，2，3......}，着色时间Petri网定义为一个六元组：CTPN=(P，T，F，W，M，H)。其中，P={Pi|i=1，2，3...n；n∈N}为有限非空库所集合，T={Tj|j=1，2，3...n；i≠j，n∈N}为有限非空变迁集合，F⊆ (P×T)(T×P)是有向弧，W:F→(1，2，3...k)为权重函数，M:P→(1，2，3....k)为初始情态集，H:T→R0×(R0U{∞})为定义在变迁集上的时间区间函数。对于t∈T，如果S∈·t→M(s)≥W(s，t)且H(t)=[a,b]，那么变迁t在标识M又发生权(M[t>)，在标识M下发生变迁t，至少经过a个单位时间变迁结束，当然如果变迁t没有被优先级更高的变迁打断，至多变迁t最晚在b个单位时间必然产生新的标识M′(M[t>M′)。

1.3 维修任务调度模型建模

维修任务调度模型主要是随机作业队根据飞机的状态，判定维修故障和定检等具体的维修项目，然后将维修项目根据工卡或维修方案分为详细的维修任务，再对维修任务所需要的维修资源进行调度申请，待维修资源调度完成，再返回维修调度模型作为响应信号，执行维修任务，待所有维修任务完成之后，对飞机的状态数据进行更新的过程。

维修任务调度模型如图2所示。其中，P0为飞机的状态，P1为随机作业队诊断维修、定检项目，P2为按照工卡或维修方案划分详细的维修任务，P3为调度等待信号，P4、P5、P6、P7、P8、P9为维修资源申请信号，P10、P11、P12、P13、P14、P15为维修资源调度完成响应信号，P16为维修项目完成信号，P17为维修任务完成后数据记录，T3、T4、T5、T6、T7、T8为各维修项目时间的相应延时。

图2 维修任务调度模型

1.4 航材/工具调度模型建模

航材/工具调度模型作为维修资源调度的重要组成部分，其调度较为复杂，不仅要考虑调度的时间、航材申请审批等，还要确定航材/工具库存是否充足，若现有航材库存不足，将以何种方式进行处理等一系列应急处理办法。因此航材/工具的调度模型在时间Petri网的基础上将代表库存的token进行着色，将其分为红、黄、蓝三种颜色，分别代表三种状态。蓝色代表库存充足，审核统计后可直接出库，经过物流运输，将所需的航材/工具交到相应的随机作业队，实施维修工作；黄色代表库存不足，需要对所需的航材/工具进行统计，然后申请航材/工具的采购，采购合同达成后，需等待厂家加工制作，制作完成后由厂家发货，经过物流运输，将所需的航材/工具交到相应的随机作业队，实施维修工作；红色代表库存数量不足且受经费、时间等原因采购申请被驳回的情况，此种情况就需要对所需的航材/工具进行串件调度处理(所谓串件调度就是从同一机型的、最近没有飞行任务的飞机上拆下所需件，更换到执行任务的飞机上)，将所需工具/航材从其他飞机拆下经过物流运输，将所需的航材/工具交到相应的随机作业队，实施维修工作。

图3 航材/工具调度模型

航材/工具调度模型如图3所示。

其中，P018代表航材/工具库存情况，T012为库存充足，P019为所需航材/工具申请清单，P020、T016、T017、P021、T018、P022为航材出库延时和相关审批手续，P023、T020、T021、P024、T022、P025/P033、T031、P034、T032、T033、P035/P042、T040、P043、T041、T042、P044为航材/工具运输调度延时和相关审批手续，P026/P036/P045为航材/工具到达随机作业队，P027为维修任务所需航材/工具到位，T013/T014为库存不足，P028为供货商比价，P029为所需航材/工具采购订单，P038为串件申请，P039、T036、P040、T041、T042、P041为串件的拆卸延时和相关流程。

1.5 维修人员调度模型建模

维修人员调度模型的搭建，受限于现阶段通航维修人员的匮乏，有放行资质的且能独立排故的成熟维修人员相对较少，因此在人员受限的情况下，需要更加合理的进行分配调度。此模型的搭建，也需在时间Petri网的基础上引入着色Petri网的概念，以黑、红、蓝、绿四色代表四种状态，其依次是ME有放行资质人员、ME无放行资质人员、AV有放行资质人员、AV无放行资质人员。当接到人员调度申请时，根据维修人员执行任务情况进行调度(如A任务需要ME放行资格人员，但只有两名ME无放行资格人员，B任务需ME人员，对资质无要求，即可进行调度)，经过一段时间，搭乘交通工具到达维修现场，开展维修任务。

图4 维修人员调度模型

维修人员调度模型如图4所示。其中，P046为维修人员所处状态，P047、T050、P048、T051、T052、P049为ME有放行资质人员差旅审批流程和延时，P051、T056、P052、T057、T058、P053为ME无放行资质人员差旅审批流程和延时，P055、T062、P056、T063、T064、P057为AV有放行资质人员差旅审批流程和延时，P058、T067、P058、T069、T064、P060为AV无放行资质人员差旅审批流程和延时，P050为维修资质人员抵达维修现场。

1.6 法规调度模型建模

法规调度模型，由于现阶段电子版的传递方便快捷，此模型采用着色Petri网，以黑、红、蓝、绿四种颜色代表飞机厂家提供的手册(AMM、AIPC、POH/FM、WDM、SRM、CAPC、NDT等)、发动机厂家提供的手册(Operator/s Manual、EMM、EIPC、Installation Manual、Trouble Shooting、Overhaul Manual等)、其他附件厂家手册(Propeller Manual、G1000 Manual、Fuel Injection、Magneto MM、Governor Manual、Aircraft Tire、Wheels&Brakes等)、其他适航性文件(CAD、SB、SI、SL等)。对维修调度模型所需的法规，经过技术科查找后，直接发送到随机作业队。

法规调度模型如图5所示。其中，P061为相关法规信息汇总，P062、P063、P064分别为飞机厂家提供的手册申请、查找和审核状态，P065为所需法规已传送到位，P066、P067、P068分别为发动机厂家提供的手册申请、查找和审核状态，P069、P070、P071分别为其他附件厂家手册申请、查找和审核状态，P072、P073、P074分别为其他适航性文件申请、查找和审核状态。

模型搭建完成后，需要对模型的相关行为特性(可达性、活性等)和结构特性(有界性、守恒性、虹吸和陷阱等)进行验证，进一步对模型进行修正。下面介绍通航维修资源调度模型调度时间计算结果，结合动态分配算法[12]，对有限资源条件下的多维修任务进行维修资源分配。

图5 法规调度模型

2 基于动态规划算法的资源分配方案

2.1 问题描述及定义

以多个维修任务下某种紧缺维修资源调度为例，建立调度时间和设备利用率最优以及经济成本最优的多目标决策动态规划模型。设a1、a2、a3为三种不同的维修资源调用方式，其中a1为基地库存资源的调用，a2为其他随机维修小队资源的调用，a3为采购维修资源的调用；b1、b2、b3……bm为m个维修任务；ai为调用资源可供应量；bj为各维修任务所需要的资源量；从an到bm的调度时间为dij(i∈(1，2…n)；j∈(1，2…m))；Tj为bj维修排故工时；Wj为bj维修任务开始到资源实际使用的等待时间；MAXj为bj维修任务的任务完成时间上限；其产生的可行调度分配方案为S，调度时间最优分配方案为s1，设备利用率最优分配方案为s2，经济成本最优分配方案为s3。

定义1 调度资源量需大于维修任务所需资源，维修任务才能响应。

定义2 维修任务一旦开始，直至任务完成，任务不能中止，资源亦处于锁定状态。

定义3 维修任务需在规定时间上限MAXj内完成。

定义4 出现紧急维修任务时，其优先级以调度时间最优、维修任务完成时间次优以及经济成本第三的调度规则。

2.2 动态分配算法建模

应用动态分配算法找到多维修任务资源分配的最优方案[12]，其中建模过程的关键是是要确定最优子结构、边界、状态转移方程式三个要素。

首先此问题的最优子结构为：第m种维修任务不参与分配时，m-1种维修任务对a1+a2+a3资源进行分配；第m种维修任务参与分配时，m-1种维修任务对a1+a2+a3-bm资源进行分配。

其次此问题的边界为：任务数量为m=1时，若三种调度方式所给的维修资源大于等于维修任务完成任务所需资源数量，那么维修任务完成耗费工时为调度时间dij和排故工时Tj之和；若三种调度方式所给的维修资源小于维修任务完成任务所需资源数量，则任务无法完成。

由于欲建立调度时间最优、设备利用率最优以及经济成本最优的多目标决策动态规划模型，故状态转移方程式有所差异。

2.2.1 调度时间最优方案s1状态转移方程式为：

2.2.2 设备利用率最优方案s2状态转移方程式为：

2.2.3 经济成本最优方案s3状态转移方程为：

有了核心三要素，基于动态分配算法的维修资源分配方案建模就完成了。动态分配算法模型对多维修任务下通航维修资源按不同目标规则进行分配，得到多资源分配调度仿真结果如表1。

由仿真结果可以看出，获得局部性能参数最优的分配方案并不是全局性能参数最优的分配方案，但在某些特殊需求下，仍要以牺牲部分其他性能参数为代价，保证某个性能指标最优，其最终方案的产生取决于实际生产需求。

表1 多资源分配调度仿真结果

3 结语

本文针对通航资源调度分配问题，在研究国内外维修保障现状的基础上，提出了基于高级Petri网的通航维修资源调度分配模型和动态分配算法以及再分配优化办法。得出可以根据维修任务、维修资源库存等实际状况实现对维修个体(针对优先级高的维修故障)和全局的最优解。并且与某通航实际调度方案进行对比，在调度时间、设备利用率等多方面取得的较为明显的改善，给现阶段通航维修资源的调度分配提供理论支持和应用参考。