李軍亮 滕克難 衣冠琛 劉國(guó)桓

(1.海軍航空工程學(xué)院 煙臺(tái) 264001)(2.92514部隊(duì) 煙臺(tái) 264007)

基于蟻群算法的艦載直升機(jī)維修資源優(yōu)化調(diào)度研究*

李軍亮1滕克難1衣冠琛1劉國(guó)桓2

(1.海軍航空工程學(xué)院 煙臺(tái) 264001)(2.92514部隊(duì) 煙臺(tái) 264007)

針對(duì)艦載直升機(jī)遠(yuǎn)航時(shí)駐艦周期長(zhǎng)、維修任務(wù)時(shí)間緊、資源有限的特殊性，合理構(gòu)建艦載直升機(jī)駐艦維修模型，建立艦載直升機(jī)駐艦維修資源優(yōu)化調(diào)度模型，采用改進(jìn)蟻群算法進(jìn)行仿真計(jì)算，通過(guò)計(jì)算驗(yàn)證表明：該算法較好的解決維修過(guò)程中出現(xiàn)的資源沖突問(wèn)題，縮短艦載直升機(jī)維修工期。

艦載直升機(jī); 維修保障; 資源調(diào)度; 蟻群算法

Class Number V241

1 引言

隨著藍(lán)色海軍戰(zhàn)略轉(zhuǎn)型的不斷深入，海軍執(zhí)行遠(yuǎn)洋任務(wù)日益頻繁，艦載直升機(jī)能夠擔(dān)負(fù)偵察、搜救、運(yùn)輸、反潛等多種使命，其作用更加突出。但艦載直升機(jī)的使用仍受到多方面因素制約，一方面由于目前艦載直升機(jī)駐艦保障仍然沿用岸基“基層級(jí)”、“中繼級(jí)”和“基地級(jí)”的三級(jí)保障體制，艦船空間有限不能攜帶較多的航材備件，維修資源相對(duì)受限；另外遠(yuǎn)航時(shí)艦載直升機(jī)駐艦周期長(zhǎng)、氣候環(huán)境惡劣，執(zhí)行任務(wù)具有突發(fā)性和應(yīng)急性，裝備故障率高且故障出現(xiàn)時(shí)間具有不確定性[1]。那么如何通過(guò)對(duì)維修資的源優(yōu)化調(diào)度來(lái)解決維修保障過(guò)程中出現(xiàn)的維修保障資源分配不均、計(jì)劃不周、預(yù)測(cè)不準(zhǔn)等問(wèn)題，充分利用現(xiàn)有維修資源，縮短待修直升機(jī)維修周期，提高維修資源利用率，在短時(shí)間內(nèi)恢復(fù)戰(zhàn)斗力，最大限度地保證直升機(jī)完好率，順利執(zhí)行各項(xiàng)任務(wù)已經(jīng)成為機(jī)務(wù)維修人員亟待解決的重大課題。

資源受限項(xiàng)目調(diào)度問(wèn)題(resource-constrained project scheduling problem,RCPSP)，要求在滿足項(xiàng)目任務(wù)的緊前關(guān)系和資源約束的條件下，優(yōu)化項(xiàng)目的進(jìn)度安排，從而優(yōu)化最小項(xiàng)目目標(biāo)函數(shù)。RCPSP算法主要分兩種：精確算法和啟發(fā)式算法。精確算法包括整數(shù)規(guī)劃、分支界定法、動(dòng)態(tài)規(guī)劃法等。由于RCPSP是NP-hard問(wèn)題，對(duì)于較復(fù)雜的項(xiàng)目，在可以接受的時(shí)間范圍內(nèi)，精確算法難以得到最優(yōu)解。相對(duì)而言啟發(fā)式算法不能保證得到最優(yōu)解，但能夠較快地找到較好解。各類啟發(fā)式算法是近年來(lái)的研究熱點(diǎn)，目前的研究主要集中于遺傳算法、模擬退火、禁忌搜索以及蟻群算法[2～3]。筆者根據(jù)艦載直升機(jī)有限資源維修問(wèn)題的特殊性，采取蟻群算法進(jìn)行優(yōu)化實(shí)現(xiàn)，基于復(fù)雜的參數(shù)設(shè)置，得到較好的結(jié)果。

2 艦載直升機(jī)駐艦保障維修資源分析

