【理論】聯合作戰資源調度模型研究_風聞

​                       聯合作戰資源調度是聯合作戰籌劃的最後環節，過程可以描述為根據既定任務和任務的優先級、資源需求、任務間協同關係等屬性，將戰場空閒、可用資源分配給任務，並確定任務的具體開始時間，是典型資源受限項目調度問題（resource-constrainedprojectscheduleproblem，RCPSP），屬於運籌學的動態規劃範疇。2017版《JP5-0JointPlanning》將聯合作戰籌劃分為籌劃啓動、使命分析、行動方案開發、行動方案分析和推演、行動方案評估、行動方案確定和計劃命令開發7個步驟。其中前6步屬於任務規劃過程，目標是開發出可行的行動方案（courseofaction，COA），又可稱為聯合作戰方案。第7步屬於資源調度過程，目標是建立聯合作戰方案和兵力資源之間的連接關係，形成聯合作戰計劃。

在智能規劃領域，資源調度的基礎是聯合作戰籌劃中擬製的行動方案，行動方案一般由任務和任務之間的關係組成，資源調度的目標就是為行動方案中的每一個任務分配執行資源並安排任務開始時間，將任務之間的因果、併發等邏輯協同關係轉換為時間協同關係。經典的RCPSP是在信息完備的靜態環境中建模，具有任務執行時間確定、資源確定、任務間邏輯關係約束單一和任務不可中斷的特徵。戰爭具有高度對抗性，戰場瞬息萬變，這給聯合作戰方案帶來高度不確定性，使得經典RCPSP的建模方法難以適應聯合作戰資源調度需求，需要採用不確定性資源調度框架來進行建模，這也是近年來RCPSP領域的研究熱點。

1不確定性資源調度研究

1.1 聯合作戰方案不確定性分析聯合作戰方案主要由初始態勢、終止態勢和一組相互關聯的任務集合組成，其主體是相互關聯的任務集合，包括任務和任務協同關係，通常採用單代號網絡（activityonnode，AON）表示，節點表示任務，邊表示任務間的邏輯協同關係，節點和邊都採用“屬性-值”形式描述其語義內涵。不確定性資源調度就是在考慮聯

合作戰方案信息中存在的不確定性條件下，將資源分配給每一個任務，並根據任務的協同關係和資源就緒情況計算任務的開始時間。

聯合作戰方案具有任務、資源和時間3個維度的不確定性。任務不確定性是聯合作戰方案中任務數量增加或減少的變化，這也是聯合作戰方案面臨的主要不確定性問題：敵我雙方的高度對抗博弈條件下，戰場瞬息萬變，指揮員需要依據戰場態勢變化對聯合作戰方案做出快速調整，以適應作戰需要。資源不確定性是指一個任務可能存在多個執行模式，不同的執行模式具有不同的資源需求，例如打擊敵方機場，可以採用常導打擊也可以採用空對地突擊，或者混合打擊，任務的執行模式需要在資源調度階段確定。時間不確定性包括機動時間不確定性、執行時長不確定性2種。（1）機動時間不確定性是指由於聯合作戰資源的多站現象帶來的資源從部署位置到目標空間的機動時間不確定性。多站是指同類資源分佈在不同的資源站；資源站即資源的存儲站點，不同的資源站具有不同的空間位置，這導致從資源站到任務目標區的機動時間不同。（2）執行時長不確定性是指任務從進入目標區域開始執行任務到結束任務退出目標區域之間時間長度的不確定性，例如執行空對地打擊任務的飛機在進入目標區域雷達開機到完成投彈並退出目標區的時間長度。

1.2 不確定性資源調度研究現狀經典RCPSP問題研究是在確定性環境下進行的，自Herroelen和Leus在2004年的魯棒項目調度綜述、2005年的不確定性環境下項目調度綜述[8]後，RCPSP研究熱點開始轉向不確定性環境下的資源調度研究[9]，中國自2009年開始出現了不確定性資源調度的相關研究。不確定性環境下資源調度的研究對象是在通過調度算法生成基礎調度方案的基礎上，如何增加基礎調度方案的魯棒性。調度方案的魯棒性是指當指揮員依據調度方案控制部隊執行任務時，在遇到不確定性干擾情況下，不對調度方案修改或僅進行小幅度調整，仍能夠完成既定作戰任務的特性，也就是調度方案的抗干擾能力。

