面向多維修中心的資源受限任務(wù)調(diào)度問題研究

齊小剛，陳玲琳，宋衛(wèi)星，王亞洲，劉立芳

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

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

1 資源約束的任務(wù)調(diào)度

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

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

1.1 維修資源分類

維修資源分配需要分類資源以便實際管理與后續(xù)研究?！盾娪醚b備維修基本術(shù)語》將維修保障資源表述為“人力、設(shè)備、備件、花費、技術(shù)、信息和工時的統(tǒng)一”[4]。維修資源分消耗性資源和復(fù)制性資源，如圖2 所示。

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

1) 消耗性資源

主要包括維修設(shè)備、備件和技術(shù)材料等。

2) 非消耗性資源

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

3) 復(fù)制性資源

常指信息資源。維修產(chǎn)生的數(shù)據(jù)即為信息。

1.2 優(yōu)先級評估

根據(jù)故障裝備屬性（如重要度，資源需求）及維修資源的有限性，需要為維修任務(wù)制定優(yōu)先級。綜合考量中外軍事經(jīng)驗，得以下結(jié)論：戰(zhàn)時裝備作用大則先維修；故障裝備易修復(fù)則先維修；耗時少則先維修；可修性好則先維修。故維修任務(wù)優(yōu)先級評估指標(biāo)如下[5]：

1) 重要級別：根據(jù)作戰(zhàn)功能大小得出；

2) 技術(shù)狀態(tài)：采用技術(shù)狀態(tài)系數(shù)評估；

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

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

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

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

優(yōu)先級評估流程如圖3 所示。

圖3 任務(wù)優(yōu)先級評估流程Fig.3 Task priority assessment process

1.3 維修調(diào)度模型

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

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

1.4 動態(tài)調(diào)度算法

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

1) 靜態(tài)化動態(tài)問題

目前研究成果常對動態(tài)調(diào)度靜態(tài)化轉(zhuǎn)換[21]以求解。文獻(xiàn)[22]分割調(diào)度時間，將動態(tài)車輛路徑問題靜態(tài)化；文獻(xiàn)[23]對DVRP 優(yōu)化時間選擇以靜態(tài)化求解；文獻(xiàn)[24]拆分DVRP 為車輛選擇及路線優(yōu)化問題，并兩階段法數(shù)學(xué)規(guī)劃求解；文獻(xiàn)[25]動態(tài)調(diào)度多維修點、多任務(wù)、多維修隊，劃分時間保證任務(wù)優(yōu)先級以實現(xiàn)靜態(tài)化求解。

2) 靜態(tài)問題算法

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

綜上，當(dāng)前針對資源受限的任務(wù)調(diào)度問題研究仍存在以下問題：

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

2) 裝備維修保障任務(wù)種類多、需求大，在資源有限情況下，必須優(yōu)先修復(fù)關(guān)鍵裝備，故確定任務(wù)優(yōu)先級是首要工作?，F(xiàn)階段對任務(wù)優(yōu)先級的研究常忽略了裝備重要度。

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

2 工序調(diào)度

軍用裝備保障對象復(fù)雜、要素眾多、環(huán)境多變。任務(wù)調(diào)度需要根據(jù)維修保障任務(wù)與資源的關(guān)系及任務(wù)間工序的關(guān)系，建立約束性規(guī)則，主要包括：

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

2) 維修任務(wù)須按工序流程進(jìn)行；

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

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

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

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

圖4 裝備維修工序調(diào)度流程Fig.4 Equipment maintenance process scheduling process

2.1 RCPSP 與PRCPSP

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

1) RCPSP

一個任務(wù)由n個工序i=1,2,···,n組成，給定任務(wù)維修時間范圍 [0,T]，K種資源中資源k擁有量Rk，工序i需資源k數(shù)量rik，工序?qū)Y源的需求不大于該資源總量。工序i維修時間di。虛擬工序i=0 和i=n+1表示任務(wù)的開始和結(jié)束，不占用維修時間和資源。工序i開始時間si，完成時間ci，則si+di=ci。假設(shè)工序不允許搶占。采用圖G(V,E)表示任務(wù)網(wǎng)絡(luò)，工序集合為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 主要約束有時序和資源約束，最小化任務(wù)完成時間為優(yōu)化目標(biāo)[34]。RCPSP 概念性模型為

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

