基于多任務(wù)理論的AGV協(xié)同多任務(wù)調(diào)度研究

董 航,樓佩煌,錢(qián)曉明,武 星,翟晶晶,胡 亞,胡子寒

(南京航空航天大學(xué)機(jī)電學(xué)院,江蘇 南京 210016)

伴隨“中國(guó)制造2025”戰(zhàn)略的提出,自動(dòng)導(dǎo)引車(chē)(automated guided vehicle,AGV)被廣泛應(yīng)用到各類(lèi)柔性制造加工系統(tǒng)中,這也隨之催生出具備不同工作能力的AGV。多AGV系統(tǒng)則是由多數(shù)量AGV、多種類(lèi)AGV組成。

目前,國(guó)內(nèi)外對(duì)于AGV系統(tǒng)的研究主要集中在單種類(lèi)、少數(shù)量AGV系統(tǒng)的研究,關(guān)于多AGV系統(tǒng)的研究較少,如Mousavi等[1]提出了一種基于多種啟發(fā)式算法(包括遺傳算法(GA)、粒子群 (PSO) 算法和GA-PSO)的混合算法模型,對(duì)任務(wù)調(diào)度進(jìn)行優(yōu)化; Heger等[2]提出一種基于離散事件的物料工廠模型,有效降低了AGV任務(wù)調(diào)度系統(tǒng)的空載率;石宇強(qiáng)等[3]基于柔性系統(tǒng)中的協(xié)同搬運(yùn)問(wèn)題,對(duì)傳統(tǒng)的粒子群算法進(jìn)行改進(jìn),有效減少任務(wù)完成時(shí)間;張博暉等[4]提出了以聚類(lèi)算法為模型的AGV調(diào)度策略;楊智飛等[5]提出一種基于自適應(yīng)多目標(biāo)的優(yōu)化方式,并將遺傳算法與差分進(jìn)化算法(AMOGA-DE)結(jié)合,獲得系統(tǒng)調(diào)度的最優(yōu)解;劉旭等[6]提出了一種改進(jìn)的遺傳算法,進(jìn)行AGV的任務(wù)分配和配送路徑優(yōu)化。本文采用基于多任務(wù)理論[7]的AGV協(xié)同多任務(wù)調(diào)度模型,提出一種改進(jìn)的遺傳算法(improved genetic algorithm,IGA),能有效提高制造系統(tǒng)的吞吐量與服務(wù)性能。

1 AGV協(xié)同多任務(wù)分配建模

1.1 任務(wù)描述

建立如圖1所示的工件加工車(chē)間,本車(chē)間總共有9個(gè)加工中心Pi(i=1,2,…,9),每個(gè)加工中心都容納一個(gè)輸入緩沖區(qū)Ei和一個(gè)輸出緩沖區(qū)Di,緩沖區(qū)容量為10件。工件從加工開(kāi)始到成品交付的生產(chǎn)過(guò)程稱(chēng)為一次任務(wù),在每個(gè)任務(wù)中含有若干個(gè)具有特定順序的子任務(wù)。對(duì)于車(chē)間內(nèi)的任何工件,在其從原料區(qū)取貨到成品區(qū)交貨的加工過(guò)程中都需要AGV完成包含牽引、搬運(yùn)和裝卸3種類(lèi)型的子任務(wù),每個(gè)子任務(wù)都需要1輛或者多輛AGV。

圖1 加工車(chē)間

1.2 任務(wù)建模

為了計(jì)算歸納方便,采用整數(shù)規(guī)劃法建造模型[8],用四元組{A,K,T,F}表示。

1)A={A1,A2,A3,…,AMs},為AGV車(chē)輛集合,Ai為AGVi,Ms為AGV的最大數(shù)量;

2)K={K1,K2,K3,…,KMn},為子任務(wù)類(lèi)型集合,Ki為某種子任務(wù)類(lèi)型,Mn為子任務(wù)類(lèi)型的最大數(shù)量,在本文有3種子任務(wù),分別是牽引、搬運(yùn)和裝卸;

