作戰(zhàn)工程保障行動(dòng)中的一種戰(zhàn)士- 裝備- 任務(wù)指派模型及其求解

張超省， 王健， 李政民， 楊鑫

(陸軍工程大學(xué) 訓(xùn)練基地， 江蘇 徐州 221004)

0 引言

信息化戰(zhàn)爭條件下，只有能夠快速實(shí)現(xiàn)作戰(zhàn)力量機(jī)動(dòng)、轉(zhuǎn)移和部署，才能在瞬息萬變的戰(zhàn)場態(tài)勢下捕獲制勝先機(jī)，這也對(duì)承擔(dān)機(jī)動(dòng)保障、戰(zhàn)斗支援等一系列作戰(zhàn)工程保障任務(wù)的工程保障部隊(duì)提出了更高要求。面對(duì)具體工程保障行動(dòng)，指揮員必須精準(zhǔn)、高效地制定出指派哪些戰(zhàn)士操作哪些裝備執(zhí)行哪些任務(wù)的決策。通常，制定決策時(shí)需要考慮以下3個(gè)方面問題：

1)一般情況下，戰(zhàn)士不會(huì)徒手完成任務(wù)，而是要操作裝備，并且工程保障部隊(duì)的戰(zhàn)士多數(shù)被培養(yǎng)成多技能操作手。指派戰(zhàn)士完成任務(wù)必須既要考慮到戰(zhàn)士的操作水平對(duì)裝備作業(yè)效率的影響，還要考慮到裝備自身的技術(shù)狀態(tài)會(huì)導(dǎo)致裝備作業(yè)效率的差異。比如一個(gè)技術(shù)熟練的操作手操作一臺(tái)裝備顯然比一個(gè)技術(shù)一般的操作手操作同臺(tái)裝備耗時(shí)更短、效率更高，同一個(gè)戰(zhàn)士操作一臺(tái)性能完好的裝備顯然比操作一臺(tái)性能堪用的同型裝備耗時(shí)更短、效率更高。

2)戰(zhàn)場環(huán)境下，上級(jí)對(duì)工程保障任務(wù)完成時(shí)間需求非常迫切，通常需要盡可能多的裝備協(xié)同作業(yè)以求最快完成任務(wù)；然而，多臺(tái)裝備在同一地域協(xié)同作業(yè)完成一項(xiàng)任務(wù)時(shí)，由于場地限制或配合影響，過多裝備甚至?xí)贡舜朔恋K。比如兩臺(tái)甚至三臺(tái)挖掘機(jī)協(xié)同挖掘大型平底坑，配合過程中不可能完全獨(dú)立同步開展，必然有一定程度的彼此干涉，總作業(yè)效率顯然比幾臺(tái)裝備作業(yè)效率簡單相加要小。

3)信息化戰(zhàn)爭條件下，工程裝備也逐漸向多功能方向發(fā)展，可以執(zhí)行多種任務(wù)。盡管戰(zhàn)士具備多項(xiàng)技能，然而考慮到長時(shí)間操作產(chǎn)生疲勞進(jìn)而帶來效率降低和安全隱患，允許工程裝備不間斷執(zhí)行多種任務(wù)，但是操作裝備的戰(zhàn)士只能執(zhí)行一項(xiàng)任務(wù)，也就是作戰(zhàn)工程保障行動(dòng)中常說的“人歇車不歇”原則。比如某型多用途工程車，既可以進(jìn)行挖掘作業(yè)，也可以進(jìn)行裝載作業(yè)，可以讓該裝備連續(xù)執(zhí)行挖掘和裝載兩項(xiàng)任務(wù)，盡量不讓操作該裝備的戰(zhàn)士連續(xù)疲勞作業(yè)去執(zhí)行兩項(xiàng)任務(wù)。

綜上所述，作戰(zhàn)工程保障行動(dòng)中任務(wù)的完成既與操作裝備的戰(zhàn)士相關(guān)，又與戰(zhàn)士操作的裝備相關(guān)，還與“人歇車不歇”以及協(xié)同作業(yè)效率相關(guān)，本質(zhì)上是一個(gè)多約束、多維度的指派問題，屬于非確定性多項(xiàng)式- 難問題(NP-Hard問題)。

