基于MDP-GERT的航空裝備維修保障流程優化研究

郭之俊，王瑛，孫贇，李超

(空軍工程大學 裝備管理與無人機工程學院，西安 710051)

0 引 言

隨著信息化戰爭向著多維一體、快速打擊等目標的不斷推進，以及高新技術在武器裝備上的廣泛應用，對航空裝備維修保障的要求日益增高。維修保障作業時間作為制約戰場上軍機再次出動能力的重要指標，關系著戰斗力的快速生成。然而，在戰時的航空裝備維修保障中，往往存在著有限的維修保障能力難以同時滿足多架軍機保障需求的矛盾。為在一定的維修保障能力下，盡可能縮短維修保障時間，提高維修保障效率，對航空裝備維修保障流程優化進行研究十分必要。目前，國內外對裝備保障流程優化的研究較為關注，使用較多的研究方法包括整數規劃[1]、多目標優化[2]、Petri網仿真[3]、隨機網絡技術[4]等多種方法。在眾多方法中，圖示評審技術(Graphical Evaluation Review Techonology，簡稱GERT)可以很好地刻畫保障活動時間服從隨機分布的情況及活動間的邏輯關系，故廣泛應用于維修保障流程的建模仿真中。鄧堃等[5]利用GERTS對具有較強資源依賴性的維修過程進行了描述，并給出相應的資源配置方案；張建強等[6]利用Q-GERT仿真了航空裝備維修保障流程中排隊過程，分析了任務完成率等指標；吳勇等[7]利用GERT網絡對艦載機保障流程模型進行求解，據此給出了相關的決策建議。上述模型主要側重于通過計算相關指標以提供流程優化的決策支持，而不能直接對保障流程進行優化排序。

與此同時，馬爾科夫決策過程(Markov Decision Process，簡稱MDP)作為一類研究隨機序貫決策的理論，可以有效地處理系統的動態調度和流程優化問題，F.Pedberg[8]首先提出了一種基于馬爾科夫過程的進度計劃方法；齊婷婷[9]應用馬爾科夫決策過程理論，對IT項目開發進度計劃進行了優化；張學杰[10]討論了馬氏決策規劃在戰時裝備維修中的應用。但是，上述研究在進度計劃時，只考慮對任務時間確定時的情況，因而無法描述現實中任務時間的隨機性，影響了優化結果的精確計算。

為了對保障流程進行優化排序，本文建立一種嵌入馬爾科夫決策過程的GERT模型，首先通過添加決策節點、構建最優維修策略下的GERT網絡，以描述裝備維修保障流程；然后基于策略改進法和蒙特卡羅方法，提出該模型的求解算法；最后結合案例，應用模型對多架飛機的維修保障流程進行優化排序和靈敏度分析。

1 裝備維修保障流程優化模型構建

航空裝備維修保障活動是由許多相關操作活動彼此按邏輯順序關聯而成的一種系統活動，具有工序多、流程復雜等特點，使用網絡圖可以較好地表達各項活動的優先級和相互作用，而流程優化問題實質是一種序貫決策求全局最優的問題，故這里嘗試在GERT網絡中嵌入決策節點，構建MDP-GERT網絡模型。

在航空裝備維修保障流程中，可以將某些重要事件作為標志，將維修保障流程劃分為若干個階段，保障活動在每個階段可能處在不同的狀態，各階段之間的狀態按照一定的概率和參數轉移，由此構建航空裝備維修保障流程MDP-GERT網絡模型基本單元，如圖1所示。

圖1 MDP-GERT網絡模型基本構成單元示意圖

Fig.1 Schematic diagram of basic components of

MDP-GERT network model

定義1MDP-GERT網絡模型基本構成單元。如果使用異或型節點表示維修保障流程中的某個階段內保障活動所處的狀態，正方形節點表示在該階段決策者采取的決策，正方形節點和異或型節點之間的箭線表示采取某一決策的情況下階段之間的轉移情況，那么，對于任意一個維修保障流程，其MDP-GERT網絡模型可以用以下五元組{S,A(i),tij(a),pij(a),V}表示。其中：

S={s1,s2,…,sn}表示維修保障流程中所有可能出現的保障活動所組成的非空有限集合；

A(i)={ai1,ai2,…,aim|i∈S}表示在狀態i后，決策者可用的決策集合，一般在實際維修保障流程中往往是非空有限的；

tij,pij(a)分別表示在當維修保障流程處于狀態i之后并且采用決策a時，維修保障流程階段轉移到狀態j過程的花費時間和概率。

V為目標函數，表示在一定策略π下從起始狀態出發到終止狀態時獲得的總傳遞變量期望。

