考慮非遍歷的搶修任務多目標動態調度

陳春良, 陳偉龍, 陳康柱, 劉彥, 史憲銘

(1.裝甲兵工程學院 技術保障工程系, 北京 100072； 2.裝甲兵工程學院 訓練部, 北京 100072；3.軍械工程學院 裝備指揮與管理系, 河北 石家莊 050003)

考慮非遍歷的搶修任務多目標動態調度

陳春良1, 陳偉龍1, 陳康柱2, 劉彥1, 史憲銘3

(1.裝甲兵工程學院 技術保障工程系, 北京 100072； 2.裝甲兵工程學院 訓練部, 北京 100072；3.軍械工程學院 裝備指揮與管理系, 河北 石家莊 050003)

針對進攻作戰中戰損裝備眾多而搶修時間與搶修力量有限的矛盾，進行了進攻作戰搶修任務動態調度研究。提出考慮非遍歷的搶修任務多目標動態調度的現實軍事問題，建立多目標規劃數學模型，分析了非遍歷、修理能力差異、待修裝備優先級3個重要影響因素；根據所建模型的特點，設計了基于遺傳算法的模型求解算法；運用Matlab軟件進行了39輛待修裝備、3個搶修組的動態調度示例仿真與分析。示例結果表明：通過實施機動伴隨搶修和搶修任務動態調度，進攻作戰部隊能夠獲得約185 h的二次作戰總時間，進而增強部隊的持續作戰能力，并大大減少決策工作量和決策時間、降低人為決策風險。

兵器科學與技術； 戰場搶修； 動態調度； 非遍歷； 遺傳算法

0 引言

所謂遍歷，是指沿著某條搜索路徑，依次對集合中的每個元素均做一次且僅做一次訪問。所謂非遍歷，是指沿著某條搜索路徑，依次對集合中的部分元素做一次且僅做一次訪問，且由于受到邊界條件限制，被訪問元素數量具有不確定性。

所謂考慮非遍歷的搶修任務多目標動態調度 (MDBTSPN)，是指在進攻作戰中，敵方火力打擊造成我方戰損裝備不斷增多，而所屬搶修力量有限，導致搶修力量無法在進攻周期內完成對修理范圍內的所有待修裝備的戰場搶修；為最大限度地迅速恢復作戰部隊的整體進攻能力，在搶修任務調度過程中，需要綜合權衡待修裝備所需修理工時、轉場所需時間、不同搶修組修理能力差異、待修裝備優先級等因素，并考慮非遍歷特性帶來的根本性影響，從修理范圍內的待修裝備中選擇部分裝備進行修理。解決該問題的關鍵在于如何合理地建立多目標動態規劃模型，動態地決策不同搶修組間的任務分工和同一搶修組內的搶修序列，使得搶修效果更有利于完成本階段進攻作戰任務。MDBTSPN作為一個典型復雜優化問題，是貼合戰場實際情況且急需解決的一個軍事難題，核心難點在于遵循MDBTSPN的實際約束限制，有效解決非遍歷型尋優難題，動態追蹤問題的最優解。

在戰場搶修任務調度方面，由于戰場環境復雜、限制條件多、研究難度大，現有戰場搶修任務調度研究成果相對匱乏。文獻[1-2]以戰時定點維修為研究對象，提出了兩種不同約束條件下的動態維修任務調度方法。文獻[3]針對維修資源短缺及資源沖突的問題，建立了戰場搶修多需求點多資源優化調度模型。文獻[4]將證據推理應用于戰時多任務搶修重要度決策，構建了重要度決策指標體系和決策模型。文獻[5]以總搶修效益最大為目標，建立了搶修資源重組決策模型，設計了混合粒子群算法進行求解。已有研究或僅限定于戰時定點維修，進而將問題轉化為生產調度問題求解，或不考慮修理能力差異和修理力量損失，且均沒有考慮非遍歷這一約束，這既與MDBTSPN實際情況明顯不符，也不能滿足進攻作戰對伴隨保障的現實需求。