目前，分析作戰(zhàn)工程保障行動(dòng)中人員任務(wù)指派問題的研究文獻(xiàn)尚不多見，但仍有一些其他領(lǐng)域的研究成果對(duì)解決前述問題具有一定的參考價(jià)值。經(jīng)典指派模型僅研究一人一事、一事一人的指派問題，既不涉及裝備性能的差異，也不涉及協(xié)同作業(yè)的情形，因此不能直接被用來解決上述問題[1]。文獻(xiàn)[2]針對(duì)柔性生產(chǎn)系統(tǒng)中多技能工人不同技能熟練水平的情況，在不考慮工具影響工人工作效率的情況下，提出了一種多技能工人的分配模型。文獻(xiàn)[3-4]考慮了維修人員的技能分級(jí)和休息時(shí)間，建立了一個(gè)適用于多技能維修人員的任務(wù)指派模型。文獻(xiàn)[5]則考慮了維修人員的疲勞積累對(duì)維修能力的影響，建立了一個(gè)適用于維修單元的任務(wù)指派模型。文獻(xiàn)[6]針對(duì)任務(wù)中存在并行作業(yè)環(huán)節(jié)的情況，設(shè)計(jì)了一種改進(jìn)匈牙利算法，從而解決包含并行環(huán)節(jié)的指派問題，但在并行作業(yè)環(huán)節(jié)中人員是獨(dú)立作業(yè)，并不存在協(xié)同作業(yè)的情形。文獻(xiàn)[7]針對(duì)某項(xiàng)任務(wù)需要多人協(xié)同作業(yè)的情形，建立了非線性的指派模型，但僅給出了兩人協(xié)作完成某項(xiàng)任務(wù)的求解過程。文獻(xiàn)[3-7]無一例外都是二維指派問題，只考慮人員和任務(wù)之間的指派關(guān)系，不涉及其他中間環(huán)節(jié)的約束。文獻(xiàn)[8-10]針對(duì)人力資源管理、多傳感器多目標(biāo)追蹤、數(shù)據(jù)融合等領(lǐng)域的問題，分別建立了相應(yīng)的三維指派模型；雖然其模型形式與本文所描述問題相差較大，但其建模過程值得借鑒。另外，上述研究也從另一角度說明了本文研究的指派問題并不是孤立的理論問題，而是一類極具應(yīng)用價(jià)值的實(shí)踐問題。

本文創(chuàng)新性主要包括以下3個(gè)方面：1)通過對(duì)作戰(zhàn)工程保障行動(dòng)特點(diǎn)的分析，將工程保障行動(dòng)中任務(wù)的派遣定義為一個(gè)由“戰(zhàn)士- 裝備- 任務(wù)”構(gòu)成的三維指派問題；2)綜合考慮戰(zhàn)士的多技能、裝備的多功能以及多臺(tái)裝備協(xié)同作業(yè)的相互影響，建立了作戰(zhàn)工程保障行動(dòng)的三維指派模型；3)基于“人歇車不歇”的原則，設(shè)計(jì)了虛擬裝備法，實(shí)現(xiàn)了三維指派模型的快速求解。

1 三維指派模型建立

假設(shè)某項(xiàng)工程保障行動(dòng)可以分為l項(xiàng)階段任務(wù)串聯(lián)執(zhí)行，指揮員要指派n名戰(zhàn)士操作m臺(tái)裝備完成l項(xiàng)階段任務(wù)，其中n>m. 為了解決上述指派問題，按以下步驟構(gòu)建指派問題的數(shù)學(xué)模型：

1)定義決策變量為

(1)

式中：xijk=1表示第i個(gè)戰(zhàn)士被指派操作第j臺(tái)裝備完成第k項(xiàng)任務(wù)，xijk=0表示第i個(gè)戰(zhàn)士未被指派操作第j臺(tái)裝備或未被指派完成第k項(xiàng)任務(wù)。

2)按照“人歇車不歇”原則，每名戰(zhàn)士最多被指派去執(zhí)行一項(xiàng)任務(wù)，因此必須滿足如下約束條件：

(2)

