多中心維修任務(wù)分配研究現(xiàn)狀

齊小剛，張仲華，宋衛(wèi)星，劉盛鈺，劉立芳

（1.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，陜西 西安 710071;2.陸軍工程大學(xué) 軍械士官學(xué)校，湖北 武漢 430075;3.中國人民解放軍32272 部隊11 分隊，甘肅 蘭州 730060;4.西安電子科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西西安 710071）

目前，戰(zhàn)爭模式趨于信息化，并演變成體系之間的對抗。由“單兵種作戰(zhàn)”模式轉(zhuǎn)變?yōu)椤奥?lián)合作戰(zhàn)”“區(qū)域作戰(zhàn)”模式，“面向裝備”的維修保障轉(zhuǎn)變?yōu)椤懊嫦蜃鲬?zhàn)區(qū)域”的維修保障，“型號保障”方式轉(zhuǎn)變?yōu)椤皡^(qū)域聯(lián)合保障”方式，區(qū)域聯(lián)合保障方式成為聯(lián)合保障力量的基礎(chǔ)。保障任務(wù)采用“模塊化組合，積木式編組”。戰(zhàn)時選擇有效的保障模塊有利于節(jié)約資源和提高效率[1]。

此外，裝備維修保障是使故障裝備恢復(fù)使用甚至高效運行的全部活動。一方面，指揮要根據(jù)作戰(zhàn)要求落實指揮員意圖；另一方面，指揮以行動為立足點。故在作戰(zhàn)中，指揮起到了從需求轉(zhuǎn)為行動的紐帶作用。裝備維修保障任務(wù)分配對指揮發(fā)揮職能與否也起到極其重要的作用。

故，有必要總結(jié)當(dāng)前多中心維修任務(wù)分配研究的現(xiàn)狀，分析存在的不足，以促進其今后的發(fā)展。

1 問題描述

多中心維修任務(wù)分配問題是指在維修時間約束下，對任務(wù)優(yōu)先級進行排序，并運用求解算法得出分配結(jié)果。詳情如圖1 所示，任務(wù)分配框架如圖2 所示，任務(wù)分配功能如表1 所示。

圖1 維修保障任務(wù)分配問題描述Fig.1 Maintenance support task assignment problem description

圖2 多中心維修任務(wù)分配框架Fig.2 Multi center maintenance tasks schedule framework

表1 任務(wù)分配功能描述Table 1 Task assignment function description

2 問題分析

2.1 任務(wù)分類

任務(wù)常指分配的工作，擔(dān)任的責(zé)任。在軍事領(lǐng)域中，任務(wù)均具有軍事目的。根據(jù)任務(wù)目的的不同，任務(wù)可以分為使命任務(wù)和行動任務(wù)。使命任務(wù)一般指比較重大的責(zé)任，而行動任務(wù)相對具體、細微。

根據(jù)任務(wù)時機的不同，任務(wù)可以分為訓(xùn)練任務(wù)和作戰(zhàn)任務(wù)。按照新版《中國人民解放軍軍語》的定義，訓(xùn)練任務(wù)是指軍事訓(xùn)練所要完成的任務(wù)，訓(xùn)練任務(wù)通常由參訓(xùn)兵力、訓(xùn)練內(nèi)容、訓(xùn)練時間和質(zhì)量指標等構(gòu)成；作戰(zhàn)任務(wù)是指作戰(zhàn)力量為達成預(yù)定作戰(zhàn)目的而擔(dān)負的任務(wù)，由上級指揮員確定，并以作戰(zhàn)命令的形式下達。

使用任務(wù)是指面向保障需要能夠反映出作戰(zhàn)單元構(gòu)成裝備的使用行為的作戰(zhàn)行動。與一般的作戰(zhàn)任務(wù)和作戰(zhàn)行動相比，使用任務(wù)更為細致地描述了執(zhí)行任務(wù)的每一個裝備的使用過程和行為活動，并由此可與每一個裝備的保障需求結(jié)合起來，而這是在保障方案制定中必須要了解的。

2.2 任務(wù)優(yōu)先級排序

