基于多優先級動態規劃算法的裝備保障任務調度

劉亞東，伊洪冰，陳祥斌，顧雪峰，劉 波

(1.軍事交通學院 裝備保障系，天津300161;2.沈陽軍區聯勤部 軍事交通運輸部，沈陽110000;3.四川省軍區 樂山預備役步兵旅，四川 樂山614200)

信息化條件下的作戰，各種武器裝備綜合應用于戰場，使得裝備保障的難度和復雜性空前增大，裝備保障已成為武器裝備發揮效能和部隊戰斗力“再生”至關重要的因素和環節。這就需要完善以往“相對分散、各成體系”的裝備保障體系，將裝備保障作為一個大系統，將裝備保障力量作為一個整體，最大限度對其進行統一配置與運用，實現高效的一體化保障。裝備保障任務調度作為體系保障能力形成的基礎，其目的在于在一定的時限內分配給具備一定保障能力的保障力量，使裝備保障任務與裝備保障力量之間進行合理的匹配，以獲取完成裝備保障任務流程的最佳效益［1］。

裝備保障任務的調度問題，可以描述為給定一個任務集合和現有的裝備保障力量單元的集合。任務集合確定了需要處理的所有裝備保障任務，任務之間的執行順序(包括任務的串行、并行以及交叉關系)、信息和數據流向，同時明確了裝備保障任務處理的時間需求、裝備保障力量單元需求等任務的基本特征;裝備保障力量單元具備處理任務的功能，單元本身具備一定的基本屬性(如運行速度、具備的功能能力、信息獲取范圍、數據或信息處理能力等)，力量單元和任務之間通過任務的能力需求和單元的功能能力關聯，以此進行力量單元—任務的分配。因而，力量單元到任務的分配通常以整個任務流程完成的時間最短或者以裝備保障力量單元的充分利用為目標。

任務調度問題在農業、工業、信息科學等領域研究較多，在軍事領域近幾年來部分軍事學者也開始借鑒一些理念與方法解決車輛運輸調度、油料保障等問題［2］。然而在裝備保障力量部署領域中，其部署主要依托作戰需求及一定的約束條件，定性判斷較多，人為經驗成分多，對于在不確定的需求及復雜動態的環境變化下，如何有效解決裝備保障任務與裝備保障力量分配并行處理問題的研究較少［3］。論文借鑒多優先級動態規劃算法，綜合考慮各種因素，構建裝備保障任務調度模型，旨在解決2 個問題:①得出裝備保障任務的最優分配方案，即執行該任務的裝備保障力量單元及執行時間;②確定任務的執行順序，即確定完成整個裝備保障任務最短時間。

1 裝備保障任務調度模型的構建

裝備保障任務調度的目標是縮短完成裝備保障總任務的時間，提高完成裝備保障任務的有效性，即分配合適的裝備保障力量單元或裝備保障力量單元的編組到正確的區域去執行合理的任務。具體地說，就是在滿足裝備保障任務力量需求的情況下，提高裝備保障力量單元的利用率，縮短完成裝備保障任務過程的時間。

1.1 條件約束

一般而言，某項裝備保障任務的處理需要具備處理這一任務的所有條件。假設某裝備保障任務由裝備保障力量單元來完成，則需要具備如下條件。

(1)假設裝備保障力量單元的數量足夠、功能齊全，能夠完成整個裝備保障任務。

(2)假設在某一任務之前的所有任務都已處理完畢。

(3)分配到某任務的所有裝備保障力量單元已在保障任務區域集結完畢。

(4)1 個裝備保障力量單元每次只能完成1 個任務，且裝備保障力量單元的能力不小于保障任務的需求量［4］。

1.2 決策變量

假設裝備保障力量單元與裝備保障任務間分配變量為wim，分配給保障力量單元Um任務ti時，wim=1，否則wim=0;保障力量單元在任務間轉移變量為xijm，在保障力量單元Um處理任務ti后，又分配給其任務tj則xijm=1，不分配給任務則xijm=0。

當裝備保障力量單元Um(1≤m≤K)和裝備保障任務ti(1≤i≤N)之間存在分配關系時，裝備保障力量單元Um被分配去執行裝備保障任務ti有2種情況:①裝備保障力量單元Um被首次使用，直接被分配處理任務ti，此時不存在轉移變量，即轉移變量xijm=0;②裝備保障力量單元Um在處理完任務tj后被分配處理任務ti，此時存在轉移變量，即轉移變量xijm=1。

基于以上考慮，假設所有裝備保障任務的起點為t1，在作戰開始階段，所有保障力量單元都在起始任務t1上，此時xiim=xjjm=0，則保障力量單元與任務分配變量wim和保障力量單元在任務間的轉移變量xijm存在如下約束關系:

由于裝備保障力量單元Um每次只能處理1個裝備保障任務，在處理完任務ti后只能被分配完成某一個任務，而不能同時被分配完成多個任務，則