艦載直升機(jī)維修資源是指與艦載直升機(jī)維修直接關(guān)聯(lián)的維修經(jīng)費(fèi)、維修物資器材、維修設(shè)施設(shè)備、維修人才、維修信息以及維修管理等有形和無(wú)形的資源[4]。而在實(shí)際工作中只考慮以實(shí)物形式存在的艦載直升機(jī)維修資源，即維修物資器材、維修設(shè)施設(shè)備和維修人才。

根據(jù)實(shí)際工作情況，艦載直升機(jī)的駐艦維修是由隨艦保障的地勤人員來(lái)完成，維修工作按照機(jī)械、特設(shè)、電子、軍械和聲納五個(gè)專業(yè)進(jìn)行劃分，如果多專業(yè)同時(shí)進(jìn)行項(xiàng)目維修，就可能會(huì)產(chǎn)生資源沖突，每個(gè)維修項(xiàng)目的工作進(jìn)度都會(huì)受到影響，就容易造成整體維修工期拖后的現(xiàn)象，要合理解決資源沖突，有效利用關(guān)鍵資源，有序分散的并行進(jìn)行維修項(xiàng)目，保證多項(xiàng)目、多工序交叉進(jìn)行和推進(jìn)，就勢(shì)必要對(duì)維修資源進(jìn)行優(yōu)化調(diào)度。

多專業(yè)多項(xiàng)目維修工作并行開(kāi)展時(shí)要考慮維修任務(wù)中維修項(xiàng)目所需的資源配置，再根據(jù)各個(gè)專業(yè)的分工職能，對(duì)所屬專業(yè)項(xiàng)目的維修資源進(jìn)行調(diào)配。直升機(jī)維修工作是一個(gè)復(fù)雜的系統(tǒng)工程，各專業(yè)并行作業(yè)時(shí)存在制約和關(guān)聯(lián)，各專業(yè)內(nèi)部工序可在滿足緊前約束的前提下串聯(lián)進(jìn)行。文獻(xiàn)[5]在資源受限模型建模時(shí)引進(jìn)維修單元重要度的概念來(lái)確定工序前后順序的優(yōu)先策略。具體表現(xiàn)為實(shí)際維修工作中維修項(xiàng)目的重要性和蟻群算法中信息素的揮發(fā)系數(shù)聯(lián)系起來(lái)，即維修項(xiàng)目重要度和信息素?fù)]發(fā)系數(shù)成反比關(guān)系，這樣的計(jì)算結(jié)果更貼近實(shí)際維修工作。

筆者結(jié)合目前艦載直升機(jī)駐艦保障的實(shí)際情況，對(duì)在艦面可完成的實(shí)際維修項(xiàng)目進(jìn)行編碼，規(guī)則如下：

按照目前的維修方式將直升機(jī)維修工作劃分為機(jī)械專業(yè)M1，特設(shè)專業(yè)M2，軍械專業(yè)M3，電子專業(yè)M4，聲納專業(yè)M5，各專業(yè)維修項(xiàng)目按照工作順序編碼，各維修項(xiàng)目完成需要的時(shí)間用矩陣D表示。

(1)

其中，矩陣中的列分別表示專業(yè)，矩陣中的行表示專業(yè)的維修項(xiàng)目。dij表示第i個(gè)專業(yè)的第j個(gè)維修項(xiàng)目的工作時(shí)間。確定每個(gè)項(xiàng)目dij的優(yōu)先策略時(shí)，首先要滿足緊前約束，其次參考重要度函數(shù)θj，θj如式(2)所示：

(2)

3 艦載直升機(jī)維修優(yōu)化調(diào)度模型的建立

由于艦載直升機(jī)維修任務(wù)比較特殊，不僅具有較高的并發(fā)性，還有關(guān)鍵資源的制約。那么一個(gè)維修項(xiàng)目可以表示為一個(gè)節(jié)點(diǎn)式(activity-on-node,AON)有向網(wǎng)絡(luò)[6]，并存在兩類約束：一類是任務(wù)之間存在的邏輯約束，用AON網(wǎng)絡(luò)中的箭頭表示；另一類是有限資源造成的資源約束，限定同一時(shí)刻各任務(wù)對(duì)資源的需求不能超過(guò)資源的供給。假設(shè)項(xiàng)目包含j個(gè)任務(wù)，需要k種可更新資源,其中第k種資源的供給量為Rk。項(xiàng)目的第j個(gè)任務(wù)，其工期為Pj，截止日期為dj對(duì)第k種資源的需求量為rjk，其所有緊前任務(wù)的集合記為Pj，任務(wù)的開(kāi)始時(shí)間標(biāo)記為Sj，結(jié)束時(shí)間標(biāo)記為Cj，項(xiàng)目從t=0時(shí)刻開(kāi)始執(zhí)行,設(shè)定最晚完工時(shí)間為T(mén)=∑Pj；在時(shí)間t所有進(jìn)行中任務(wù)的集合標(biāo)記為It，可以用任務(wù)結(jié)束時(shí)間向量表示一個(gè)項(xiàng)目進(jìn)度計(jì)劃S=(C1,C2,…,Cj)。因此，RCPSP可以描述為