裝備維修任務(wù)的優(yōu)先級是指給定的優(yōu)先等級。它決定維修任務(wù)得到維修相應(yīng)及占用資源的優(yōu)先次序，這主要與任務(wù)本身屬性和調(diào)度算法有關(guān)。特別在實時系統(tǒng)中，任務(wù)優(yōu)先級反應(yīng)了任務(wù)的重要性與緊迫性。

任務(wù)分配中的優(yōu)先級是基礎(chǔ)，任務(wù)優(yōu)先級越高須越先分配；資源分配是一個中間角色，可以合理分配資源以保證維護任務(wù)的順利進行；任務(wù)調(diào)度是關(guān)鍵，可快速響應(yīng)實時需求。為了使裝備維修保障順利進行以滿足作戰(zhàn)需要，優(yōu)先級分類、分配和調(diào)度的合理性皆是必需的。

2.3 任務(wù)分配

合理分配任務(wù)是維修保障的前提，可充分發(fā)揮保障的力量。裝備維修中的任務(wù)分配問題一般是指，為了在作戰(zhàn)中恢復(fù)作戰(zhàn)部隊的戰(zhàn)斗力，必須首先按照一定的機制為故障裝備分配一個或多個維修機構(gòu)，以充分利用保障資源，盡快恢復(fù)戰(zhàn)斗力。無需強調(diào)維修任務(wù)的前后順序，只考慮在哪個機構(gòu)維修。

任務(wù)分配過程中，每時間段、每作戰(zhàn)區(qū)域的每個作戰(zhàn)單元可能出現(xiàn)多個故障，將其反饋到信息管理中心，并對維修需求進行匯總篩選，綜合考慮維修機構(gòu)負載能力、資源等因素，以及考慮故障裝備受維修時間、成本、環(huán)境等影響，制定并下發(fā)維修分配計劃，使維修效益最大化。維修效益指維修效果與所耗資源之比。維修分配流程如圖3 所示，各專業(yè)的不同裝備維修單元體維修詳情如圖4 所示。

圖3 維修任務(wù)分配流程Fig.3 Maintenance task allocation process

圖4 各專業(yè)的不同裝備維修單元體維修示意圖Fig.4 Maintenance schematic diagram of different equipment maintenance units of different majors

3 模型與算法

3.1 優(yōu)先級排序

維修任務(wù)確定后，明確了資源需求和維修時間。在戰(zhàn)斗系統(tǒng)中裝備重要度體現(xiàn)在對戰(zhàn)斗的貢獻，其詳情如圖5 所示。

圖5 優(yōu)先級分類Fig.5 Priority classification

任務(wù)優(yōu)先級分類基于損壞級別。曾擁華等[2]分析了這一問題，戰(zhàn)場損傷評估的流程基本由此確定。文獻[3]構(gòu)建并驗證了戰(zhàn)場損傷等級評價模型。然而，如果不考慮受損裝備對作戰(zhàn)的貢獻，維修任務(wù)的重要性就無法得到充分的體現(xiàn)。通過引入裝備作戰(zhàn)貢獻，推導(dǎo)出優(yōu)先級分類模型。目前研究很少有涉及這一問題的，文獻[4]以ELECTRE TRI 評估了維修任務(wù)的優(yōu)先級。

多屬性決策考慮各種相關(guān)屬性，排序并選擇令人滿意的方案。研究的重點是確定指標的權(quán)重及排序的方案。

3.1.1 指標權(quán)重

確定指標權(quán)重方法：主觀賦權(quán)法、客觀賦權(quán)法、主客觀組合賦權(quán)法和交互賦權(quán)法[5]。

1)主客觀賦權(quán)法以問卷或?qū)＜掖蚍值臄?shù)據(jù)獲取到指標權(quán)重，如層次分析法[6]、D-S 證據(jù)理論[7]、德爾菲法[8]等。近年優(yōu)化賦權(quán)結(jié)果采用了AHP和灰色模糊結(jié)合[9]、D-S 證據(jù)和灰色關(guān)聯(lián)度結(jié)合[10]的混合主觀方法。其優(yōu)點是流程簡單、對數(shù)據(jù)要求低，缺點是在賦權(quán)過程中缺乏統(tǒng)一原則且伴有大量的主觀干擾。

