面向任務(wù)時(shí)限提前的工程機(jī)械機(jī)群動(dòng)態(tài)調(diào)度研究

李金鑫 何曉暉 杜毛強(qiáng) 王金康

（1.陸軍工程大學(xué)野戰(zhàn)工程學(xué)院 南京 210007）（2.中國(guó)人民解放軍32382部隊(duì) 洛陽(yáng) 471000）（3.中國(guó)人民解放軍32228部隊(duì) 廈門 361100）

1 引言

工程機(jī)械機(jī)群同時(shí)開(kāi)展多任務(wù)作業(yè)時(shí)，受不確定因素影響，某一任務(wù)可能會(huì)面臨任務(wù)時(shí)限提前的情況，指揮中心依據(jù)實(shí)時(shí)的調(diào)度相關(guān)信息調(diào)度，將其他任務(wù)的工程機(jī)械調(diào)度到該任務(wù)協(xié)助作業(yè)，使得任務(wù)在規(guī)定時(shí)間內(nèi)完成。本文基于時(shí)空網(wǎng)絡(luò)，建立機(jī)群動(dòng)態(tài)調(diào)度時(shí)的時(shí)空網(wǎng)絡(luò)模型［1］，進(jìn)而對(duì)問(wèn)題進(jìn)行求解。

2 基于時(shí)空網(wǎng)絡(luò)建立動(dòng)態(tài)調(diào)度模型

2.1 問(wèn)題描述

工程機(jī)械機(jī)群在執(zhí)行任務(wù)的過(guò)程中因突發(fā)情況導(dǎo)致某一任務(wù)需要提前完成，這一情況的出現(xiàn)要求任務(wù)執(zhí)行過(guò)程中必須臨時(shí)從其他任務(wù)調(diào)度工程機(jī)械來(lái)增援該任務(wù)，即開(kāi)展任務(wù)間的交叉調(diào)度。將各個(gè)任務(wù)的空閑裝備充分調(diào)度起來(lái)，盡可能地在不影響其他任務(wù)完成的情況下使得該任務(wù)在最短時(shí)間完成，是解決這一問(wèn)題的最佳方法。如圖1 所示。任務(wù)1到任務(wù)n在前期機(jī)群配置的基礎(chǔ)上開(kāi)展作業(yè)，當(dāng)任務(wù)n 存在空閑裝備時(shí)，將其調(diào)度至不存在空閑裝備的任務(wù)上，當(dāng)任務(wù)n 即將飽和作業(yè)時(shí)，調(diào)度的裝備應(yīng)該在飽和作業(yè)前返回，避免出現(xiàn)任務(wù)n延時(shí)完成的情況。

圖1 動(dòng)態(tài)調(diào)度問(wèn)題描述實(shí)例圖

圖2 遺傳算法流程圖

綜上所述，工程機(jī)械的動(dòng)態(tài)調(diào)度方案，由于其工作性質(zhì)的特殊性，其優(yōu)化的目標(biāo)是工程機(jī)械的空閑率最低、完成時(shí)間最短，即在不影響任務(wù)完成的情況下，將各任務(wù)點(diǎn)的工程裝備充分地調(diào)動(dòng)起來(lái)，在為簡(jiǎn)化模型［2］故作以下假設(shè)。

1）調(diào)度達(dá)到的工程機(jī)械到達(dá)施工現(xiàn)場(chǎng)后可第一時(shí)間開(kāi)展作業(yè)。

2）工程機(jī)械機(jī)群的燃料及資源等充足，在各任務(wù)的搶修完成前，并不需要返回營(yíng)地進(jìn)行維修資源的補(bǔ)給。

3）工程機(jī)械的施工效率不因工程機(jī)械的增多而變化。

4）一般情況下，機(jī)群工程機(jī)械型號(hào)是不相同的，不同型號(hào)機(jī)械的工作效率、轉(zhuǎn)運(yùn)速度也會(huì)存在偏差，為了簡(jiǎn)化問(wèn)題的復(fù)雜程度，故不考慮機(jī)型的問(wèn)題。

5）由于任務(wù)之間的距離較近所以不考慮工程機(jī)械調(diào)度轉(zhuǎn)移的時(shí)間。

