工程機械機群動態調度問題淺析

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了工程機械機群動態調度問題淺析范文，希望能給你帶來靈感和參考，敬請閱讀。

摘要：針對工程機群在道路搶修任務過程中，面臨的多裝備、多任務、多點同時作業的機群調度難題，用整數線性規劃理論建立模型，用離散粒子群算法求解。實例分析表明，該機群動態調度方法可以快速、高效地提出工程機械機群動態調度方案，為充分發揮軍用工程機械的保障能力提供了決策支持。

關鍵詞：工程機械機群；道路搶修；粒子群算法；動態調度

0引言

道路搶修是工程機械機群工程保障任務之一。通常可將其分為清除塌方、填塞彈坑、壕溝、修復崩塌路基4種任務，往往需要在不同地域同時開展。每種任務均涉及到推土機、挖掘機、裝載機等多種類型軍用工程機械協同作業。當前工程機械機群實際運用過程中，機群往往是多點同時開展工作，指揮員通常是根據主觀經驗來確定機群的動態調度，工程機群開始工作后各工作點之間基本沒有動態調度。由于每個點的工作量不同，任務難度不同，故工程進度也會不同。因此，合理地調度各個工作點的工程機械，才能保證任務順利完成，使工作效率達到最大化。如何利用有限資源在最短時間內完成道路搶修任務成為檢驗戰斗力的標準。因此，研究工程機械機群優化調度方法，有助于合理、高效地使用工程機械，進而為指揮員定下方案提供依據。

1模型構建

工程機械的調度需要依據任務類型、工程量及機械的作業能力確定，因此必須對調度問題進行建模分析，以制定最優的調度方案。

1.1任務描述

道路搶修一般分為4種任務：新筑道路，清除塌方，填平彈坑、壕溝，修復崩塌道路。一般情況下，往往同時、不同地點展開，且都需要推土機、挖掘機、裝載機協同完成。由于不同任務的難易程度不同，故任務進展不同，現其中一點的任務已經完成，為使整體作業效率最大化，需將這一點的工程機械調度至其他任務點。將工程機械機群中的每一臺工程機械看做一個單位，單位集：X={B1，…，Bi，…，Bn；E1，…，Ei，…En；M1，…，Mi，…Mn}。式中：B為推土機；E為挖掘機；M為裝載機。假設推土機b臺，挖掘機e臺，裝載機m臺，工程裝備數量總共為C臺，任務數量為a。機群調度的任務-單位分配關系表示為式中，各變量表示任務與單位的關系，其賦值為推土機：

1.2問題建模

合理調度工程機械，使總任務完成的時間最少。總任務完成的時間等于各任務完成時間的最大值。工程機群調度模型目標函數為mint=max{ti|i=1，2，…，a}。（4）需要滿足的約束條件有：1）各工程機械調度數量不大于該項目工程機械數量。式中：j=ej=1∑eij為第i個任務點的挖掘機數量；j=ej=1∑bij為第i個任務點調度的推土機數量；j=mj=1∑mij為第i個任務點調度的裝載機數量。2）時間約束。各任務必須在要求時間限制內完成：ti=Qiuini≤tL，i=1…a。（6）式中：Qi為任務i的工程量；uj為單位j的作業率；ni各任務工程機械數量。3）各任務要盡可能地同時完工，避免出現某段任務完工過早或過晚的現象，以保證機群資源更加均衡合理分配使用。0.9<maxti/minti<1.1，i=1，2，…，a。（7）4）每個任務的機械數量為整數。ni≤N，i=1，2，…a。（8）通過對問題的描述和約束條件分析，可建立如下數學模型：

2模型求解

工程機械機群調度模型求解可以看做是一個尋找最優解的過程，即離散組合優化問題；解決此類問題的有效方法是啟發式算法，主要包括離散粒子群算法[1]、遺傳算法[2]、隱枚舉法[3]等算法。本文采用粒子群算法求解動態調度模型。該算法具有收斂速度快、全局優化性好的特點，其應用領域已從連續空間優化問題擴展到離散組合優化問題[4]，在解決機群動態調度問題上優勢尤為明顯。

2.1算法流程

PSO算法中每一個潛在的解都被稱為一個“粒子”，粒子在解空間內“運行”，隨著算法運行，粒子不斷逼近函數的最值[5]。在每次進化過程中，粒子通過跟蹤2個“極值”來更新自己所在的位置。第一個極值為粒子自身找到的最優位置，相對應的適應值為pBest；另一個極值是整個種群當前找到的最優位置，相對于的適應值稱為全局極值為gBest[6]。其流程圖如圖1所示。在得知最優方案后，即可得調度方案。

2.2粒子編碼的設計

每個粒子位置對應一個新的分配方案，這樣就將每一種配置方案映射成一個粒子，粒子的飛行表示從一個調度方案到另一個調度方案的選擇。隨著算法的收斂，粒子逐漸逼近最優調度方案。機群的調度矩陣為XB、XE、XZ分別為推土機、挖掘機、裝載機在各任務的調度情況。設種群中粒子位置的集合為X={X1，X2，…，XPOP}。（12）式中，POP為種群大小。種群中粒子位置如圖2所示。例如，任務1、任務2、任務3分配推土機、挖掘機、裝載機各1臺，其中任務2已完成，將任務2的各類工程機械任意調度到任務1、任務3，其矩陣粒子編碼可表示為這樣的編碼方式的優點是直觀地將各任務的機群調度情況表示出來，將任務2的1臺推土機、挖掘機、裝載機調度給任務1，2臺挖掘機、裝載機調度給任務3。

2.3粒子位置更新方式

由于每個單位只能被分到1個任務，每個任務至少分配1個單位，所以位置矩陣每行的和大于1，每行每列任意互換。同時滿足以下束縛條件：

3案例分析

本文以文獻[3]中的構筑急造軍路任務為例。該急造軍路共有3條道路的構筑任務，各道路的偵查情況為：道路1大面積塌方，道路2有連續彈坑，道路3路基崩塌，據此將任務區分為：任務1清除塌方，任務2克服連續彈坑，任務3修復崩塌路基，各任務工程量如表1所示。因突發情況導致任務1和任務2的機械作業效率降為一半。現有推土機10臺、挖掘機7臺、裝載機6臺，各類機械在不調度的情況下，各任務的作業率如表2所示。文獻[3]完成總任務時間為7.86h。根據本文建立的數學模型，以最小化總任務完成時間為優化目標，用粒子群算法求解，用MatlabR2015b編程計算。模型求解的優化過程如圖3所示。可見，目標函數適應值在算法迭代75次左右達到收斂，總任務完成時間最小值為6.895h，優于未調度工程機械的任務完成時間7.86h。最優結果的機群調度矩陣為：矩陣中“-1”代表調出一輛，“1”代表調入一輛。故方案為將任務2的4輛推土機和任務3的1輛推土機調到任務1，將任務1的3輛挖掘機和任務2的1輛挖掘機調到任務3，將任務1的1輛裝載機和任務3的1輛裝載機調至任務2。

4結論

本文對軍用工程機械遂行構筑急造軍路任務面臨的多型裝備、多種任務、多點同時作業的機群動態調度問題進行分析，提出了基于離散粒子群算法求解模型的機群動態調度方法。該方法能有效解決機群的動態調度問題，提高軍用工程機械的保障能力。

作者:李金鑫 何曉暉 單位:中國人民解放軍32382部隊