2)挖掘數(shù)據(jù)內(nèi)在特征獲取指標定量權(quán)重的客觀賦權(quán)法包括主成分分析[11]、熵權(quán)法[12]、目標規(guī)劃[13]等。其優(yōu)點是權(quán)重根據(jù)已有數(shù)據(jù)得到，客觀準確；缺點是對數(shù)據(jù)要求較高。

3)主客觀組合賦權(quán)法結(jié)合上述兩種方法，充分發(fā)揮各自優(yōu)勢，如熵權(quán)法和AHP 結(jié)合[14]、AHP和主成分分析結(jié)合[15]，效果良好。

4)決策中的交互賦權(quán)法會根據(jù)信息更新調(diào)整指標權(quán)重[16]。

3.1.2 排隊論

有許多排序方法可供選擇，其適應(yīng)條件一般不盡相同?？筛鶕?jù)具體研究內(nèi)容選擇合適的方法，例如模糊綜合評判法[17]、TOPSIS[18]、投影法[19]、ELECTRE[20]等。然而，在排序的過程中面臨著新需求的出現(xiàn)與舊需求的滿足，故涉及排隊論。

排隊論起源于電話通信。丹麥數(shù)學(xué)家A.K.Erlang 在1909 年研究了隨機需求導(dǎo)致非穩(wěn)態(tài)隊列的問題。其后，他進一步發(fā)現(xiàn)了自動電話通信系統(tǒng)可以以兩種基本概率模型模擬：泊松輸入，指數(shù)分布服務(wù)時間，多服務(wù)流；泊松輸入，穩(wěn)定常態(tài)服務(wù)時間，單服務(wù)流。Erlang 亦提出隊列穩(wěn)態(tài)平衡的概念與排隊系統(tǒng)的初步優(yōu)化辦法。排隊論源自對實際現(xiàn)象的研究，而后接近半個世紀，排隊論主要針對理論進行研究(生滅理論，嵌入馬爾可夫模型)。直到二戰(zhàn)以后，學(xué)者開始為該理論賦予應(yīng)用價值，大量研究開始導(dǎo)向如何精確求解先前學(xué)者留下的復(fù)雜數(shù)學(xué)模型，并直接應(yīng)用于現(xiàn)實的管理決策中。例如：復(fù)雜排隊模型，排隊網(wǎng)絡(luò)的近似解與數(shù)值模擬辦法等。近現(xiàn)代排隊論主要為管理決策軟件的開發(fā)提供理論與模擬支持。

隨機服務(wù)系統(tǒng)對服務(wù)時間進行統(tǒng)計研究，根據(jù)規(guī)律對服務(wù)系統(tǒng)進行重構(gòu)，使其滿足服務(wù)需要，成本又盡可能小等。排隊系統(tǒng)在生活中一般非常復(fù)雜，常包括輸入、排隊和服務(wù)，如圖6 所示。顧客的到達稱為輸入，離開即為輸出，顧客到達和系統(tǒng)服務(wù)時間常假設(shè)服從定長分布、負指數(shù)分布、幾何分布[21-22]。

圖6 排隊過程Fig.6 Queuing process

1)輸入過程：可采用某時間內(nèi)顧客到達數(shù)或相鄰兩顧客到達的時間間隔來考察顧客到達系統(tǒng)的規(guī)律。一般有確定型和隨機型。當(dāng)時間t內(nèi)到達顧客數(shù)n(t)隨機即為隨機型輸入，且根據(jù)統(tǒng)計可能服從某一分布。若服從泊松分布，時間t內(nèi)到達顧客n的概率為Pn(t)=e?λt(λt)n/n!(n=0,1,2,···,N)；若相鄰顧客到達時間間隔服從負指數(shù)分布，則有P(T≤t)=1?e?λt，其中λ 為顧客平均到達率，1/λ為相鄰顧客的平均時間間隔。

2)排隊規(guī)則：等待制、損失制和混合制最為常用。服務(wù)機構(gòu)忙且顧客等候為等待制。服務(wù)機構(gòu)忙顧客離去即為損失制。服務(wù)次序有先(后)到先服務(wù)、服從優(yōu)先權(quán)服務(wù)等模式。

