公務(wù)員期刊網(wǎng) 論文中心 正文

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

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

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

摘要:針對(duì)工程機(jī)群在道路搶修任務(wù)過程中,面臨的多裝備、多任務(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í)開展。每種任務(wù)均涉及到推土機(jī)、挖掘機(jī)、裝載機(jī)等多種類型軍用工程機(jī)械協(xié)同作業(yè)。當(dāng)前工程機(jī)械機(jī)群實(shí)際運(yùn)用過程中,機(jī)群往往是多點(diǎn)同時(shí)開展工作,指揮員通常是根據(jù)主觀經(jīng)驗(yàn)來確定機(jī)群的動(dòng)態(tài)調(diào)度,工程機(jī)群開始工作后各工作點(diǎn)之間基本沒有動(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ù)類型、工程量及機(jī)械的作業(yè)能力確定,因此必須對(duì)調(diào)度問題進(jìn)行建模分析,以制定最優(yōu)的調(diào)度方案。

1.1任務(wù)描述

道路搶修一般分為4種任務(wù):新筑道路,清除塌方,填平彈坑、壕溝,修復(fù)崩塌道路。一般情況下,往往同時(shí)、不同地點(diǎn)展開,且都需要推土機(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問題建模

合理調(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ù)完工過早或過晚的現(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)通過對(duì)問題的描述和約束條件分析,可建立如下數(shù)學(xué)模型:

2模型求解

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

2.1算法流程

PSO算法中每一個(gè)潛在的解都被稱為一個(gè)“粒子”,粒子在解空間內(nèi)“運(yùn)行”,隨著算法運(yùn)行,粒子不斷逼近函數(shù)的最值[5]。在每次進(jìn)化過程中,粒子通過跟蹤2個(gè)“極值”來更新自己所在的位置。第一個(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的各類工程機(jī)械任意調(diào)度到任務(wù)1、任務(wù)3,其矩陣粒子編碼可表示為這樣的編碼方式的優(yōu)點(diǎn)是直觀地將各任務(wù)的機(jī)群調(diào)度情況表示出來,將任務(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),各類機(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)化過程如圖3所示??梢姡繕?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)度問題進(jìn)行分析,提出了基于離散粒子群算法求解模型的機(jī)群動(dòng)態(tài)調(diào)度方法。該方法能有效解決機(jī)群的動(dòng)態(tài)調(diào)度問題,提高軍用工程機(jī)械的保障能力。

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