在動態調度及非遍歷方面，研究熱點主要集中于動態車輛路徑問題[6]、生產調度問題[7-8]和多無人機協同任務分配問題[9]及三者的變體問題，焦點約束條件包括動態的需求集合[10]、時間窗[11]、多種類型的任務主體[12]、時間的不確定性[13]、費用[14]、動態環境[15]等。前述研究的數學實質絕大部分屬于遍歷型，少有對非遍歷情況的考慮，且考慮到MDBTSPN的自身約束條件、目標函數、數學模型的特殊性，已有的模型、算法等均無法求解MDBTSPN.

從已掌握的文獻分析，本文提出的考慮非遍歷搶修任務動態調度問題作為一個復雜系統問題，尚無學者進行深入研究。據此，本文提出考慮非遍歷的搶修任務動態調度這一軍事問題，構建其數學模型，設計遺傳算法并編程求解，通過示例仿真與分析驗證算法有效性，解決非遍歷型尋優難題并追蹤MDBTSPN最優解的動態變化。MDBTSPN的高效解決能夠為裝備保障指揮員提供輔助決策支持，縮短保障決策時間，降低主觀決策風險，提高進攻作戰持續時間內的裝備參戰率。

1 模型建立

1.1 條件假設

1)開始搶修的時刻為0 min，進攻戰斗結束時刻為Te；進攻戰斗中，在時刻ti(i=0,1,…,N)產生新的待修裝備，編號為i，其位置坐標(xi,yi),節點重要度為ρi，計劃修理工時為Tri(人·h)，計劃修理時間為Tsi(min)。

2)待修裝備集合為J，始發點集合為I，搶修組集合為K，且|J|≥1，|I|≥1，|K|=m≥1，m為搶修組數量；無向圖G=(V,E)，其中V=I∪J，E={(i,j)|i∈V,j∈J}. 各搶修組從不同初始位置出發，負責搶修其修理范圍內的損傷裝備(包括大部分輕損裝備及少量維修工作量小的中損裝備)，最終無需回到各自始發點。后文中提到的所有待修裝備均是指搶修組修理范圍內的損傷裝備。

(1)

式中：i∈V,j∈J,i≠j.

(2)

式中：i∈J.

1.2 動態調度的處理方法設計

本文處理動態調度問題的總體思路是：由于在任意時刻t，MDBTSPN中的動態和靜態需求信息均己知，引入滾動時域思想，基于本文設計的重調度驅動策略，將進攻周期內的動態調度問題P(t)轉化為一系列離散時間點的靜態調度問題P(ti)進行求解。

具體來說，就是根據在一體化進攻作戰中搶修任務調度的實際情況，合理設計重調度驅動策略，并根據不斷出現的搶修需求信息，確定出各個重調度時刻t(q)(q=1,2,…)；由于時刻t(q)的動態和靜態搶修需求信息均為己知，進而將進攻周期內的搶修任務動態調度問題P(t)離散化，轉化成為基于各個重調度時刻的靜態任務分配問題P(t(q))；在滾動的每一步，針對當前離散點的局部問題P(t(q))，在分析其約束條件和確定其目標參數的基礎上，建立搶修任務多目標靜態調度數學模型，并依據模型特點設計解析算法或智能優化算法求解各搶修單元的任務分配決策方案，確定不同搶修單元的任務分工及同一搶修單元的搶修序列；方案執行，進入下一個重調度周期。

考慮進攻作戰中搶修任務動態調度的時效性和可操作性的要求，本文采用數量分批驅動策略。

t(q)為重調度時刻，其確定公式為

(3)

為將動態調度問題P(t)離散轉化為靜態任務分配問題P(t(q))，還需要判斷和標定各個重調度時刻的搶修需求信息。為達成這一目的，須對搶修需要進行合理分類。