3)服務(wù)機構(gòu)：多個服務(wù)臺平行或串聯(lián)布置(也可一個服務(wù)臺服務(wù))。服務(wù)時間有確定型和隨機型。

對排隊論的研究常關(guān)注服務(wù)的效率、質(zhì)量。排隊系統(tǒng)評價指標如下：

1)系統(tǒng)負載ρ：服務(wù)能力的度量。

2)系統(tǒng)空閑概率P0：無顧客請求的概率。

3)隊長：系統(tǒng)內(nèi)等候和正在接受服務(wù)的客戶數(shù)，均值為Ls。

4)隊列長：等候接受服務(wù)的客戶數(shù)，均值Lg。

5)逗留時間：一個顧客等候和接受服務(wù)時間的和，均值Ws。

6)等候時間：一個顧客的等候時間，均值Wg。

系統(tǒng)的各項指標可由狀態(tài)轉(zhuǎn)移速度推算出來，如圖7 所示。

圖7 狀態(tài)轉(zhuǎn)移速度圖Fig.7 State transition velocity diagram

M/M/1 排隊系統(tǒng)是最簡單的排隊系統(tǒng)，如表2所示。

表2 M/M/1 排隊系統(tǒng)的指標Table 2 Indicators of the M/M/1 queuing system

3.1.3 排隊系統(tǒng)其他分類

1)按故障特性分類

實際上完全可靠的服務(wù)系統(tǒng)是不存在的。按故障類型可分如下兩類：

①完全故障：服務(wù)臺故障時服務(wù)完全停止。

②不完全故障：服務(wù)臺故障時低效服務(wù)。

此外，根據(jù)維修時間不同可分如下兩類：

①即刻維修：故障后即刻維修。

②延遲維修：故障后等候維修時間隨機。

Bruneel 等[23-25]在經(jīng)典的排隊模型中考慮了故障特性。從經(jīng)濟學(xué)角度來看，排隊系統(tǒng)始于2008年，Economou 等[26]最早考慮了完全失效可修排隊系統(tǒng)，根據(jù)排隊長度決定是否加入的顧客均衡閾值策略由此給出。Li 等[27]拓展了文獻[26]，分析了不可見情況。Li 等[28]關(guān)于排隊系統(tǒng)通過對不完全故障即時維修的研究，獲得了在顧客完全(不)可見排隊的進入策略。Yu 等[29]豐富了文獻[28]成果，研究幾乎(不)可見的不完全故障顧客的排隊策略。Xu 等[30]通過研究不完全故障延遲維修的M/M/1，考慮完全(不)可見時顧客的止步策略和平均收益。Yang 等[31]研究了Geo/Geo/1 隊列中存在服務(wù)器故障和維護的顧客均衡行為。Boudali等[32-33]考慮有災(zāi)難的M/M/1，災(zāi)難時顧客離開系統(tǒng)，至服務(wù)臺完成維修，采用納什均衡策略決定新顧客接受與否。

2)根據(jù)多類顧客分類

如優(yōu)先權(quán)顧客、不耐煩顧客等存在于排隊系統(tǒng)中，排隊系統(tǒng)將由此變得更加難以分析。馬占友等[34-35]研究了不同優(yōu)先權(quán)顧客。Yang 等[36-37]研究了可抵消正顧客和負顧客。劉楠[38]研究了不耐煩顧客。Balachandran[39]最早研究了優(yōu)先權(quán)M/M/1，得到顧客的支付數(shù)可提高其的優(yōu)先級。Adiri等[40-41]研究了兩類不同優(yōu)先級排隊，獲取了均衡進隊純閾值等策略。Lillo[42]在M/G/1 中考慮不同優(yōu)先級排隊，獲得了兩個閾值的最佳控制策略。Sun 等[43]研究的排隊系統(tǒng)具有不同費用函數(shù)，在絕對優(yōu)先時得到了最佳策略。Xu 等[44]分析了不可見條件下具有搶占優(yōu)先權(quán)顧客的M/G/1 顧客均衡和全局最佳策略。

3)帶啟動時間的服務(wù)