在每一個階段下，由于GERT網絡具有馬爾科夫性，顯然決策的做出依賴于當前的維修保障狀態，與之前的歷史無關，而在維修保障流程中，每一階段的決策都是一種確定選擇而非以一定概率的選擇，故可以用隨機馬氏策略π={a1,a2,…,an}表示整個維修保障流程中的決策序列。那么，目標函數V表示在一定策略π下從起始狀態出發到終止狀態時獲得的總傳遞變量期望。

為便于對維修保障流程進行優化，根據GERT網絡模型傳遞參數與矩母函數的關系，給出以下定義：

定義2MDP-GERT網絡模型傳遞函數。在某一策略π下，隨機網絡的參數傳遞函數為

(1)

(2)

式中：pik為在采用決策a時，狀態i到狀態k的狀態轉移概率；Mik(s,a)為此時的活動參數服從的隨機變量的矩母函數。

定義3MDP-GERT網絡模型報酬函數。若維修保障流程處于狀態i之后并且采用決策a時，則這里由(i,a)所決定的維修保障流程下一階段所需花費的時間T(i,a)可被稱為MDP-GERT網絡模型報酬函數。

定義4MDP-GERT網絡模型目標函數。在策略π下，由初始狀態i出發的期望總報酬作為最優策略的比較目標，以Yn,Dn分別代表在n階段維修保障流程所處的狀態和將采取決策，則

(3)

目標函數(或稱為準則函數)V是尋找項目最優決策的函數，是各階段期望報酬的和。目標函數可以由式(4)表示

(4)

在這里需要說明，由于維修保障流程優化中的目標是維修效率最高，或者說總維修時間最短，故決策帶來的并非“報酬”而是耗費的時間，相當于“費用”，這樣在計算時將所有ti(a)加上負號，最終就可以得到相同的結果。

2 裝備維修保障流程優化模型求解

2.1 MDP-GERT網絡模型的簡化

根據信號流圖的拓撲等價性質，如果存在自環，可以對階段內的網絡模型按式(5)進行化簡，使之成為等價的單箭頭網絡模型，如圖2所示。

(5)

圖2 MDP-GERT網絡模型中自環結構的等價轉化Fig.2 Equivalent transformation of self-loop structure in MDP-GERT network model

這里根據定義2和信號流圖的等效轉換關系，由于采取決策a后所有可能的ti(a)間為并聯關系，可以對階段內的網絡按公式(6)進行化簡，使之成為等價的單箭頭網絡模型，如圖3所示。

T(i,a)=∑pi(a)ti(a)

(6)

圖3 MDP-GERT網絡模型中并聯結構的等價轉化Fig.3 Equivalent transformation of parallel structure in MDP-GERT network model

在某一策略下，在每一階段后只能選擇一種決策，這意味著在這種情況下，只有被采取的決策后的箭線上的參數有意義[11-12]，沒有被選擇的決策點后的網絡部分需要被剪枝，如圖4所示，傳遞函數恒為0。

圖4 在某一策略下MDP-GERT網絡模型時的等價轉化Fig.4 Equivalent transformation of MDP-GERT network model under a certain strategy

2.2 航空裝備維修保障流程最優策略求解

通常使用德爾菲法獲得保障流程中各單項活動的概率分布類型和數字特征。由于每次決策都會帶來網絡的結構調整，使用矩母函數求解最優策略具有相當大的困難，故這里直接利用各活動時間的期望進行策略尋優，對于MDP過程采取策略迭代法進行迭代，步驟如下：

Step1初始化：令初值V(i,a)=0，中間變量c1=c2=0；

Step3計算邊界值：

c2=|V(i,a)-c1|

Step4進行比較：當c2<ε時，輸出最優策略π，否則重新進入Step2進行迭代。

當t≤0時，V(i,a)滿足策略迭代法尋優的收斂條件[13]。

2.3 最優策略下的維修保障流程時間分析

針對利用解析法對航空裝備維修保障MDP-GERT網絡模型求解存在網絡結構過于復雜，只能得到參數的期望而不能得到各參數的準確概率分布等問題，考慮運用蒙特卡羅仿真模擬的方法來對最優策略下的維修保障流程時間進行分析。蒙特卡羅方法求解GERT網絡一般可分為鄰接矩陣法和簡化遞推法。鄰接矩陣法的思路是分解網絡成后利用已知各狀態間的轉移概率，隨機地對某一子網絡進行模擬計算，經過若干次的模擬后，統計各子網絡實現次數和參數的特征值，得出模擬結果。采用簡化遞推法先對GERT網絡進行簡化，當網絡通過等價變換逐步簡化、綜合成一個確定型網絡后，再進行模擬計算。鄰接矩陣法僅適用于結構不是很復雜且不包含環路的GERT網絡，在這里選擇簡化遞推法，其中網絡中非自環需要先被轉化為自環。轉化公式如下：

(7)

(8)

