面向多維修中心的資源受限任務調度問題研究

齊小剛，陳玲琳，宋衛星，王亞洲，劉立芳

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

當今信息化作戰條件下，充分利用戰場信息資源、合理進行維修任務調度，影響著我軍作戰勝利使命的完成。首先，戰時維修時間有限，我軍需合理進行任務調度以快速恢復故障裝備作戰能力；其次，裝備的研制也需要合適的調度，以減少費用[1-2]；再次，戰時維修任務時間緊迫，維修資源有限，如何在最短的時間內合理安排各工序的順序，分配維修保障資源使得調度方案最優也是至關重要的[3-4]。

1 資源約束的任務調度

資源約束的維修任務調度涉及任務的分配，以解決由誰完成何種任務的指派問題。是裝備保障實施的直觀表現。裝備保障任務調度流程復雜、約束眾多，且涉及循環往復的不斷優化，詳情如圖1 所示。

圖1 裝備維修任務調度基本流程及約束條件Fig.1 Basic process and constraints of equipment maintenance task scheduling

1.1 維修資源分類

維修資源分配需要分類資源以便實際管理與后續研究。《軍用裝備維修基本術語》將維修保障資源表述為“人力、設備、備件、花費、技術、信息和工時的統一”[4]。維修資源分消耗性資源和復制性資源，如圖2 所示。

圖2 裝備維修保障資源分類圖Fig.2 Classification chart of equipment maintenance support resources

1) 消耗性資源

主要包括維修設備、備件和技術材料等。

2) 非消耗性資源

指人力資源，如執行維修的技工和組織管理方案的人員。本文主要考慮技工。維修人力資源須有專業技能，如液壓、機械等。且維修人力資源根據工作時長、學歷等，可分為初、中、高級工。

3) 復制性資源

常指信息資源。維修產生的數據即為信息。

1.2 優先級評估

根據故障裝備屬性（如重要度，資源需求）及維修資源的有限性，需要為維修任務制定優先級。綜合考量中外軍事經驗，得以下結論：戰時裝備作用大則先維修；故障裝備易修復則先維修；耗時少則先維修；可修性好則先維修。故維修任務優先級評估指標如下[5]：

1) 重要級別：根據作戰功能大小得出；

2) 技術狀態：采用技術狀態系數評估；

3) 耗費工時：開始至完成維修的時間；

4) 所需設備：根據所需設備數及獲取難度劃分級別；

5) 所需技術：根據維修水平將所需技術劃分；

6) 可維修性：采用可維修性系數評估。

優先級評估流程如圖3 所示。

圖3 任務優先級評估流程Fig.3 Task priority assessment process

1.3 維修調度模型

維修調度方案的合理性影響著維修的時效性，如縮短時間、增大效益等。陸軍維修形式有自修、伴隨修理、巡回修理、定點修理、戰區后方修理等。野戰時伴隨、巡回、定點修理起至關重要的作用[6]。

近年來，部分學者對維修任務調度進行了研究[7]。模型方面，文獻[8]研究了雙目標排流車間調度問題，并采用NSGA-II 算法求解；文獻[9]提出了涉及剩余壽命的調度模型，采用改進遺傳算法求解；文獻[10]提出了魯棒雙目標混合整數線性規劃模型，在不確定條件下同時最小化維修總成本和最大化任務總浮動；文獻[11]在車輛正常運行的情況下，模擬車輛的周期維修，在給定的時間內安排維修任務，優化車輛運營、降低成本和提高服務可靠性；文獻[12]提出了帶重調度的維修方案，信息跟新后進行重調度；文獻[13]利用混合粒子群遺傳算法解決無人機裝備軍事維修任務調度問題；文獻[14]提出了混合整數線性規劃以優化列車運行維修延成文；文獻[15]研究了任務優先級，改善馬氏距離，并提出了逼近理想解排序法；文獻[16] 以優化維修重要度為目標，采用改進蟻群算法求解；文獻[17-18]給出的方案可用于伴隨維修；文獻[19]利用采用離散事件仿真對定點維修任務調度求解。

