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

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

關鍵詞：工程機械機群；道路搶修；粒子群算法；動態(tài)調(diào)度

0引言

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

1模型構(gòu)建

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

1.1任務描述

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

1.2問題建模

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

2模型求解

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

2.1算法流程

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

2.2粒子編碼的設計

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

2.3粒子位置更新方式

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

3案例分析

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

4結(jié)論

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

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