基于PERT網(wǎng)絡(luò)的航空彈藥保障人員優(yōu)化配置

郭小威 馬登武 鄧 力

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

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

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

1 基于MC法的PERT網(wǎng)絡(luò)仿真

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

1.1 PERT網(wǎng)絡(luò)參數(shù)計算

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

1.1.1 工序持續(xù)時間的概率特征

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

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

仿真過程中由上述參數(shù)組成各工序持續(xù)時間的隨機數(shù)發(fā)生器.

1.1.2 按期完工概率

網(wǎng)絡(luò)計劃圖中，各節(jié)點工序完成時刻的方差具有累加性.節(jié)點j的方差即是以j為終節(jié)點的關(guān)鍵路線上各工序持續(xù)時間的方差之和，表示為

當(dāng)節(jié)點j為網(wǎng)絡(luò)圖的結(jié)束節(jié)點n時，Pn就表示整個工程按期完工概率.

1.2 基于風(fēng)險分析的關(guān)鍵指標(biāo)

在工程網(wǎng)絡(luò)計劃中進行資源優(yōu)化，往往需要考慮各工序相對重要程度以及對整個工程的影響程度.基于風(fēng)險管理原則，引用工序關(guān)鍵度指標(biāo)ACI(Activity Criticality Index)和工序重要度指標(biāo)CRI(Cruciality Index)來分析各工序產(chǎn)生的影響.

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

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

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

其數(shù)值可由以下各式求得

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

2 保障人員優(yōu)化配置建模

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

2.1 問題分析

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

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

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

4)保障人員總數(shù)確定.

保障人員的優(yōu)化配置即是在滿足優(yōu)化指標(biāo)的情況下合理配置第2部分的保障人員.

2.2 優(yōu)化配置模型

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

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

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

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

CRI反應(yīng)了工序?qū)θ蝿?wù)工期的風(fēng)險影響，為保證任務(wù)不受某些工序的較大影響，須使得各工序的CRI盡量均衡集中，同樣用標(biāo)準(zhǔn)差表示CRI的離散度:

v值越小，表示工序CRI分布越集中，出現(xiàn)高風(fēng)險工序的可能性越低.

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

2.3 工序均值和方差的確定

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

2.4 基于遺傳算法的方案尋優(yōu)

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

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

式中Cp是個極小值.

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

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

5)變異操作.在每個“基因”上下限范圍內(nèi)產(chǎn)生隨機整數(shù)，取代原數(shù)值.

2.5 MC法仿真次數(shù)的確定

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

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

具體由Chebyshev不等式表示為

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

2.6 算法流程

以遺傳算法為優(yōu)選框架，基于Monte Carlo仿真方法的PERT網(wǎng)絡(luò)求得優(yōu)選指標(biāo)，以此求解最優(yōu)的航空彈藥保障人員配置方案的流程如圖1所示.

圖1 算法流程圖

3 算例分析

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

圖2 PERT網(wǎng)絡(luò)及工序參數(shù)表示

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

最終得到的最優(yōu)方案及供需相關(guān)參數(shù)如表1所示，此方案的平均任務(wù)按期完工概率為99.61%.

圖3 目標(biāo)函數(shù)進化曲線

表1 優(yōu)選配置方案工序參數(shù)

4 結(jié)論

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

References)

［1］馬登武，郭小威，鄧力.基于改進蟻群算法的艦載機彈藥調(diào)度［J］.系統(tǒng)仿真學(xué)報，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］馬登武，郭小威，呂曉峰.基于網(wǎng)絡(luò)計劃技術(shù)的艦載機航空導(dǎo)彈轉(zhuǎn)運流程［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行為時間參數(shù)近似計算公式選優(yōu)［J］.合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，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網(wǎng)絡(luò)關(guān)鍵路線和最關(guān)鍵活動分析［J］.系統(tǒng)工程與電子技術(shù)，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］唐建，嚴(yán)駿，凌海風(fēng)，等.基于隨機PERT網(wǎng)絡(luò)Monte-Carlo仿真的任務(wù)可靠性分析［J］.計算機應(yīng)用研究，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，F(xiàn)atemi 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］李學(xué)京.置信分布的貝塔分布近似及其在可靠性統(tǒng)計中的應(yīng)用［J］.強度與環(huán)境，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］盛驟，謝式千，潘承毅.概率論與數(shù)理統(tǒng)計［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)