3)T={T1,T2,T3,…,TMr},為所有任務(wù)集合,Ti為任務(wù)i,Mr為最大任務(wù)數(shù)量;

4)F={F1,F2,F3,…FMr},為任務(wù)約束集合,通常在AGV協(xié)同多任務(wù)中存在任務(wù)的時(shí)間約束、AGV是否協(xié)同搬運(yùn)的約束以及AGV自身能力的約束等。

1.3 設(shè)定約束條件

1)時(shí)間約束。Tfloor為該任務(wù)執(zhí)行時(shí)間的下限,Tceiling為該任務(wù)執(zhí)行時(shí)間的上限,t為子任務(wù)Ki的完成時(shí)間,具體表示為:

Tfloor≤t≤Tceiling

(1)

2)AGV功能約束。對(duì)AGV的功能進(jìn)行約束,即參與該項(xiàng)任務(wù)的AGV必須具有滿(mǎn)足該任務(wù)要求的能力。設(shè)定AGV所能完成的子任務(wù)集合為tasktype(Ai),假定該AGV可以完成子任務(wù)Kj,則滿(mǎn)足以下條件:

Kj∈tasktype(Ai)

(2)

(3)

1.4 設(shè)定調(diào)度優(yōu)化目標(biāo)

(4)

式中:L(Distancei)為AGVi在執(zhí)行某個(gè)任務(wù)時(shí)的行駛距離。

2)時(shí)間代價(jià)。設(shè)q(i)為AGV執(zhí)行子任務(wù)i的時(shí)間代價(jià),則任務(wù)實(shí)際完成時(shí)間的總和C2為:

(5)

3)利用率代價(jià)。為確保執(zhí)行任務(wù)過(guò)程中每個(gè)AGV行駛的路程都差不多,達(dá)到AGV利用率最大化,對(duì)AGV路徑代價(jià)進(jìn)行方差運(yùn)算,方差C3可以反映數(shù)據(jù)的離散程度。

(6)

將以上3個(gè)指標(biāo)進(jìn)行歸一化處理,可以得到AGV協(xié)同多任務(wù)分配問(wèn)題的綜合評(píng)價(jià)指標(biāo)Cmin為:

(7)

2 改進(jìn)的遺傳算法設(shè)計(jì)

本節(jié)提出一種改進(jìn)的遺傳算法[10],為使初始種群結(jié)構(gòu)多樣化,使用隨機(jī)函數(shù)構(gòu)建種群,在交叉變異階段采用自適應(yīng)迭代模式以防止陷入局部最優(yōu)并有效保留優(yōu)秀個(gè)體。具體算法流程如圖2所示。

圖2 算法流程

2.1 基于任務(wù)排序的染色體編碼

設(shè)W為任務(wù)分配矩陣,W=[wij]u×v,列數(shù)v為所有任務(wù)中子任務(wù)的總數(shù)量,如果某子任務(wù)為協(xié)同任務(wù),則該子任務(wù)次數(shù)為所需車(chē)輛數(shù);行數(shù)u為AGV數(shù)量。

(8)

矩陣W滿(mǎn)足以下條件:

3)每個(gè)任務(wù)分配矩陣W代表一個(gè)任務(wù)分配方案;

4)總共有u輛AGV,從1～u分別編號(hào),Pk,n表示Tk任務(wù)中Kn子任務(wù)需要幾輛AGV執(zhí)行,那么整個(gè)系統(tǒng)共有子任務(wù):

(9)

2.2 構(gòu)建初始種群

由于染色體編碼方式不同,且在交叉變異操作中AGV自身能力的原因造成種群多樣性減少,為使得初始種群在開(kāi)始階段就保持結(jié)構(gòu)優(yōu)良,提出改進(jìn)的構(gòu)建初始種群方法。