3)按照“人歇車不歇”原則，每臺(tái)裝備都應(yīng)該盡量多地參與各個(gè)階段的任務(wù)，但同時(shí)應(yīng)該滿足該裝備的參與不會(huì)導(dǎo)致整體作業(yè)效率的降低，也即某臺(tái)裝備可能參與多個(gè)階段任務(wù)，也可能不參與任意一項(xiàng)階段任務(wù)，因此必須滿足如下約束條件：

(3)

4)每個(gè)階段任務(wù)的完成最少需要一臺(tái)裝備，參與的裝備數(shù)量最多不超過具有完成該項(xiàng)任務(wù)功能的裝備數(shù)量mk，因此必須滿足如下約束條件：

(4)

5)引入tijk表示第i個(gè)戰(zhàn)士操作第j臺(tái)裝備獨(dú)立完成第k項(xiàng)任務(wù)所需的時(shí)間，可以通過(5)式計(jì)算：

tijk=tjk/(cjeij),

(5)

式中：tjk表示理想狀態(tài)下(戰(zhàn)士熟練程度和裝備技術(shù)狀態(tài)均為最好)第j臺(tái)裝備獨(dú)立完成第k項(xiàng)階段任務(wù)的耗時(shí)；cj表示第j臺(tái)裝備的技術(shù)狀態(tài)影響系數(shù)，取值區(qū)間為[0,1]，數(shù)值越大表示作業(yè)效率越高；eij表示第i個(gè)操作手操作第j臺(tái)裝備的熟練程度影響系數(shù)，取值區(qū)間為[0,1]，數(shù)值越大表示熟練程度越高。

6)各階段任務(wù)耗時(shí)之和便是整個(gè)工程保障行動(dòng)的耗時(shí)，優(yōu)化目標(biāo)即找到一組決策變量，使得完成工程保障行動(dòng)耗時(shí)最短，即目標(biāo)函數(shù)可表述為

(6)

綜上所述，(6)式描述了指派模型的目標(biāo)函數(shù)，(2)式、(3)式和(4)式則共同組成了指派模型的約束條件。不難發(fā)現(xiàn)，本文所描述的模型不僅考慮了戰(zhàn)士的操作水平，還考慮了裝備的技術(shù)狀態(tài)和協(xié)同作業(yè)的影響系數(shù)。該模型隨著參與協(xié)同作業(yè)裝備數(shù)量mk的增加變成了mk次整數(shù)規(guī)劃問題，本質(zhì)上屬于大規(guī)模非線性整數(shù)規(guī)劃問題。

2 快速求解算法設(shè)計(jì)

對(duì)于大規(guī)模非線性整數(shù)規(guī)劃問題，極特殊情形下可以通過變換將指派模型轉(zhuǎn)換為整數(shù)線性規(guī)劃問題，進(jìn)而按照整數(shù)線性規(guī)劃方法求解；大部分情形下不能求出精確解，通常采用擴(kuò)展割平面法[11]、廣義Benders分解[12]、分支定界算法[13]、外逼近算法[14]來獲得近似解，這些方法均是通過求解原非線性整數(shù)規(guī)劃問題的松弛問題或者線性子問題來進(jìn)行求解[15]。然而，不同于現(xiàn)有的絕大多數(shù)非線性整數(shù)規(guī)劃問題，本文所描述指派模型的目標(biāo)函數(shù)形式復(fù)雜且是高階非線性的，既不能變換為整數(shù)線性規(guī)劃問題，又難以找到對(duì)應(yīng)的松弛問題或線性子問題，因此很多快速求解非線性整數(shù)規(guī)劃的優(yōu)秀算法都不能直接用來求解本文模型。

如果沒有快速求解算法，通常的解法是：首先，構(gòu)建一個(gè)由2l×m×n個(gè)解構(gòu)成的較大可行域；然后，逐個(gè)判斷是否滿足(2)式、(3)式和(4)式給出的約束條件以縮小可行域；最后，通過(6)式求解可行域中最優(yōu)化的決策變量。如果按照上述思路，完成求解將相當(dāng)耗時(shí)，不能滿足信息化戰(zhàn)爭條件下快速?zèng)Q策的需要。