1.4 動態調度算法

其中，因戰時維修任務多、時間緊，維修部隊趕至戰損裝備處的伴隨維修，可參考動態車輛路徑問題(dynamic vehicle routing problem,DVRP)或動態旅行商問題(dynamic traveling salesman problem,DTSP)以求解[20]。

1) 靜態化動態問題

目前研究成果常對動態調度靜態化轉換[21]以求解。文獻[22]分割調度時間，將動態車輛路徑問題靜態化；文獻[23]對DVRP 優化時間選擇以靜態化求解；文獻[24]拆分DVRP 為車輛選擇及路線優化問題，并兩階段法數學規劃求解；文獻[25]動態調度多維修點、多任務、多維修隊，劃分時間保證任務優先級以實現靜態化求解。

2) 靜態問題算法

維修任務調度是NP-hard 問題，需采用模擬退火、禁忌搜索等算法求解。模擬退火算法[26]采用蒙特卡羅迭代求解，效果良好但收斂緩慢；禁忌搜索算法[27]采用禁忌表避免重復搜索，對初始解敏感；遺傳算法[28]采用選擇、交叉、變異算子對初始種群進行優化，搜索能力強但速度緩慢；人工智能方法采用智能系統動態優化，如神經網絡[29]、專家系統[30]、蟻群算法[31]、粒子群算法[32]等。

綜上，當前針對資源受限的任務調度問題研究仍存在以下問題：

1) 目前對于裝備維修保障的研究與作戰實踐背景、任務裝備重要度等結合不夠緊密。

2) 裝備維修保障任務種類多、需求大，在資源有限情況下，必須優先修復關鍵裝備，故確定任務優先級是首要工作。現階段對任務優先級的研究常忽略了裝備重要度。

3) 信息化條件下，保障需求可及時傳達，這對維修時效性要求更加苛刻。但現階段任務調度常為靜態問題，不能滿足實際需求。

2 工序調度

軍用裝備保障對象復雜、要素眾多、環境多變。任務調度需要根據維修保障任務與資源的關系及任務間工序的關系，建立約束性規則，主要包括：

1) 資源充足前提下，任務才能開始；

2) 維修任務須按工序流程進行；

3) 正在使用的資源不得同時被任務占用，直到任務完成；

4) 維修任務獨立，任務間互不影響。

在最短時間內形成維修保障工序調度方案，可提升保障效能。維修時人員分配不當、維修調度不周等影響任務完工時間，資源受限工序調度詣在合理的安排工序調度以縮短工時、減少成本，可轉化為資源受限項目調度問題(resourceconstrained project scheduling problem,RCPSP)。

裝備維修工序調度流程如圖4 所示。常見調度問題如下：

圖4 裝備維修工序調度流程Fig.4 Equipment maintenance process scheduling process

2.1 RCPSP 與PRCPSP

目前，RCPSP 充分應用于各場景。此外，非搶占式RCPSP[33]以及搶占式PRCPSP(preemptive resource-constrained project scheduling problem,PRCPSP)[28]的應用取決于：該工序可否暫停，占用的資源被另一工序使用。研究表明，搶占可高度利用資源，減少閑置情況，從而減小工時。文獻[33]對離散PRCPSP 問題，在整數時刻對工序進行搶占，并分為一次搶占和多次搶占。

1) RCPSP

一個任務由n個工序i=1,2,···,n組成，給定任務維修時間范圍 [0,T]，K種資源中資源k擁有量Rk，工序i需資源k數量rik，工序對資源的需求不大于該資源總量。工序i維修時間di。虛擬工序i=0 和i=n+1表示任務的開始和結束，不占用維修時間和資源。工序i開始時間si，完成時間ci，則si+di=ci。假設工序不允許搶占。采用圖G(V,E)表示任務網絡，工序集合為V={0,1,···,n+1}，弧集合為E={(i,j)|i,j∈V,i→j}，表示工序i是j的緊前工序。工序i緊前工序集合 pre(i)={j|(j,i)∈E}，工序i的后繼活動集合 suc(i)={j|(i,j)∈E}。RCPSP 主要約束有時序和資源約束，最小化任務完成時間為優化目標[34]。RCPSP 概念性模型為

