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

(空軍工程大學(xué) 裝備管理與無(wú)人機(jī)工程學(xué)院，西安 710051)

0 引 言

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

與此同時(shí)，馬爾科夫決策過(guò)程(Markov Decision Process，簡(jiǎn)稱MDP)作為一類研究隨機(jī)序貫決策的理論，可以有效地處理系統(tǒng)的動(dòng)態(tài)調(diào)度和流程優(yōu)化問(wèn)題，F(xiàn).Pedberg[8]首先提出了一種基于馬爾科夫過(guò)程的進(jìn)度計(jì)劃方法；齊婷婷[9]應(yīng)用馬爾科夫決策過(guò)程理論，對(duì)IT項(xiàng)目開(kāi)發(fā)進(jìn)度計(jì)劃進(jìn)行了優(yōu)化；張學(xué)杰[10]討論了馬氏決策規(guī)劃在戰(zhàn)時(shí)裝備維修中的應(yīng)用。但是，上述研究在進(jìn)度計(jì)劃時(shí)，只考慮對(duì)任務(wù)時(shí)間確定時(shí)的情況，因而無(wú)法描述現(xiàn)實(shí)中任務(wù)時(shí)間的隨機(jī)性，影響了優(yōu)化結(jié)果的精確計(jì)算。

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

1 裝備維修保障流程優(yōu)化模型構(gòu)建

航空裝備維修保障活動(dòng)是由許多相關(guān)操作活動(dòng)彼此按邏輯順序關(guān)聯(lián)而成的一種系統(tǒng)活動(dòng)，具有工序多、流程復(fù)雜等特點(diǎn)，使用網(wǎng)絡(luò)圖可以較好地表達(dá)各項(xiàng)活動(dòng)的優(yōu)先級(jí)和相互作用，而流程優(yōu)化問(wèn)題實(shí)質(zhì)是一種序貫決策求全局最優(yōu)的問(wèn)題，故這里嘗試在GERT網(wǎng)絡(luò)中嵌入決策節(jié)點(diǎn)，構(gòu)建MDP-GERT網(wǎng)絡(luò)模型。

在航空裝備維修保障流程中，可以將某些重要事件作為標(biāo)志，將維修保障流程劃分為若干個(gè)階段，保障活動(dòng)在每個(gè)階段可能處在不同的狀態(tài)，各階段之間的狀態(tài)按照一定的概率和參數(shù)轉(zhuǎn)移，由此構(gòu)建航空裝備維修保障流程MDP-GERT網(wǎng)絡(luò)模型基本單元，如圖1所示。

圖1 MDP-GERT網(wǎng)絡(luò)模型基本構(gòu)成單元示意圖

Fig.1 Schematic diagram of basic components of

MDP-GERT network model

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

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

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

tij,pij(a)分別表示在當(dāng)維修保障流程處于狀態(tài)i之后并且采用決策a時(shí)，維修保障流程階段轉(zhuǎn)移到狀態(tài)j過(guò)程的花費(fèi)時(shí)間和概率。

V為目標(biāo)函數(shù)，表示在一定策略π下從起始狀態(tài)出發(fā)到終止?fàn)顟B(tài)時(shí)獲得的總傳遞變量期望。

在每一個(gè)階段下，由于GERT網(wǎng)絡(luò)具有馬爾科夫性，顯然決策的做出依賴于當(dāng)前的維修保障狀態(tài)，與之前的歷史無(wú)關(guān)，而在維修保障流程中，每一階段的決策都是一種確定選擇而非以一定概率的選擇，故可以用隨機(jī)馬氏策略π={a1,a2,…,an}表示整個(gè)維修保障流程中的決策序列。那么，目標(biāo)函數(shù)V表示在一定策略π下從起始狀態(tài)出發(fā)到終止?fàn)顟B(tài)時(shí)獲得的總傳遞變量期望。

為便于對(duì)維修保障流程進(jìn)行優(yōu)化，根據(jù)GERT網(wǎng)絡(luò)模型傳遞參數(shù)與矩母函數(shù)的關(guān)系，給出以下定義：

定義2MDP-GERT網(wǎng)絡(luò)模型傳遞函數(shù)。在某一策略π下，隨機(jī)網(wǎng)絡(luò)的參數(shù)傳遞函數(shù)為

(1)

(2)

式中：pik為在采用決策a時(shí)，狀態(tài)i到狀態(tài)k的狀態(tài)轉(zhuǎn)移概率；Mik(s,a)為此時(shí)的活動(dòng)參數(shù)服從的隨機(jī)變量的矩母函數(shù)。

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

定義4MDP-GERT網(wǎng)絡(luò)模型目標(biāo)函數(shù)。在策略π下，由初始狀態(tài)i出發(fā)的期望總報(bào)酬作為最優(yōu)策略的比較目標(biāo)，以Yn,Dn分別代表在n階段維修保障流程所處的狀態(tài)和將采取決策，則

(3)

目標(biāo)函數(shù)(或稱為準(zhǔn)則函數(shù))V是尋找項(xiàng)目最優(yōu)決策的函數(shù)，是各階段期望報(bào)酬的和。目標(biāo)函數(shù)可以由式(4)表示

