改進的分層邊際算法優(yōu)化備件的初始配置方案

阮旻智，李慶民，，李承，黃傲林

(1.海軍工程大學 科研部，湖北 武漢430033;2.海軍工程大學 兵器工程系，湖北 武漢430033;3.海軍工程大學 導航工程系，湖北 武漢430033)

0 引言

備件是裝備維護檢修和應急處理的保障性物資，是影響裝備戰(zhàn)備完好性及其作戰(zhàn)能力的重要因素。初始備件是裝備形成戰(zhàn)斗力的初始保障期內(nèi)裝備使用與維修所需要的備件，在裝備列裝服役初期，由承制方同步交付部隊，在采購裝備的同時，軍方需要與承制方協(xié)商來確定初始備件的種類和數(shù)量，即所謂的裝備初始配置問題［1］。因此，合理規(guī)劃備件的初始配置方案是降低裝備壽命費用、提高保障效能的有效途徑。對于故障率高、消耗量(報廢率)低、價格昂貴的修復性備件，多級維修供應是一種較為科學的備件管理模式。但多級保障模式下的備件配置優(yōu)化是大規(guī)模、非線性的NP 難問題［2］，模型求解需要在多站點、多層次、多系統(tǒng)等問題之間進行協(xié)同規(guī)劃，因此，尋求合理的優(yōu)化算法是關鍵。文獻［3］運用相關回歸技術尋求備件的最優(yōu)配置;文獻［4］引入拉格朗日乘子對模型進行分解，采用啟發(fā)式算法求解備件的訂購策略。目前，邊際優(yōu)化算法［5］是求解該類問題最為常見的一種方法，該方法是一種漸進的優(yōu)化技術，用于分配短缺資源來獲得最大效益。近些年，隨著計算機及人工智能技術的發(fā)展，如仿真優(yōu)化方法［6］、啟發(fā)式算法［7］、BP 神經(jīng)網(wǎng)絡［8］、遺傳算法［9］、粒子群算法［10］等也曾先后被應用于備件模型的求解。

相比而言，啟發(fā)式算法能夠在較短時間內(nèi)得到備件方案的最優(yōu)結果，通常被用于計算備件的訂購方案;仿真方法可以在設計上考慮各項隨機因素，其結果可信度較高，被廣泛應用于備件方案的評估與驗證，如瑞典開發(fā)的SIMLOX 軟件就是基于離散事件的仿真系統(tǒng)，采用蒙特卡洛方法對備件方案進行評估;遺傳、粒子群等進化算法優(yōu)化速度快、效率相對較高，但該算法缺乏備件方案的費效全過程分析能力;邊際優(yōu)化算法操作簡單、結果精度高，其最大優(yōu)勢在于算法迭代的整個過程中不丟失最優(yōu)解［11］，能夠得到方案的最優(yōu)費效曲線。瑞典開發(fā)的OPUS10、美國開發(fā)的VMETRIC 等備件優(yōu)化系統(tǒng)，都將邊際優(yōu)化算法作為核心算法，但該算法的突出問題是優(yōu)化效率低。

本文針對多級維修供應模式下，針對多層次結構的串聯(lián)系統(tǒng)，在傳統(tǒng)邊際算法的基礎上，提出一種改進的分層邊際優(yōu)化算法對初始備件配置進行優(yōu)化。

1 備件初始庫存配置模型

1.1 備件需求率預測

設m=1，2，…，M 為保障站點編號，j =1，2，…，J 為備件項目編號，則備件j 在站點m 的需求率λmj由兩部分構成［12］:

1)站點m 所保障的所有下一級別站點l(l∈Unit(m))對故障件j 不能維修的數(shù)量之和;這些不能維修的故障件需要送到站點m 進行維修。

2)站點m 對故障件j 的母體l(l∈Aub(j))進行維修時，其發(fā)生對備件j 的需求次數(shù)。

式中:NRTSmj為站點m 不能對故障件j 進行修復的比例;qmlj為故障隔離率，即故障件l 在站點m 進行維修時，發(fā)生對l 的分組件j 的需求占故障件l 維修次數(shù)的比例。

