面向緩沖區(qū)容量有限的多載AGV系統(tǒng)調度研究

熊 曄，毛劍琳

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

自動導引車(Automated Guided Vechicle，AGV)在柔性制造系統(tǒng)、自動化集裝箱碼頭、自動化倉儲以及物流業(yè)中應用廣泛[1]。多載AGV是一種水平作業(yè)設備，一次搬運一件以上的制件，能大幅度提高了作業(yè)效率[2]。在傳統(tǒng)的AGV調度研究中，大多數都是假定AGV系統(tǒng)的緩沖區(qū)容量無限且以單載AGV研究為主，對多載且緩沖區(qū)容量有限得AGV系統(tǒng)研究甚少。

Azimi等[3]用仿真實驗提出了單載AGV的最優(yōu)調度策略；Ho等[4]提出了同時求解多載AGV的負載選擇和裝載調度問題的多屬性方法；Fazlollahtabar等[5]提出了一種自動化集裝箱碼頭最小化多載AGV提前與延遲時間的綜合啟發(fā)算法；谷寶慧[6]針對單載AGV載重和運送貨箱體積限定問題簡歷AGV路徑優(yōu)化模型，利用改進的量子微粒群算法進行實現；杜亞江[7]等建立了復雜約束的單載AGV多參數問題數學模型，采用混合遺傳算法優(yōu)化了調度時間。

以上研究大多以緩沖區(qū)容量有限、AGV只能進行單載操作為主。在實際的FMS中，多數AGV系統(tǒng)加工區(qū)中緩沖區(qū)容量都是有限的，且多載AGV有著節(jié)約運輸成本、提高整體系統(tǒng)效率的優(yōu)點。因此，對柔性制造系統(tǒng)(Flexible Manufacturing System，FMS)中的加工區(qū)緩沖區(qū)容量的多載AGV調度進行研究具有十分重要的理論和應用價值。

本文從提高柔性制造系統(tǒng)AGV作業(yè)效率入手，以加工區(qū)緩沖區(qū)容量、AGV的負載為約束，建立緩沖區(qū)容量有限的多載AGV調度模型，使用融合了灰狼優(yōu)化算法思想的混合灰狼遺傳算法求解，并與傳統(tǒng)遺傳算法進行對比，模擬實驗結果驗證了新算法的優(yōu)越性。

1 問題描述

一個典型的柔性制造系統(tǒng)作業(yè)車間包括AGV小車、緩沖區(qū)有限的加工區(qū)、導向網絡和倉庫，其平面構造圖如圖1所示。AGV按需求一次可運送一個大制件或者兩個小制件進入FMS中，由倉庫駛出進入FMS，經過5個加工區(qū)的作業(yè)后返回倉庫，即為完成一個循環(huán)。

圖1 柔性制造系統(tǒng)作業(yè)車間的構造平面圖

一個特定FMS中有一個AGV和一個制件集，目的是最小化所有任務時間：計算出每個制件在每臺機器的加工時間以及每個輸入/輸出緩沖區(qū)的時間，從而確定每個機器與機器之間所走路程的起始和完成時間。

2 模型建立

在數學模型中，符號定義如下：

M：加工區(qū)集；

W：制件集；

A：搬運任務集；

N：任務次序集；

G：系統(tǒng)允許的最大制件量；

m：加工區(qū)編號，m∈M，Mo表示倉庫；

w：制件編號，w∈W；

A：任務編號，a∈A；

n：任務執(zhí)行的次序編號，n∈N；

CIm：加工區(qū)m的輸入緩沖區(qū)容量，CIm>0；

COm：加工區(qū)m的輸出緩沖區(qū)容量，COm=CIm；

CImh：加工區(qū)m的輸入緩沖區(qū)的剩余可容納制件的量；

Im：加工區(qū)m的輸入緩沖區(qū)上的制件個數；

COmh：加工區(qū)m的輸出緩沖區(qū)的剩余可容納制件的量；

Cm：加工區(qū)m的輸出緩沖區(qū)上的制件數。

Um：表示在加工區(qū)m上現有的制件數；

Twm：制件w在加工區(qū)m上的加工時間；

Uwm：表示制件w在加工區(qū)m上加工；