步驟1,根據(jù)AGV數(shù)量確定染色體矩陣行數(shù),根據(jù)子任務(wù)總數(shù)量確定染色體矩陣列數(shù);

步驟2,對(duì)染色體進(jìn)行約束調(diào)整,使得AGV自身能力符合任務(wù)要求;

步驟3,使用創(chuàng)建離散隨機(jī)種群的方式對(duì)染色體基因即矩陣中的列隨機(jī)生成0或1;

步驟4,對(duì)染色體進(jìn)行調(diào)整,若出現(xiàn)重復(fù)基因則采用覆蓋法消除;

步驟5,以上步驟重復(fù)20次,直到生成具有20個(gè)個(gè)體的初始種群。

2.3 自適應(yīng)迭代模式下的交叉變異

在染色體進(jìn)化初期,交叉率較大和變異率較小會(huì)有助于適應(yīng)度高的個(gè)體生成,而在后期優(yōu)秀個(gè)體已經(jīng)出現(xiàn),使用較小交叉率和較大變異率可以防止陷入局部最優(yōu),并且可以維持目前較高的適應(yīng)性群體。

(10)

(11)

1)交叉:每個(gè)AGV自身具有的能力不同,在交叉變異后不能改變自身能力,否則就會(huì)在實(shí)際工作中出現(xiàn)車(chē)輛與任務(wù)不相匹配的問(wèn)題。

2)變異:由于AGV自身能力不能發(fā)生改變,因此變異操作只可以在其自身能力范圍內(nèi)發(fā)生,表現(xiàn)為同能力的列可以交換。

2.4 適應(yīng)度計(jì)算

確定好染色體編碼后,通過(guò)評(píng)價(jià)指標(biāo)對(duì)其進(jìn)行篩選。在前文中已經(jīng)制定了相應(yīng)的評(píng)價(jià)指標(biāo),因此改進(jìn)遺傳算法中適應(yīng)度可以使用任務(wù)分配評(píng)價(jià)指標(biāo)來(lái)衡量。

(12)

式中:F(Si)為個(gè)體適應(yīng)度函數(shù)。選擇操作使用輪盤(pán)賭方法,按照適應(yīng)度從小到大進(jìn)行排序,本文取σ=0.4,τ=0.2,π=0.4。

2.5 精英保留

為了保持群體規(guī)模不變,如果子代個(gè)體被加入到新一代群體中,則可以將新一代群體中適應(yīng)度值最小的個(gè)體淘汰掉。精英個(gè)體是種群進(jìn)化到當(dāng)前為止遺傳算法搜索到的適應(yīng)度值最大的個(gè)體,它具有最好的基因結(jié)構(gòu)和優(yōu)良特性。采用精英保留的優(yōu)點(diǎn)是:遺傳算法在進(jìn)化過(guò)程中,迄今出現(xiàn)的最優(yōu)個(gè)體不會(huì)被選擇、交叉和變異操作所丟失和破壞。精英保留策略對(duì)改進(jìn)標(biāo)準(zhǔn)遺傳算法的全局收斂能力產(chǎn)生了重大作用,使用高斯罰函數(shù),δ=0.15。

(13)

2.6 迭代終止

算法達(dá)到了最大迭代次數(shù)Nm=100或者在交叉變異后Nr=20代個(gè)體中最佳個(gè)體沒(méi)有發(fā)生變化,則操作結(jié)束。

3 仿真與結(jié)果分析

3.1 對(duì)比仿真設(shè)置

為了驗(yàn)證本文提出的IGA的合理性,首先與最小空閑時(shí)間優(yōu)先原則(shortest vacancy time first,SVF)對(duì)比吞吐量(貨物運(yùn)送量),然后與GA(genetic algorithm,GA)及BBA(brand and bound algorithm,BBA)對(duì)比驗(yàn)證IGA的優(yōu)越性。