備件需求率可根據(jù)(1)式進行遞推，遞推的開始是從使用現(xiàn)場的LRU 進行，可根據(jù)裝備配置量、系統(tǒng)結構、站點維修條件等參數(shù)確定，則LRUj在使用現(xiàn)場的年平均需求率

式中:m∈Echelon(N);j∈Inden(1);DCj為占空比;RIPj為原位維修率;HWm為裝備的平均周工作時間(h);Zj為部件j 的單機安裝數(shù);Nm為裝備配置量;MTBFj為組件j 的平均故障間隔時間;RtOKj為重測完好率。

1.2 備件供應渠道模型

備件供應渠道決定了備件短缺數(shù)的大?。?3］，而備件短缺數(shù)將直接影響裝備可用度和維修供應效能，因此確定備件供應渠道均值與方差是備件庫存配置優(yōu)化建模的核心。

1)故障件的在修數(shù)量:λmj(1 -NRTSmj)tmj，tmj為故障件j 的平均修復時間;

3)正在進行補給中的備件數(shù)量:λmjNRTSmjOmj，Omj為站點m 向上級申請備件的延誤時間;

4)補給延誤的備件數(shù)量:fmjEBOSUP(m)，j，fmj為影響站點m 的短缺占備件短缺總數(shù)的比例。

備件供應渠道由上述4 部分構成，則站點m 的第j 項備件供應渠道均值為

式中:SUP(m)表示直接對m 進行備件供應的上級保障站點;Sub(j)表示j 的分組件集合。

當站點m 向上級n(n∈SUP(m))申領備件時，上級出現(xiàn)備件短缺所造成對m 補給延誤概率服從二項分布［14］。因此，根據(jù)(5)式可得出備件供應渠道方差為

式中:EBOmj為備件期望短缺數(shù);VBOmj為備件短缺數(shù)方差，可通過(5)式和(6)式計算得到的E［Xmj］和Var［Xmj］確定。當差均比Var［Xmj］/E［Xmj］=1時，備件供應渠道概率分布函數(shù)p(Xmj)用泊松分布計算;當Var［Xmj］/E［Xmj］＞1 時，用負二項分布近似計算［15］。當Var［Xmj］/E［Xmj］＜1 時，用二項分布對p(Xmj)作近似估計。

2 基于可用度的備件配置優(yōu)化

裝備可用度是衡量備件維修供應效能的重要指標，是指任意時刻，裝備處于可工作或可使用狀態(tài)的程度，使用站點m 的所有Nm個裝備的期望可用度為

而整個保障體系的所有裝備平均可用度為

備件初始配置優(yōu)化是在保證裝備可用度指標的前提下，使整個保障體系的備件費用最低。所建優(yōu)化模型如下:

式中Cj表示第j 項備件的單價。對(7)式等號兩端取對數(shù)，可將系統(tǒng)可用度指標轉化為備件短缺數(shù)之和來近似處理，即

采用傳統(tǒng)邊際優(yōu)化算法進行求解時，首先，初始化備件庫存量，計算每一輪迭代過程中的邊際效應值

3 邊際優(yōu)化算法性能分析

邊際優(yōu)化算法在迭代過程中的最優(yōu)費效曲線如圖1所示，若設定指標A0=0.9，則曲線上所對應的大于A0的下一個點s*即為最優(yōu)庫存點，根據(jù)費效曲線，能夠便于決策人員對設定指標和庫存結果進行分析和調(diào)整。

圖1 邊際優(yōu)化算法的最優(yōu)費效曲線Fig.1 The optimal curve of availability vs cost for marginal algorithm

該算法的不足之處主要體現(xiàn)在算法的搜索效率方面。如，設保障體系中的站點數(shù)量為m，裝備系統(tǒng)中的備件類型數(shù)量為n，模型決策變量輸出結果為一個關于各站點備件庫存量集合的m ×n 矩陣