Tbm：為制件w在加工區(qū)m上的開始加工時間；

Tem：為制件w在加工區(qū)m上的結束加工時間；

Tq：AGV裝載制件的固定時間；

Tf：AGV卸載制件的固定時間；

Tba：AGV的搬運任務a的開始時間；

Tea：AGV的搬運任務a的結束時間；

Tb(m1,m2)：AGV從加工區(qū)m1移動到m2的所用時間；

Ta：AGV執(zhí)行任務a所用的時間；

Cq：任務q完成操作后AGV容量的占用情況；

C：AGV最大負荷能力；

D：AGV在任務q完成后的容量改變情況。

定義決策變量

緩沖區(qū)容量有限的多載AGV調度問題，以最小化多載AGV完成調度集內所有任務花費時間最短為目標，建立數學模型，模型的目標函數與約束條件如下

(1)

式(1)表示自動導引小車完成調度集內全部任務所用最短時間。自動導引小車每次完成且只完成一個任務以式(2)表示。

(2)

搬運任務a的結束時間減去開始時間為AGV完成一次搬運任務所耗費的時間

Tea-Tba=xnaTa,?a∈A,n∈N

(3)

后一個任務開始時間等于前一個任務的結束時間，即

x(n+1)kTbk=xnaTea,?a,k∈A∩a≠k,n∈N

(4)

加工區(qū)輸出緩沖區(qū)上有多個制件，則存在一個加工區(qū)分配多個搬運任務時，在調度時段，相同加工區(qū)的任務只能按分配時間的先后執(zhí)行

n>1,Cm>1,xnaTbm>xlkTem,?a,k∈A∩a≠k,n,
l∈N∩n≠1

(5)

一個加工區(qū)一次只能加工一個制件

bmwj+bmjw=1,?w,j∈W,m∈M

(6)

系統(tǒng)現有制件數不可超過系統(tǒng)承受的最大制件數

(7)

輸入緩沖區(qū)的容量不滿時，完成一次搬運任務所耗時等價于小車從當前位置空載移動到目標制件所在的加工區(qū)、目標制件裝載的時間、AGV移動到目標加工區(qū)輸入緩沖區(qū)的時間、目標制件卸載的時間的總和

xnaTa=Tb(Ya,Xwa)+Tq+Ta(XwaUwm)+Tf,CImh≠0,
?a∈A,w∈W,n∈N

(8)

輸入緩沖區(qū)的剩余容量為零時，AGV完成一次搬運任務所耗時等價于在目標加工區(qū)上的制件的結束加工時間及目標制件卸載的時耗總和

xnaTa=ymwTem+Tf,CImh=0,ymwj=1,?w,j∈W,
w≠j,a∈A,n∈N

(9)

輸入/輸出緩沖區(qū)的剩余容量為輸入/輸出緩沖區(qū)容量減去輸入/輸出緩沖區(qū)上的制件數

CImh=CIm-Im,?m∈M

(10)

COmh=COm-Om,?m∈M

(11)

輸入緩沖區(qū)的制件數、輸出緩存區(qū)上的制件、加工區(qū)上正在加工的制件數的總和即為加工區(qū)現有的制件數

Um=Im+Om+ymwj,?w,j∈W,w≠j,m∈M

(12)

加工區(qū)的輸出緩存器剩余容量不為零時，制件的加工結束時間等于制件的加工開始時間加上制件在加工區(qū)上的加工時間

Tem=Tbm+Twm,?m∈M,w∈W,COmh≠0

(13)

加工區(qū)的輸出緩存器為滿時，制件加工完畢之后需等候進入輸出緩存區(qū)

Tem>Tbm+Twm,?m∈M,w∈W,COmh=0

(14)

AGV相繼完成任務q、p后AGV的負載變化如下

zqp(Cq+dp-Cp)=0

(15)

對AGV負載的約束為

dq≤Cq≤C

(16)

0≤Cp≤C+dp

(17)

3 多載混合灰狼遺傳算法(MHGWOGA)