其中：式(1)為目標函數；式(2)為工序時序約束；式(3) 為資源約束；式(4) 說明從時刻0 開始維修；式(5)限制工序開始時間為非負整數。

2) PRCPSP

若允許搶占發生在整數時間點，則為離散搶占；若允許搶占發生在任意時間點，則稱為連續搶占。

PRCPSP 概念性模型為

其中：式(6)為目標函數；式(7)表示時刻0 開始維修；式(8)為時序約束，工序i的完成后工序j開始；式(9)表示子工序的優先關系，子活動iip結束后ip+1開 始；式(10)表示工序i工時等于子工序工時之和；式(11)表示工序資源限制；式(12)表示子工序開始時刻和工時為非負整數；拆分工序i的子工序p開始時間sip，工序工期dip。

2.2 其他調度問題

1) 目標函數

經典的RCPSP 數學模型是以工期最短為目標，但實際維修保障中，單一指標難以評價方案優劣，決策者常需考慮多個指標并進行權衡。

對于維修資源受限式維修工序調度問題，需要考慮的目標有以下幾個：

①最小化項目工期：

該式最小化最后虛擬活動的開始時間，等價于最小化項目工期[35-36]。

②最小化項目拖期：

該式最小化活動加權拖期之和，其中活動i拖期嚴重程度 βi，活動i實際完成時間fi，計劃交付時間Di。該目標適于有時間限制調度問題[37]。

③資源均衡：

該式最小化資源使用量平方加權和。時刻t需資源k數量時刻t正在執行活動集合Vt={i|si,p≤t≤si,p+di,p}。資源均衡可確保資源利用穩定，是項目調度的重要目標[38]。

④最小化資源可用量成本：

其中，活動中斷成本z。該目標函數增加了活動搶占成本[39]。

2) 約束條件

對于工序調度，資源是非常重要的約束條件。裝備維修保障資源分為可更新資源、消耗性資源以及雙重資源。

1) 可更新資源在每個時刻的供應鏈是有限的，并不隨維修保障的進度而消耗，例如人力、設備等。可更新資源約束表示：

對人力資源進行再進一步的劃分，有不同維修作業對用的維修人員種類以及根據不同維修能力不同導致的維修時間不等將維修人員劃分為不同等級：

2) 消耗性資源是在裝備維修保障作業啟動時以總量出現，并隨著作業進展逐漸消耗的資源，例如各種原材料、能源等。消耗性資源的約束表示為

3) 時序約束：根據工藝要求限制工序順序。如工序i未結束，工序j不開始。

2.3 常用算法

常用遺傳算法、禁忌搜索等算法解決任務調度問題。這些算法需合理編碼，產生隨機方案集并不斷篩選更新種群，以求解問題。

2.3.1 編碼

1) 活動編碼[40]前部分表示子工序，后部分表示工序工時；

2) 資源編碼[41]表示工序維修在某時間內消耗資源量；

3) 優先級編碼[42]前部分表示子工序，后部分表示占用工時。

2.3.2 解碼

調度方案(schedule generation scheme,SGS)有：

1)串行調度方案(serial SGS,SSGS)

SGS 隨工序展開而進行擴展[43]，分為J個階段，階段n有對應不完全計劃 PSn和對應的可行工序集En={j|j?PSn,Pj∈PSn}。調度中新階段n，選擇En中某工序并入 PSn，工序開始時間滿足資源和緊前約束。設工序j最晚開始時間 STj，在t階段，正在維修的工序集合At，資源k剩余量Rkt，則有任務工期上限串行調度方案產生流程為

①初始化n:=1,PSn:={1},ST1=0

2)并行調度方案(parallel SGS,PSGS)

PSGS 隨時間進行擴展[43]，包含J個階段，階段n調度時刻tn的 3 個工序集合：已完成工序Cn、正在維修工序An和可進行維修工序En，滿足：En=

