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

蒋陵平（中国民用航空飞行学院 航空工程学院，四川 广汉 618300）

徐文强， 葛杭 ，沈峰

摘要：通航作业多为跨地域作业、且作业时间多具有不确定性，给通航维修资源的调度带来了一定困难。通航维修资源调度作为一个典型的离散事件动态系统，本文结合petri网发展的相关研究，提出建立基于着色和时间的高级petri网^[1-3]维修资源调度模型，通过该模型可用于维修资源的预调度，实现对相关维修资源的调度时间预估、可视化调度状态查询。最后模型计算输出的维修资源调度时间结合实际通航维修资源的实际状况，通过动态规划算法对维修资源进行合理分配，以达到保障飞机持续适航和提高维修资源利用率的目的，且给现阶段通航维修资源的调度分配提供理论支持和应用参考。

Abstract：The navigation operations are mostly cross-regional operations, and the operation time is uncertain, which brings certain difficulties to the scheduling of navigation maintenance resources. As a typical discrete event dynamic system, this paper proposes a hybrid petri network maintenance resource scheduling model based on coloring and time. This model can be used for pre-scheduling of maintenance resources. Scheduling time estimation of relevant maintenance resources, visual scheduling status query. Finally, the maintenance resource scheduling time of the output of the model calculation is combined with the actual situation of the actual general aviation maintenance resources, and the maintenance resources are rationally distributed through the dynamic programming algorithm to achieve the purpose of ensuring the continuous airworthiness of the aircraft and improving the utilization rate of the maintenance resources, and to the present stage. The scheduling and allocation of general aviation maintenance resources provides theoretical support and application reference.

关键词：调度分配  时间petri网  颜色petri网  利用率  动态规划

1、背景   

通航产业高速增长的同时，不可避免地存在着一些安全隐患问题，较为突出的就是现阶段通航维修资源保障能力不足而造成的通航事故频发，而通航维修资源保障能力不足主要表现在由于维修资源需求关系冲突而造成的库存备件不足^[4]。且通航维修的目的就是合理、有效地利用各种维修资源，用最短的时间、尽可能高的利用有限的维修资源，恢复飞机至适航状态，保证通航飞行任务的安全实施，不难发现通航维修保障能力不足的根本原因是由于通航作业特点导致的维修资源的调度分配不合理所导致。通航维修资源调度，是将维修资源在规定的时间表内分配到具体的随机维修作业队（一般通航企业的随机作业队为1~2名飞行员和若干名机务人员组成）。通航维修资源调度作业作为一典型的离散过程，由于飞机故障具有随机性、作业地点具有任意性、作业时间具有不确定性等特性，但飞机一旦发生故障需要根据飞机所处环境，按照适航法规等要求，对具备该维修故障等级及以上的维修资质人员、所需航材以及专门的维修工具进行调度。若单一一架飞机故障对资源的分配调度较为简单，往往实际情况是需要同时对多驾故障飞机进行维修资源调度，其调度先后顺序交叉，容易引起维修资源的冲突，如何对有限的维修资源进行调度，调度分配计划显得尤为困难。

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

2、Petri网定义

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

设N={1,2,3......}，着色时间petri网定义为一个六元组：CTPN=(P,T;F,W,M,H)。其中：

（1）P={P_i | i=1,2,3...n；n∈N}为有限非空库所集合，集合元素在网模型中用圆圈表示，表示状态，例如发动机后减震器是否准备好，n为库所的个数。

（2）（2）T={T_j | j=1,2,3...n；ij，n∈N}为有限非空变迁集合，集合元素在网模型中用长方形表示，表示事件引起状态的改变，例如发动机后减震器出库的过程。

（3）（3）是有向弧，使用有向箭头表示，表示资源流动方向；

（4）W:F→(1,2,3......)^k为权重函数，表示每个变迁发生时资源移动的数量，k表示着色petri网库所内包含颜色标识个数；

（5）M:P→(1,2,3......)^k为初始情态集，表示网模型一开始所包含的资源数量；

（6）H:T→R₀×(R₀U{∞})为定义在变迁集上的时间区间函数，这里的R₀表示非负实数集。

