基于PERT網絡的航空彈藥保障人員優化配置

郭小威 馬登武 鄧 力

(海軍航空工程學院 兵器科學與技術系，煙臺264001)

艦載航空彈藥的保障工作主要由保障調度系統完成，各戰位呈立體式分布且銜接緊密，保障工作實施難度大，高效、快速、可靠的彈藥保障對艦載機的快速出動及再次出動能力影響重大.為此合理設計保障方案，并對相應的保障資源進行分配整合與優化十分必要［1－2］，為提高航空彈藥保障的可靠性，在確定保障體系的情況下對保障人員進行合理優化配置的研究工作也勢在必行.

在考慮任務風險、按期完工率和資源均衡等主要影響因素時，應用計劃評審技術(PERT，Program Evaluation and Review Technique)對邏輯關系確定的保障流程進行分析較為適當.傳統PERT網絡分析方法以工作流程為基礎，用各工序的期望持續時間和方差估計任務的完工概率［3－5］.以此為基礎眾多學者開展了關鍵路線和工序重要度及敏感性的研究工作［6－8］，大量仿真分析隨計算機技術的發展也得以實現.蒙特卡羅(MC，Monte Carlo)方法引入到PERT網絡的分析中，通過對PERT網絡中關鍵路線/關鍵活動對任務工期的敏感性等的分析［9－12］，可以抓住重點對資源配置和工作進度進行有效控制［13－15］.而當前PERT網絡在資源優化方面的分析多注重于有限資源下的工序按時開展與否，鮮少涉及通用資源的調整配置.鑒于此，本文通過分析每個保障人員配置方案中各工序對任務工期的影響程度，選取配置方案評價指標，進而優選出有限保障人員的配置方案.

1 基于MC法的PERT網絡仿真

建立在MC法基礎上的PERT網絡仿真，其基本思想是由計算機模擬實際的工作實施概率過程，隨機產生服從指定分布的工作時間，每一次仿真過程都產生一次各項工序的隨機持續時間，各次過程下的工期和關鍵路線都可能不相同.經過多次的仿真統計分析，得到所需的各項工作指標數據，以此做出合理決策提高計劃實施的可靠性.

1.1 PERT網絡參數計算

PERT網絡基于由n個節點組成的雙代號網絡圖，(i－j)表示各項工序.

1.1.1 工序持續時間的概率特征

PERT網絡中各項工序持續時間假設服從β分布，這也為多數文獻所接受［16］.根據經典PERT的基本假設，在已知工序時間的最樂觀值a、最可能值m和最悲觀值b，采用式(1)確定工序持續時間的期望值μ和方差σ2:

β分布的形狀參數值γ和η由式(2)得出

仿真過程中由上述參數組成各工序持續時間的隨機數發生器.

1.1.2 按期完工概率

網絡計劃圖中，各節點工序完成時刻的方差具有累加性.節點j的方差即是以j為終節點的關鍵路線上各工序持續時間的方差之和，表示為

當節點j為網絡圖的結束節點n時，Pn就表示整個工程按期完工概率.

1.2 基于風險分析的關鍵指標

在工程網絡計劃中進行資源優化，往往需要考慮各工序相對重要程度以及對整個工程的影響程度.基于風險管理原則，引用工序關鍵度指標ACI(Activity Criticality Index)和工序重要度指標CRI(Cruciality Index)來分析各工序產生的影響.

關鍵路線上的關鍵工序直接決定了項目的完工期，而在PERT進度計劃中，各工序持續時間的不確定性使得仿真過程中關鍵路線可能不唯一.最可能組成關鍵路線的各項工序就應予以重視.則工序的關鍵度指標定義為

式中mij為工序(i，j)在N次仿真中成為關鍵工序的次數，顯然 p(i，j)∈［0，1］.