啟動過程是無服務(wù)時關(guān)閉服務(wù)臺，服務(wù)請求開始時，經(jīng)一隨機啟動時間恢復(fù)服務(wù)。Choudhury 等[45-49]在經(jīng)典的排隊模型中引入了啟動期的研究。排隊論2007 年引進了啟動時間，Burnetas等[50]最早對其進行了研究，均衡分析已得可見(不可見)情況的顧客均衡排隊策略和平均收益。Sun等[51-52]以馬爾可夫過程和差分方程求解，分析了系統(tǒng)信息(不)可見情況下帶有啟動關(guān)閉的的隊列進入策略。Zhang 等[53]進一步推廣了M/G/1 排隊系統(tǒng)，分析了系統(tǒng)信息可見情形下的均衡進隊概率。Hao 等[54]研究了單服務(wù)臺具有啟動時間，考慮了系統(tǒng)的閾值和完全故障。

3.2 任務(wù)分配

3.2.1 典型模型、算法概述

維修任務(wù)分配中應(yīng)明確任務(wù)分工和執(zhí)行路徑，制訂維修計劃。分配時應(yīng)考慮維修人員、維修能力及時間約束。

Choudhury 等[55]在生產(chǎn)中為改善任務(wù)分配的合理性引入了柔性，并在調(diào)度中為實現(xiàn)優(yōu)化引入了遺傳算法。Yu 等[56]協(xié)同無人機研究任務(wù)分配，提取有效信息以實現(xiàn)動態(tài)分配；Gopalakrishnan 等[57]指出任務(wù)分配、復(fù)雜程度、維修能力之間存在相關(guān)性；Macedo 等[58]分析了機械、電子等預(yù)防性維修的任務(wù)分配，建立了基于維修的任務(wù)分配模型，但修復(fù)性問題尚未解決；薛桂香[59]將多任務(wù)動態(tài)分配視為NP 組合優(yōu)化問題，提出了動態(tài)遺傳算法，并根據(jù)網(wǎng)絡(luò)系統(tǒng)服務(wù)節(jié)點計算能力及負載進行了動態(tài)任務(wù)分配；Shi 等[60]結(jié)合蟻群、蝙蝠、狼群算法對多無人機進行了任務(wù)分配；Jia 等[61]基于遺傳算法對異物無人機進行了任務(wù)分配；Keiser等[62]首創(chuàng)并使用多維列表規(guī)劃來獲取任務(wù)之間的匹配方案，從而更好地全局最優(yōu)化任務(wù)分配的解；Khouadjia 等[63]結(jié)合DAPSO 算法、VNS 算法對動態(tài)的需求問題進行了車輛送貨的任務(wù)分配。

Jia 等[64]設(shè)計并應(yīng)用了一個計算機輔助系統(tǒng)來解決軍械維修中的任務(wù)分配，但沒有對典型案例進行分析。Yuan 等[65]關(guān)于任務(wù)分配構(gòu)建了模型，并以蒙特卡洛法研究了石油裝備維修。李龍躍等[66]對多波目標分配反導(dǎo)進行了研究，關(guān)于分配導(dǎo)彈-目標的模型由此建立，但未考慮不確定性與可靠性等因素。曾家友等[67]對分配艦載導(dǎo)彈的目標進行了研究，考慮了價值收益、效費比優(yōu)先級排序等問題；Yang 等[68]在遺傳算法中引入隨機移民、二元論等，可用于動態(tài)任務(wù)分配問題。

3.2.2 常用典型算法簡介及對比

局部搜索算法是一種重要的求解組合優(yōu)化問題的啟發(fā)式算法，由于簡單且易于理解，其已受到越來越廣泛的重視。常見有2-Opt、2-Opt*等[63]。

模擬退火算法的思想最早由Metropolis 等于1953 年提出，后由Krikpatrick[69]于2002 年第一次用于求解組合優(yōu)化問題。此算法以一定概率選擇鄰域中的劣質(zhì)解以克服其他算法易陷入局部最優(yōu)的缺陷和對初值的依賴。