(4)

在這里需要說(shuō)明，由于維修保障流程優(yōu)化中的目標(biāo)是維修效率最高，或者說(shuō)總維修時(shí)間最短，故決策帶來(lái)的并非“報(bào)酬”而是耗費(fèi)的時(shí)間，相當(dāng)于“費(fèi)用”，這樣在計(jì)算時(shí)將所有ti(a)加上負(fù)號(hào)，最終就可以得到相同的結(jié)果。

2 裝備維修保障流程優(yōu)化模型求解

2.1 MDP-GERT網(wǎng)絡(luò)模型的簡(jiǎn)化

根據(jù)信號(hào)流圖的拓?fù)涞葍r(jià)性質(zhì)，如果存在自環(huán)，可以對(duì)階段內(nèi)的網(wǎng)絡(luò)模型按式(5)進(jìn)行化簡(jiǎn)，使之成為等價(jià)的單箭頭網(wǎng)絡(luò)模型，如圖2所示。

(5)

圖2 MDP-GERT網(wǎng)絡(luò)模型中自環(huán)結(jié)構(gòu)的等價(jià)轉(zhuǎn)化Fig.2 Equivalent transformation of self-loop structure in MDP-GERT network model

這里根據(jù)定義2和信號(hào)流圖的等效轉(zhuǎn)換關(guān)系，由于采取決策a后所有可能的ti(a)間為并聯(lián)關(guān)系，可以對(duì)階段內(nèi)的網(wǎng)絡(luò)按公式(6)進(jìn)行化簡(jiǎn)，使之成為等價(jià)的單箭頭網(wǎng)絡(luò)模型，如圖3所示。

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

(6)

圖3 MDP-GERT網(wǎng)絡(luò)模型中并聯(lián)結(jié)構(gòu)的等價(jià)轉(zhuǎn)化Fig.3 Equivalent transformation of parallel structure in MDP-GERT network model

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

圖4 在某一策略下MDP-GERT網(wǎng)絡(luò)模型時(shí)的等價(jià)轉(zhuǎn)化Fig.4 Equivalent transformation of MDP-GERT network model under a certain strategy

2.2 航空裝備維修保障流程最優(yōu)策略求解

通常使用德?tīng)柗品ǐ@得保障流程中各單項(xiàng)活動(dòng)的概率分布類型和數(shù)字特征。由于每次決策都會(huì)帶來(lái)網(wǎng)絡(luò)的結(jié)構(gòu)調(diào)整，使用矩母函數(shù)求解最優(yōu)策略具有相當(dāng)大的困難，故這里直接利用各活動(dòng)時(shí)間的期望進(jìn)行策略尋優(yōu)，對(duì)于MDP過(guò)程采取策略迭代法進(jìn)行迭代，步驟如下：

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

Step3計(jì)算邊界值：

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

Step4進(jìn)行比較：當(dāng)c2<ε時(shí)，輸出最優(yōu)策略π，否則重新進(jìn)入Step2進(jìn)行迭代。

當(dāng)t≤0時(shí)，V(i,a)滿足策略迭代法尋優(yōu)的收斂條件[13]。

2.3 最優(yōu)策略下的維修保障流程時(shí)間分析

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

(7)

(8)

網(wǎng)絡(luò)中非自環(huán)被轉(zhuǎn)化為自環(huán)之后，還需要判斷網(wǎng)絡(luò)中的串并聯(lián)情況和自環(huán)情況，如果存在自環(huán)則還需要將其消除直至網(wǎng)絡(luò)被轉(zhuǎn)化成為一個(gè)確定型網(wǎng)絡(luò)。為了方便利用計(jì)算機(jī)求解，可利用矩陣化變換解析方法[14]對(duì)網(wǎng)絡(luò)進(jìn)行消除自環(huán)和節(jié)點(diǎn)的操作。

總結(jié)上述過(guò)程，航空裝備維修保障流程MDP-GERT網(wǎng)絡(luò)模型的建模和求解可按照以下步驟進(jìn)行。

Step1根據(jù)實(shí)際問(wèn)題的背景和系統(tǒng)的基本特征，利用德?tīng)柗品ǐ@得各單項(xiàng)活動(dòng)的傳遞參量，構(gòu)造航空裝備維修保障流程MDP-GERT網(wǎng)絡(luò)模型；

Step2根據(jù)網(wǎng)絡(luò)中每項(xiàng)活動(dòng)的基本參量，按照定義2和定義3，確定每項(xiàng)活動(dòng)的報(bào)酬函數(shù)及整個(gè)項(xiàng)目的目標(biāo)函數(shù)，利用策略迭代法求解最優(yōu)隨機(jī)馬氏策略π；

Step3對(duì)最優(yōu)策略π下的網(wǎng)絡(luò)進(jìn)行剪枝；

Step4利用蒙特卡羅模擬方法對(duì)最優(yōu)策略π下的航空裝備維修保障流程MDP-GERT網(wǎng)絡(luò)模型進(jìn)行求解，得到最優(yōu)策略π下的維修項(xiàng)目進(jìn)度的時(shí)間分布。