在進度計劃中某工序的關鍵度大并不意味著該工序的風險量較大，也并不意味著整個工程項目不能完工的風險就大.因此，資源優化中除了需要考慮某工序成為關鍵工序的關鍵度外，還需要考慮其一旦發生意外時對整個工程項目進度的影響和進度的損失.可通過估計工作持續時間對項目工期的敏感度影響來評價，采用Williams提出的重要度指標CRI來表示，即

其數值可由以下各式求得

式中，Dij和分別為工序(i，j)的持續時間和第k次仿真時的持續時間;T和T(k)分別為工程總工期和第k次仿真時的總工期;E(Dij)和σ(Dij)分別為工序(i，j)的持續時間在N次仿真后的期望值和標準差;E(T)和σ(T)分別為N次仿真后工程總工期的期望值和標準差;Cov(Dij，T)和 Corr(Dij，T)分別為工序 (i，j)持續時間與總工期的協方差和線性相關系數.

2 保障人員優化配置建模

航空彈藥保障具有批次量大、完成可靠性要求高的特點，要求合理配置所屬保障人員以求保障效率最高.

2.1 問題分析

1)假設所配置的保障人員都能勝任所指定崗位的工作，亦即是保障工序持續時間參數只與保障人員數量有關.

2)整個保障流程的工序分為2部分:第1部分為基本由設施設備完成的工序，其持續時間的均值和方差固定;第2部分主要由保障人員完成，持續時間不確定，并且與保障人員數量有關.

3)第2部分各工序保障人員數量存在下限以保證工作的順利完成，理論上講人員數量越多工序持續時間越短，但由于組織協調、空間場地等的限制，工序持續時間只在一定范圍內隨人員數量變換，即需要設定各工序保障人員數量上限.

4)保障人員總數確定.

保障人員的優化配置即是在滿足優化指標的情況下合理配置第2部分的保障人員.

2.2 優化配置模型

保障流程的PERT網絡共計n個節點，共計na個工序，其中第2部分工序數量為nt，其保障人員數量的上下限標記為和某次人員配置方案為，則有…，nt)，并且要保證其第2部分保障人員數量總數一定，即為設定常數.在此方案下所有工序持續時間的期望值和方差分別為Dij(i，j∈{1，2，…，n})和 σij(i，j∈ {1，2，…，n})，第 1部分工序持續時間固定，而第2部分工序持續時間的期望值和方差則由保障人員的具體數量而定.

保障人員配置方案確定的情況下，亦即是各工序持續時間的期望值和方差得到確定，以此對PERT網絡進行Monte Carlo仿真實驗，以獲取工程計劃的所需數據.仿真次數設定為N，在計劃工期Tp下第k次仿真獲得的保障工作按期完工概率為，該方案下的工作按期完工概率取各次仿真結果的均值:

顯然Pn越大保障工作按期完成的可能性越大，即是此配置方案更優.

另外，為使得整個保障工作中各工序實施緊湊，須保證各工序的總時差最小，也就是到達最終節點的各條路線的時長相差最小.反映在仿真過程中，就是每條路線都可能成為關鍵路線，即由式(6)計算得到的各工序關鍵度指標p(i，j)分布均衡，這里用標準差表示各工序關鍵度指標的離散度:

CRI反應了工序對任務工期的風險影響，為保證任務不受某些工序的較大影響，須使得各工序的CRI盡量均衡集中，同樣用標準差表示CRI的離散度:

v值越小，表示工序CRI分布越集中，出現高風險工序的可能性越低.

根據式(14)～式(16)對保障人員配置方案優劣的影響，評價配置方案的函數表示為

2.3 工序均值和方差的確定

第2部分工序持續時間參數隨保障人員的數量而變化，在其上下限范圍內為便于計算，可認為其方差保持不變，期望值以工序保障人員數量上限為基礎，按以下公式計算:

2.4 基于遺傳算法的方案尋優

1)編碼方案.遺傳算法染色體采用實值編碼方式.染色體共計nt個“基因”，順次每個“基因”表示第2部分工序的保障人員數量，其數值大小在上下限范圍之內.