6）在已知機(jī)群配置和各任務(wù)工程量的情況下，基于動(dòng)態(tài)規(guī)劃法可得出，個(gè)任務(wù)工程機(jī)械的空閑時(shí)間。

7）緊急時(shí)期道路為軍車優(yōu)先使用或?qū)Ｓ?。所以行駛速度不受車流量的影響，因此各路段的旅行時(shí)間可認(rèn)為己知。

2.2 模型構(gòu)建

通過(guò)分析工程機(jī)械機(jī)群的動(dòng)態(tài)調(diào)度問(wèn)題可知，要解決這一問(wèn)題，核心問(wèn)題要實(shí)時(shí)了解各個(gè)任務(wù)點(diǎn)工程機(jī)械的使用情況，在靜態(tài)調(diào)度模型的基礎(chǔ)上，將任務(wù)點(diǎn)的實(shí)時(shí)空閑裝備這一因素考慮進(jìn)去，建立數(shù)學(xué)模型。因此，基于對(duì)機(jī)群動(dòng)態(tài)調(diào)度問(wèn)題的定義以及模型假設(shè)，本文采用時(shí)空網(wǎng)絡(luò)建模方法構(gòu)建工程機(jī)械機(jī)群的動(dòng)態(tài)調(diào)度方案的混合整數(shù)模型。

1）參數(shù)定義

為方便后續(xù)模型描述和讀者理解，這里對(duì)模型的參數(shù)、變量進(jìn)行介紹。

表1 中n?N+的，如u1代表推土機(jī)、u2代表挖掘機(jī)、u3代表裝載機(jī)等等。

表1 面向任務(wù)時(shí)限提前的工程機(jī)械機(jī)群動(dòng)態(tài)調(diào)度參數(shù)表

2）建立模型

本文以工程機(jī)械機(jī)群完成任務(wù)時(shí)間最短為優(yōu)化目標(biāo)，考慮機(jī)械數(shù)量約束、機(jī)械調(diào)度數(shù)量約束和任務(wù)完成時(shí)間約束，制定機(jī)群調(diào)度策略。利用時(shí)空網(wǎng)絡(luò)精確性和直觀性的特點(diǎn)，可以比較方便地解決上文提出的機(jī)群靜態(tài)調(diào)度問(wèn)題。

工程機(jī)械機(jī)群靜態(tài)調(diào)度模型的目標(biāo)函數(shù)為

需要滿足的約束條件有：

（1）機(jī)械數(shù)量約束條件

①在機(jī)群的調(diào)度中，T 時(shí)刻任務(wù)i 的調(diào)度弧上的第n 種工程機(jī)械的數(shù)量小于等于任務(wù)i 的第n 種工程機(jī)械的空閑機(jī)械數(shù)量。其約束條件如下：

②機(jī)群調(diào)度結(jié)束后，機(jī)群工程機(jī)械的總數(shù)之和應(yīng)不變。其約束條件如下：

（2）時(shí)間約束

③各任務(wù)必須在要求時(shí)間限制內(nèi)完成：

綜上，工程機(jī)械機(jī)群的靜態(tài)調(diào)度模型為

3 基于遺傳算法求解

面向任務(wù)時(shí)限提前的工程機(jī)械機(jī)群動(dòng)態(tài)調(diào)度問(wèn)題是一個(gè)將空閑的工程機(jī)械如何調(diào)度和調(diào)度幾次的組合優(yōu)化問(wèn)題，是機(jī)群科學(xué)配置的基礎(chǔ)上開(kāi)展的。在之前研究的基礎(chǔ)上，可以得出啟發(fā)式算法［12］是解決此類問(wèn)題的常用算法。因此本文采用啟發(fā)式算法中的遺傳算法［3］來(lái)求解。

3.1 算法流程

在遺傳算法中染色體可以用行數(shù)為一的矩陣表示，矩陣中的每一列對(duì)應(yīng)一個(gè)基因。將許許多多的行數(shù)為一的矩陣匯聚在一起，便組成算法解的種群。對(duì)每個(gè)矩陣進(jìn)行選擇運(yùn)算、交叉運(yùn)算和變異運(yùn)算等。從中選取出算法的最優(yōu)解。

最優(yōu)解遺傳算法的基本運(yùn)算過(guò)程如算法流程圖1～2所示。其到達(dá)進(jìn)化條件［7］后結(jié)束。