網絡中非自環被轉化為自環之后，還需要判斷網絡中的串并聯情況和自環情況，如果存在自環則還需要將其消除直至網絡被轉化成為一個確定型網絡。為了方便利用計算機求解，可利用矩陣化變換解析方法[14]對網絡進行消除自環和節點的操作。

總結上述過程，航空裝備維修保障流程MDP-GERT網絡模型的建模和求解可按照以下步驟進行。

Step1根據實際問題的背景和系統的基本特征，利用德爾菲法獲得各單項活動的傳遞參量，構造航空裝備維修保障流程MDP-GERT網絡模型；

Step2根據網絡中每項活動的基本參量，按照定義2和定義3，確定每項活動的報酬函數及整個項目的目標函數，利用策略迭代法求解最優隨機馬氏策略π；

Step3對最優策略π下的網絡進行剪枝；

Step4利用蒙特卡羅模擬方法對最優策略π下的航空裝備維修保障流程MDP-GERT網絡模型進行求解，得到最優策略π下的維修項目進度的時間分布。

Step5根據結果結合實際情況對航空裝備維修保障流程進行分析，對單項項目參數進行優化改善，便于進一步縮短維修保障流程，提高裝備維修保障能力。

3 案例分析

選取三架不同型號飛機在戰時需要進行快速充氮的情境為例，說明本文提出的建模和求解方法的使用。根據工作分解結構(Work Breakdown Structure，簡稱WBS)原理[15]，該航空裝備分系統的維修保障流程可以分成三個階段。由于飛機的型號不同，充氮工作的工序稍有區別，充氮設備有限，需要維修保障的管理人員針對不同狀態采取決策，決定本階段對某一飛機型號進行檢修。針對該問題，構造其保障流程MDP-GERT網絡模型如圖5所示，使用德爾菲法，依據相關經驗和歷史數據，已知相關活動參數如表1所示。

圖5 三機戰時充氮保障作業MDP-GERT網絡模型Fig.5 MDP-GERT network model for nitrogen filling support operation of three aircrafts in wartime

表1 三機戰時充氮保障作業各活動參數Table 1 Activity parameters of nitrogen filling support operation of three aircrafts in wartime

為驗證模型的決策效果，按照式(3)進行策略迭代計算定義的報酬函數，不考慮其他條件對活動的制約，將部分策略獲得進行對比，結果如表2所示，可以看出：決策序列中首先對a3決策所代表的機型進行維修是較為合理的。

表2 部分策略下三機戰時充氮保障作業總報酬值Table 2 Total rewards of nitrogen filling guarantee operation in three aircrafts under part of the policy

全部計算結果表明當采取策略5，即π={a3,a5,a8}的決策序列為最優策略。在策略5下對原網絡進行化簡，化簡后網絡如圖6所示。

圖6 最優策略下化簡的保障作業MDP-GERT網絡模型Fig.6 Simplified MDP-GERT network model of guarantee job under the optimal strategy

網絡模型進行蒙特卡羅仿真模擬如圖7所示，試驗次數設置為20 000次，當作業排序π={a3,a5,a8}時得到三機戰時充氮保障作業最優維修時間期望為16.18 min，利用一般的GERT網絡對未經優化的充氮保障作業流程進行維修時間估計，得到維修時間期望為22.04 min，優化后保障時間較未優化時縮短了26.59%。

圖7 優化前后的三機戰時充氮保障作業時間Fig.7 Operation time of nitrogen filling guarantee before and after optimization of three aircrafts in wartime

對流程中各活動時間進行敏感性分析和相關分析，結果如圖8～圖9所示，可以看出：充氮保障作業流程中活動a3(s1,s5)，即充氮車的及時到位是制約充氮保障作業流程的關鍵活動，充氮車的到位時間與充氮保障作業的總時間為正相關關系，其影響達到43.1%，事實上，在實際保障作業的優化中，充氮車是否到位直接決定了戰場上保障活動能否直接進行，避免等待，因此應該得到著重關注。

圖8 充氮保障作業時間敏感性分析結果Fig.8 Sensitivity analysis of nitrogen filling operation time

圖9 充氮保障作業時間相關性分析矩陣Fig.9 Correlation analysis of operation time of nitrogen filling guarantee

4 結 論

(1) 本文建立了一種新的航空裝備維修保障流程優化模型。通過結合GERT網絡技術和馬爾科夫決策過程，解決保障流程中的工序優化問題。MDP-GERT技術可以很好地刻畫任務時間分布和任務邏輯關系，從而更加準確地估計保障流程時間，實現工序的進一步優化。

(2) 在GERT網絡中加入決策點，使維修保障決策對作業時間的影響可以充分體現。利用蒙特卡羅仿真求解出在最優裝備維修保障策略的流程時間，有效避免了GERT網絡存在的難以表達和分析復雜流程的問題，為類似問題的求解提供了一種值得參考的方法。