工程機(jī)械機(jī)群動(dòng)態(tài)調(diào)度問(wèn)題淺析

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

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

關(guān)鍵詞：工程機(jī)械機(jī)群；道路搶修；粒子群算法；動(dòng)態(tài)調(diào)度

0引言

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

1模型構(gòu)建

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

1.1任務(wù)描述

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

1.2問(wèn)題建模

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

2模型求解

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

2.1算法流程

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

2.2粒子編碼的設(shè)計(jì)

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

2.3粒子位置更新方式

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

3案例分析

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

4結(jié)論

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

作者:李金鑫 何曉暉 單位:中國(guó)人民解放軍32382部隊(duì)