1.3 時間約束

假設任務順序變量為aji，如果任務tj的處理必須在任務ti處理完后才能開始則為1，否則aji=0;假設時間變量為si，sj為處理任務ti的開始時間。由于任務間的順序關系，任務ti的處理開始必須在其所有前導任務(pr(ti))處理完畢之后。因此，存在順序關系的任務處理時間存在如下約束:式中D(ti)為裝備保障任務的處理時間。

當裝備保障力量單元Um(1≤m≤K)在處理完任務ti后被分配任務tj時，由于條件約束中已經假定，要求執行該裝備保障任務的所有保障力量單元都到達任務區域，而現實中執行該任務的所有單元不可能同時到達，此時，先到達的保障力量單元需要等待。因此，保障力量單元Um開始處理裝備保障任務ti的開始時間sj不小于保障力量單元到裝備保障任務tj區域的時間，即

式中:dij為裝備保障任務ti與任務tj之間的空間距離;vm為裝備保障力量單元Um的機動速度。

其中

式中:(xi，yi)、(xj，yj)分別為裝備保障任務ti與裝備保障任務tj的地理位置。

綜合式(3)和式(4)，記Y'為所有裝備保障任務完成時間的上界，則裝備保障力量單元在任務的分配以及任務間的順序關系約束可描述為

1.4 能力約束

成功處理裝備保障任務ti的條件，是被分配處理這一任務的所有裝備保障力量單元的能力不小于裝備保障任務的需求Ri，即

式中:L為裝備保障力量單元的功能類型，如彈藥保障、器材保障、維修保障、信息保障、防衛保障等。

令所有的裝備保障任務全部完成時間為Y，則對任意裝備保障任務處理的時間約束式(8)總能成立，即

綜上所述，裝備保障任務調度過程的數學模型可以描述為

式中N、K、L分別為任務總數、裝備保障力量單元數量和功能類型數量。

2 多優先級列表動態規劃算法

2.1 相關概念的定義

在裝備保障任務調度過程中，需要選擇當前要執行的任務，確定任務對力量單元(或單元編組)的選擇、力量單元對任務的選擇。因此，在算法闡述之前需要定義裝備保障任務分配的3 種優先權:任務優先權系數pr、任務選擇力量單元的優先權tu和力量單元選擇任務的優先權ut。

2.1.1 任務優先權系數

當某一任務之前所有任務都已處理完時，該任務便進入分配任務集rest中，在rest中首先選擇任務優先權系數高的任務進行保障力量單元的分配，任務的優先權系數根據任務流程圖中的任務序列依據算法來確定。本文通過采用加權長度算法來計算任務的優先權系數pr:

式中:rest(i)為裝備保障任務之后待完成的任務集合;D(ti)為裝備保障任務ti的完成時間。

2.1.2 任務選擇保障力量單元的優先權

任務選擇保障力量單元的目的是充分利用裝備保障力量，保證完成任務的時間最短。充分利用力量單元就是要正好滿足任務的資源需求，而任務的完成時間需要選擇能在較短時間內到達任務區域進行處理任務的力量單元。因此，定義任務選擇保障力量單元的時間優先系數tu1和保障力量單元功能矢量距離優先系數tu2分別為

式中:tl(m)為力量單元Um最后處理的任務;UCm為力量單元Um的功能矢量;l為功能類型。

tu1是保障力量單元在處理完最后的任務后到達當前需要處理的任務區域的時間，tu2是保障力量單元的能力對任務需求的滿足程度。因此，對于這2 個不同的系數，應通過tu1和tu2升序所建立的任務選擇力量單元的優先級表來計算，即保障力量單元到達任務區域的時間早則優先考慮，保障力量單元能力滿足任務需求矢量距離近則優先考慮。假設i、j分別代表優先系數tu1和tu2在各自序列中的位置，則任務選擇保障力量單元的優先權tu為

2.1.3 保障力量單元選擇任務的優先權

保障力量單元選擇任務的優先權ut，是指對未處理的任務進行優先級的排序。假設保障力量單元選擇任務的時間優先系數為ut1，任務需求矢量距離優先系數為ut2。對某一個單元Um，其對任務選擇的時間優先系數只需要考慮當前處理任務的區域到達等待處理的各任務間的距離。由此，2種優先系數可定義為

假設g、h分別為優先系數ut1和ut2在各自序列中的位置，則單元選擇任務的優先權ut為

2.2 優先選擇沖突的消除