通過(3)式，不難發(fā)現(xiàn)：由于xijk為0-1變量，該公式所描述的約束條件實(shí)際上是無效的，導(dǎo)致不能為模型的求解構(gòu)建一個(gè)較小可行域。進(jìn)一步，如果將所有多功能裝備看作是多臺(tái)單功能裝備的虛擬集合，這樣(3)式所描述的約束條件就可以轉(zhuǎn)換為

(7)

式中：mv表示將多功能裝備拆分為虛擬裝備之后實(shí)際裝備與虛擬裝備數(shù)量之和，因此mv≥m.

上述方法之所以稱為虛擬裝備法，是因?yàn)榉纸夂缶哂袉喂δ艿难b備物理上是不存在的，即虛擬的集合。通過虛擬裝備法，(3)式的約束力得到了增強(qiáng)，從而極大地縮小了指派模型的可行域。不僅如此，基于虛擬裝備法修改指派模型的約束條件后，本文設(shè)計(jì)了一套快速求解算法，以下是具體實(shí)現(xiàn)步驟：

1) 按階段任務(wù)進(jìn)展的時(shí)間順序，給各階段任務(wù)進(jìn)行編號(hào)，得到階段任務(wù)編號(hào)數(shù)組。

2)引入Ik,mk表示能夠協(xié)同完成第k項(xiàng)階段任務(wù)所有可能的裝備組合方案，可以指派到第k項(xiàng)階段任務(wù)中裝備組合方案的數(shù)量為

(8)

進(jìn)一步，引入I表示整個(gè)工程保障行動(dòng)中裝備組合方案的組合，由于整個(gè)工程保障行動(dòng)是由各階段任務(wù)串聯(lián)而成，因此I=I1,m1∪I2,m2∪…∪Il,ml，整個(gè)工程保障行動(dòng)對(duì)應(yīng)的裝備組合方案數(shù)量為

(9)

3)從所有裝備組合方案選擇某一個(gè)裝備組合方案，并按裝備編號(hào)順序排列得到裝備編號(hào)數(shù)組。

4) 按照“人歇車不歇”的原則，要求每名戰(zhàn)士只需要執(zhí)行一項(xiàng)任務(wù)，因此戰(zhàn)士的指派要綜合考慮工程保障行動(dòng)的裝備組合和戰(zhàn)士的數(shù)量。那么，被指派到某一裝備組合方案中戰(zhàn)士組合方案的數(shù)量為

(10)

式中：mw=card(I)表示某一裝備方案組合對(duì)應(yīng)的裝備數(shù)量，由于每臺(tái)裝備分配一名戰(zhàn)士，實(shí)際上也就是某一裝備方案對(duì)應(yīng)的戰(zhàn)士數(shù)量。

5)從所有戰(zhàn)士組合方案中選擇某一個(gè)戰(zhàn)士組合方案，并按戰(zhàn)士編號(hào)進(jìn)行全排序得到戰(zhàn)士編號(hào)數(shù)組。

6) 由于決策變量矩陣中元素的坐標(biāo)是根據(jù)戰(zhàn)士編號(hào)、裝備編號(hào)和任務(wù)編號(hào)而給定的，可以根據(jù)步驟2、步驟4、步驟6確定決策變量中戰(zhàn)士、裝備、任務(wù)的坐標(biāo)，可以得到一組決策變量x.

7)遍歷所有裝備組合方案的集合，再遍歷該裝備組合方案對(duì)應(yīng)戰(zhàn)士組合方案的集合，可以得到所有決策變量x，逐次代入(6)式計(jì)算，得到最優(yōu)決策變量及對(duì)應(yīng)的任務(wù)耗時(shí)。

3 實(shí)例分析

某班要執(zhí)行一項(xiàng)構(gòu)筑掩蔽工事的行動(dòng)，該行動(dòng)主要由開挖平地坑(挖坑)、設(shè)置支撐結(jié)構(gòu)(起重)、覆土作業(yè)(覆土)3個(gè)階段任務(wù)串聯(lián)而成，必須完成上一個(gè)階段任務(wù)之后才能進(jìn)入下一個(gè)階段。該班共編有8名戰(zhàn)士，配備5類6臺(tái)工程裝備(2臺(tái)挖掘機(jī)、1臺(tái)挖坑機(jī)、1臺(tái)起重機(jī)、1臺(tái)推土機(jī)和1臺(tái)裝載機(jī))。各階段任務(wù)出動(dòng)最多工程裝備的組合可以由這些裝備的功能明確給出，進(jìn)而給出整個(gè)構(gòu)筑掩蔽工事一種可能的裝備組合方案，稱為最大裝備組合方案，如圖1所示。由圖1可以看出，裝載機(jī)既可以參與挖掘作業(yè)，又可以參與覆土作業(yè)。