灰狼優(yōu)化算法(Gery Wolf Optimization，GWO)是由Mirjalili S等[8]在2014年提出的新算法，通過模仿自然界灰狼種群領導層級和以及狼群跟蹤、包圍獵物的狩獵過程來實現優(yōu)化。GWO算法能在解空間中快速找出最優(yōu)解，避免出現局部最優(yōu)[9]。

本文將GWO算法中灰狼社會等級、狩獵機制引入至標準遺傳算法的選擇算子中，克服了傳統(tǒng)的遺傳算法易早熟的缺點，提高了算法全局搜索的效率。

3.1 編碼與解碼

本文研究的是AGV任務排序問題，選擇加工區(qū)的序數方式進行編碼[10]，將搬運任務集內的任務進行排序，自動導引小車執(zhí)行的任務的先后順序從而決定制件去加工區(qū)作業(yè)的順序。同一個加工區(qū)使用相同的編號，如圖2所示。

圖2 編碼解釋

解碼按照AGV單載、多載需求開始進行。針對同一加工區(qū)的不同任務，AGV會根據任務工件的大小來判斷是使用單載AGV還是多載AGV執(zhí)行任務，執(zhí)行任務的順序是根據染色體中出現的同一序號的順序執(zhí)行：同一個加工區(qū)發(fā)出的第一個任務是染色體基因中出現的第一個序號，以此類推，即可得出同一加工區(qū)的不同任務的執(zhí)行順序。

3.2 適應度函數

適應度函數設計為

(18)

3.3 選擇

選擇操作是為了避免優(yōu)良基因的損失，使性能好的個體生存繁殖的概率增大[11]。這里采用輪盤賭和精英選擇結合的方法。若不采用精英保留策略，僅是采用輪盤賭選擇算子，會造成優(yōu)良的個體缺失，因此引入灰狼優(yōu)化算法來化解這個矛盾。

在每一次選擇操作的時候保留α、β、δ3種個體，形成如圖3所示的灰狼內部社會等級地位，三者適應度關系滿足式(19)。剩余的個體即是ω，整個種群在α、β、δ的領導下向全局最優(yōu)解進化。

圖3 灰狼層級金字塔圖

(19)

灰狼需先判斷獵物位置并進行包圍，數學表達式如下

D=|C*Xp(t)-X(t)|

(20)

其中，Xp(t)表示第t代獵物位置向量；X(t)表示第t代時灰狼位置向量；常數C為擺動因子[12]，由式(21)決定

C=2r1

(21)

r1為[0,1]區(qū)間的隨機值，對灰狼位置更新

X(t+1)=Xp(t)-A*D

(22)

其中收斂因子A由式(23)決定

A=2a*r2-a

(23)

其中，r2亦為[0，1]區(qū)間的隨機值。a在迭代過程中從2線性下降到0，計算公式如式(24)所示

(24)

在追捕過程中，α帶領β、δ狼完成狩獵行為，即由α、β、δ狼距離獵物的位置，判斷獵物的大致位置后，對獵物進行追捕。狼群狩獵的原理[13]如圖4所示。

圖4 灰狼狩獵原理圖

(25)

Dβ=C2*Xβ(t)-X(t)

(26)

Dδ=C3*Xδ(t)-X(t)

(27)

X1=Xα-A1*Dα

(28)

X2=Xβ-A2*Dβ

(29)

X3=Xδ-A3*Dδ

(30)

X(t+1)=(X1+X2+X3)/3

(31)

其中，Xα表示α當前位置，Xβ表示β當前位置，Xδ表示δ當前位置，X(t)為第t代灰狼的位置向量[14]。由式(25)～式(30) 計算出個體與α、β、δ之間的距離，然后由式(31)即可定義出獵物的最終方位。

改進后的選擇步驟如下：

步驟1初始化隨機狼群；

步驟2計算出每頭狼對應的適應度值；

步驟3將適應度排列前3的灰狼個體位置分別記為α、β、δ；

步驟4按照式(25)～式(27)計算其它個體與α、β、δ的距離，并根據式(28)～式(30)計算每個灰狼個體的位置；

步驟5更新參數a、A、C等參數的值；

步驟6如不滿足結束條件，跳轉至步驟2；

步驟7導出α狼的位置；

步驟8按輪盤賭規(guī)則選擇個體復制到下一代。

3.4 交叉