由式(6)可知，單元選擇任務的時間優先系數ut1在任務確定之后排序是不變的，其優先級列表是靜態的，而任務選擇單元的時間優先系數tu1是隨著任務對單元的選擇而不斷變化的，其優先級列表是動態的。由于任務對單元的選擇只考慮自身需求，而單元對任務的選擇是對所有未處理任務的優選，這就存在著局部與全局的矛盾。因此，只要解決了任務選擇單元的優先級問題(列表是動態的)，即可解決2 種選擇的沖突問題。在裝備保障任務調度過程中，期望tu1優先級高的同時，也期望tu1優先級盡可能高。設單元對任務選擇的靜態優先級列表為SL，任務對單元選擇的動態優先級列表為DL，Sut和Stu分別為utmi和tuim在SL、DL 中的排序，可用加權方法解決裝備保障任務調度過程中的選擇沖突問題。令PR(tu，ut)為2種選擇優先權的協調，則加權公式為

式中:λ 為權系數;β=Stu-2/λ。

2.3 算法流程

多優先級列表動態規劃算法(multi-PRI list dynamic scheduling，MPLDS)，主要包括3 個步驟:對選擇的任務進行可分配性檢查;從任務圖中根據優先權選擇要處理的任務;選擇處理任務的最佳保障力量單元或單元編組(該部分包括任務對單元的選擇、單元對任務的選擇與2 種選擇沖突的消除)。其流程如圖1 所示。

圖1 MPLDS 算法流程

3 實例分析

選取某部隊一次進攻演習過程中的某一階段(即攻占敵方a1和b1高地所涉及的裝備保障任務)來進行實例分析。按作戰計劃將總體的作戰任務劃分為13 個任務階段，任務流程如圖2 所示［5］，任務內容見表1。

圖2 任務流程

表1 任務屬性及裝備保障功能需求分析

由于在作戰過程中需要對裝備實施有效的維修保障、供應保障(彈藥和器材)、信息保障及防衛保障，因此根據裝備保障任務需要以及未來裝備保障力量模塊化的發展趨勢，將裝備保障力量單元劃分為彈藥保障力量單元、器材保障力量單元、信息保障力量單元、上裝保障力量單元、底盤保障力量單元、防衛保障力量單元等7 類，具體屬性見表2［6］。

表2 裝備保障力量單元屬性

根據裝備保障任務調度模型及MPLDS 算法，利用Matiab7.0 軟件對算法進行編程，選取λ 為1和5 分別進行計算，結果如圖3 所示。當λ 為1時，完成任務的總體時間為189.8 s，裝備保障力量單元的協同總量為65;當λ 為5 時，完成任務的總體時間為100.6 s，裝備保障力量單元的協同總量為43。

圖3 MPLDS 求解結果甘特圖

4 結 語

(1)通過力量單元對任務選擇與任務對力量單元選擇兩者的結合，可以使裝備保障任務調度的過程更加緊湊，任務的處理更為合理。一方面可以縮短完成總體任務的時間，為作戰及保障的順利實施提供了可靠的保證;另一方面可以充分利用裝備保障資源，最大限度地利用和挖掘裝備保障力量的保障能力，在提高保障資源利用率、保障力量協同保障能力的同時，促進保障效能的有效發揮。

(2)戰時裝備保障力量單元彼此之間需要加強協同，以促進體系保障能力的快速生成。通過2個結果對比分析可以發現，并不是保障力量單元協同越多，保障效能的發揮就越好，單元之間的協同過多反而會降低完成任務的效能，不必要的協同甚至會導致任務處理出錯。因此，在平時的訓練及演習過程中，要避免過分強調協同保障，當某個保障力量單元的能力能夠勝任某一任務的需求時，就不用選擇多個單元來完成這一任務。

(3)由于裝備保障力量單元與任務的匹配需要多維變量測度，任務本身需要異構功能的裝備保障力量單元的協同處理，并且要求裝備保障力量單元能夠處理多個任務，使得裝備保障任務調度的復雜性大大增加。本文采用多優先級動態規劃列表算法進行實例分析，解決了裝備保障力量單元分配過程中存在的局部搜索和優先權函數的合理性問題，避免了力量單元在執行任務過程中不必要的協同。

［1］ 任連生.基于信息系統體系作戰能力概論［M］. 北京:軍事科學出版社，2009:1.

［2］ 崔浩，周慶忠，樊榮，等.一體化油料保障資源配置布局優化研究［J］.軍事物流，2010(8):139.

［3］ 張春潤，劉亞東. 基于復雜網絡的裝備保障力量體系保障研究［C］//中國兵工學會. 第二屆質量、可靠性、風險、維修性、安全性國際學術會議論文集.2011:723-724.

［4］ 吳秀鵬.裝備保障力量模塊化設計研究［D］. 石家莊:軍械工程學院，2010:48-51.

［5］ 張春潤，劉亞東.裝備保障需求開發方法研究［J］.裝甲兵工程學院學報，2012(3):14-18.

［6］ 劉亞東，張春潤，伊洪冰. 基于社會網絡的裝備保障組織網絡拓撲結構研究［C］ //中國兵工學會. 第二屆質量、可靠性、風險、維修性、安全性國際學術會議論文集.2011:727.