通航維修資源調(diào)度分配方法及應用研究

蔣陵平，徐文強，葛 杭，沈 峰

(中國民用航空飛行學院 航空工程學院，四川 廣漢 618300)

0 引言

通航產(chǎn)業(yè)高速增長的同時，不可避免地存在著一些安全隱患問題，較為突出的就是現(xiàn)階段通航維修資源保障能力不足造成的通航事故頻發(fā)，而通航維修資源保障能力不足主要表現(xiàn)在在修資源需求關系沖突造成的庫存?zhèn)浼蛔鉡1]。通航維修的目的是合理、有效地利用各種維修資源，即用最短的時間恢復飛機至適航狀態(tài)，保證通航飛行任務的安全實施。不難發(fā)現(xiàn)通航維修保障能力不足的根本原因是通航作業(yè)特點導致的維修資源調(diào)度分配不合理。

通航維修資源調(diào)度是將維修資源在規(guī)定的時間內(nèi)分配到具體的隨機維修作業(yè)隊(一般通航企業(yè)的隨機作業(yè)隊由1至2名飛行員和若干名機務人員組成)。飛機故障具有隨機性、作業(yè)地點具有任意性、作業(yè)時間具有不確定性，飛機一旦發(fā)生故障需要根據(jù)飛機所處環(huán)境，按照適航法規(guī)等要求，對具備該維修故障等級及以上的維修資質(zhì)人員、所需航材以及專門的維修工具進行調(diào)度，因此通航維修資源調(diào)度作業(yè)是一個典型的離散過程。若對一架飛機進行排故資源分配調(diào)度，其調(diào)度分配方法較為簡單，但實際情況往往是需要同時對多架飛機進行排故資源分配調(diào)度，其調(diào)度先后順序交叉，容易引起維修資源的沖突，因此對有限的維修資源進行調(diào)度分配計劃顯得尤為重要。

通航維修資源調(diào)度復雜性表現(xiàn)在其存在眾多影響維修資源調(diào)度的因素上[2]，且各需求關系之間存在同步、并發(fā)、沖突、互斥、死鎖等情況?，F(xiàn)階段關于通航維修資源調(diào)度的研究較少，針對離散事件動態(tài)系統(tǒng)的研究方法主要有語言與自動機、馬爾科夫鏈、排隊論、Petri網(wǎng)等。通航資源調(diào)度分配的難點是由于飛機排故時間、地點、飛機故障原因等的不確定性而造成的飛機排故維修資源分配的沖突、互斥等，而Petri網(wǎng)[3-5]能較好的解決此類問題，且Petri網(wǎng)已經(jīng)被成功應用于物流分配、電力排故等多個領域，因此本文選用Petri網(wǎng)來解決通航維修資源調(diào)度分配問題。在選用Petri網(wǎng)的基礎上將時間概念引入著色Petri網(wǎng)，可以更有針對性的解決通航維修資源調(diào)度分配問題。

1 模型建立

1.1 Petri網(wǎng)模型關系確立

對通航維修資源調(diào)度分配進行建模，首先要對整個通航運營做深入的了解，梳理清楚維修資源需求調(diào)度各狀態(tài)之間存在的并發(fā)、順序、競爭等關系，然后明確各個狀態(tài)及狀態(tài)之間的消息傳遞關系[6]，確定狀態(tài)和事件驅(qū)動的狀態(tài)改變所持續(xù)的時間(由于通航維修資源調(diào)度很難給定某一工序具體時間，所以本文均采用其工序的上下限時間為計算標準)，然后建立仿真系統(tǒng)的模型并優(yōu)化調(diào)度分配方案。

圖1 通航維修資源保障系統(tǒng)發(fā)動機拆裝工藝與資源調(diào)度關系