式中sij表示第i 個站點的第j 項備件配置量。首先進行變量初始化，令sm×n=［0］，分別對sm×n中的每一個元素加1，并計算其所對應的邊際效應值δ(sij)(i∈［1，m］，j∈［1，n］).將最大值maxδ(sij)所對應的sij加1.確定下一個優(yōu)化點時需要在當前變量矩陣sm×n的基礎上進行分析，直到滿足設定的指標為止。每確定一個最優(yōu)點時，算法需要迭代次數(shù)為m·n，如果矩陣中的備件庫存量之和sum(sm×n)=s，則算法在整個優(yōu)化計算過程中需要迭代的次數(shù)為m·n·s.

4 改進的分層邊際優(yōu)化算法

4.1 優(yōu)化算法設計

在傳統(tǒng)邊際優(yōu)化算法的基礎上，通過引入分層的思想對算法進行改進，以提高搜索效率。改進的算法步驟為:

1)根據(jù)裝備可用度指標確定其所屬的各項LRUj初始可用度A0j;

由于裝備系統(tǒng)的可用度取決于其所屬的LRU可用度大小，對于組成上具有串聯(lián)結構的系統(tǒng)，可用度A 可表示為其所屬的各項LRUj可用度之積:

若設定系統(tǒng)可用度指標為A0，并認為各項LRU具有相同的關鍵度(模型中暫不考慮非關鍵部件)，即任何一項LRU 失效都會導致系統(tǒng)停機。根據(jù)(11)式可知:要保證A≥A0，LRUj的可用度必須至少滿足A0j≥A0.

2)采用邊際優(yōu)化算法分別對每項LRU 及其SRU 進行優(yōu)化計算;

3)進行算法迭代，在滿足每項LRUj的可用度指標A0j情況下，得到關于LRUj的若干條可用度-費用曲線;

4)計算當前每項LRUj費效曲線上點的斜率

式中:|A0j(i +1)-A0j(i)|表示曲線上相鄰點之間的可用度之差;|Cj(i +1)-Cj(i)|表示費用之差。若每項Δ0j的值近似相等并且LRUj的可用度之積滿足∏Aj≥A0，則算法結束，得到最優(yōu)備件方案;否則在當前備件方案的基礎上，繼續(xù)進行迭代計算，直到滿足指標為止。算法流程如圖2所示。

圖2 分層邊際優(yōu)化算法流程Fig.2 The optimization flow of layered marginal algorithm

4.2 優(yōu)化效率分析

證明:設第j 項LRU 及其所屬的分部數(shù)量之和為nj，保障體系內(nèi)的站點數(shù)量為m，每確定一個最優(yōu)點時需要迭代m·nj次，若方案結果中LRUj及其SRUi的數(shù)量之和為sj，則需要迭代m·nj·sj次才能使LRUj滿足指標A0j.完成系統(tǒng)的優(yōu)化計算，基于分層的邊際算法的迭代次數(shù)為

根據(jù)上述定義，系統(tǒng)中備件總數(shù)為n1+n2+…+nJ，優(yōu)化結果中所有備件庫存量之和為s1+s2+…+sJ，采用傳統(tǒng)的邊際優(yōu)化算法進行計算時，需要迭代的次數(shù)為

對于?nj，sj，并且nj≥0，sj≥0，下列不等式恒成立

對于?nj，sj不全為0 時，有N' ＜N.因此，改進的分層邊際優(yōu)化算法迭代次數(shù)要小于傳統(tǒng)邊際優(yōu)化算法，從而具有更高的運算效率，證畢。

圖3 保障體系的組織結構Fig.3 The framework and relation of support system

5 算例

由基地站點(H0)、中繼站點(R1、R2)和基層站點(J1、J2、J3)構成的三級保障體系中，其組織結構如圖3所示。裝備部署在基層站點(J1、J2、J3)，配置數(shù)量Nm分別為18，12，15.需對各站點的備件初始庫存配置量進行合理地規(guī)劃，使保障體系內(nèi)的裝備可用度指標A0≥0.95，裝備備件清單及其相關參數(shù)如表1所示。

表1 裝備備件清單及相關參數(shù)Tab.1 The spare parts’bill and the correlative parameters