对于t ԑ T,如果S ԑt→M(s)≥W（s，t）且H(t)=[a,b]，那么变迁t在标识M又发生权（M[t>），在标识M下发生变迁t，至少经过a个单位时间变迁结束，当然如果变迁t没有被优先级更高的变迁打断，至多变迁t最晚在b个单位时间必然发生产生新的标识（M[t>）。

                       公式1

3、模型建模

3.1 网模型关系确立

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

下图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为维修工时上限。发动机拆换过程中会出现某两个工艺同时需要某一维修资源，调度时间会有所不同，由于网模型采用延时预估调度时间，类似于栈数据存储方式，“先进后出，后进先出”，因此以调度用时短者为准。在详细分析通航维修资源保障系统的基础上，以飞机排故维修工作所需维修资源为输入条件，输入信号分别进入航材调度子模型、维修资质人员调度子模型、法规维护手册等调度子模型、维修工具调度子模型作为输入信号，以库存数量作为库所中的托肯数，当满足公式1变迁激发条件时，变迁激发，前置库所中的托肯销毁，经过规定时间的变迁延时，在后置库所中产生新的库所，此过程代表一个最小事件的状态改变。通过模拟维修资源之间的状态变迁，以此来仿真整个维修资源调度过程，实现对相关维修资源的调度时间预估、可视化调度状态查询。

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

3.2 维修调度任务子模型建模

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

图2 维修任务调度模型

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

3.3 航材/工具调度子模型建模

航材/工具调度模型作为维修资源调度的重要组成部分，其调度较为复杂，不仅要考虑调度的时间、航材申请审批等，还要确定航材/工具库存是否充足的问题，若现有航材库存不足时，将以何种方式进行处理等一系列应急处理办法。因此航材/工具的调度模型在时间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、Y040、P043、T041、T042、P044为航材/工具运输调度延时和相关审批手续；P026/P036/P045为航材/工具到达随机作业队；P027为维修任务所需航材/工具到位；T013/T014为库存不足；P028为供货商比价；P029为所需航材/工具采购订单；P038为串件申请；P039、T036、P040、T041、T042、P041为串件的拆卸延时和相关流程。

3.4 维修人员调度子模型建模

维修人员调度模型的搭建，受限于现阶段通航维修人员的匮乏，有放行资质的能独立排故的成熟维修人员相对较少，因此在人员受限的情况下，需要更加合理的进行分配调度。此模型的搭建，也需在时间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为维修资质人员抵达维修现场。

3.5 法规调度子模型建模

法规调度模型，由于现阶段电子版的传递方便快捷，此模型采用着色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  法规调度模型

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

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

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

4.1问题描述及定义：

以多维修任务下某种紧缺维修资源调度为例，建立调度时间最优、设备利用率最优以及经济成本最优的多目标决策动态规划模型。设A₁、A₂、A₃为三种不同的维修资源调用方式，其中A₁为基地库存资源的调用，A₂为其他随机维修小队资源的调用，A₃为采购维修资源的调用；B₁、B₂、B₃……B_m为m个维修任务；a_i为调用资源可供应量；b_j为各维修任务所需要的资源量；从A_n到B_m的调度时间为d_ij(i1,2,3)；j1,2…..,m))； T_j为B_j维修排故工时；W_j为B_j维修任务开始到资源实际使用的等待时间；MAX_j为B_j维修任务的任务完成时间上限；其产生的可行调度分配方案为S，调度时间最优分配方案为s₁，设备利用率最优分配方案为s₂，经济成本最优分配方案为s₃。

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

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

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

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

4.2动态分配算法建模

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

（1）首先此问题的最优子结构为：第m种维修任务不参与分配时，m-1种维修任务对a₁+ a₂+ a₃资源进行分配；第m种维修任务参与分配时，m-1种维修任务对a₁+ a₂+ a₃-b_m资源进行分配。

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

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

①调度时间最优方案s₁状态转移方程式为：

 公式2

②设备利用率最优方案s₂状态转移方程式为：

公式3

③经济成本最优方案s₃状态转移方程为：

                          公式4

  有了核心三要素，基于动态分配算法的维修资源分配方案建模就算完成了，下表2为动态分配算法模型对多维修任务下通航维修资源按不同目标规则进行分配，得到不同分配方案下的各项参数情况。由仿真结果可以清楚看出，获得局部性能参数的最优的分配方案并不是全局性能参数最优的分配方案，但在某些特殊需求下，仍要以牺牲部分其他性能参数为代价，保证某个性指标最优，其最终方案的产生取决于实际生产需求。

5、结束语

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

参考文献：

[1] 汤新民,朱新平.petri网原理及其在民航交通运输工程中的应用[M].北京：中国民航出版社,2013:82-148.

[2] 袁崇义.petri网应用[M].北京:科学出版社,2013:65-71.

[3] 吴哲辉.petri网导论[M].北京:机械工业出版社,2006:181-240.

[4] 倪晓晨,徐文强,等.面向通航维修保障能力现状分析及改善方法[J].电子世界,2018:30-31.

[5] 汪凯,等.基于petri网的军用飞机使用维护保障建模[J].装备指挥技术学院学报.2005(06).13-17.

[6] 朱正月,陈增强.基于面向对象时间petri网的智能电商物流服务系统建模[J].智能系统学报.2017.303-313.

[7] B Berthomieu,D Lime,OH Roux.Reachability Problems and Abstract State Spaces for Time Petri Nets with Stopwatches.Discrete Event Dynamic Systems[J].2007:133-158.

[8] Berthomieu, F Peres, F Vernadat.Bridging the gap between Timed Automata and Bounded Time Petri Nets[J], In Proceedings of FORMATS 2006. Springer Verlag, LNCS 4202, 2006. 

[9] Berthomieu, F Peres, F Vernadat. Model-checking Bounded Prioriterized Time Petri Nets[J], In Proceedings of ATVA 2007. Springer Verlag, LNCS 4762, 2007.

[10] 张绍阳,王选伦.公路施工petri网全过程仿真及关键算法研究[J].武汉理工大学学报(交通科学与工程版).2006,6(3).388-391.

[11] M Herajy,F Liu,C Rohr,M Heiner.Coloured Hybrid Petri Nets: an Adaptable Modelling Approach for Multi-scale Biological Networks.Computational Biology & Chemistry[J].2018.

[12] 席利贺,张欣,耿聪,薛奇成.基于动态规划算法的增程式电动汽车能量管理策略优化[J].交通运输工程学报.2018,06.148-156.

[13] A Brahma, Y Guezennec, G Rizzoni. Dynamic optimization of mechanical\electrical power flow in parallel hybrid electric vehicles[J]. Proceedings of AVEC 2000 5th Int Symposium on Advanced Vehicle Control . 2000.