面向任務時限提前的工程機械機群動態調度研究

李金鑫 何曉暉 杜毛強 王金康

（1.陸軍工程大學野戰工程學院 南京 210007）（2.中國人民解放軍32382部隊 洛陽 471000）（3.中國人民解放軍32228部隊 廈門 361100）

1 引言

工程機械機群同時開展多任務作業時，受不確定因素影響，某一任務可能會面臨任務時限提前的情況，指揮中心依據實時的調度相關信息調度，將其他任務的工程機械調度到該任務協助作業，使得任務在規定時間內完成。本文基于時空網絡，建立機群動態調度時的時空網絡模型［1］，進而對問題進行求解。

2 基于時空網絡建立動態調度模型

2.1 問題描述

工程機械機群在執行任務的過程中因突發情況導致某一任務需要提前完成，這一情況的出現要求任務執行過程中必須臨時從其他任務調度工程機械來增援該任務，即開展任務間的交叉調度。將各個任務的空閑裝備充分調度起來，盡可能地在不影響其他任務完成的情況下使得該任務在最短時間完成，是解決這一問題的最佳方法。如圖1 所示。任務1到任務n在前期機群配置的基礎上開展作業，當任務n 存在空閑裝備時，將其調度至不存在空閑裝備的任務上，當任務n 即將飽和作業時，調度的裝備應該在飽和作業前返回，避免出現任務n延時完成的情況。

圖1 動態調度問題描述實例圖

圖2 遺傳算法流程圖

綜上所述，工程機械的動態調度方案，由于其工作性質的特殊性，其優化的目標是工程機械的空閑率最低、完成時間最短，即在不影響任務完成的情況下，將各任務點的工程裝備充分地調動起來，在為簡化模型［2］故作以下假設。

1）調度達到的工程機械到達施工現場后可第一時間開展作業。

2）工程機械機群的燃料及資源等充足，在各任務的搶修完成前，并不需要返回營地進行維修資源的補給。

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

4）一般情況下，機群工程機械型號是不相同的，不同型號機械的工作效率、轉運速度也會存在偏差，為了簡化問題的復雜程度，故不考慮機型的問題。

5）由于任務之間的距離較近所以不考慮工程機械調度轉移的時間。

6）在已知機群配置和各任務工程量的情況下，基于動態規劃法可得出，個任務工程機械的空閑時間。

7）緊急時期道路為軍車優先使用或專用。所以行駛速度不受車流量的影響，因此各路段的旅行時間可認為己知。

2.2 模型構建

通過分析工程機械機群的動態調度問題可知，要解決這一問題，核心問題要實時了解各個任務點工程機械的使用情況，在靜態調度模型的基礎上，將任務點的實時空閑裝備這一因素考慮進去，建立數學模型。因此，基于對機群動態調度問題的定義以及模型假設，本文采用時空網絡建模方法構建工程機械機群的動態調度方案的混合整數模型。

1）參數定義

為方便后續模型描述和讀者理解，這里對模型的參數、變量進行介紹。

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

表1 面向任務時限提前的工程機械機群動態調度參數表

2）建立模型

本文以工程機械機群完成任務時間最短為優化目標，考慮機械數量約束、機械調度數量約束和任務完成時間約束，制定機群調度策略。利用時空網絡精確性和直觀性的特點，可以比較方便地解決上文提出的機群靜態調度問題。

工程機械機群靜態調度模型的目標函數為

需要滿足的約束條件有：

（1）機械數量約束條件

①在機群的調度中，T 時刻任務i 的調度弧上的第n 種工程機械的數量小于等于任務i 的第n 種工程機械的空閑機械數量。其約束條件如下：

②機群調度結束后，機群工程機械的總數之和應不變。其約束條件如下：

（2）時間約束

③各任務必須在要求時間限制內完成：

綜上，工程機械機群的靜態調度模型為

3 基于遺傳算法求解

面向任務時限提前的工程機械機群動態調度問題是一個將空閑的工程機械如何調度和調度幾次的組合優化問題，是機群科學配置的基礎上開展的。在之前研究的基礎上，可以得出啟發式算法［12］是解決此類問題的常用算法。因此本文采用啟發式算法中的遺傳算法［3］來求解。