對於不確定性RCPSP研究，Demeulemeester和Her?roelen將求解過程劃分為3個階段：第1階段，基於任務的協同關係約束和資源約束求解可行調度方案；第2階段，利用主動式調度模型增強方案的魯棒性；第3階段，利用反應式調度模型在執行時對受到干擾破壞的調度方案進行修復。可見，按照調度方案魯棒性模型的作用時機，可以將不確定性資源調度方法分為主動式調度模型和反應式調度模型2種，這2種模型都不能獨立解決不確定性問題，需要相互配合，區別是研究側重點不同。當前主動式調度模型研究成果角度，包括時間緩衝、資源緩衝、累計不穩定性權重和最壞情形分析等方法；反應式調度模型研究成果較少，包括完全重新調度、修復調度、應急調度和趕工策略等方法。

1.3 聯合作戰方案不確定性研究框架1.3.1聯合作戰方案魯棒性策略分析

常説“大炮一響，計劃歸零”，聯合作戰方案的主要不確定性來自任務不確定性，也就是根據戰場態勢變化，對聯合作戰中任務的動態增加、刪除和參數修改等臨機決策帶來的不確定性。當前主動式調度模型主要針對時間和資源2個維度的不確定性，採用的手段通常是插入冗餘時間、增加戰役總時長，或者增加冗餘資源來提高方案的魯棒性。但是在信息化戰爭中，“觀察-判斷-決策-行動”（observe-orient-decision-action，OO-DA）循環的時間越短，則戰爭越具有主動性，插入冗餘時間和增加戰役時長與信息化戰爭的高時效形成矛盾，在戰役資源總量確定條件下，增加冗餘資源會減少瞬時資源可用量，進一步增加調度方案的執行時間，加深這種矛盾。此外，隨着計算機硬件和雲計算技術的發展，反應式調度面臨的計算瓶頸正在逐步緩解。綜上分析，反應式資源調度模型更適合聯合作戰資源調度問題。

反應式魯棒策略包括修復和再規劃2種。修復是指針對任務的增加、刪除、參數修改，對調度方案結構進行局部調整，適用於對反應速度敏感的調度方案；再規劃是將未執行的全部任務看作完整方案，重新執行調度算法，適用於對反應速度不敏感的調度方案。修復策略包括右移、趕工2類，右移是在時間軸上將受增加或延時任務影響的任務向後移動，實現方案的魯棒性，適用於針對干擾修復速度敏感的方案；趕工是通過調整任務參數實現部分或全部任務的執行時間對齊，適用於需要考慮時間、費用均衡問題或者時間、資源均衡問題的方案。聯合作戰方案在執行過程中，需要針對不確定性場景進行快速調度，宜採用修復中的右移方法。雖然目前右移研究較少，但是主動式調度方案中插入時間緩衝和資源緩衝的方法給右移策略提供了很好的借鑑，Leus提出了活動依賴浮動因子（activitydependentfloatfac?tor，ADFF）模型，VandeVonder等提出了資源流依賴浮動因子（resourceflowdependentfloatfactor，RFDFF）模型，可以作為改進右移方法的參考。

1.3.2基於資源流建模方法研究

資源流網絡綜合考慮任務間的協同關係和資源的流轉關係，是一種有效的魯棒性資源調度方法[16]，常見於主動式調度模型中針對時間不確定性的時間緩衝方法。從資源調度視角來看，資源不確定性、任務不確定性都可以轉化為等待資源就緒的時間不確定性。故本文在任務和任務協同關係構成的任務網絡的基礎上構建資源流網絡，通過任務子網和資源流子網的加權分析，研究戰場態勢變化帶來任務增加不確定性的調度方案魯棒性策略。

對於任務時間不確定性通常有概率描述、區間數和模糊數描述3種方式。概率描述的前提是通過歷史數據分析出任務執行時間的概率分佈函數；區間數方法是指通過統計，整理出任務執行時間的區間，採用的形式描述任務的執行時間，其中表示任務執行時間的下限，表示任務執行時間的上限；模糊數描述是結合歷史數據和指揮員先驗知識，採用隸屬度函數來描述任務時間的不確定性。由於前2種方法都需要較大數據樣本，而數據的稀少和戰爭的一次性、不可類比性，致使前2種方式具有很大侷限性；基於模糊集的方法能夠將歷史數據和專家經驗相融合，比基於概率的方法更符合實際和有效。本文采用三角模糊數對任務的執行時間、開始時間、結束時間進行描述，並將採用模糊數描述的任務構成的任務子網和資源流子網合稱模糊網絡。