在任意時刻t，根據搶修組所在位置和任務完成情況，將所有搶修需求分為4類：1)已完成搶修的裝備G1；2)搶修組正在搶修的以及正在前往搶修點路上的待修裝備G2(已不可更改，稱之為關鍵點)；3)已規劃到搶修任務序列，但暫時沒有搶修組前往的待修裝備G3；4)新出現的待修裝備G4. 其中ti時刻的關鍵點識別是解決動態調度問題的重要難點之一。

1.3 數學模型建立

進攻戰斗戰場搶修，旨在盡快恢復或部分恢復受損裝備的任務功能，使其能夠再次投入戰斗，且修竣裝備對作戰裝備體系的貢獻率最大。

MDBTSPN的目標函數確定如下：

(4)

(5)

(6)

(7)

其中，(4)式表示：在有限的進攻作戰持續時間內，各搶修組應盡可能多地修竣故障裝備、優先修理節點重要度高的裝備，并使其能夠獲得盡可能多的二次參戰時間。

進一步將目標函數轉化為

(8)

轉化的原因在于：對于兩種不同的搶修任務分配方案，如果在相同時間范圍內，兩種方案均能修竣1臺營指揮車和1臺戰斗裝備，且能贏得相同的二次作戰時間總和，那么當目標函數采用(5)式時，則兩種方案的目標函數值相同，即兩種方案優劣程度相同；事實上，兩種方案的優劣程度是不同的，因為營指揮車的節點重要度高于其他戰斗裝備，優先修竣營指揮車，其能更長時間地發揮指控功能，對于整個作戰裝備體系的貢獻顯然更大。基于此，本文采用(8)式所示的目標函數表達式。(8)式的實際意義可解釋為：所有修竣裝備的功能屬性值與其發揮作用的時間長度乘積的代數和。

約束條件考慮了各搶修組修竣各個待修裝備的時間約束關系、遍歷與非遍歷、各個待修裝備是否被修竣、任一修竣的待修裝備有且僅由一個搶修組完成。約束條件的具體數學關系式為

(9)

(10)

(11)

(12)

(13)

(14)

式中：(9)式表示搶修組k從各自任務起點出發到完成第1個待修裝備搶修的計劃修竣時刻之間的時間約束關系；(10)式表示ok中，由搶修組k完成搶修的相鄰兩車的計劃修竣時刻之間的時間約束關系；(11)式表示任一搶修組只在進攻戰斗結束前進行搶修，用以保證非遍歷的實現；(12)式表示如果i點任務完成，則有且僅有某一個搶修組嚴格訪問一次；(13)式表示任意一條弧的終點待修裝備僅有一個起點待修裝備與之相連；(14)式表示任意一條弧的起點待修裝備僅有一個終點待修裝備與之相連。

2 模型分析

2.1 非遍歷分析

時間限制是導致非遍歷問題出現的根本原因，非遍歷型問題的實質是從num_veh中取n(n具有不確定性)、規模為n的遍歷型問題。MDBTSPN內含了遍歷與非遍歷兩種搶修任務調度問題，其模型及算法需要同時考慮這兩種情況，求解難度顯著增大，算法難以收斂。

2.2 修理能力差異分析

由于敵火威脅將直接導致修理力量的損失，進而造成各搶修組的修理能力產生差異。這種差異包括各搶修組之間的修理能力差異和搶修組內部的修理工修理技能差異。

對于前者，在每次任務調度開始前統計搶修力量損失，納入模型進行計算。針對關鍵點待修裝備，若搶修組正在前往該搶修點的路上，理應采用重調度后的修理力量進行計算；若搶修組正在搶修該裝備，采用重調度前后各組修理力量的平均值進行計算。

對于后者，考慮修理工的修理水平差異，將其區分為初級修理工和高級修理工，設定前者每人每小時提供θ1，后者提供θ2，則任一待修裝備計劃修理時間為

(15)

2.3 待修裝備優先級分析