通航維修資源保障系統(tǒng)發(fā)動機拆裝工藝與資源調(diào)度關系為圖1所示，發(fā)動機拆裝維修任務按照工卡維修任務又可以細劃分為A、B、C、D、E、F六大工作內(nèi)容，其中A、B、C、D、E、F分別代表準備工作、發(fā)動機油封及潤滑油、拆卸發(fā)動機、拆卸發(fā)動機上的飛機附件、安裝發(fā)動機、發(fā)動機安裝后的操作檢查。發(fā)動機拆裝任務計劃維修工時為60～80工時，圖示[x，y]為執(zhí)行A、B、C、D、E、F中某一維修任務所需要的維修工時，x為維修工時下限，y為維修工時上限。發(fā)動機拆換過程中會出現(xiàn)某兩個工藝同時需要某一維修資源，調(diào)度時間會有所不同，由于Petri網(wǎng)模型采用延時預估調(diào)度時間，類似于棧數(shù)據(jù)存儲方式，“先進后出，后進先出”，因此以調(diào)度用時短者為準。在詳細分析通航維修資源保障系統(tǒng)的基礎上，以飛機排故維修工作所需維修資源為輸入條件，輸入信號分別進入航材調(diào)度子模型、維修資質(zhì)人員調(diào)度子模型、法規(guī)維護手冊等調(diào)度子模型、維修工具調(diào)度子模型作為輸入信號，以庫存數(shù)量作為庫所中的托肯數(shù)，當滿足公式(1)變遷激發(fā)條件時，變遷激發(fā)，前置庫所中的托肯銷毀，經(jīng)過規(guī)定時間的變遷延時，在后置庫所中產(chǎn)生新的庫所，此過程代表一個最小事件的狀態(tài)改變。通過模擬維修資源之間的狀態(tài)變遷來仿真整個維修資源調(diào)度過程，實現(xiàn)對相關維修資源的調(diào)度時間預估、可視化調(diào)度狀態(tài)查詢。

1.2 Petri網(wǎng)模型的定義

通航維修調(diào)度分配作為一個狀態(tài)空間離散，且狀態(tài)的轉(zhuǎn)移是事件作為驅(qū)動的復雜離散事件動態(tài)系統(tǒng)(DEDS)。該系統(tǒng)調(diào)度航材、維修工具等過程中存在著庫存調(diào)度、采購調(diào)度、其他基地跟隨機作業(yè)隊調(diào)度等多種調(diào)度狀態(tài)，故選用著色Petri網(wǎng)(Coloured Petri Net，CP-Nets)，著色Petri網(wǎng)[7]中托肯以不同顏色來對各調(diào)用狀態(tài)進行分類，且可以實現(xiàn)對網(wǎng)系統(tǒng)的折疊、簡化。著色Petri網(wǎng)的使用的確可以較為方便的查詢通航維修調(diào)度分配過程中的狀態(tài)，但對于狀態(tài)的停滯時間和事件發(fā)生所經(jīng)歷的時延問題沒有得到有效解決，導致Petri網(wǎng)模型輸出結(jié)果難以達到預期的效果，給后期的動態(tài)規(guī)劃調(diào)度分配造成了困難。因此在著色Petri網(wǎng)的基礎上于變遷節(jié)點處引入表現(xiàn)時間Petri網(wǎng)(Time Petri Net，TPN)的時間參量[8-11]，因此Petri網(wǎng)模型名稱定義為CTPN(Coloured Time Petri Net)，該Petri網(wǎng)模型不僅能夠?qū)ο到y(tǒng)狀態(tài)/事件進行查詢，而且還能實現(xiàn)對維修資源調(diào)度時間的預估。