對於求解策略，研究RCPSP問題產生幾十年以來，國內外學者對求解方法的研究成果，可以將其劃分為精確式方法和啓發式方法2種。精確式求解方法包括分支定界法、整數規劃法和枚舉法等；啓發式方法包括基於規則的啓發式方法和元啓發式方法。基於優先規則的啓發式方法，常用的優先規則包括最小化完成時間、最小化資源總需求、最大化資源利用率等；元啓發式方法是根據生物的運動形態抽象成的數學模型，包括遺傳算法、蟻羣算法、粒子羣算法、禁忌搜索算法等。由於RCPSP 已經被證明為Non-deterministic  Poly-nomial-hard（NP-hard）問題，隨着資源數量和資源約束的增加，算法複雜度成指數方式增長，所以啓發式方法是一種有效的求解策略。在啓發式算法中，遺傳算法是目前應用較為成熟的一種方法，並被廣泛用於任務規劃、資源調度等領域。本文采用遺傳算法對反應式模糊網絡調度模型進行求解，並將這種融合遺傳算法的模糊網絡調度模型稱為遺傳模糊網絡模型（Genet-ic Fuzzy Network, GFN） 。

2基於GFN 的聯合作戰資源調度建模

2.1 問題假設1）任務描述假設。採用AON 方式對任務子網和資源流子網進行描述，節點為任務和資源站，任務節點集合描述為，其中K 為任務總數，邊為任務之間的資源流轉關係和協同關係、資源站和任務之間的資源調度關係。增加虛擬開始任務節點Begin和虛擬結束任務節點End，為Begin 與任務子網的最早開始任務之間設置因果關係邊，為End 與任務子網最後結束任務之間設置因果關係邊，將全部資源站資源調入Begin 節點，任務所需資源除了Begin 節點外，全部通過任務間資源流轉實現。

2）任務關係假設。任務之間存在協同關係和資源流轉關係。 用於描述任務節點和之間的協同關係，具有方向性，並稱為的協同前序任務，例如當Rqk 為因果協同時，表示 必須在 結束後才能執行；用於描述任務節點 和之間的資源流轉關係，即資源從流轉到。

3）任務優先級假設。任務優先級描述為Y={1, 2,3, …, M}，1 表示最大任務優先級，M 表示最小任務優先級，Y 值大的任務先分配資源，具有相同Y 值的任務在進行資源分配時不區分先後順序。

4）執行模式假設。任務存在一種或多種執行模式，不同執行模式具有不同資源需求，在對任務進行資源分配前必須確定任務的執行模式，執行模式確定規則為，其中為任務執行時間最短規則，為獲取可用資源時間最早規則。首先令，判斷當前可直接使用資源是否滿足全部模式的執行資源需求，如果只能滿足該任務的一個模式，則選擇該模式為任務執行模式，否則令，選擇執行時間最短模式作為任務的執行模式，並將選定執行模式的資源需求向量作為任務的資源需求向量。

5）任務執行假設。任務必須在全部資源滿足後才能執行，執行過程不可被中斷，執行完畢後，釋放全部資源。

6）資源類型假設。本文研究只針對可更新資源，也就是可以被重複使用的資源，例如飛機、艦艇、坦克等資源；不考慮不可更新資源，即消耗性資源，例如導彈、火箭彈、油料等。

2.2 模型參數1）：任務節點的協同前序任務集合，，q為的協同前序任務總數，協同前序任務即與之間存在直接或間接的協同關係，方向為。

2）U：資源集合，，其中i為資源種類標識，I為資源類型總量，j為資源站標識，J為第I類資源的資源站總量，為第i類資源第j站的資源數量。

3）：分配給任務Tk的第i類第j站資源數量。

4）：任務的資源需求，，i 為資源類型，I 為資源類型數量，為任務第i 類資源的需求量。