本文采用了部分映射交叉方式，隨機產生兩個隨機數p，q∈[2，n-1]，交換兩個染色體i和j位于p和q之間的基因片段，映射交叉操作如圖5所示[15]。

圖5 部分映射交叉示意圖

3.5 變異

本文中的變異方法采用倒置變異[16]，也就是在染色體上隨機選擇兩個位置，然后顛倒兩個基因序列，如圖6所示。

圖6 倒置變異示意圖

4 數學實驗

為驗證混合灰狼遺傳算法的有效性，本文以某柔性制造車間為例，設計一組仿真實驗。該FMS中存在5個加工區(qū)和1個倉庫。每個加工區(qū)均配有容量為3的輸入緩沖區(qū)F1和容量為3的輸出緩沖區(qū)F2。制件從倉庫出發(fā)，經過加工區(qū)后運回，倉庫加工區(qū)分別用a、b、c、d、e表示，倉庫用0來表示。

AGV的移動路徑時間如表1所示，制件在不同加工區(qū)的加工時間如表2所示。

表1 AGV的移動路徑時間

表2 制件在不同加工區(qū)加工時間

通過MATLAB進行實驗仿真，使用傳統(tǒng)的遺傳算法和本文設計的混合灰狼遺傳算法對緩沖區(qū)容量有限的多載AGV調度模型進行求解，得出AGV配送及加工完成所有制件的總時間。參數設置如下：初始種群規(guī)模為50；交叉概率Pc為0.6；變異概率Pm為0.01。在制件數不同的情況下，仿真結果如表3所示。HGWOGA最優(yōu)解、GA最優(yōu)解的列表示為分別采用單載AGV模型混合灰狼遺傳算法和單載AGV模型遺傳算法進行調度后AGV配送及加工完成所有制件的總時間。MHGWOGA最優(yōu)解、MGA最優(yōu)解的列表為分別采用多載AGV模型混合灰狼遺傳算法和多載AGV模型遺傳算法進行調度后，AGV配送及加工完成所有制件的總時間。

表3 制件數不同時4種算法的調度結果

上表可看出，當制件數<15時，4種算法都能得到相同的最優(yōu)解。但是隨著制件數的增加，當制件數>15時，MHGWOGA算法的調度時間要遠小于HGWOGA算法的調度時間，且當制件數>20時，單載AGV系統(tǒng)已經發(fā)生死鎖，而多載AGV系統(tǒng)仍然能運行至22個制件。這說明本文所提出的緩沖區(qū)容量有限的混合灰狼遺傳算法多載AGV調度模型較單載AGV調度模型的改進策略是有效的。

以1表示小制件，2表示大制件，確定制件從倉庫的運出次序。以制件數分別為15、20為例，設定制件運出次序分別為1，2，1，2，1，1，1，1，2，1，2，1，1，2，2和1，2，2，1，1，2，1，2，1，1，2，1，2，1，1，1，1，2，1，1 ，可得出圖7、圖8兩種算法的進化迭代圖。

圖7 制件數為15兩種算法進化過程對比

圖8 制件數為20兩種算法進化過程對比

從圖中可以看出，當制件數為15時，MGA算法約在10代收斂，MHGWOGA算法約在3代就已經達到收斂；當制件數為20時，MGA算法約在90代收斂，而MHGWOGA算法約在10代就已經達到收斂，后者的收斂速度要遠快于前者的收斂速度，且能得到更好的最優(yōu)解。這也說明了MHGWOGA算法的有效性。

5 結束語

本文針對FMS中緩沖區(qū)容量有限的多載AGV調度模型，通過將灰狼優(yōu)化算法中的社會等級、狩獵制度引入傳統(tǒng)的遺傳算法中，提出了一種全新的多載混合灰狼遺傳算法，大幅提升了算法的搜索能力。仿真實驗結果表明，相對于傳統(tǒng)的遺傳算法，MHGWOGA算法能有效求解緩沖區(qū)容量有限的多載AGV調度的問題，且具有收斂速度快、得到調度更優(yōu)解及提升AGV調度效率的優(yōu)點。但在實際生產中，存在大量有限緩沖區(qū)的多載AGV情況，仍亟待深入研究。