在進攻作戰過程中，進入搶修力量修理范圍的待修裝備主要包括指揮裝備和主戰裝備。本文主要從待修裝備的功能屬性差異(指揮或主戰)和任務屬性差異(主攻與助攻)來分析其優先級。顯然，同一級別的指揮裝備與主戰裝備、不同級別的指揮裝備、擔任不同作戰任務的主戰裝備，在進攻作戰持續時間內發揮著截然不同的作用，也就具有了不同的待修裝備優先級。

本文采用節點重要度作為待修裝備優先級的評價參數，基于戰場搶修原則“優先搶修指揮裝備，爾后搶修主戰裝備”，通過定性分析，得到待修裝備的節點重要度排序如下，從高到低分別是：高級別指揮裝備，主攻方向的低級別指揮裝備，助攻方向的低級別指揮裝備，主攻方向的主戰裝備，助攻方向的主戰裝備。本文分別將上述5種裝備的節點重要度分成5個等級：A、B、C、D、E.

3 模型求解方法設計

由于MDBTSPN是NP問題，針對其待修裝備規模大、需要不斷進行動態規劃的特點，本文設計并編程實現遺傳算法進行求解。

3.1 多目標處理方法確定

若采用經典的多目標決策方法處理MDBTSPN，如加權和方法、ε-約束法、目標規劃法、極小極大法等，可通過不同方法將多目標優化問題轉化為單目標優化問題進行求解。雖簡單高效，但存在：1)參數的選取依賴于MDBTSPN的先驗知識，不同的參數設置會產生不同的Pareto最優解；2)在大多數情況下，只能得到一個Pareto最優解，且該解的獲取與參數設定存在很大關系。

帶精英策略的非支配排序遺傳算法(NSGA-II)[16]是非支配排序遺傳算法 (NSGA)的改進算法，具有以下優點：1)提出的快速NSGA降低了計算的復雜度；2)采用擁擠距離比較算子代替了適值度共享方法，使得準Pareto域中的個體能均勻地擴展到整個Pareto域，保證了種群的多樣性；3)引入了精英保留機制，有利于保存種群中的優良個體，提高種群的整體進化水平。

基于此，本文采用NSGA-II對MDBTSPN中的多目標問題進行處理，其核心是快速NSGA和擁擠距離比較算子的實現，目標是得到多個滿意解或可接受的非劣解(即Pareto最優解)。在第η次調度中，首先求出MDBTSPN的Pareto最優解集，爾后裝備保障指揮員根據該時刻的戰場態勢和決策策略，從Pareto最優解集選擇出最滿意解。

3.2 編碼與解碼設計

本文通過編碼與解碼來解決搶修任務動態調度中的非遍歷約束，其解決思路為：1)通過設計兩段式編碼方式實現遍歷情況下的搶修任務分配；2)通過非遍歷約束及解碼，計算得到截點位置信息，依靠截點位置來確保非遍歷約束的實現。

在兩段式編碼中，前段采用順序編碼，用以確定搶修組間的任務分工；后段采用整數編碼，用以表示斷點位置。該編碼方式簡單直觀，不僅滿足了約束條件中的(10)式和(11)式，且染色體與解一一對應，遺傳操作不會產生不可行解。

編碼示例如圖1所示，設定某染色體X=(3,10,2,6,8,1,7,4,5,9,3,7),|J|=10,m=3，斷點為(3,7)，用豎虛線表示。

圖1 編碼示例Fig.1 Encoding example

解碼時，根據約束條件中的(9)式～(12)式及其他約束，編程計算出截點位置和適應值，進而可求得3個搶修組的任務分工、各組搶修序列、該染色體的適應值。

圖2 解碼示例Fig.2 Decoding example

3.3 遺傳算子設計

染色體由2段編碼組成，各段編碼方式與現實意義各不相同，無法直接采用模擬二元交叉等方式進行交叉變異。為增大搜索范圍、方便快速收斂，本文設計了融合式遺傳操作算子，即采用二元錦標賽選擇從上一代染色體中選出1/4的個體作為父代染色，對每一條父代染色體進行下列4種操作：