3.2 算法設(shè)計(jì)

1）染色體的編碼設(shè)計(jì)

當(dāng)情況發(fā)生后，將完成時(shí)限提前的任務(wù)放入待優(yōu)化任務(wù)集合σ中，設(shè)每個(gè)任務(wù)提前后的完成時(shí)限為tig，對(duì)于未進(jìn)入集合σ的任務(wù)，設(shè)它們空閑的工程機(jī)械數(shù)量為n，將其組成行數(shù)為1 列數(shù)為n 的矩陣，則每列中的元素代表一個(gè)空閑裝備。則空閑裝備存在兩種狀態(tài)［8］調(diào)度和不調(diào)度，其等于1 則說(shuō)明該空閑裝備調(diào)度，反之不調(diào)度。如Z=[1,0,1,0] ，則表示有4臺(tái)空閑裝備。代號(hào)為第1、4空閑裝備參與調(diào)度，代號(hào)為2，4裝備不參與。

2）染色體的適應(yīng)值

適應(yīng)值［4］由目標(biāo)函數(shù)決定，當(dāng)機(jī)群的調(diào)度問(wèn)題以待優(yōu)化任務(wù)在規(guī)定時(shí)間內(nèi)完成任務(wù)為目標(biāo)時(shí)，則適應(yīng)值為根據(jù)染色體當(dāng)前代表的機(jī)群調(diào)度方案得到的任務(wù)完成時(shí)間。

3）染色體的更新方式

（1）選擇運(yùn)算

用適應(yīng)度比列選擇法［9］，把優(yōu)良個(gè)體選擇［11］出來(lái)傳到下一代。設(shè)種群規(guī)模為J，第i 個(gè)個(gè)體的適應(yīng)度值為F(i)，則被選擇的概率為

（2）交叉運(yùn)算

①將R1,R2除了起點(diǎn)和終點(diǎn)之外的其他共同節(jié)點(diǎn)作為潛在的交叉節(jié)點(diǎn)，并將這些節(jié)點(diǎn)組成集合R；

②將R中節(jié)點(diǎn)前后信息不一致的任意一個(gè)節(jié)點(diǎn)作為交叉點(diǎn)

③新個(gè)體產(chǎn)生后，檢查新個(gè)體中是否存在環(huán)路，若無(wú)，操作結(jié)束；若有，將相同節(jié)點(diǎn)之間的基因和相同節(jié)點(diǎn)一起刪掉。

具體實(shí)例如圖3所示。

圖3 交叉操作實(shí)例

（3）變異運(yùn)算

變異運(yùn)算是模仿生物遺傳基因中的基因突變，同交叉算法一樣是產(chǎn)生新個(gè)體的重要方法，使種群的多樣性更加豐富，防止算法陷入局部最優(yōu)解。其具體操作如下：

①刪除基因。

在課堂教學(xué)中主要表現(xiàn)為教師對(duì)自身的情感、儀表、舉止等方面的約束能力。這是實(shí)現(xiàn)課堂教學(xué)控制的根本前提。著名教育家加里寧曾經(jīng)指出：“一個(gè)教育工作者,必須很好地收斂自己,他應(yīng)該感到,他的一舉一動(dòng)都處在嚴(yán)格的監(jiān)督之下,世界上任何人也沒(méi)有受到這樣嚴(yán)格的監(jiān)督。”教師的情感、儀表、舉止等直接影響到融洽的課堂氣氛的形成,影響教學(xué)效果的實(shí)現(xiàn)。

第一步：在R1中選擇變異節(jié)點(diǎn)［10］。

第二步：判斷選中節(jié)點(diǎn)的前后節(jié)點(diǎn)否相連通，即前一節(jié)點(diǎn)與后一節(jié)點(diǎn)直接相連，若相連通，則開(kāi)始下一步；否則改用下面的單點(diǎn)或兩點(diǎn)變異，以增加種群的多樣性。

第三步：刪除選擇的的節(jié)點(diǎn)，判斷其適應(yīng)度值是否優(yōu)于R1的適應(yīng)度值，優(yōu)于，進(jìn)入下一步；反之，改用下面的單點(diǎn)或兩點(diǎn)變異，以增加種群的多樣性。

具體實(shí)例如圖4所示。

圖4 變異運(yùn)算實(shí)例1

②基因變異。