2) PRCPSP

若允許搶占發(fā)生在整數(shù)時間點，則為離散搶占；若允許搶占發(fā)生在任意時間點，則稱為連續(xù)搶占。

PRCPSP 概念性模型為

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

2.2 其他調(diào)度問題

1) 目標(biāo)函數(shù)

經(jīng)典的RCPSP 數(shù)學(xué)模型是以工期最短為目標(biāo)，但實際維修保障中，單一指標(biāo)難以評價方案優(yōu)劣，決策者常需考慮多個指標(biāo)并進(jìn)行權(quán)衡。

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

①最小化項目工期：

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

②最小化項目拖期：

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

③資源均衡：

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

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

其中，活動中斷成本z。該目標(biāo)函數(shù)增加了活動搶占成本[39]。

2) 約束條件

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

1) 可更新資源在每個時刻的供應(yīng)鏈?zhǔn)怯邢薜模⒉浑S維修保障的進(jìn)度而消耗，例如人力、設(shè)備等?？筛沦Y源約束表示：

對人力資源進(jìn)行再進(jìn)一步的劃分，有不同維修作業(yè)對用的維修人員種類以及根據(jù)不同維修能力不同導(dǎo)致的維修時間不等將維修人員劃分為不同等級：

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

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

2.3 常用算法

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

2.3.1 編碼

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

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

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

2.3.2 解碼

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

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

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

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

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

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

并行調(diào)度方案產(chǎn)生從階段n到階段n+1描述如下：

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

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

①初始化：

③如果En≠空，繼續(xù)執(zhí)行②，否則n:=n+1

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

綜上，在裝備維修工序調(diào)度算法設(shè)計時，應(yīng)當(dāng)考慮以下兩方面的因素：

在實際維修中，人員進(jìn)行下一工序維修時需要切換時間，故可考慮帶有懲罰時間的多次隨機搶占方案在實際調(diào)度中的應(yīng)用。

現(xiàn)有調(diào)度問題多以最小工期為單目標(biāo)優(yōu)化，但實際需考慮人員多技能、勝任力差異等問題，單一目標(biāo)難以符合實際調(diào)度。

3 結(jié)束語

現(xiàn)階段的一體化作戰(zhàn)信息系統(tǒng)，對取得優(yōu)秀的裝備維修效果具有重要意義。需要根據(jù)瞬息萬變的戰(zhàn)場情況及時更新信息，動態(tài)調(diào)度任務(wù)。目前任務(wù)調(diào)度研究存在以下問題：

1) 多數(shù)研究建立的是靜態(tài)模型，或?qū)討B(tài)模型轉(zhuǎn)化為靜態(tài)模型，但實際需動態(tài)的任務(wù)調(diào)度。

2) 多數(shù)研究針對定點維修調(diào)度問題，野戰(zhàn)維修調(diào)度研究較少。

3) 對于維修任務(wù)的優(yōu)先級確定也需要進(jìn)一步結(jié)合戰(zhàn)時具體情況進(jìn)行分析?？紤]的優(yōu)化目標(biāo)相對單一。

4) 對帶有懲罰函數(shù)的搶占式維修工序調(diào)度問題沒有很好地應(yīng)用于軍用裝備維修保障系統(tǒng)內(nèi)。

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

1) 實現(xiàn)平時、戰(zhàn)時不同條件下的裝備維修任務(wù)調(diào)度。

2) 單任務(wù)內(nèi)部的工序調(diào)度問題需考慮備件、人員等因素，使其更加符合實際的調(diào)度問題。

3) 在搶占式的工序調(diào)度問題中，搶占的次數(shù)往往是固定的，可以將搶占次數(shù)設(shè)計為隨機的，求解出最佳的搶占次數(shù)，使得搶占機制更加靈活，結(jié)果更加準(zhǔn)確。

4) 目前所提出的任務(wù)調(diào)度算法有一定的局限性，不僅要考慮動態(tài)的調(diào)度算法，還需要將多種算法有效結(jié)合起來，使優(yōu)化效果更加明顯。

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