3.1 算法流程

在遺傳算法中染色體可以用行數為一的矩陣表示，矩陣中的每一列對應一個基因。將許許多多的行數為一的矩陣匯聚在一起，便組成算法解的種群。對每個矩陣進行選擇運算、交叉運算和變異運算等。從中選取出算法的最優解。

最優解遺傳算法的基本運算過程如算法流程圖1～2所示。其到達進化條件［7］后結束。

3.2 算法設計

1）染色體的編碼設計

當情況發生后，將完成時限提前的任務放入待優化任務集合σ中，設每個任務提前后的完成時限為tig，對于未進入集合σ的任務，設它們空閑的工程機械數量為n，將其組成行數為1 列數為n 的矩陣，則每列中的元素代表一個空閑裝備。則空閑裝備存在兩種狀態［8］調度和不調度，其等于1 則說明該空閑裝備調度，反之不調度。如Z=[1,0,1,0] ，則表示有4臺空閑裝備。代號為第1、4空閑裝備參與調度，代號為2，4裝備不參與。

2）染色體的適應值

適應值［4］由目標函數決定，當機群的調度問題以待優化任務在規定時間內完成任務為目標時，則適應值為根據染色體當前代表的機群調度方案得到的任務完成時間。

3）染色體的更新方式

（1）選擇運算

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

（2）交叉運算

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

②將R中節點前后信息不一致的任意一個節點作為交叉點

③新個體產生后，檢查新個體中是否存在環路，若無，操作結束；若有，將相同節點之間的基因和相同節點一起刪掉。

具體實例如圖3所示。

圖3 交叉操作實例

（3）變異運算

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

①刪除基因。

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

第一步：在R1中選擇變異節點［10］。

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

第三步：刪除選擇的的節點，判斷其適應度值是否優于R1的適應度值，優于，進入下一步；反之，改用下面的單點或兩點變異，以增加種群的多樣性。

具體實例如圖4所示。

圖4 變異運算實例1

②基因變異。

第一步：從父代個體R1根據變異概率p中隨機選擇變異節點，標記起點到該點前一節點的基因組成基因片段a；

第二步：標記該點到終點的基因產生新的基因片段b，基因片段a,b相連得到新個體，判斷基新的染色體是否存在相同基因，若有，轉到第三步；無，則轉到第四步；

第三步：將相同節點合并操作產生最新個體，用來代替第二步中的新個體；

第四步：新個體的適應度值是否優于父代個體的適應度值，若優于，則用新個體進入下一代種群；否則，則轉到第五步；

第五步：進行兩點變異，以增加種群的多樣性。

具體實例如圖5所示。

圖5 變異運算實例2

4 案例分析

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

表2 各任務工程量

表3 機群配置

表4 各任務完成時間

機群任務作業1 小時后，指揮中心接到任務，將任務2 提前30 分鐘完成，同時其他任務按時完成，故需要對機群開展任務交叉調度，調度的對象為任務1、3 的空閑裝備，設機群轉移路途為10 分鐘，任務開始作業時為12：00。其個任務中工程機械的空閑情況如表5。

表5 任務1、任務2的裝備空閑情況

指揮中心接受任務后，任務2 需在3 小時內完成，及在15 時前完成，由表1～9 可知可供調度的空閑裝備為推土機6 臺次、挖掘機6 臺次、裝載機1 臺次，閑置時間均為1小時。

按照本文建立的數學模型，以規定時間完成為優化目標，用遺傳算法求解，用Matlab R2021a 編程計算。可得調度矩陣如圖6所示。

圖6 調度矩陣

得其調度矩陣為

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

模型求解的優化過程如圖7所示。

圖7 模型求解優化過程

按表6 調度方案開展調度，可在不影響任務1和任務3的情況下，使任務2在3h內完成。

表6 機群動態調度方案

5 結語

本文基于時空網絡建立面向任務時限提前的軍用工程機械機群動態調度模型，以在規定時間內完成任務為優化目標建立數學模型，并基于遺傳算法求解，最后利用Matale2021a 進行編程設計，通過實例驗證，得出該方法可以快速、科學得出調度方案。