圖1 最大裝備組合方案圖Fig.1 Maximum combination scheme of equipment

每名戰(zhàn)士的編號(hào)和操作各類工程裝備的熟練程度如表1所示，其中，熟練程度A、B、C、D對(duì)應(yīng)的影響系數(shù)分別是1.0、0.8、0.6、0.

表1 戰(zhàn)士編號(hào)和操作水平

每臺(tái)工程裝備的技術(shù)狀態(tài)如表2所示，其中，技術(shù)狀態(tài)A、B、C對(duì)應(yīng)的影響系數(shù)分別是1.0 、0.8、0.6.

表2 工程裝備技術(shù)狀態(tài)

結(jié)合測算和經(jīng)驗(yàn)，可以得到理想狀態(tài)下(熟練程度為A的操作手操作單臺(tái)技術(shù)狀態(tài)為A的工程裝備)完成各階段任務(wù)耗時(shí)，如表3所示。

表3 理想狀態(tài)下各階段任務(wù)耗時(shí)

采用虛擬裝備法，將裝載機(jī)看作兩臺(tái)虛擬裝載機(jī)(裝載機(jī)v1和裝載機(jī)v2)，一臺(tái)只能進(jìn)行挖坑，另一臺(tái)只能進(jìn)行覆土，按照?qǐng)D1所示的最大裝備組合方案，由左到右、由上到下給出工程裝備的編號(hào)，如表4所示。

表4 基于虛擬裝備法的裝備編號(hào)及任務(wù)耗時(shí)

各階段任務(wù)的編號(hào)及在該階段內(nèi)多臺(tái)裝備協(xié)作的影響系數(shù)，如表5所示，數(shù)值越大表示越礙事。

表5 各階段任務(wù)的協(xié)作影響系數(shù)

實(shí)踐中，工程保障部隊(duì)所屬的單位、人員和裝備在相應(yīng)的軟件系統(tǒng)中都會(huì)事先賦予唯一的標(biāo)識(shí)碼，而戰(zhàn)士操作裝備的熟練程度、裝備的技術(shù)狀態(tài)和多臺(tái)裝備協(xié)作對(duì)作業(yè)效率的影響系數(shù)一般通過部隊(duì)日常訓(xùn)練考核、演習(xí)演練考核或裝備在役考核等方式獲取后錄入系統(tǒng)。為便于計(jì)算和分析，本文中戰(zhàn)士、裝備和任務(wù)的編號(hào)均是人為指定，而熟練程度影響系數(shù)、技術(shù)狀態(tài)影響系數(shù)、協(xié)作影響系數(shù)則屬假設(shè)已知條件。因此，上述各種影響系數(shù)僅用來驗(yàn)證算法，不作其他用途。

最后，在搭載Intel Core i7 7th Gen處理器的Windows 7 64位平臺(tái)上，采用本文所描述的指派模型和求解算法，基于數(shù)學(xué)仿真軟件MATLAB 2017a求解上述實(shí)例，求得最優(yōu)化的指派方案，如表6所示，最優(yōu)指派方案對(duì)應(yīng)的行動(dòng)耗時(shí)為142.24 min.

表6 最優(yōu)化戰(zhàn)士- 裝備- 任務(wù)指派方案