20 世紀60 年代，Holland[70]提出了遺傳算法，隨機生成初始種群，通過選擇、交叉、變異產(chǎn)生更適應(yīng)環(huán)境的個體以得到優(yōu)化解。我國遺傳算法從20 世紀末開始研究且迅速膨脹。羅雄等[71]對遺傳算法解決柔性作業(yè)、車間調(diào)度問題進行了綜述。劉國強[72]根據(jù)任務(wù)分配特點，采用多目標遺傳算法解決了維修任務(wù)分配問題。

上述啟發(fā)式算法對比如表3 所示。

表3 啟發(fā)式算法間的對比Table 3 Comparison of heuristic algorithms

3.3 路徑規(guī)劃

維修任務(wù)分配確定任務(wù)承擔(dān)者，路徑規(guī)劃確定完成路徑。任務(wù)劃分是維修任務(wù)分配的基礎(chǔ)，路徑規(guī)劃是其重點。維修任務(wù)規(guī)劃是尋找最佳分配方案的問題。二者相互結(jié)合，相互影響，共同決定分配的最終結(jié)果。

裝備維修任務(wù)路徑規(guī)劃可抽象為車輛規(guī)劃最短路線遍歷所有目標點的問題，此即為車輛路徑問題(vehicle routing problem,VRP)。VRP 隨約束的增加而發(fā)展。文獻[73]研究了有車輛負載能力上限約束的VRP 問題。文獻[74]研究了電動車輛的VRP，考慮電容量的約束，并將規(guī)劃結(jié)果與燃油汽車進行了對比。文獻[75]詳細分析了VRP中的最優(yōu)速度、垃圾傾倒、長距離運輸問題，區(qū)分了時間安排原則。文獻[76]考慮了無沖突VRP以解決后勤運輸路徑規(guī)劃的沖突和死鎖問題。文獻[77]對多配送中心動態(tài)VRP 給予了優(yōu)化，采用智能優(yōu)化可解決VRP 這種NP 問題。文獻[78]使用改進遺傳聚類解決了多中心配送VRP 問題。文獻[79]使用并行模擬退化來解決同時發(fā)送和取貨的VRP 問題。文獻[80]采用變鄰域下降算法來求解兩級VRP 問題。文獻[57]使用混合遺傳算法來解決存在車輛租借、共享等條件的多個中心配送的VRP 問題。并行運算、可全局搜索的蟻群算法衍生出了混合蟻群算法[81]、量子蟻群算法[82]、蟻群系統(tǒng)[83]和最大-最小螞蟻系統(tǒng)(maxmin ant system,MMAS)[84]等。解決離散時間最佳路徑規(guī)劃的方法?MMAS 可進一步改進。VRP和裝備維修任務(wù)路徑規(guī)劃問題均選擇最佳路徑以實現(xiàn)某一目標，但是又存在一定差異：

1)決策目標不同：VRP 追求路徑(時間)最小化，任務(wù)路徑規(guī)劃則追求維修效益最大化。

2)約束條件不同：VRP 及其衍生問題多以車輛的載重、最大航程、存儲容量等為約束，且此問題中車輛一般要經(jīng)過所有服務(wù)點；而任務(wù)路徑規(guī)劃是解決作戰(zhàn)時維修的問題，不必接受所有維修任務(wù)。

4 結(jié)束語

綜上所述，已有的工作對維修任務(wù)分配問題進行了深入研究，但在裝備維修任務(wù)分配的模型和算法方面還存在一定的不足，有待進一步開展，具體表現(xiàn)如下：

1)目前關(guān)于裝備維修任務(wù)分配的研究甚少，裝備維修保障任務(wù)品種多、約束多，資源有限時，能使系統(tǒng)體系平穩(wěn)運行的裝備優(yōu)先修復(fù)?，F(xiàn)研究常忽略待修裝備作戰(zhàn)貢獻值，即便有部分研究，也是針對優(yōu)先級的定性排序，應(yīng)同時考慮多因素以定量研究任務(wù)優(yōu)先級。

2)戰(zhàn)爭逐漸趨于信息化，未來作戰(zhàn)空間更大。在動態(tài)作戰(zhàn)環(huán)境下，及時合理分配維修任務(wù)，充分發(fā)揮保障系統(tǒng)效能，是維修保障任務(wù)分配的迫切需求與發(fā)展方向。