5）：任務的模糊開始時間。

6）：任務從資源所在位置機動到任務目標位置的時間，其計算公式為

其中，為第i 類第j 資源站的座標，為任務的目標座標，為第i 類第j 站資源的機動速度，的機動時間取全部資源運動到的最長時間。

7）：任務的模糊執行時間，由歷史數據統計結合專家經驗預先給出參數。

8）：第i 類第j 站資源的維護時間，預先給定參數。

2.3 調度模型

其中，式（2）表示RCPSP問題目標函數，要求聯合作戰方案執行時間最小；式（3）表示當兩個任務之間存在因果協同關係時，這兩個任務開始時間的約束；式（4）表示聯合作戰方案的總執行時間不能超過預定的戰役總時長；式（5）表示時間取值約束，任務的開始執行時間必須為正模糊數；式（6）表示資源總量約束，在任何時刻Ht正在執行的任務佔用第i類第j站資源總量不能超過第i類第j站資源總量；式（7）表示任務資源需求約束，只有任務的全部需求資源被滿足後才開始執行。

2.4 魯棒模型魯棒模型是在調度模型產生的最優調度方案的基礎上，通過增加反應式魯棒性機制，提高調度方案的魯棒性。本文魯棒性針對任務增加和執行時間延長的不確定性，其中執行時間延長可以看作原任務按時完成並增加一個新的任務。對於任務增加，魯棒性策略主要是尋找增加任務的最優插入位置，模型如下：

式（8）表示獲取候選插入位置的規則，其中為新增任務，為的資源前序任務的開始時間，Hcur為方案執行過程中插入新增任務的時間，為的開始時間，為從 向流轉的資源類型，為執行所需要的資源類型，為執行所需第i 類資源數量，為執行所需第i 類資源數量；式（9）表示候選插入位置的權重計算方法，其中為帶插入位置的權重，表示 是否為基線任務，是則=1，不是則=0，基線任務為從虛擬開始任務到虛擬結束全部路徑中總時間最長路徑上的任務集合，表示調度方案所有任務節點出度的最大值，表示是否為基線任務，是則=1，不是則=0，表示 和之間存在資源流邊，表示和之間存在協同邊；式（10）表示最優插入位置選擇規則，K 為候選插入位置數量。

3實驗驗證

3.1 實驗環境介紹以紅藍雙方海、空、導、網電多維聯合體系對抗想定為背景，設計22個任務，如圖1所示。

圖1任務子網示意

Fig.1Tasksubnetdiagram

任務的優先級取值範圍Y={1,2,3}，每個任務的優先級採用隨機賦值；任務間的協同關係取值範圍={1,2}，表示任務節點和之間的關係為因果協同關係，即執行完才能執行，=2表示任務節點和之間的關係為時間協同關係，即和必須同時開始執行；任務目標區域隨機生成。

設計9類14站資源，空間位置隨機生成，數量如表1所示。

3.2 基於遺傳算法的調度模型求解3.2.1預處理

預處理的目標是將任務網絡根據任務關係類型，轉化為任務深度網絡，為任務深度網絡中的每一個任務賦予深度層信息，具有協同、併發關係的任務處在同一深度層，具有因果關係的任務處在不同深度層，進行資源分配時逐深度層展開，這是一種用空間換時間的算法優化方法，喬士東在其基於個體修正的MMGRCP-SP（multi- mode generalized resource constrained project scheduling）算法中也採用了該方法。

3.2.2遺傳編碼

設計染色體的編碼是遺傳算法的關鍵問題，按照基因位的符號類型，可以劃分為二進制編碼、實數編碼、字母編碼等，在資源調度領域，按照基因所表示的含義，可以劃分為隨機優先級編碼、時間編碼、資源編碼等，張迎新的資源調度算法和何立華的FDFRCPSP（fuzzy duration and fuzzy resource-constrained project scheduling problem）算法採用的是隨機優先權編碼， Kevin M. Calhoun 的MMGRCPSP 算法和喬士東基於個體修正的MMGRCPSP 算法就是採用的時間編碼。由於隨機優先權編碼為整數編碼，且基因位數少，計算機處理速度快，故採用隨機優先權編碼。

3.2.3遺傳解碼流程