minf(s)

(3)

s.t

Sj≥Ch,?j,h∈Pj

(4)

∑j∈Itrk≤Rk,?k,t

(5)

式(3)表示項(xiàng)目的目標(biāo)函數(shù)，式(4)表示任務(wù)之間的緊前關(guān)系，式(5)表示資源約束。對(duì)于經(jīng)典RCPSP問(wèn)題，目標(biāo)是最小化項(xiàng)目總工期。

4 蟻群算法設(shè)計(jì)

蟻群算法是對(duì)螞蟻群體利用信息素進(jìn)行覓食行為的仿生，已經(jīng)被廣泛應(yīng)用于各種組合優(yōu)化問(wèn)題，以及應(yīng)用于求解RCPSP[7～8]。一般而言，蟻群算法采用進(jìn)度生成機(jī)制，通過(guò)逐步擴(kuò)展局部進(jìn)度計(jì)劃來(lái)生成一個(gè)完整可行的項(xiàng)目進(jìn)度計(jì)劃，并通過(guò)反復(fù)搜索獲得最優(yōu)解。

(6)

式中：τij為信息素信息，ηij為啟發(fā)式信息,α和β為控制兩類信息權(quán)重的參數(shù)。啟發(fā)式信息一般表示螞蟻在搜索決策中可以利用的直觀信息。在RCPSP中，一般用優(yōu)先規(guī)則來(lái)構(gòu)造啟發(fā)式信息，最常見(jiàn)的是最遲完工(late finish，LF)時(shí)間，記任務(wù)j的最遲完工時(shí)間為L(zhǎng)j，則啟發(fā)式信息可以表示為

(7)

信息素的更新是蟻群算法的重點(diǎn)，包括信息素的揮發(fā)和累積。鑒于艦載直升機(jī)維修工作的特殊性，本文將ρ的變化為與重要度函數(shù)θj成反比的函數(shù)，各條路徑信息素更新如式(8)所示：

(8)

Δτij(g)=ρ/f

(9)

式中：ρ為信息素的揮發(fā)率，f為螞蟻在完成一次完整的搜索后得到的目標(biāo)函數(shù)值。當(dāng)螞蟻k從第1個(gè)任務(wù)逐步搜索到第j個(gè)任務(wù)時(shí)，就構(gòu)成一個(gè)完整的任務(wù)列。以該任務(wù)列的順序，在滿足資源約束的前提下，按照盡早原則逐個(gè)安排所有任務(wù)的開(kāi)始時(shí)間，就得到一個(gè)可行的項(xiàng)目進(jìn)度計(jì)劃。

5 算例分析

蟻群算法是一種自適應(yīng)、正反饋、分布式的模擬優(yōu)化計(jì)算法，它在求解各復(fù)雜的組合優(yōu)化問(wèn)題上表現(xiàn)出一定優(yōu)勢(shì)，較好的α，β有較好的解質(zhì)量以及好的穩(wěn)定性，但如果對(duì)蟻群參數(shù)選擇不當(dāng)，蟻群算法較快收斂到局部最優(yōu)或較慢的收斂，對(duì)算法有極大地影響。文獻(xiàn)[9～10]利用大量數(shù)據(jù)分析了α，β參數(shù)不同組合得到的算法性能。在0.1≤α≤0.3，3≤β≤6的些范圍內(nèi)，算法總體上有較好的性能，到達(dá)的最優(yōu)解與全局最優(yōu)接近，同時(shí)，所需的迭代次數(shù)也較少，不易陷入局部最優(yōu)，導(dǎo)致算法停滯。本文算法中控制參數(shù)取值如表1所示。

表1 計(jì)算參數(shù)的選擇