并行調度方案產生從階段n到階段n+1描述如下：

①計算tn+1，Cn+1，An+1，更新資源剩余量 πRkt和En+1；

②若En+1中 的工序j資源需求不超過資源剩余量，則執行j，更新En+1，重復2) 直至En+1為空。并行調度方案產生流程如下：

①初始化：

③如果En≠空，繼續執行②，否則n:=n+1

在解決問題方面，目前研究常建立多約束模型并利用啟發式算法求解。但當前研究不能很好滿足實際的RCPSP 問題，文獻[44]采用一種改進的離散布谷鳥搜索算法（IDCS）來解決RCPSP 問題，將搜索空間劃分為多個區域，每個子群體將專注于在其指定區域內搜索解決方案；文獻[45]考慮到每個活動都有固定的持續時間和資源需求，將其建模為一個矩形塊，其高度代表資源需求，寬度代表持續時間，將移動塊序列解碼為有效的時間表，根據每個區塊如何從其初始位置移動到適當位置的情況，設計了4 種移動模式，以最大限度地縮短項目的完成時間，并采用多智能體進化算法（MAEA）求解RCPSP 問題；文獻[46]通過在最大的分割次數和最小的連續執行周期的約束條件下，研究在離散時間點上分割活動的資源約束項目調度的并行調度方案產生流程問題；文獻[47]通過將每個任務的處理時間被建模為其開始時間和特定退化日期的階躍函數，利用改進的禁忌搜索算法進行求解，提出了基于問題特征的4 種鄰域結構和兩種變異算子；文獻[48]提出基于分散搜索的混合元啟發式算法對工期最小資源約束項目調度問題求解；文獻[49]提出基于蟻群的元啟發式算法對考慮搶占懲罰的多技能資源約束項目調度問題求解；文獻[50]提出兩階段優化算法對考慮人員能力差異的RCPSP 求解；文獻[51]研究了連續時間柔性資源配置的項目調度問題；文獻[52]采用預處理和在線調度兩階段策略及兩階段局部搜索對項目時間隨機的資源約束調度問題求解。

綜上，在裝備維修工序調度算法設計時，應當考慮以下兩方面的因素：

在實際維修中，人員進行下一工序維修時需要切換時間，故可考慮帶有懲罰時間的多次隨機搶占方案在實際調度中的應用。

現有調度問題多以最小工期為單目標優化，但實際需考慮人員多技能、勝任力差異等問題，單一目標難以符合實際調度。

3 結束語

現階段的一體化作戰信息系統，對取得優秀的裝備維修效果具有重要意義。需要根據瞬息萬變的戰場情況及時更新信息，動態調度任務。目前任務調度研究存在以下問題：

1) 多數研究建立的是靜態模型，或將動態模型轉化為靜態模型，但實際需動態的任務調度。

2) 多數研究針對定點維修調度問題，野戰維修調度研究較少。

3) 對于維修任務的優先級確定也需要進一步結合戰時具體情況進行分析。考慮的優化目標相對單一。

4) 對帶有懲罰函數的搶占式維修工序調度問題沒有很好地應用于軍用裝備維修保障系統內。

具體的研究方法和解決方案如下：

1) 實現平時、戰時不同條件下的裝備維修任務調度。

2) 單任務內部的工序調度問題需考慮備件、人員等因素，使其更加符合實際的調度問題。

3) 在搶占式的工序調度問題中，搶占的次數往往是固定的，可以將搶占次數設計為隨機的，求解出最佳的搶占次數，使得搶占機制更加靈活，結果更加準確。

4) 目前所提出的任務調度算法有一定的局限性，不僅要考慮動態的調度算法，還需要將多種算法有效結合起來，使優化效果更加明顯。

新時代情況下，我軍裝備維修調度研究急需符合實際情況。需不斷探索對新型裝備和技術，且根據平時、戰時等情況分類研究。以合理資源分配、合理任務調度，提高保障效能。