根據(jù)改進的分層邊際優(yōu)化算法，可以得到關于LRU 的最優(yōu)費效變化曲線，如圖4～圖6所示。計算各項LRU 費效曲線上大于0.95 的各點所對應的斜率，選擇斜率近似相等的點并且使各項LRU 可用度之積大于等于0.95，最終得到最優(yōu)庫存點。所選擇的LRU 最優(yōu)方案點對應的可用度分別為A1=0.990 1、A2=0.980 4、A3=0.979 2.通過LRU 費效曲線合成得到裝備系統(tǒng)的費效曲線如圖7所示。

圖4 LRU1 的最優(yōu)費效變化曲線Fig.4 The optimal curves of effectiveness vs.cost for LRU1

圖5 LRU2 的最優(yōu)費效變化曲線Fig.5 The optimal curves of effectiveness vs.cost for LRU2

圖6 LRU3 的最優(yōu)費效變化曲線Fig.6 The optimal curves of effectiveness vs.cost for LRU3

最優(yōu)配置方案如表2所示，在該方案下，整個保障體系的裝備可用度A=0.950 42、備件滿足率EFR=0.665 57、保障延誤時間td=33.146 h、總費用C =337.98 萬元。

圖7 裝備系統(tǒng)的最優(yōu)費效變化曲線Fig.7 The optimal curves of effectiveness vs.cost for system

表2 備件的初始最優(yōu)配置方案Tab.2 The optimal initial configuration project of items

將3 種不同算法的計算結果和優(yōu)化時間進行比較，如表3所示，可得到各算法的特性和適用范圍如下:

1)邊際優(yōu)化算法:操作簡單、結果精度高，但優(yōu)化效率較低。因此，該算法適合于針對備件層次結構簡單、備件數(shù)量較少的優(yōu)化問題。

2)改進的分層邊際優(yōu)化算法:搜索效率高、不僅能夠得到系統(tǒng)單元級的費效曲線，通過曲線合成還能夠得到系統(tǒng)級的費效曲線，可以對各單元影響因素的敏感性進行分析，便于對方案進行調(diào)整，但該算法的程序設計上相對復雜。因此，該算法適合于針對保障組織體系龐大、備件層次結構復雜、備件數(shù)量較多的優(yōu)化問題。

3)人工免疫算法:搜索效率較高，能夠?qū)⒍嘀笜藘?yōu)化問題通過抗體親和度函數(shù)的構造而轉化為單目標優(yōu)化問題，缺點是算法穩(wěn)定性差。此外，程序設計時需要選擇合理的指標權系數(shù)和懲罰因子，否則會造成結果偏差。因此，該算法適合于針對備件層次結構復雜、數(shù)量規(guī)模大，具有多個約束目標的備件優(yōu)化問題。

表3 不同算法的計算結果及運行時間Tab.3 The calculation result and time for different algorithms

6 結論

本文針對多級保障模式下的備件配置優(yōu)化問題;提出一種改進的分層邊際優(yōu)化算法。通過算例中的數(shù)值結果可知:分層邊際優(yōu)化算法能夠在保證優(yōu)化結果完全一致的前提下，提高算法的優(yōu)化效率，以本文算例為例，分層邊際優(yōu)化算法的運行時間為196 s，相比傳統(tǒng)邊際優(yōu)化算法(870 s)，其運行時間提高了近3 倍，當系統(tǒng)中LRU 類型的數(shù)量較多時，這一優(yōu)勢更為突出。文中所提出的算法能夠為復雜保障系統(tǒng)的備件配置優(yōu)化節(jié)省大量的計算時間，工程上具有一定的實用性，為備件庫存配置的優(yōu)化方法提供一種新的思路。

文中在建立基于裝備可用度的備件優(yōu)化配置模型時，僅考慮了串聯(lián)結構系統(tǒng)，因而需要根據(jù)實際需求對該問題作進一步深入研究。

References)

［1］ 周偉，郭波，張濤.兩級供應關系裝備常用備件初始配置模型［J］.系統(tǒng)工程與電子技術，2011，33(1):89 -93.ZHOU Wei，GUO Bo，ZHANG Tao.Initial configuration model for common equipment parts based on two-class supply relationship［J］.Systems Engineering and Electronics，2011，33(1):89 -93.(in Chinese)