1)前段采用倒置操作，后段采用隨機更新操作；

2)前段采用滑動平移操作，后段采用隨機更新操作；

3)前段采用互換操作，后段采用隨機更新操作；

4)前段不進行任何操作，后段采用隨機更新操作。

將遺傳操作產生的子代染色體與父代染色體按適應值大小進行整體降序排列，取前pop_size條作為新的染色體種群。

3.4 算法流程設計

基于遺傳算法的搶修任務動態調度總體算法流程，如圖3所示。

圖3 總體算法流程Fig.3 Flow chart of overall algorithm

具體步驟如下：

1)初始化相關參數。

2)生成初始規劃路徑種群{S}。

4)采用NSGA-II進行非支配排序和個體間擁擠距離計算。

5)令iter=1.

6)采用二元錦標賽選擇從pop_chm中優選出數量規模為pool_size的parent_chm.

7)進行遺傳操作，產生offspring_chm.

9)運用NSGA-II對集合{parent_chm,offspring_chm}進行快速非支配排序和個體間擁擠距離計算。

10)利用二元錦標賽選擇和比較算子從{parent_chm,offspring_chm}中篩選出基因較優的新一代pop_chm.

11)判斷iter≤num_iter？成立，轉步驟12；否則，轉步驟13.

12)iter=iter+1，轉步驟5，進行新一輪尋優。

13)停止迭代，得到本次搶修任務調度的Pareto最優解集，依據該時刻的決策策略從Pareto最優解集中選出最滿意解，轉步驟14.

14)判斷重調度驅動策略是否滿足？是，轉步驟15進行重調度；否則，轉步驟25.

15)令k=1.

22)判斷k<|K|?成立，轉步驟23；否則，轉步驟24.

23)k=k+1，轉步驟16.

25)輸出結果。

3.5 算法復雜度分析

對于搶修任務動態調度問題，設其種群規模為P，迭代次數為G，問題規模為N，目標數量為T. 本文設計的遺傳算法，其算法復雜度可分析如下：

1)初始化算子的時間復雜度是O(PN2)；

2)解碼算子的時間復雜度是O(N2)；

3)快速非支配排序算子的時間復雜度是O(TN2)；

4)選擇算子的時間復雜度是O(P)；

5)遺傳操作算子的時間復雜度是O(PN2)；

6)替換算子的時間復雜度是O(N)；

7)狀態判斷算子的時間復雜度是O(N2)。

根據遺傳算法的框架，可計算其時間復雜度：

O=O(PN2)+O(TN2)+G(O(P)+O(PN2)+
O(TN2)+O(N))+O(N2)≈GPO(N2)。

分析決定該算法時間復雜度的核心因素，在于遺傳操作算子。而本文為實現父代染色體的交叉變異而設計的4種遺傳操作算子，其本身的時間復雜度為O(P)，并不會導致較高的時間復雜度。究其原因，是因為遺傳操作算子內含著解碼算子，且解碼算子的時間復雜度是O(N2). 而導致解碼算子時間復雜度較高的原因在于，本文為解決搶修任務動態調度問題的多個實際約束(包括不同搶修組的任務分工、同一搶修組的搶修序列、非遍歷)，設計了兩段式編碼，且前段采用了實數編碼。而實數編碼在解碼過程中需要耗費大量時間來計算染色體的截點位置信息，以及各個目標函數的適應值。

4 示例仿真與分析

4.1 示例仿真

某月某日，M國以其機步101團為核心，對我西北邊境Q地區突然發動進攻，突襲失利后，轉入機動防御。我數字化機步27師遵照上級命令擔任主攻任務，務求15 h內殲驅該敵。27師部署100臺步兵戰車、30臺主戰坦克、30臺裝甲突擊車；配署3個綜合搶修組，采用全域伴隨保障模式，負責搶修120 min內能完成的輕度損傷及極少部分中度損傷的作戰裝備。進攻作戰持續時間內，戰損裝備不斷出現，如何動態地確定不同搶修組間的任務分工以及同一搶修組內的修理順序。