對CTPN進行定義：設N={1，2，3......}，著色時間Petri網(wǎng)定義為一個六元組：CTPN=(P，T，F(xiàn)，W，M，H)。其中，P={Pi|i=1，2，3...n；n∈N}為有限非空庫所集合，T={Tj|j=1，2，3...n；i≠j，n∈N}為有限非空變遷集合，F(xiàn)? (P×T)(T×P)是有向弧，W:F→(1，2，3...k)為權重函數(shù)，M:P→(1，2，3....k)為初始情態(tài)集，H:T→R0×(R0U{∞})為定義在變遷集上的時間區(qū)間函數(shù)。對于t∈T，如果S∈·t→M(s)≥W(s，t)且H(t)=[a,b]，那么變遷t在標識M又發(fā)生權(M[t>)，在標識M下發(fā)生變遷t，至少經(jīng)過a個單位時間變遷結(jié)束，當然如果變遷t沒有被優(yōu)先級更高的變遷打斷，至多變遷t最晚在b個單位時間必然產(chǎn)生新的標識M′(M[t>M′)。

1.3 維修任務調(diào)度模型建模

維修任務調(diào)度模型主要是隨機作業(yè)隊根據(jù)飛機的狀態(tài)，判定維修故障和定檢等具體的維修項目，然后將維修項目根據(jù)工卡或維修方案分為詳細的維修任務，再對維修任務所需要的維修資源進行調(diào)度申請，待維修資源調(diào)度完成，再返回維修調(diào)度模型作為響應信號，執(zhí)行維修任務，待所有維修任務完成之后，對飛機的狀態(tài)數(shù)據(jù)進行更新的過程。

維修任務調(diào)度模型如圖2所示。其中，P0為飛機的狀態(tài)，P1為隨機作業(yè)隊診斷維修、定檢項目，P2為按照工卡或維修方案劃分詳細的維修任務，P3為調(diào)度等待信號，P4、P5、P6、P7、P8、P9為維修資源申請信號，P10、P11、P12、P13、P14、P15為維修資源調(diào)度完成響應信號，P16為維修項目完成信號，P17為維修任務完成后數(shù)據(jù)記錄，T3、T4、T5、T6、T7、T8為各維修項目時間的相應延時。

圖2 維修任務調(diào)度模型

1.4 航材/工具調(diào)度模型建模

航材/工具調(diào)度模型作為維修資源調(diào)度的重要組成部分，其調(diào)度較為復雜，不僅要考慮調(diào)度的時間、航材申請審批等，還要確定航材/工具庫存是否充足，若現(xiàn)有航材庫存不足，將以何種方式進行處理等一系列應急處理辦法。因此航材/工具的調(diào)度模型在時間Petri網(wǎng)的基礎上將代表庫存的token進行著色，將其分為紅、黃、藍三種顏色，分別代表三種狀態(tài)。藍色代表庫存充足，審核統(tǒng)計后可直接出庫，經(jīng)過物流運輸，將所需的航材/工具交到相應的隨機作業(yè)隊，實施維修工作；黃色代表庫存不足，需要對所需的航材/工具進行統(tǒng)計，然后申請航材/工具的采購，采購合同達成后，需等待廠家加工制作，制作完成后由廠家發(fā)貨，經(jīng)過物流運輸，將所需的航材/工具交到相應的隨機作業(yè)隊，實施維修工作；紅色代表庫存數(shù)量不足且受經(jīng)費、時間等原因采購申請被駁回的情況，此種情況就需要對所需的航材/工具進行串件調(diào)度處理(所謂串件調(diào)度就是從同一機型的、最近沒有飛行任務的飛機上拆下所需件，更換到執(zhí)行任務的飛機上)，將所需工具/航材從其他飛機拆下經(jīng)過物流運輸，將所需的航材/工具交到相應的隨機作業(yè)隊，實施維修工作。

圖3 航材/工具調(diào)度模型

航材/工具調(diào)度模型如圖3所示。

其中，P018代表航材/工具庫存情況，T012為庫存充足，P019為所需航材/工具申請清單，P020、T016、T017、P021、T018、P022為航材出庫延時和相關審批手續(xù)，P023、T020、T021、P024、T022、P025/P033、T031、P034、T032、T033、P035/P042、T040、P043、T041、T042、P044為航材/工具運輸調(diào)度延時和相關審批手續(xù)，P026/P036/P045為航材/工具到達隨機作業(yè)隊，P027為維修任務所需航材/工具到位，T013/T014為庫存不足，P028為供貨商比價，P029為所需航材/工具采購訂單，P038為串件申請，P039、T036、P040、T041、T042、P041為串件的拆卸延時和相關流程。

1.5 維修人員調(diào)度模型建模

維修人員調(diào)度模型的搭建，受限于現(xiàn)階段通航維修人員的匱乏，有放行資質(zhì)的且能獨立排故的成熟維修人員相對較少，因此在人員受限的情況下，需要更加合理的進行分配調(diào)度。此模型的搭建，也需在時間Petri網(wǎng)的基礎上引入著色Petri網(wǎng)的概念，以黑、紅、藍、綠四色代表四種狀態(tài)，其依次是ME有放行資質(zhì)人員、ME無放行資質(zhì)人員、AV有放行資質(zhì)人員、AV無放行資質(zhì)人員。當接到人員調(diào)度申請時，根據(jù)維修人員執(zhí)行任務情況進行調(diào)度(如A任務需要ME放行資格人員，但只有兩名ME無放行資格人員，B任務需ME人員，對資質(zhì)無要求，即可進行調(diào)度)，經(jīng)過一段時間，搭乘交通工具到達維修現(xiàn)場，開展維修任務。

圖4 維修人員調(diào)度模型

維修人員調(diào)度模型如圖4所示。其中，P046為維修人員所處狀態(tài)，P047、T050、P048、T051、T052、P049為ME有放行資質(zhì)人員差旅審批流程和延時，P051、T056、P052、T057、T058、P053為ME無放行資質(zhì)人員差旅審批流程和延時，P055、T062、P056、T063、T064、P057為AV有放行資質(zhì)人員差旅審批流程和延時，P058、T067、P058、T069、T064、P060為AV無放行資質(zhì)人員差旅審批流程和延時，P050為維修資質(zhì)人員抵達維修現(xiàn)場。

1.6 法規(guī)調(diào)度模型建模

法規(guī)調(diào)度模型，由于現(xiàn)階段電子版的傳遞方便快捷，此模型采用著色Petri網(wǎng)，以黑、紅、藍、綠四種顏色代表飛機廠家提供的手冊(AMM、AIPC、POH/FM、WDM、SRM、CAPC、NDT等)、發(fā)動機廠家提供的手冊(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等)。對維修調(diào)度模型所需的法規(guī)，經(jīng)過技術科查找后，直接發(fā)送到隨機作業(yè)隊。

法規(guī)調(diào)度模型如圖5所示。其中，P061為相關法規(guī)信息匯總，P062、P063、P064分別為飛機廠家提供的手冊申請、查找和審核狀態(tài)，P065為所需法規(guī)已傳送到位，P066、P067、P068分別為發(fā)動機廠家提供的手冊申請、查找和審核狀態(tài)，P069、P070、P071分別為其他附件廠家手冊申請、查找和審核狀態(tài)，P072、P073、P074分別為其他適航性文件申請、查找和審核狀態(tài)。

模型搭建完成后，需要對模型的相關行為特性(可達性、活性等)和結(jié)構特性(有界性、守恒性、虹吸和陷阱等)進行驗證，進一步對模型進行修正。下面介紹通航維修資源調(diào)度模型調(diào)度時間計算結(jié)果，結(jié)合動態(tài)分配算法[12]，對有限資源條件下的多維修任務進行維修資源分配。

圖5 法規(guī)調(diào)度模型

2 基于動態(tài)規(guī)劃算法的資源分配方案

2.1 問題描述及定義

以多個維修任務下某種緊缺維修資源調(diào)度為例，建立調(diào)度時間和設備利用率最優(yōu)以及經(jīng)濟成本最優(yōu)的多目標決策動態(tài)規(guī)劃模型。設a1、a2、a3為三種不同的維修資源調(diào)用方式，其中a1為基地庫存資源的調(diào)用，a2為其他隨機維修小隊資源的調(diào)用，a3為采購維修資源的調(diào)用；b1、b2、b3……bm為m個維修任務；ai為調(diào)用資源可供應量；bj為各維修任務所需要的資源量；從an到bm的調(diào)度時間為dij(i∈(1，2…n)；j∈(1，2…m))；Tj為bj維修排故工時；Wj為bj維修任務開始到資源實際使用的等待時間；MAXj為bj維修任務的任務完成時間上限；其產(chǎn)生的可行調(diào)度分配方案為S，調(diào)度時間最優(yōu)分配方案為s1，設備利用率最優(yōu)分配方案為s2，經(jīng)濟成本最優(yōu)分配方案為s3。

定義1 調(diào)度資源量需大于維修任務所需資源，維修任務才能響應。

定義2 維修任務一旦開始，直至任務完成，任務不能中止，資源亦處于鎖定狀態(tài)。

定義3 維修任務需在規(guī)定時間上限MAXj內(nèi)完成。

定義4 出現(xiàn)緊急維修任務時，其優(yōu)先級以調(diào)度時間最優(yōu)、維修任務完成時間次優(yōu)以及經(jīng)濟成本第三的調(diào)度規(guī)則。

2.2 動態(tài)分配算法建模

應用動態(tài)分配算法找到多維修任務資源分配的最優(yōu)方案[12]，其中建模過程的關鍵是是要確定最優(yōu)子結(jié)構、邊界、狀態(tài)轉(zhuǎn)移方程式三個要素。

首先此問題的最優(yōu)子結(jié)構為：第m種維修任務不參與分配時，m-1種維修任務對a1+a2+a3資源進行分配；第m種維修任務參與分配時，m-1種維修任務對a1+a2+a3-bm資源進行分配。

其次此問題的邊界為：任務數(shù)量為m=1時，若三種調(diào)度方式所給的維修資源大于等于維修任務完成任務所需資源數(shù)量，那么維修任務完成耗費工時為調(diào)度時間dij和排故工時Tj之和；若三種調(diào)度方式所給的維修資源小于維修任務完成任務所需資源數(shù)量，則任務無法完成。

由于欲建立調(diào)度時間最優(yōu)、設備利用率最優(yōu)以及經(jīng)濟成本最優(yōu)的多目標決策動態(tài)規(guī)劃模型，故狀態(tài)轉(zhuǎn)移方程式有所差異。

2.2.1 調(diào)度時間最優(yōu)方案s1狀態(tài)轉(zhuǎn)移方程式為：

2.2.2 設備利用率最優(yōu)方案s2狀態(tài)轉(zhuǎn)移方程式為：

2.2.3 經(jīng)濟成本最優(yōu)方案s3狀態(tài)轉(zhuǎn)移方程為：

有了核心三要素，基于動態(tài)分配算法的維修資源分配方案建模就完成了。動態(tài)分配算法模型對多維修任務下通航維修資源按不同目標規(guī)則進行分配，得到多資源分配調(diào)度仿真結(jié)果如表1。

由仿真結(jié)果可以看出，獲得局部性能參數(shù)最優(yōu)的分配方案并不是全局性能參數(shù)最優(yōu)的分配方案，但在某些特殊需求下，仍要以犧牲部分其他性能參數(shù)為代價，保證某個性能指標最優(yōu)，其最終方案的產(chǎn)生取決于實際生產(chǎn)需求。

表1 多資源分配調(diào)度仿真結(jié)果

3 結(jié)語

本文針對通航資源調(diào)度分配問題，在研究國內(nèi)外維修保障現(xiàn)狀的基礎上，提出了基于高級Petri網(wǎng)的通航維修資源調(diào)度分配模型和動態(tài)分配算法以及再分配優(yōu)化辦法。得出可以根據(jù)維修任務、維修資源庫存等實際狀況實現(xiàn)對維修個體(針對優(yōu)先級高的維修故障)和全局的最優(yōu)解。并且與某通航實際調(diào)度方案進行對比，在調(diào)度時間、設備利用率等多方面取得的較為明顯的改善，給現(xiàn)階段通航維修資源的調(diào)度分配提供理論支持和應用參考。