2)適應度評估.尋求最優的保障人員配置方案即是解決目標函數(式(17))的最大化問題，又知f(R)＞0，則當∑R=NI時適應度函數可直接設為Fit［f(R)］=f(R)，否則采用懲罰策略降低該染色體的適應度值.

式中Cp是個極小值.

3)選擇操作.根據每個染色體的適應度值大小采用輪盤賭選擇策略實施.

4)交叉操作.采取兩點交叉方式進行.

5)變異操作.在每個“基因”上下限范圍內產生隨機整數，取代原數值.

2.5 MC法仿真次數的確定

現代計算機性能的提高，也為大規模數據仿真的實現提供了可能，但由于每個配置方案都需要進行一次仿真，為實現算法的快速性有必要確定每次的仿真次數N.保障工作持續時間T服從分布，可由 1.1 節求得.為保證平均按期完工概率Pn真實反映保障工作持續時間，須使得N次仿真的均值趨近于其分布的期望值 μn，可表示為

由辛欽大數定理可知［17］，對任意的 ε ＞0，有

具體由Chebyshev不等式表示為

通過式(24)即可確定單個方案的仿真次數.

2.6 算法流程

以遺傳算法為優選框架，基于Monte Carlo仿真方法的PERT網絡求得優選指標，以此求解最優的航空彈藥保障人員配置方案的流程如圖1所示.

圖1 算法流程圖

3 算例分析

某次航空彈藥保障任務的網絡計劃圖如圖2所示，其中虛箭線表示虛工序.工序箭線下方為工序保障人員數量上下限，上方為人員上限時的時間參數(單位為同一量綱)，Tp=550，保障人員總數100，可知第2部分工序保障人員數量NI=59.用各工序人員數量上限時的時間參數來估計Monte Carlo方法的仿真次數，此時的任務工期的均值與方差分別為 ˉμn=509.58 和 ˉσ2n=75.0 ，在參數 Pb=99.5% 和 ε′=1% 時 N≥577.7，這里取N=1000.

圖2 PERT網絡及工序參數表示

遺傳算法參數設置為:進化代數100，染色體個數40，交叉概率 0.8，變異概率 0.1.權重系數ω =［0.6 0.2 0.2］時，以式(17)為目標函數采用所提出算法進行配置方案優選，進化曲線如圖3所示，圖中達到最優值時產生的微小波動由Monte Carlo仿真的隨機性產生.

最終得到的最優方案及供需相關參數如表1所示，此方案的平均任務按期完工概率為99.61%.

圖3 目標函數進化曲線

表1 優選配置方案工序參數

4 結論

航空彈藥保障任務是一個復雜的系統工程，不僅要求按時按量高標準完成，又受到保障資源很大的制約，且任務工序充滿著不確定性.合理科學地配置保障資源及控制計劃進度直接影響到戰機作戰效率的高低.本文基于保障流程的不確定性，以PERT網絡仿真為基礎，在保證任務按期完工率的同時兼顧工期風險評價指標ACI和CRI，建立了人員配置方案尋優模型，對保障人員進行優化配置.有效保證保障工作的效率和均衡，以使彈藥保障工作的高效穩定開展.以此為基礎可進一步研究航空彈藥多批次保障的資源優化問題.

References)

［1］馬登武，郭小威，鄧力.基于改進蟻群算法的艦載機彈藥調度［J］.系統仿真學報，2012，24(6):1207 －1211 Ma Dengwu，Guo Xiaowei，Deng Li.Ammunition scheduling of carrier-based aircraft based on modified ant colony algorithm［J］.Journal of System Simulation，2012，24(6):1207 － 1211(in Chinese)

［2］馬登武，郭小威，呂曉峰.基于網絡計劃技術的艦載機航空導彈轉運流程［J］.兵工自動化，2010，29(9):48 －51 Ma Dengwu，Guo Xiaowei，Lü Xiaofeng.Airborne missile transport process of carrier-based aircraft based on network planning techniques［J］.Ordnance Industry Automation，2010，29(9):48－51(in Chinese)