從表6中可以看出：最優(yōu)化指派方案中，E4和E7分別參與了T1和T3兩個(gè)階段任務(wù)，也就是裝載機(jī)共參與了挖坑和覆土兩個(gè)階段任務(wù)；而E2代表的挖掘機(jī)2并沒有被指派參與挖坑作業(yè)。實(shí)際上，如果按最大裝備組合方案，挖掘機(jī)2也被指派參與挖坑作業(yè)，此時(shí)最優(yōu)指派方案對(duì)應(yīng)的行動(dòng)耗時(shí)為142.80 min，說明挖掘機(jī)2的參與并沒有加快挖坑作業(yè)反而稍微妨礙了挖坑作業(yè)，也即最大裝備組合方案并不一定是最優(yōu)的裝備組合方案。進(jìn)一步分析不難發(fā)現(xiàn)，挖掘機(jī)2的技術(shù)狀態(tài)為C，作業(yè)效率本來就不高，再加上4臺(tái)工程裝備協(xié)同挖坑作業(yè)的影響系數(shù)為0.3，因此才會(huì)出現(xiàn)“幫倒忙”的現(xiàn)象。不難得出結(jié)論：表6所示的決策方案更加符合實(shí)際情況，從而驗(yàn)證了指派模型的實(shí)用性和有效性。

另一方面，如果采用遍歷全部決策變量的做法，直接在2l×m×n個(gè)決策變量構(gòu)成的可行域內(nèi)搜索滿足約束條件的解(共28×6×3個(gè)決策變量，每個(gè)決策耗時(shí)約9.4×10-5s)，在同樣配置的計(jì)算平臺(tái)中估計(jì)耗時(shí)約2.1×1039s，這幾乎是不可接受的；而采用本文所描述的快速求解算法可以極大地減小可行域(共284 928個(gè)決策變量)，耗時(shí)僅為26.85 s. 因此，基于虛擬裝備法的快速算法能夠極大地降低計(jì)算消耗，是解決上述指派模型的一種切實(shí)有效地解法。

4 結(jié)論

本文分析了作戰(zhàn)工程保障行動(dòng)的特征，設(shè)計(jì)了工程保障行動(dòng)的戰(zhàn)士- 裝備- 任務(wù)的三維指派模型及其快速求解算法，并用實(shí)例對(duì)模型和求解算法進(jìn)行了驗(yàn)證。所得主要結(jié)論如下：

1)工程保障行動(dòng)中的任務(wù)指派問題應(yīng)考慮戰(zhàn)士操作水平、裝備技術(shù)狀態(tài)和任務(wù)協(xié)作影響等因素，因此，該問題是一個(gè)由“戰(zhàn)士- 裝備- 任務(wù)”構(gòu)成的三維指派問題。

2)基于“人歇車不歇”原則的虛擬裝備法，可以增強(qiáng)三維指派模型的約束條件，降低決策變量的可行域，從而實(shí)現(xiàn)指派模型的快速求解。

3)實(shí)例證明了本文建立模型及快速求解算法的實(shí)用性和有效性。

值得注意的是，根據(jù)戰(zhàn)士和裝備是否安排休息的情況，約束條件可以有4種情況：“人歇車不歇”、“人歇車歇”、“人不歇車歇”、“人不歇車不歇”。因?yàn)椤叭诵嚥恍笔亲鲬?zhàn)工程保障行動(dòng)中符合作戰(zhàn)原則的典型場景，因此本文僅針對(duì)這一種場景制定約束條件。在實(shí)際作戰(zhàn)行動(dòng)中，如果該工程裝備具有完成某階段任務(wù)的能力而且其自身技術(shù)狀態(tài)是正常的，除非經(jīng)過計(jì)算該裝備參與協(xié)作時(shí)導(dǎo)致整體作業(yè)效率降低，否則是不會(huì)出現(xiàn)“車歇”這種場景的。反倒是在任務(wù)非常緊急的情況下，極可能出現(xiàn)“人不歇車不歇”的場景。關(guān)于“人不歇車不歇”這種場景下的求解，可以按作戰(zhàn)工程保障行動(dòng)中階段任務(wù)的劃分，逐階段求解，是一種相對(duì)比較簡單的情況，感興趣的讀者可以自行研究。

與所有“指派戰(zhàn)士完成任務(wù)”的指派模型最大區(qū)別在于，本文所提出的指派模型能夠幫助指揮員在考慮“指派哪些戰(zhàn)士完成哪些任務(wù)”時(shí)，還綜合考慮了裝備技術(shù)狀態(tài)和協(xié)作影響因素帶來的影響。然而，本文尚沒有考慮一臺(tái)裝備有多個(gè)工位需要多名戰(zhàn)士協(xié)同作業(yè)完成某項(xiàng)任務(wù)的情形，這些問題將在以后的研究中繼續(xù)深入。