表1 待修裝備信息

已知t=54 min時，戰場已出現3輛損傷裝備，此時搶修1組、2組、3組伴隨進攻部隊分別前進到(-2.8 km，-4.0 km)、(-15.7 km，-3.1 km)、(15.9 km，-5.6 km) 3點；裝備保障指揮員下達指令，將其均分給3個搶修組。設定數量分批驅動策略閾值trg_num=5，爾后每次新的搶修需求達到閾值，即進行一次重調度，并運用算法求解。各搶修組的搶修力量變化信息如表2所示。

裝備保障指揮員的既定決策策略為：對Pareto最優解集進行無量綱化處理，并采用加權法優選出最滿意方案：

表2 搶修力量變化信息

(16)

式中：α、β為權重系數。

作戰初期(當t<300 min)，需要較高的裝備參戰率以保證殲敵有生力量的順利執行，α取較大值，α=0.7，β=0.3. 作戰中后期(當t≥300 min)，為更有效地達成作戰目的，作戰裝備間需要相互聯合，β取較大值，α=0.4，β=0.6.

上述MDBTSPN案例，規劃結果如表3所示。各搶修組的最終搶修序列如圖4所示。

表3 規劃結果

注：“無”表示該搶修組到重調度的開始時刻，已完成搶修序列中的所有任務，不存在關鍵點。

圖4 最終搶修序列圖Fig.4 Diagram of final rush-repair sequence

4.2 結果分析

1)由表3分析可知，到進攻戰斗結束時，經搶修獲得的二次作戰總時間為11 103 min，約185 h；相當于為進攻部隊增添了18輛可以參與10 h進攻作戰的戰斗裝備，間接證明了實施伴隨保障的重要性和建強伴隨保障力量的必要性。

2)由表3分析可知，在時刻378 min，規劃結果將待修裝備22(故障時刻為370 min)安排在搶修1組的第7搶修順位；但在時刻463 min進行重調度時，搶修1組還在搶修其他“關鍵點”裝備19，待修裝備22參與重調度，最后將其規劃到搶修2組的第7順位，并在時刻799 min才完成了搶修。類似的還有待修裝備13、14、16、20、27. 雖然每一個搶修組的搶修序列對其自身而言不一定最優，但在各個規劃時刻對整體而言是最優的。這樣的動態調度為待修裝備贏得了更多的修竣裝備總量、節點重要度總和以及二次作戰時間，直接證明了動態調度的優越性。

3)由表3分析可知，在時刻327 min和378 min，根據規劃結果，待修裝備17(故障時刻為193 min)分別被安排在搶修3組的第5順位和第8順位，但最終放棄了對其進行搶修。類似的“先被列入搶修計劃，后又被放棄搶修”的待修裝備還有10、14. 究其原因，在進攻作戰初期，戰損裝備相對較少且搶修時間充裕，搶修組對所有待修裝備進行遍歷型搶修；隨著累積的損傷裝備越來越多，搶修組在規定時間內已無法完成對所有損傷裝備的修理，只能進行非遍歷型搶修；結果顯示到進攻作戰結束時刻，還有13輛損傷裝備尚未進行搶修。這直接突顯了非遍歷型搶修與遍歷型搶修的差異所在，且與戰場搶修實際情況更加貼合。

4)深入分析表3和圖4可知，在327 min，待修裝備12和待修裝備15同時參與重調度，搶修2組在完成關鍵點任務6后，放棄了節點重要度較高的待修裝備15，優先修理了距離更近且維修工作量更小的待修裝備12，體現了“優先搶修維修工作量小的戰損裝備”搶修原則。與此相反，在463 min，待修裝備22和待修裝備24同時參與重調度，搶修2組在完成關鍵點任務15后，放棄了距離更近的待修裝備22，優先修理了裝備優先級較高的待修裝備24，體現了“優先搶修指揮裝備，而后作戰裝備”的搶修原則。究其原因，為謀求整體搶修效果的最優(即獲得盡可能多的修竣裝備總量、節點重要度總和以及二次作戰時間總和)，MDBTSPN綜合權衡了多項搶修原則，通過算法在維修工作量大小、轉場路程遠近、待修裝備優先級高低等多個相互制約的因素間進行了結果尋優。