採用串行調度生成機制（serial schedule generation scheme，SSGS）方式將染色體解碼成一個滿足資源約束的調度方案，解碼需要考慮任務深度、任務優先級、隨機優先級和任務執行模式優先級4 個因素。解碼流程分為資源流網絡生成和時延計算2 個子流程（圖2）。

圖2 解碼流程

Fig. 2 Decoding process

其中資源流網絡生成子流程如下。

1）初始化。

設置虛擬開始節點時間參數：

設置兩個任務和，存儲已完成資源分配任務節點，存儲未分配資源隊列，並將任務Begin 放入，其他任務全部放入。

2）對中任務排序。

按照任務的深度值 E 對中任務進行升序排序，深度值越小位置越靠前，相同深度值的任務不區分先後順序。

按照任務優先級Y={1,2,3}對具有相同深度值的任務進行升序排序，1 表示最大任務優先級，3 表示最小任務優先級，表示任務的優先級越高，位置越靠前，具有相同Y 值的任務不區分先後順序。

按照隨機優先級X={1, 2, …, K}對當前深度層具有相同E 值和Y 值的任務進行升序排序，K 為任務的數量，任務的X 值越大，表示任務的優先級越高，位置越靠前。

3）調度終止測試。

獲取中第一個任務為當前任務，如果為End 任務，則轉入步驟8），否則轉入步驟4）。

4）計算當前任務資源需求向量。

針對當前任務，根據2.1 小節模式優先級規則假設選擇執行模式，並將選定執行模式的資源需求向量作為任務的資源需求向量。

5）生成當前任務的資源流邊。

按照任務結束時間依次獲取中任務，如果包含當前任務需要的資源，根據任務的資源剩餘數量和的需求數量在 與之間生成資源流邊，資源流向為，如果中所需的第i 類資源來自多個資源站，則依據公式（13）計算需要調度的資源站

其中，表示資源流邊調度任務中的資源站，表示第i 類、第j 站資源的座標，J 表示第i 類資源的資源站總量，表示任務目標區域的座標，

為第i類第j 站資源的機動速度，min 表示獲取第i 類資源中最近資源站的資源。

6）當前任務模糊時間計算。

根據當前任務生成的資源流邊，獲取的資源前序任務集合，資源前序任務即當2 個任務節點和之間存在資源流邊，稱為的資源前序任務計算的模糊開始時間，公式為

並根據的模糊開始時間、模糊執行時間、機動時間計算結束時間，公式為

7）更新。

將Tk 放入，並轉入步驟3）。

8）終止。

根據公式（10）計算End 的模糊開始時間，並將End 添加到。為遺傳算法的適應度計算參數。

時延計算就是在資源流子網的基礎上，根據模糊任務子網的任務協同關係，計算每個任務因為協同關係產生的延遲，該子流程步驟如下。

1）獲取當前任務。

依次從中獲取一個任務作為當前任務。

2）更新當前任務的任務結束時間。

獲取的全部協同前序任務，依次根據和之間的協同關係，計算給帶來的執行時間延遲，計算規則為

其中，為的任務結束時間，為的任務開始時間，為的任務開始時間。

最後根據的任務開始時間計算其任務結束時間，計算公式為（10）。

3.2.4 遺傳選擇

採用輪盤賭方法進行選擇操作，首先生成隨機數，然後根據式（16）進行選擇計算

式中s 為種羣規模，g(x)表示適應度函數。然後根據式（17）求其對應的適應度函數

其中為虛擬結束任務End 的模糊開始時間的α 截集。

3.2.5遺傳交叉操作

交叉操作是隨機選擇2 個父代染色體，根據交叉概率進行重組，以形成子代染色體，其作用是讓遺傳算法進行全局尋優，交叉的方法有單點交叉、多點交叉等， 本文采用單點交叉操作。隨機優先級染色體的交叉操作步驟如下。

1）設置交叉概率。

2）隨機選擇兩個染色體和作為交叉操作的父代，交叉操作的兩個子代用和表示。

3）隨機生成交叉操作概率，當時，執行交叉操作。

4）生成隨機整數作為交叉點，K 為任務總數，交叉點前面的父代基因直接繼承，交叉點後面的基因進行交叉操作。