第一步：從父代個(gè)體R1根據(jù)變異概率p中隨機(jī)選擇變異節(jié)點(diǎn)，標(biāo)記起點(diǎn)到該點(diǎn)前一節(jié)點(diǎn)的基因組成基因片段a；

第二步：標(biāo)記該點(diǎn)到終點(diǎn)的基因產(chǎn)生新的基因片段b，基因片段a,b相連得到新個(gè)體，判斷基新的染色體是否存在相同基因，若有，轉(zhuǎn)到第三步；無(wú)，則轉(zhuǎn)到第四步；

第三步：將相同節(jié)點(diǎn)合并操作產(chǎn)生最新個(gè)體，用來(lái)代替第二步中的新個(gè)體；

第四步：新個(gè)體的適應(yīng)度值是否優(yōu)于父代個(gè)體的適應(yīng)度值，若優(yōu)于，則用新個(gè)體進(jìn)入下一代種群；否則，則轉(zhuǎn)到第五步；

第五步：進(jìn)行兩點(diǎn)變異，以增加種群的多樣性。

具體實(shí)例如圖5所示。

圖5 變異運(yùn)算實(shí)例2

4 案例分析

以文獻(xiàn)［5］中的構(gòu)筑急造軍路任務(wù)為例。該急造軍路共有3 條道路的構(gòu)筑任務(wù)，各道路的偵查情況為：道路1 大面積塌方，道路2 有連續(xù)彈坑，道路3 路基崩塌，據(jù)此將任務(wù)區(qū)分為：任務(wù)1 清除塌方，任務(wù)2克服連續(xù)彈坑，任務(wù)3修復(fù)崩塌路基，各任務(wù)工程量如表2所示，機(jī)群配置如表3所示，完成時(shí)間如表4所示。

表2 各任務(wù)工程量

表3 機(jī)群配置

表4 各任務(wù)完成時(shí)間

機(jī)群任務(wù)作業(yè)1 小時(shí)后，指揮中心接到任務(wù)，將任務(wù)2 提前30 分鐘完成，同時(shí)其他任務(wù)按時(shí)完成，故需要對(duì)機(jī)群開(kāi)展任務(wù)交叉調(diào)度，調(diào)度的對(duì)象為任務(wù)1、3 的空閑裝備，設(shè)機(jī)群轉(zhuǎn)移路途為10 分鐘，任務(wù)開(kāi)始作業(yè)時(shí)為12：00。其個(gè)任務(wù)中工程機(jī)械的空閑情況如表5。

表5 任務(wù)1、任務(wù)2的裝備空閑情況

指揮中心接受任務(wù)后，任務(wù)2 需在3 小時(shí)內(nèi)完成，及在15 時(shí)前完成，由表1～9 可知可供調(diào)度的空閑裝備為推土機(jī)6 臺(tái)次、挖掘機(jī)6 臺(tái)次、裝載機(jī)1 臺(tái)次，閑置時(shí)間均為1小時(shí)。

按照本文建立的數(shù)學(xué)模型，以規(guī)定時(shí)間完成為優(yōu)化目標(biāo)，用遺傳算法求解，用Matlab R2021a 編程計(jì)算?？傻谜{(diào)度矩陣如圖6所示。

圖6 調(diào)度矩陣

得其調(diào)度矩陣為

［0 1 1 1 1 1 0 0 1 1 1 1 0］

模型求解的優(yōu)化過(guò)程如圖7所示。

圖7 模型求解優(yōu)化過(guò)程

按表6 調(diào)度方案開(kāi)展調(diào)度，可在不影響任務(wù)1和任務(wù)3的情況下，使任務(wù)2在3h內(nèi)完成。

表6 機(jī)群動(dòng)態(tài)調(diào)度方案

5 結(jié)語(yǔ)

本文基于時(shí)空網(wǎng)絡(luò)建立面向任務(wù)時(shí)限提前的軍用工程機(jī)械機(jī)群動(dòng)態(tài)調(diào)度模型，以在規(guī)定時(shí)間內(nèi)完成任務(wù)為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，并基于遺傳算法求解，最后利用Matale2021a 進(jìn)行編程設(shè)計(jì)，通過(guò)實(shí)例驗(yàn)證，得出該方法可以快速、科學(xué)得出調(diào)度方案。