5)由圖4分析可知，在進行待修裝備眾多而Te有限的搶修任務動態調度時，將相繼出現遍歷型搶修與非遍歷型搶修兩種形態，最終各搶修組的任務分工呈現出相互交叉的全域保障趨勢，旨在通過搶修組間的相互協作，在Te內從整體上謀得最佳的搶修效果，以維持進攻部隊的持續進攻能力。

6)與此同時，由于待修裝備眾多，不同搶修組間的任務分工和同一搶修組內的搶修序列可能排列情況眾多，以時刻463 min時的重調度為例，即有2.964 1×1012種可能的排列情況，人為找尋最優解難度大、耗時久；若戰損裝備數量較大，在有限時間內人為計算最優解幾乎不可能。利用MDBTSPN模型及遺傳算法編程求解，便于根據戰場實際態勢，調整模型參數及輸入，動態、高效地求得問題的最優解。

5 結論

本文提出了MDBTSPN的現實軍事問題，建立了其數學模型，設計并實現了基于遺傳算法的模型求解，通過示例驗證了模型能夠有效解決非遍歷型尋優難題、動態追蹤問題的滿意解。研究結論如下：

1)通過實施機動伴隨搶修和搶修任務動態調度，能夠獲得約185 h的二次作戰總時間，相當于增加了18輛可以參與10 h進攻作戰的戰斗裝備，能夠有力增強進攻部隊的持續作戰能力。

2)在進攻作戰進程中，MDBTSPN模型及求解算法能夠根據不斷變化的搶修需求，不斷調整搶修單元間的任務分工及搶修單元內的搶修序列，進而獲得更高的搶修效益。

3)MDBTSPN模型及求解算法能夠將“遍歷”這一約束條件松弛為“非遍歷”，擴大了模型的適用范圍，且更加貼合作戰實際。

4)MDBTSPN模型及求解算法能夠大大減少保障指揮員的決策工作量和決策時間，降低人為決策風險，并提高搶修效益。

下一步主要研究方向：考慮不同重調度驅動策略對搶修任務動態調度結果的影響。

References)

[1] 王正元, 朱昱, 宋建社, 等. 動態維修任務調度的優化方法[J]. 機械工程學報, 2008, 44(1): 92-97. WANG Zheng-yuan, ZHU Yu, SONG Jian-she, et al. Optimal method on dynamic maintenance task scheduling [J]. Chinese Journal of Mechanical Engineering, 2008, 44(1): 92-97.(in Chinese)

[2] 王正元, 嚴小琴, 朱昱, 等. 一種考慮專業的動態維修任務調度的優化方法[J]. 兵工學報, 2009, 30(2): 252-256. WANG Zheng-yuan, YAN Xiao-qin, ZHU Yu, et al. An optimal method on dynamic maintenance task scheduling with subject taken into account[J]. Acta Armamentarii, 2009, 30(2): 252-256. (in Chinese)

[3] 曹繼平, 宋建社, 朱昱, 等. 戰場搶修多需求點多資源優化調度研究[J]. 兵工學報, 2008, 29(8): 995-1000. CAO Ji-ping, SONG Jian-she, ZHU Yu, et al. Research on battlefield maintenance optimization scheduling of multi-requirement-points and multi-resources[J]. Acta Armamentarii, 2008, 29(8): 995-1000. (in Chinese)

[4] 郭軍, 宋建社, 楊檬, 等. 基于證據理論的多任務搶修重要度決策[J]. 系統工程與電子技術, 2011, 33(3): 581-584. GUO Jun, SONG Jian-she, YANG Meng, et al. Recovery importance decision making for multi-missions based on Dempster-Shafer theory[J]. Systems Engineering and Electronic, 2011, 33(3): 581-584. (in Chinese)