Step5根據(jù)結(jié)果結(jié)合實(shí)際情況對(duì)航空裝備維修保障流程進(jìn)行分析，對(duì)單項(xiàng)項(xiàng)目參數(shù)進(jìn)行優(yōu)化改善，便于進(jìn)一步縮短維修保障流程，提高裝備維修保障能力。

3 案例分析

選取三架不同型號(hào)飛機(jī)在戰(zhàn)時(shí)需要進(jìn)行快速充氮的情境為例，說(shuō)明本文提出的建模和求解方法的使用。根據(jù)工作分解結(jié)構(gòu)(Work Breakdown Structure，簡(jiǎn)稱WBS)原理[15]，該航空裝備分系統(tǒng)的維修保障流程可以分成三個(gè)階段。由于飛機(jī)的型號(hào)不同，充氮工作的工序稍有區(qū)別，充氮設(shè)備有限，需要維修保障的管理人員針對(duì)不同狀態(tài)采取決策，決定本階段對(duì)某一飛機(jī)型號(hào)進(jìn)行檢修。針對(duì)該問(wèn)題，構(gòu)造其保障流程MDP-GERT網(wǎng)絡(luò)模型如圖5所示，使用德?tīng)柗品?，依?jù)相關(guān)經(jīng)驗(yàn)和歷史數(shù)據(jù)，已知相關(guān)活動(dòng)參數(shù)如表1所示。

圖5 三機(jī)戰(zhàn)時(shí)充氮保障作業(yè)MDP-GERT網(wǎng)絡(luò)模型Fig.5 MDP-GERT network model for nitrogen filling support operation of three aircrafts in wartime

表1 三機(jī)戰(zhàn)時(shí)充氮保障作業(yè)各活動(dòng)參數(shù)Table 1 Activity parameters of nitrogen filling support operation of three aircrafts in wartime

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

表2 部分策略下三機(jī)戰(zhàn)時(shí)充氮保障作業(yè)總報(bào)酬值Table 2 Total rewards of nitrogen filling guarantee operation in three aircrafts under part of the policy

全部計(jì)算結(jié)果表明當(dāng)采取策略5，即π={a3,a5,a8}的決策序列為最優(yōu)策略。在策略5下對(duì)原網(wǎng)絡(luò)進(jìn)行化簡(jiǎn)，化簡(jiǎn)后網(wǎng)絡(luò)如圖6所示。

圖6 最優(yōu)策略下化簡(jiǎn)的保障作業(yè)MDP-GERT網(wǎng)絡(luò)模型Fig.6 Simplified MDP-GERT network model of guarantee job under the optimal strategy

網(wǎng)絡(luò)模型進(jìn)行蒙特卡羅仿真模擬如圖7所示，試驗(yàn)次數(shù)設(shè)置為20 000次，當(dāng)作業(yè)排序π={a3,a5,a8}時(shí)得到三機(jī)戰(zhàn)時(shí)充氮保障作業(yè)最優(yōu)維修時(shí)間期望為16.18 min，利用一般的GERT網(wǎng)絡(luò)對(duì)未經(jīng)優(yōu)化的充氮保障作業(yè)流程進(jìn)行維修時(shí)間估計(jì)，得到維修時(shí)間期望為22.04 min，優(yōu)化后保障時(shí)間較未優(yōu)化時(shí)縮短了26.59%。

圖7 優(yōu)化前后的三機(jī)戰(zhàn)時(shí)充氮保障作業(yè)時(shí)間Fig.7 Operation time of nitrogen filling guarantee before and after optimization of three aircrafts in wartime

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

圖8 充氮保障作業(yè)時(shí)間敏感性分析結(jié)果Fig.8 Sensitivity analysis of nitrogen filling operation time

圖9 充氮保障作業(yè)時(shí)間相關(guān)性分析矩陣Fig.9 Correlation analysis of operation time of nitrogen filling guarantee

4 結(jié) 論

(1) 本文建立了一種新的航空裝備維修保障流程優(yōu)化模型。通過(guò)結(jié)合GERT網(wǎng)絡(luò)技術(shù)和馬爾科夫決策過(guò)程，解決保障流程中的工序優(yōu)化問(wèn)題。MDP-GERT技術(shù)可以很好地刻畫(huà)任務(wù)時(shí)間分布和任務(wù)邏輯關(guān)系，從而更加準(zhǔn)確地估計(jì)保障流程時(shí)間，實(shí)現(xiàn)工序的進(jìn)一步優(yōu)化。

(2) 在GERT網(wǎng)絡(luò)中加入決策點(diǎn)，使維修保障決策對(duì)作業(yè)時(shí)間的影響可以充分體現(xiàn)。利用蒙特卡羅仿真求解出在最優(yōu)裝備維修保障策略的流程時(shí)間，有效避免了GERT網(wǎng)絡(luò)存在的難以表達(dá)和分析復(fù)雜流程的問(wèn)題，為類似問(wèn)題的求解提供了一種值得參考的方法。