5）在交叉操作中，需要考慮優先級的唯一性，和交叉點後基因值相同的基因位通過順序右移操作後直接交叉，基因值不一致的基因位需要進行變換後再進行交叉操作，如圖3 所示。

圖3  交叉操作示意

Fig. 3 Cross diagram

3.2.6 遺傳變異操作

變異操作是根據變異概率，隨機選擇染色體的一個基因位，並改變該基因位的基因值，作用是局部尋優。具體流程如下。

1）設置變異概率。

2）選擇一個染色體，併產生隨機數。

3）如果，則隨機選擇一個變異基因位，執行變異操作。由於隨機優先級需要保證優先級的唯一性，所以會產生受影響基因位，如圖4 所示。

圖4   變異操作示意

Fig. 4 Mutation diagram

3.2.7 實驗結果

採用 0.9 的交叉概率，0.03 的變異概率，種羣規模

30，遺傳代數30，結果如圖5、6 所示。

圖5 基於GFN 的調度方案

Fig. 5 Scheduling scheme based on GFN

圖6 GFN 調度模型遺傳優化數據

Fig. 6 Genetic optimization data of GFN scheduling model

圖6顯示GFN模型的調度解在第16代開始收斂於738，圖5顯示收斂後的聯合作戰資源調度結果。

3.3 反應式魯棒模型測試假定正在利用某兵棋系統對聯合作戰方案進行推演，當前作戰時間隨機生成，且滿足

其中表示聯合作戰方案中描述的推演開始時間，表示聯合作戰方案描述的預定推演結束時間，表示根據隨機算法生成的當前作戰時間。

隨機生成一個任務，任務的資源需求中包含3個類型，數量隨機賦值，針對染色體適應度為738的染色體，進行2個隨機插入任務實驗：一是利用優化算

法選擇任務的插入位置，計算優化後時延；二是在候選可插入位置中隨機產生插入位置，並計算其平均實驗。實驗結果如圖7所示。

圖7GFN魯棒策略實驗結果

Fig.7ExperimentalresultsofGFNrobuststrategy

圖7中紅色折線表示採用傳統右移方法插入隨機任務產生的時延，藍色折線表示採用本文設計反應式魯棒模型優化後插入隨機任務產生的時延，實驗結果顯示，本文設計的反應式魯棒模型在處理任務不確定性時優於傳統右移方法。

3.4 結果分析目前對於魯棒性調度方案的分析，存在解魯棒性和質量魯棒性2種方法。解的魯棒性又叫方案穩定性，是指將調度方案中任務的預定開始時間和執行時的實際開始時間的偏差作為魯棒性評估指標；質量魯棒性不關心任務實際執行時間的分佈，而是選擇方案執行總時長、方案總成本最小等效能參數作為魯棒性評估指標。對於聯合作戰方案來説，在執行過程中任務的高度不確定性，決定了解魯棒性難以對其進行有效分析，需要採用總時長、總資源消耗量等質量魯棒性類指標。由於戰爭以取勝為最終目標，信息化戰爭中，縮短我方“OODA”循環時間，提高調度方案時效性，關乎戰爭勝敗，故選用方案總時長最短作為評估指標。根據實驗，基於GFN的反應式調度模型，借鑑了主動式調度模型中的時間緩衝因子計算方法，相對於傳統直接右移式修復模型，具有更好的魯棒性。

4結論

針對聯合作戰籌劃過程中面臨的不確定性資源調度問題，提出了基於遺傳模糊網絡的反應式調度模型，該模型分為調度和魯棒2個子模型，通過實驗驗證了調度子模型在處理存在時間、資源不確定性聯合作戰資源調度問題時的有效性，驗證了魯棒模型在方案執行過程中抗任務不確定性干擾的有效性。遺傳模糊網絡模型與傳統不確定性資源受限項目調度模型的明顯區別，就是突出了方案執行過程中的任務不確定性，並利用反應式魯棒子模型來處理這種不確定性。但是模型對聯合作戰方案進行了大量簡化，實際作戰中，任務類型、任務協同關係，遠比實驗想定中的複雜，要想將模型進一步應用於實踐，還需要對模型進行進一步優化完善。

參考文獻（略）

作者：劉兆鵬，司光亞，唐宇波，柳少軍

※ ※ ※

創新體系工程基礎理論和方法

推動系統工程理論再發展