［3］José Manuel Herrerías-Velasco，Rafael Herrerías-Pleguezuelo，Johan René van Dorp.Revisiting the PERT mean and variance［J］.European Journal of Operational Research，2011，210:448－451

［4］Castroa J，Gómeza D，Tejada J.A polynomial rule for the problem of sharing delay costs in PERT networks［J］.Computers ＆ Operations Research，2008，35:2376 －2387

［5］Premachandra I M.An approximation of the activity duration distribution in PERT［J］.Computers ＆ Operations Research，2001，28:443－452

［6］段建中，李民奎.PERT行為時間參數近似計算公式選優［J］.合肥工業大學學報:自然科學版，2001，24(3):365－369 Duan Jianzhong，Li Minkui.Optimizing estimation of PERT activity time parameters［J］.Journal of Hefei University of Technology:Natural Science，2001，24(3):365 －369(in Chinese)

［7］Fatemi G S M T，Teimouri E.Path critical index and activity critical index in PERT networks［J］.European Journal of Operational Research，2002，141(2):147 －152

［8］Cho J G，Yum B J.Functional estimation of activity criticality indices and sensitivity analysis of expected project completion time［J］.Journal of Operational Research Society，2004，55(8):850－859

［9］王卓甫，丁繼勇，劉媛，等.基于Monte Carlo方法的PERT網絡關鍵路線和最關鍵活動分析［J］.系統工程與電子技術，2012，34(8):1646 －1651 Wang Zhuofu，Ding Jiyong，Liu Yuan，et al.Analysis of critical path and most critical activity in PERT networks based on Monte Carlo method［J］.Systems Engineering and Electronics，2012，34(8):1646－1651(in Chinese)

［10］唐建，嚴駿，凌海風，等.基于隨機PERT網絡Monte-Carlo仿真的任務可靠性分析［J］.計算機應用研究，2012，29(8):2948－2951 Tang Jian，Yan Jun，Ling Haifeng，et al.Mission reliability analysis based on Monte-Carlo simulation of stochastic PERT network［J］.Application Research of Computers，2012，29(8):2948－2951(in Chinese)

［11］Baradaran S，Fatemi Ghomi S M T，Mobini M，et al.A hybrid scatter search approach for resource-constrained project scheduling problem in PERT-type networks［J］.Advances in Engineering Software，2010，41:966 －975

［12］Bowman R A.Efficient sensitivity analysis of PERT network performance measures to significant changes in activity time parameters［J］.Journal of Operational Research Society，2007，58(10):1354－1360

［13］Azaron A，Perkgoz C，Sakawa M.A genetic algorithm approach for the time-cost trade-off in PERT networks［J］.Applied Mathematics and Computation，2005，168:1317 －1339

［14］Azaron A，Tavakkoli-Moghaddam R.A multi-objective resource allocation problem in dynamic PERT networks［J］.Applied Mathematics and Computation，2006，181:163 －174

［15］Kong Xiangxing，Zhang Xuan，Hou Zhenting.Markov skeleton process in pert networks［J］.Acta Mathematica Scientia，2010，30B(5):1440 －1448

［16］李學京.置信分布的貝塔分布近似及其在可靠性統計中的應用［J］.強度與環境，2007，34(2):17－23 Li Xuejing.Beta distribution approximation of confidence distributions and application in reliability statistics［J］.Structure ＆Environment Engineering，2007，34(2):17 －23(in Chinese)

［17］盛驟，謝式千，潘承毅.概率論與數理統計［M］.4版.北京:高等教育出版社，2008:119－126 Sheng Zhou，Xie Shiqian，Pan Chengyi.Probability theory ＆mathematical statistics［M］.4th ed.Beijing:Higher Education Press，2008:119 －126(in Chinese)