假設(shè)艦載直升機(jī)在執(zhí)行某次任務(wù)后，部分裝備受到損傷，再次出動(dòng)需要對(duì)5個(gè)專業(yè)9個(gè)項(xiàng)目維修，如表2所示。

表2 維修項(xiàng)目、時(shí)間及保障重要度

根據(jù)以上假設(shè)和優(yōu)化目標(biāo)，采用蟻群算法用Matlab編程計(jì)算結(jié)果如圖1所示。

圖1 最佳路徑和最短工時(shí)

假設(shè)條件數(shù)據(jù)不變，應(yīng)用其它算法求解本例，得到計(jì)算結(jié)果如表3所示，可以發(fā)現(xiàn)本文所述算法求解結(jié)果基本優(yōu)于其他算法，其求解時(shí)間對(duì)比顯示：本文求解時(shí)間小于其它算法，基本適用于應(yīng)急保障資源調(diào)度對(duì)決策時(shí)間的快速要求。

表3 計(jì)算結(jié)果的比較

6 結(jié)語(yǔ)

該模型可以計(jì)算出艦載直升機(jī)在有限資源情況下保障維修的最短工時(shí)和最優(yōu)工序，能夠提高維修效率，從而提高艦載直升機(jī)的完好率。本文在計(jì)算維修任務(wù)的重要度時(shí)只考慮了三個(gè)影響因素，為了更切近實(shí)際保障工作，可以全面研究各種影響因素，確定更為合理的維修工序。

[1] 張?chǎng)?金超.基于蟻群算法的艦船維修資源優(yōu)化調(diào)度[J].兵工自動(dòng)化,2011,30(11):1-35.

[2] 壽涌毅,傅奧.多目標(biāo)資源受限項(xiàng)目調(diào)度的多種一群算法[J].浙江大學(xué)學(xué)報(bào),2010,44(1):51-55.

[3] 崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:國(guó)防工業(yè)出版社,2008:253-256.

[4] 李耀華,譚娜,郝貴和.飛機(jī)維修計(jì)劃優(yōu)化模型與算法研究[J].控制工程,2008,15(1):99-102.

[5] 孫寶琛,賈希勝.基于蟻群算法的維修資源應(yīng)急調(diào)度研究[J].研究與設(shè)計(jì),2012(6):37-41.

[6] 陳慶華.裝備運(yùn)籌學(xué)[M].北京:國(guó)防工業(yè)出版社,2007:85-89.

[7] Merkle D, Middendorf M, Sch Meck H. Ant colony optimization for resource constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation,2002,6(4):333-346.

[8] Mazzeo S, Loiseau I. An ant colony algorithm for the capacitated vehicle routing[J]. Electronic Notes indiscrete Mathematics,2004(8):181-186.

[9] 蔣玲艷.蟻群算法的參數(shù)分析[J].計(jì)算機(jī)工程與應(yīng)用,2007(20):31-36.

[10] 黃翰,郝志峰,吳春國(guó).蟻群算法的收斂速度分析[J].計(jì)算機(jī)學(xué)報(bào),2007,30(8):1344-1353.

Optimal Scheduling of Shipboard Helicopter Maintenance Resource Based on Ant Colony Algorithm

LI Junliang1TENG Ke’nan1YI Guanchen1LIU Guohuan2

(1. Naval Aeronautical Engineering Institute, Yantai 264001)(2. No. 92514 Troops of PLA, Yantai 264007)

According to the particularity of the maintenance of shipboard helicopter with constrained resource and time limited, the optimized scheduling model of shipboard helicopter maintenance resource is put forward. By using the ant colony algorithm, the simulating calculation proves that the method uses the pheromone update to enhance search capability of ants to the optimal path, which solves the resource shortage problem well and reduces the maintenance cycle.

shipboard helicopter maintenance, resource constraint, optimized resources, shortest time, ant-colony-algorithm

2014年5月10日,

2014年6月23日 作者簡(jiǎn)介:李軍亮,男,博士研究生,研究方向:飛行器動(dòng)力學(xué)和航空裝備保障。滕克難,男,博士,教授,博士生導(dǎo)師,研究方向:武器裝備發(fā)展論證。衣冠琛,男,碩士,研究方向:航空裝備保障。劉國(guó)桓,男,工程師,研究方向:航空裝備保障。

V241

10.3969/j.issn1672-9730.2014.11.035