使用MATLAB進(jìn)行仿真，包括6臺(tái)具有不同能力的AGV，8個(gè)任務(wù)目標(biāo)，每個(gè)任務(wù)中都含有3種子任務(wù)類(lèi)型。表1為AGV的能力約束表，標(biāo)明了每臺(tái)AGV具有的能力。任務(wù)目標(biāo)由系統(tǒng)隨機(jī)生成。共設(shè)置了6組AGV數(shù)量不同的對(duì)比實(shí)驗(yàn)組，即對(duì)表1AGV實(shí)驗(yàn)組擴(kuò)充倍數(shù)，分別為1倍到6倍，每組仿真時(shí)間為24 h，AGV運(yùn)行速度為1 m/s。

表1 AGV能力約束表

3.2 仿真結(jié)果分析

圖3和圖4所示為第一組實(shí)驗(yàn)下的最終仿真結(jié)果,從圖中可看出,由于在算法中適應(yīng)度計(jì)算是基于總行程、總時(shí)間和AGV總利用率三者進(jìn)行的,因此在結(jié)果中可以發(fā)現(xiàn),IGA方法中有T3、T4、T6和T84個(gè)任務(wù)皆出現(xiàn)由同一輛AGV完成同一任務(wù)中多個(gè)子任務(wù)的現(xiàn)象,而在SVF中由同一輛AGV完成同一任務(wù)中多個(gè)子任務(wù)的情況幾乎沒(méi)有,說(shuō)明IGA算法會(huì)盡可能安排同一AGV執(zhí)行同一個(gè)任務(wù),減少了AGV不斷更換子任務(wù)導(dǎo)致的空車(chē)路程與空車(chē)行駛時(shí)間,這對(duì)于系統(tǒng)整體的優(yōu)化是有利的。

圖3 第一組實(shí)驗(yàn)IGA方法任務(wù)分配圖

圖4 第一組實(shí)驗(yàn)SVF方法任務(wù)分配圖

圖5所示為各組實(shí)驗(yàn)下兩種方法的系統(tǒng)總吞吐量,由圖可知,IGA算法相比SVF能明顯提高系統(tǒng)內(nèi)吞吐量,并且可以發(fā)現(xiàn),從第四組實(shí)驗(yàn)開(kāi)始,IGA算法吞吐量的增長(zhǎng)幅度逐漸減少,這是因?yàn)橄到y(tǒng)內(nèi)AGV數(shù)量已經(jīng)可以滿(mǎn)足當(dāng)前任務(wù)的需求,再增加AGV數(shù)量對(duì)系統(tǒng)并不會(huì)有太大好處。而SVF的增長(zhǎng)幅度并沒(méi)有實(shí)質(zhì)變化,說(shuō)明在同等數(shù)量AGV下,IGA算法可以有效提升AGV的利用率。

圖5 各組實(shí)驗(yàn)的系統(tǒng)總吞吐量

圖6所示為3種算法的適應(yīng)度值對(duì)比,雖然3種算法都可以得到相同的適應(yīng)度值,但I(xiàn)GA明顯比GA和BBA更加優(yōu)化,更快得到最佳適應(yīng)度值。

圖6 最佳適應(yīng)度值曲線(xiàn)圖

4 結(jié)束語(yǔ)

本文基于多任務(wù)理論基礎(chǔ)對(duì)AGV協(xié)同多任務(wù)分配進(jìn)行了研究。AGV種類(lèi)較多,一方面由于不同種AGV可執(zhí)行的任務(wù)不同,因此要對(duì)不同種類(lèi)AGV進(jìn)行能力限制;另一方面是任務(wù)數(shù)量多、類(lèi)型多,包括單AGV任務(wù)與多AGV協(xié)同執(zhí)行任務(wù)。在理論基礎(chǔ)上對(duì)其進(jìn)行數(shù)學(xué)建模并進(jìn)行多種類(lèi)型的約束,提出了一種改進(jìn)的遺傳算法,仿真分析結(jié)果證明該算法可以有效提升系統(tǒng)的吞吐量,相較于傳統(tǒng)遺傳算法性能更優(yōu)。