多中心維修任務分配研究現狀

齊小剛，張仲華，宋衛星，劉盛鈺，劉立芳

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

目前，戰爭模式趨于信息化，并演變成體系之間的對抗。由“單兵種作戰”模式轉變為“聯合作戰”“區域作戰”模式，“面向裝備”的維修保障轉變為“面向作戰區域”的維修保障，“型號保障”方式轉變為“區域聯合保障”方式，區域聯合保障方式成為聯合保障力量的基礎。保障任務采用“模塊化組合，積木式編組”。戰時選擇有效的保障模塊有利于節約資源和提高效率[1]。

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

故，有必要總結當前多中心維修任務分配研究的現狀，分析存在的不足，以促進其今后的發展。

1 問題描述

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

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

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

表1 任務分配功能描述Table 1 Task assignment function description

2 問題分析

2.1 任務分類

任務常指分配的工作，擔任的責任。在軍事領域中，任務均具有軍事目的。根據任務目的的不同，任務可以分為使命任務和行動任務。使命任務一般指比較重大的責任，而行動任務相對具體、細微。

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

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

2.2 任務優先級排序

裝備維修任務的優先級是指給定的優先等級。它決定維修任務得到維修相應及占用資源的優先次序，這主要與任務本身屬性和調度算法有關。特別在實時系統中，任務優先級反應了任務的重要性與緊迫性。

任務分配中的優先級是基礎，任務優先級越高須越先分配；資源分配是一個中間角色，可以合理分配資源以保證維護任務的順利進行；任務調度是關鍵，可快速響應實時需求。為了使裝備維修保障順利進行以滿足作戰需要，優先級分類、分配和調度的合理性皆是必需的。

2.3 任務分配

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

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

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

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

3 模型與算法

3.1 優先級排序

維修任務確定后，明確了資源需求和維修時間。在戰斗系統中裝備重要度體現在對戰斗的貢獻，其詳情如圖5 所示。

圖5 優先級分類Fig.5 Priority classification

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

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

3.1.1 指標權重

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

1)主客觀賦權法以問卷或專家打分的數據獲取到指標權重，如層次分析法[6]、D-S 證據理論[7]、德爾菲法[8]等。近年優化賦權結果采用了AHP和灰色模糊結合[9]、D-S 證據和灰色關聯度結合[10]的混合主觀方法。其優點是流程簡單、對數據要求低，缺點是在賦權過程中缺乏統一原則且伴有大量的主觀干擾。

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

3)主客觀組合賦權法結合上述兩種方法，充分發揮各自優勢，如熵權法和AHP 結合[14]、AHP和主成分分析結合[15]，效果良好。

4)決策中的交互賦權法會根據信息更新調整指標權重[16]。

3.1.2 排隊論

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

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

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

圖6 排隊過程Fig.6 Queuing process

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

2)排隊規則：等待制、損失制和混合制最為常用。服務機構忙且顧客等候為等待制。服務機構忙顧客離去即為損失制。服務次序有先(后)到先服務、服從優先權服務等模式。

3)服務機構：多個服務臺平行或串聯布置(也可一個服務臺服務)。服務時間有確定型和隨機型。

對排隊論的研究常關注服務的效率、質量。排隊系統評價指標如下：

1)系統負載ρ：服務能力的度量。

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

3)隊長：系統內等候和正在接受服務的客戶數，均值為Ls。

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

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

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

系統的各項指標可由狀態轉移速度推算出來，如圖7 所示。

圖7 狀態轉移速度圖Fig.7 State transition velocity diagram

M/M/1 排隊系統是最簡單的排隊系統，如表2所示。

表2 M/M/1 排隊系統的指標Table 2 Indicators of the M/M/1 queuing system

3.1.3 排隊系統其他分類

1)按故障特性分類

實際上完全可靠的服務系統是不存在的。按故障類型可分如下兩類：

①完全故障：服務臺故障時服務完全停止。

②不完全故障：服務臺故障時低效服務。

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

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

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

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

2)根據多類顧客分類

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

3)帶啟動時間的服務

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

3.2 任務分配

3.2.1 典型模型、算法概述

維修任務分配中應明確任務分工和執行路徑，制訂維修計劃。分配時應考慮維修人員、維修能力及時間約束。

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

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

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

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

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

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

上述啟發式算法對比如表3 所示。

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

3.3 路徑規劃

維修任務分配確定任務承擔者，路徑規劃確定完成路徑。任務劃分是維修任務分配的基礎，路徑規劃是其重點。維修任務規劃是尋找最佳分配方案的問題。二者相互結合，相互影響，共同決定分配的最終結果。

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

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

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

4 結束語

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

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

2)戰爭逐漸趨于信息化，未來作戰空間更大。在動態作戰環境下，及時合理分配維修任務，充分發揮保障系統效能，是維修保障任務分配的迫切需求與發展方向。