資源受限裝備試驗鑒定任務調度建模與決策*

崔榮偉 趙佳音 張千利 李錦輝 方 成

（1.92785部隊 葫蘆島 125000）（2.92283部隊 上海 200463）（3.91286部隊 青島 266000）

1 引言

裝備試驗鑒定任務管理是保證裝備采辦進度及確保裝備質量和作戰適用性的重要環節，對于發現裝備缺陷，牽引裝備發展具有重要作用［1］。承擔裝備試驗鑒定任務的單位需要合理安排各類型測控保障設備，優化各試驗任務的進度安排，以確保安全高效完成年度試驗鑒定任務［2］。

在裝備試驗鑒定任務管理方面，楊春周［3］等針對航天裝備一體化試驗鑒定任務，構建了“面向需求，基于能力”的一體化試驗鑒定流程?？潞臧l［4］等總結了美軍裝備試驗鑒定組織實施的經驗做法，從系統工程的角度，提出了裝備試驗鑒定組織實施的建議。曹裕華［5］等研究了典型航天裝備全壽命周期的試驗階段和關鍵節點，為航天裝備試驗鑒定設計與實施提供參考。陳汗龍［6］等通過分析比測試驗項目管理現狀，提出了比測試驗理論研究和工程實踐的項目管理建議。

裝備試驗鑒定任務調度涉及各子任務的執行時刻籌劃和各類測控保障設備調配，傳統人工統籌分配方法容易導致設備資源沖突，且難以獲取較優的任務調度方案，延誤試驗進程。任務調度是項目管理的重要技術，其核心是合理安排各類資源及各項任務的執行時刻，以產生高效可行的任務調度方案，并指導工程實踐［7～8］。其中，資源受限項目調度是任務調度的一類，在各類調度優化問題中得到了廣泛應用［9～12］。

本文針對裝備試驗鑒定任務調度問題，基于資源受限項目調度問題的建模方法，分析試驗鑒定任務中的邏輯約束和保障設備約束，建立了資源受限裝備試驗鑒定任務調度模型（Resource-Constrained Equipment Test Mission Scheduling Model，RCETMSO）。然后，設計了一種基于優先規則的啟發式調度框架用于模型求解。最后，在案例仿真環節，針對某試驗鑒定任務給出了任務調度方案。

2 RCETMSO模型建立

根據年度試驗計劃安排，某單位需要同時開展n 個試驗鑒定任務，各項任務間無先后邏輯約束，但共用一個保障資源池。用集合I={1，2，…，n}表示需要開展的試驗鑒定任務。第i個鑒定任務共由Ji項具有邏輯約束的子任務構成，用符號（i，j）表示第i 個鑒定任務的第j 個子任務，dij表示其工期，Pij表示其前驅子任務集合。在實際裝備試驗鑒定任務中，各項子任務需要按照一定的邏輯順序依次完成，即任意子任務（i，j）都需要在其所有前驅工序完成后才能開始：

其中，決策變量Sij是子任務（i，j）的開始時刻，令Eij=Sij+dij表示子任務（i，j）的結束時刻。

完成裝備試驗鑒定任務需要各類保障設備提供通信、測控環境，如大型船舶性能鑒定試驗中需要使用GPS設備、無線通信設備等。記保障設備類型集合為 T，第 k 類保障設備集合為Lk={1，2，…，|Lk|}，符號rijk=1 表示子任務（i，j）在試驗中需要使用第k 類保障設備，否則rijk=0。決策變量Xijtkl表示在t 時刻第k 類第l 個保障設備用于子任務（i，j）的保障。各項子任務至多需要一個同種類的保障設備，即：

同一時刻，分配給所有裝備試驗鑒定任務的保障設備數量不能超過該類型設備的總數量：

裝備試驗鑒定任務調度的目的是統籌規劃保障設備的分配情況，合理設置各項子任務的執行時刻，最大化利用保障資源，高效完成各項裝備試驗鑒定任務，故設置模型的優化目標為最小化試驗鑒定任務的完工時間：

3 RCETMSO模型求解

第2 節建立的RCETMSO 模型中主要涉及邏輯約束和保障設備約束兩類約束，是一類具有NP-hard 性質的復雜組合優化難題。當前，求解該類組合優化問題的方法主要包括精確算法和啟發式算法兩類。以分支定界算法為代表的精確算法可以獲得問題的最優解，但是在大規模問題中無法解決計算效率問題，在實際工程應用中有很大局限性。啟發式算法雖然不能保證得到問題的最優解，但其具備調度效率高的優勢，在該類組合優化問題中得到廣泛應用。本節設計一種基于調度優先規則的啟發式調度框架求解RCETMSO 模型，其調度流程圖如圖1所示。

圖1 基于優先規則的啟發式調度框架

啟發式調度框架以時間為調度階段變量，在每一個時刻t，為所有滿足保障設備約束和邏輯約束的試驗鑒定任務安排保障設備，并設定任務的執行時刻。若當前時刻無可安排任務，則將時間變量t后移，待釋放相關資源后，再安排其余任務執行，直至所有的試驗鑒定任務全部完成調度。在時刻t，可能有多項任務同時滿足邏輯約束和保障設備約束，此時，需要依據一定的調度優先規則選取優先級最高的任務（u，v）。

4 案例分析

4.1 試驗鑒定任務案例生成

某單位7月份共需完成2 項裝備試驗鑒定任務，每項任務各有6 項子任務，各子任務的邏輯約束如圖2所示。

圖2 裝備試驗鑒定任務邏輯關系

圖2 中，S 節點和E 節點分別是試驗任務的開始、結束節點。2 項裝備試驗任務共需用到GPS 設備、無線通信設備和雷達對抗設備等3 類保障設備，分別用代號a、b、c 表示，該單位庫存的各類型保障設備均為2 臺。各項子任務工期及保障設備需求情況如表1所示。

表1 子任務工期及保障設備需求情況

4.2 調度方案生成

基于第3 節設計的啟發式調度框架，生成滿足保障設備約束和邏輯約束的試驗鑒定任務調度方案。為了對比不同調度優先規則的優劣，共設計了4類調度優先規則，如表2所示。

表2 調度優先規則

采用表2所示的調度優先規則產生任務調度甘特圖及各個時間段保障設備資源余量如圖3所示。

圖3 試驗鑒定任務調度甘特圖

經過檢驗，圖3 給出的裝備試驗鑒定任務調度方案滿足保障設備約束和邏輯約束。此外，經過對比可以看出，采用任務工期最長優先規則得到的調度方案中，任務完工時間最短，具有最優的調度效能。同時，從GPS 設備、無線通信設備和雷達對抗設備的資源余量來看，任務期間各類型保障設備得到了充分利用。采用任務工期最短優先和任務序號最小優先兩類優先規則給出的調度方案中，任務完工時間相同。任務序號最大優先的調度效能最差，在任務后期，存在較多閑置保障設備。綜上，可采用任務工期最長作為該類試驗保障任務的調度優先規則。

5 結語

針對裝備試驗鑒定任務調度問題，在建立RCETMSO 模型的基礎上，設計了一種基于優先規則的啟發式調度框架用于模型求解。在案例仿真環節，針對某試驗鑒定任務給出四種不同調度優先規則情況下的調度方案，結果表明，任務工期最長優先調度效能最高。后續研究方向是提出更高效的優化算法，進一步提升裝備試驗鑒定任務完工效率。5-10.