[5] 郭軍, 宋建社, 曹繼平, 等. 戰場搶修資源重組決策方法[J]. 系統工程與電子技術, 2014, 36(2): 306-311. GUO Jun, SONG Jian-she, CAO Ji-ping, et al. Battlefield urgent maintenance resource recombination decision making[J]. Systems Engineering and Electronics, 2014, 36(2): 306-311. (in Chinese)

[6] Pillac V, Gendreau M, Guéret C, et al. A review of dynamic vehicle routing problems[J]. European Journal of Operational Research, 2013, 225(1): 1-11.

[7] Liu C H, Hsu C I. Dynamic job shop scheduling with fixed interval deliveries[J]. Production Engineering, 2015, 9(3): 377-391.

[8] Kuzmanovska A, Mak R H, Epema D. Dynamically scheduling a component-based framework in clusters[J]. Lecture Notes in Computer Science, 2015, 8828: 129-146.

[9] Moon S, Oh E, Shim D H. An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments[J]. Journal of Intelligent and Robotic Systems, 2013, 70(1): 303-313.

[10] Sarasola B, Doerner K F, Schmid V, et al. Variable neighborhood search for the stochastic and dynamic vehicle routing problem[J]. Annals of Operations Research, 2016, 236(2): 425-461.

[11] Schneider M. The vehicle-routing problem with time windows and driver-specific times[J]. European Journal of Operational Research, 2016, 250(1): 101-119.

[12] Yepes V, Medina J. Economic heuristic optimization for heterogeneous fleet VRPHESTW[J]. Journal of Transportation Engineering, 2015, 132(4): 303-311.

[13] Lorini S, Potvin J Y, Zufferey N. Online vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research, 2011, 38(7): 1086-1090.

[14] Letchforda A N, Nasiri S D. The Steiner travelling salesman problem with correlated costs[J]. European Journal of Operational Research, 2015, 245: 62-69.

[15] Akar E, Topcuoglu H R, Ermis M. Hyper-heuristics for online UAV path planning under imperfect information[J]. Lecture Notes in Computer Science ,2014, 8602:741-752.

[16] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

Multi-objective and Dynamic Scheduling of Battlefield Rush-repair Tasks Based on Non-ergodicity

CHEN Chun-liang1, CHEN Wei-long1, CHEN Kang-zhu2, LIU Yan1, SHI Xian-ming3

(1.Department of Technical Support Engineering, Academy of Armored Force Engineering, Beijing 100072, China;2.Department of Training, Academy of Armored Force Engineering,Beijing 100072, China;3.Department of Equipment Command and Management, Ordinance Engineering College,Shijiazhuang 050003, Hebei, China)

In the offensive operation, equipment is constantly damaged, but the battlefield rush-repair time and power are limited. The dynamic scheduling of battlefield rush-repair tasks in the offensive operation is studied. A multi-objective and dynamic scheduling of battlefield rush-repair tasks based on non-ergodicity, which is a real military problem, is presented. A mathematical model of multi-objective programming is established. Three key factors, including non-ergodicity, repair ability difference and priority of equipment to be repaired, are analyzed. A scheduling example of 39 equipment to be repaired and 3 repair groups is simulated and analyzed by using Matlab. The simulated result shows that the proposed model is scientific and reasonable, and the algorithm is correct and efficient, which can effectively solve the difficult problem of non-ergodic optimization and dynamically track the change of the optimal solution.

ordnance science and technology; battlefield rush-repair; dynamic scheduling; non-ergodicity; genetic algorithm

2017-01-05

陳偉龍(1988—)，男，博士研究生。E-mail:amose_chen@163.com

陳春良(1963—)，男，教授，博士生導師。E-mail: chen1963@126.com

E92

A

1000-1093(2017)08-1593-10

10.3969/j.issn.1000-1093.2017.08.018