基于多優(yōu)先級動態(tài)規(guī)劃算法的裝備保障任務(wù)調(diào)度

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

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

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

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

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

1 裝備保障任務(wù)調(diào)度模型的構(gòu)建

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

1.1 條件約束

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

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

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

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

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

1.2 決策變量

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

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

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

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

1.3 時間約束

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

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

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

其中

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

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

1.4 能力約束

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

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

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

綜上所述，裝備保障任務(wù)調(diào)度過程的數(shù)學(xué)模型可以描述為

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

2 多優(yōu)先級列表動態(tài)規(guī)劃算法

2.1 相關(guān)概念的定義

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

2.1.1 任務(wù)優(yōu)先權(quán)系數(shù)

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

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

2.1.2 任務(wù)選擇保障力量單元的優(yōu)先權(quán)

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

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

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

2.1.3 保障力量單元選擇任務(wù)的優(yōu)先權(quán)

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

假設(shè)g、h分別為優(yōu)先系數(shù)ut1和ut2在各自序列中的位置，則單元選擇任務(wù)的優(yōu)先權(quán)ut為

2.2 優(yōu)先選擇沖突的消除

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

式中:λ 為權(quán)系數(shù);β=Stu-2/λ。

2.3 算法流程

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

圖1 MPLDS 算法流程

3 實例分析

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

圖2 任務(wù)流程

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

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

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

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

圖3 MPLDS 求解結(jié)果甘特圖

4 結(jié) 語

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

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

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

［1］ 任連生.基于信息系統(tǒng)體系作戰(zhàn)能力概論［M］. 北京:軍事科學(xué)出版社，2009:1.

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

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

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

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

［6］ 劉亞東，張春潤，伊洪冰. 基于社會網(wǎng)絡(luò)的裝備保障組織網(wǎng)絡(luò)拓撲結(jié)構(gòu)研究［C］ //中國兵工學(xué)會. 第二屆質(zhì)量、可靠性、風(fēng)險、維修性、安全性國際學(xué)術(shù)會議論文集.2011:727.