［2］ Sherbrooke C C.Vari-metric:improved approximations for multiindenture multi-echelon availability models［J］.Operations Research，1986，(34):311 -319.

［3］ Lee H L.A multi-echelon inventory model for repairable items with emergency lateral transshipments［J］.Management Science，1987，33(10):1302 -1316.

［4］ Al-Rifai M H，Rossetti M D.An efficient heuristic optimization algorithm for a two-echelon (R，Q)inventory system［J］.International Journal of Production Economics，2007，(109):195 -213.

［5］ 阮旻智，李慶民，彭英武，等.任意結構系統(tǒng)的備件滿足率模型及優(yōu)化方法［J］.系統(tǒng)工程與電子技術，2011，32(8):1799-1803.RUAN Min-zhi，LI Qing-min，PENG Ying-wu，et al.Model of spare parts fill rate for system of various structures and optimization method［J］.Systems Engineering and Electronics，2011，32(8):1799 -1803.(in Chinese)

［6］ Kilpi J，Toyli J，Vepsalainen A.Cooperative strategies for the availability service of repairable aircraft components［J］.International Journal of Production Economics，2009，117(2):360 -370.

［7］ Archibald T W，Black D，Glazebrook K D.An index heuristic for transshipment decisions in multi-location inventory systems based on a pairwise decomposition［J］.European Journal of Operational Research，2009，192(3):69 -78.

［8］ Wu M C，Hsu Y K.Design of BOM configuration for reducing spare parts logistic costs［J］.Expert Systems with Applications，2008，34(1):2417 -2423.

［9］ Saranga H，Kumar U D.Optimization of aircraft maintenance support infrastructure using genetic algorithms-level of repair analysis［J］.Ann Oper Res，2006，143(1):91 -106.

［10］ 阮旻智，李慶民，王紅軍，等.人工免疫粒子群算法在系統(tǒng)可靠性優(yōu)化中的應用［J］.控制理論與應用，2010，27(9):1253 -1258.RUAN Min-zhi，LI Qing-min，WANG Hong-jun，et al.Application of artificial immune particle swarm optimization algorithm to system reliability optimization［J］.Control Theory ＆ Application，2010，27(9):1253 -1258.(in Chinese)

［11］ Lee J Y，Schwarz L B.Leadtime management in a periodic-review inventory system:a state-dependent base-stock policy［J］.European Journal of Operational Research，2009，199:122 -129.

［12］ Sleptchenko A，van der Heijden M C，van Harten A.Effects of finite repair capacity in multi-echelon，multi-indenture service part supply systems［J］.International Journal of Production Economics，2002，79:209 -230.

［13］ 阮旻智，李慶民，彭英武，等.串件拼修對策下多級維修供應的裝備系統(tǒng)可用度評價［J］.航空學報，2012，33(4):658-665.RUAN Min-zhi，LI Qing-min，PENG Ying-wu，et al.Evaluation of equipment system availability for multi-echelon maintenance supply with cannibalization［J］.Acta Aeronautica et Astronautica Sinica，2012，33(4):658 -665.(in Chinese)

［14］ Sherbrooke C C.Optimal inventory modeling of system:multiechelon techniques［M］.2nd ed.Boston:Artech House，2004.

［15］ 王乃超，康銳，程海龍.基于馬爾科夫過程的備件庫存動態(tài)特性分析［J］.兵工學報，2009，30(7):984 -988.WANG Nai-chao，KANG Rui，CHENG Hai-long.Study on the dynamic characteristics of spare inventory based on Markov process［J］.Acta Armanentarii，2009，30(7):984 -988.(in Chinese)

［16］ 阮旻智，李慶民，劉天華.編隊防空火力分配建模及其優(yōu)化方法研究［J］.兵工學報，2010，31(11):1525 -1529.RUAN Min-zhi，LI Qing-min，LIU Tian-hua.Modeling and optimization on fleet antiaircraft firepower allocation［J］.Acta Armanentarii，2010，31(11):1525 -1529.(in Chinese)