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

熊曄+毛劍琳+郭寧+付麗霞

摘要：實(shí)際柔性制造系統(tǒng)中，由于加工區(qū)緩沖區(qū)容量有限，導(dǎo)致AGV配送任務(wù)時(shí)間延長，降低了系統(tǒng)工作效率。為解決此問題，建立緩沖區(qū)容量有限的AGV系統(tǒng)調(diào)度數(shù)學(xué)優(yōu)化模型，提出混合灰狼遺傳算法對AGV系統(tǒng)進(jìn)行優(yōu)化。新算法在傳統(tǒng)遺傳算法選擇操作上，結(jié)合灰狼優(yōu)化算法中的種群等級制度和灰狼狩獵機(jī)制，避免了傳統(tǒng)精英策略中種群多樣性變差的特點(diǎn)，增強(qiáng)了全局搜索能力。仿真結(jié)果表明：混合灰狼遺傳算法較傳統(tǒng)遺傳算法具有更快的收斂速度，能得到更優(yōu)解，提高AGV調(diào)度的效率，驗(yàn)證了相關(guān)改進(jìn)機(jī)制的有效性。

關(guān)鍵詞：柔性制造系統(tǒng)；AGV配送；緩沖區(qū)容量有限；AGV系統(tǒng)調(diào)度；混合灰狼遺傳算法

DOIDOI：10.11907/rjdk.172156

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：1672-7800（2018）001-0152-05

Abstract：In the actual flexible manufacturing system， due to the limited capacity of the processing zone buffer， AGV delivery task time is prolonged， the processing cost is increased， and the working efficiency of the system is reduced. In order to solve this problem， a mathematical model of AGV system scheduling optimization with limited buffer capacity is established. A hybrid grey wolf optimization and genetic algorithm （HGWOGA） is proposed to optimize the AGV system. The new algorithm in the selection operation， combined with the gray wolf optimization algorithm in the population hierarchy and gray wolf hunting mechanism， to avoid the traditional elite strategies in the diversity of the characteristics of population diversity， and enhance the global search capabilities The simulation results show that the hybrid wolf genetic algorithm has faster convergence rate than traditional genetic algorithm， can get better solution， improve the efficiency of AGV scheduling， and verify the effectiveness of the relevant improvement mechanism.

Key Words：Flexible Manufacturing System （FMS）； AGV distribution； limited buffer capacity； AGV system scheduling； HGWOGA

0引言

在柔性制造系統(tǒng)（Flexible Manufacturing System，F(xiàn)MS）中，自動(dòng)化搬運(yùn)系統(tǒng)有顯著地位。常見的自動(dòng)化搬運(yùn)設(shè)備有堆垛機(jī)、傳送帶和自動(dòng)導(dǎo)引小車（Automatic Guided Vehicle，AGV）等[1]，而AGV有代替人工、節(jié)省成本；充電、驅(qū)動(dòng)系統(tǒng)耗能少；能源利用率高、噪音低等優(yōu)點(diǎn)[2]。在集成化生產(chǎn)環(huán)境中，AGV是連接倉庫和生產(chǎn)車間的重要環(huán)節(jié)，成為FMS中不可或缺的重要組成部分。

傳統(tǒng)AGV的研究大致分為兩個(gè)方向：AGV系統(tǒng)的路徑規(guī)劃和AGV在車間的調(diào)度研究，但主要研究集中在AGV系統(tǒng)路徑和生產(chǎn)效率優(yōu)化方面[3]，AGV在車間調(diào)度中的影響研究較少。喬巖[4]等研究了基于改進(jìn)時(shí)間窗的AGVs的避障路徑規(guī)劃。谷寶慧[5]針對AGV載重和運(yùn)送貨箱體積限定問題建立AGV路徑優(yōu)化模型，利用改進(jìn)的量子微粒群算法實(shí)現(xiàn)。劉旭[6]等針對多AGV在混流作業(yè)車間配送物料問題，運(yùn)用一種改進(jìn)的遺傳算法來進(jìn)行求解。Nishi[7]等針對柔性制造系統(tǒng)中多AGV路徑規(guī)劃問題，建立多AGV調(diào)度模型，提出了一種分解算法進(jìn)行求解。杜亞江[8]等建立了復(fù)雜約束的AGV多參數(shù)問題數(shù)學(xué)模型，采用混合遺傳算法優(yōu)化了調(diào)度時(shí)間。

上述研究中有多數(shù)未考慮加工區(qū)緩沖區(qū)容量有限的情況，針對AGV在物料配送、AGV路徑最優(yōu)的方面進(jìn)行研究，而在實(shí)際生產(chǎn)應(yīng)用中，很多情況下加工區(qū)的緩沖區(qū)是有限的，并且存在大量的單AGV的生產(chǎn)系統(tǒng)，因此對FMS中的加工區(qū)緩沖區(qū)容量的單AGV調(diào)度進(jìn)行研究具有十分重要的理論和應(yīng)用價(jià)值[9]。

本文對緩沖區(qū)容量有限的單AGV系統(tǒng)調(diào)度問題進(jìn)行了分析，建立了問題優(yōu)化模型，分析了模型的特點(diǎn)。針對優(yōu)化模型提出了混合灰狼遺傳算法，在傳統(tǒng)遺傳算法的選擇算子中引入了灰狼優(yōu)化算法中灰狼社會(huì)等級、狩獵機(jī)制理念進(jìn)行求解。模擬實(shí)驗(yàn)結(jié)果顯示：本文提出的混合灰狼遺傳算法具有有效性。

1AGV調(diào)度問題

1.1問題描述

一個(gè)典型的柔性制造系統(tǒng)作業(yè)車間包括AGV小車、緩沖區(qū)有限的加工區(qū)、導(dǎo)向網(wǎng)絡(luò)和倉庫，其平面構(gòu)造圖如圖1所示。AGV進(jìn)入FMS的先后順序是確定的，并視作AGV在系統(tǒng)中的流動(dòng)路線為一個(gè)循環(huán)，制件從倉庫出發(fā)，按加工次序依次流經(jīng)各個(gè)加工機(jī)器進(jìn)行加工最終回到倉庫。AGV小車將制件w從當(dāng)前加工區(qū)移動(dòng)到目標(biāo)加工區(qū)m上的一個(gè)過程定義為一次搬運(yùn)任務(wù)。endprint

在一個(gè)給定的柔性制造系統(tǒng)中，有一臺(tái)自動(dòng)導(dǎo)引車和一個(gè)制件集，目標(biāo)是使得完成整個(gè)過程的時(shí)間最短，計(jì)算每個(gè)制件在每臺(tái)機(jī)器的加工時(shí)間和每個(gè)輸入/輸出緩沖區(qū)的時(shí)間，確定每個(gè)機(jī)器與機(jī)器之間所走路程的起始和完成時(shí)間。

為了便于研究，作如下假設(shè)：

（1）AGV一次僅執(zhí)行一次任務(wù)。

（2）每個(gè)加工區(qū)每次只加工一個(gè)制件。

（3）輸入緩沖區(qū)和輸出緩沖區(qū)容量有限不為零且相等。

（4）制件在整個(gè)加工過程中不中止。

（5）自動(dòng)導(dǎo)引車的起始位置處于倉庫緩沖區(qū)內(nèi)，等待自動(dòng)導(dǎo)引車執(zhí)行完當(dāng)前任務(wù)后，駛?cè)氩⑼Ｔ趧倛?zhí)行完的任務(wù)的緩沖區(qū)內(nèi)，等待指令，準(zhǔn)備執(zhí)行另一個(gè)任務(wù)。

1.2調(diào)度模型

M：加工區(qū)集：

W：制件集；

A：搬運(yùn)任務(wù)集；

N：任務(wù)次序集；

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

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

w：制件編號(hào)，w∈W；

A：任務(wù)編號(hào)，a∈A；

n：任務(wù)執(zhí)行的次序編號(hào)，n∈N；

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

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

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

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

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

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

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

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

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

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

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

Tq：AGV裝載制件的固定時(shí)間；

Tf：AGV卸載制件的固定時(shí)間；

Tba：AGV的搬運(yùn)任務(wù)a的開始時(shí)間；

Tea：AGV的搬運(yùn)任務(wù)a的結(jié)束時(shí)間；

Xwa：搬運(yùn)任務(wù)a開始時(shí)制件w所在的加工區(qū)；

Ya：AGV的搬運(yùn)任務(wù)a開始時(shí)AGV所在的加工區(qū)；

Tb（m1，m2）：AGV從加工區(qū)m1移動(dòng)到m2的所用時(shí)間；

Ta：AGV執(zhí)行任務(wù)a所用的時(shí)間。

式（1）表示AGV完成調(diào)度集內(nèi)全部任務(wù)所用時(shí)間最短；式（2）是AGV每次完成且只完成一個(gè)任務(wù)。式（3）是搬運(yùn)任務(wù)a的結(jié)束時(shí)間減去搬運(yùn)任務(wù)a的開始時(shí)間即為AGV完成一次搬運(yùn)任務(wù)所耗費(fèi)的時(shí)間；式（4）是后一個(gè)任務(wù)開始時(shí)間等于前一個(gè)任務(wù)的結(jié)束時(shí)間；式（5）表示加工區(qū)的輸出緩沖區(qū)上有多個(gè)制件，則存在一個(gè)加工區(qū)分配多個(gè)搬運(yùn)任務(wù)時(shí)，在調(diào)度時(shí)段，相同加工區(qū)的任務(wù)只能按分配時(shí)間的先后執(zhí)行。式（6）是一個(gè)加工區(qū)一次只能加工一個(gè)制件；式（7）表示系統(tǒng)的現(xiàn)有制件數(shù)不可超過系統(tǒng)承受的最大制件數(shù)；式（8）表示輸入緩沖區(qū)的容量不滿時(shí)，完成一次搬運(yùn)任務(wù)所耗時(shí)等價(jià)于小車從當(dāng)前位置空載移動(dòng)到目標(biāo)制件所在的加工區(qū)加上目標(biāo)制件裝載的時(shí)間再加上AGV移動(dòng)到目標(biāo)加工區(qū)的輸入緩沖區(qū)的時(shí)間和目標(biāo)制件卸載的時(shí)間；式（9）表示輸入緩沖區(qū)的剩余容量為零時(shí)，AGV完成一次搬運(yùn)任務(wù)所耗時(shí)等價(jià)于在目標(biāo)加工區(qū)上的制件的結(jié)束加工時(shí)間加上目標(biāo)制件卸載的時(shí)耗；式（10）和（11）表示輸入/輸出緩沖區(qū)容量減去輸入/輸出緩沖區(qū)上的制件數(shù)即是輸入/輸出緩沖區(qū)的剩余容量；式（12）輸入緩沖區(qū)的制件數(shù)加上輸出緩存區(qū)上的制件再加上加工區(qū)上正在加工的制件數(shù)即加工區(qū)現(xiàn)有的制件數(shù)；式（13）表示加工區(qū)的輸出緩存器剩余容量不為零時(shí)，制件的加工結(jié)束時(shí)間等于制件的加工開始時(shí)間加上制件在加工區(qū)上的加工時(shí)間；式（14）表示加工區(qū)的輸出緩存器為滿時(shí)，制件加工完畢之后需等候進(jìn)入輸出緩存區(qū)。

2混合灰狼遺傳算法

灰狼優(yōu)化算法（Gery Wolf Optimization，GWO）是由Mirjalili S等[10]在2014年提出的新算法，原理為模仿自然界灰狼種群領(lǐng)導(dǎo)層級和以及狼群跟蹤、包圍獵物的狩獵過程來實(shí)現(xiàn)優(yōu)化。GWO算法能在解空間中快速找出最優(yōu)解，避免出現(xiàn)局部最優(yōu)[11]。

本文將GWO算法中灰狼社會(huì)等級、狩獵機(jī)制引入至標(biāo)準(zhǔn)遺傳算法的選擇算子中，來克服了傳統(tǒng)的遺傳算法易早熟的缺點(diǎn)，從而提高了算法全局搜索的效率。新算法流程如圖2所示。

2.1編碼與解碼

本文研究的是AGV任務(wù)排序問題，則選擇加工區(qū)的序數(shù)方式進(jìn)行編碼，將搬運(yùn)任務(wù)集內(nèi)的任務(wù)數(shù)中加工區(qū)進(jìn)行排序，AGV小車任務(wù)的先后順序按照加工區(qū)序號(hào)執(zhí)行，同一個(gè)加工區(qū)使用相同的編號(hào)。例如：某染色體的編碼為“3 5 1 4 3 6 2 3”（如圖3所示）。

2.2適應(yīng)度函數(shù)

緩沖區(qū)容量有限的AGV 調(diào)度模型適應(yīng)度函數(shù)設(shè)計(jì)為：

2.3選擇算子設(shè)計(jì)

本文是采用輪盤賭和精英選擇策略結(jié)合的方式。如果不采用精英保留策略，僅是采用輪盤賭選擇算子，這樣就會(huì)導(dǎo)致優(yōu)良的個(gè)體丟失，為了解決這個(gè)矛盾引入灰狼優(yōu)化算法的理念。

在每一次選擇操作的時(shí)候保留α，β，δ 3種個(gè)體，形成如圖4所示的灰狼內(nèi)部社會(huì)層級地位，三者適應(yīng)度關(guān)系滿足式（16）。剩余的個(gè)體即是ω，整個(gè)種群在α，β，δ的領(lǐng)導(dǎo)下向全局最優(yōu)解進(jìn)化。

Xα表示α當(dāng)前位置，Xβ表示β當(dāng)前位置，Xδ表示δ當(dāng)前位置，X（t） 表示第t代灰狼的位置向量。由式（22）-式（27） 計(jì)算出個(gè)體與α，β，δ的距離，然后由式（28）即可定義出獵物的最終方位。

改進(jìn)后的選擇步驟如下：

step1：初始化隨機(jī)狼群。endprint

step2：計(jì)算出每頭狼對應(yīng)的適應(yīng)度值。

step3：將適應(yīng)度排列前三的灰狼個(gè)體位置分別記為α，β，δ。

step4：按照式（22）-（24）計(jì)算其它個(gè)體與α，β，δ的距離，并根據(jù)式（25）-（28）計(jì)算每個(gè)灰狼個(gè)體的位置。

step5：更新參數(shù)a，A，C等參數(shù)的值。

step6：如不滿足結(jié)束條件，轉(zhuǎn)到第二步。

step7：導(dǎo)出α狼的位置。

step8：按輪盤賭規(guī)則選擇個(gè)體復(fù)制到下一代

2.4交叉算子設(shè)計(jì)

本文采用了部分映射交叉方式，隨機(jī)產(chǎn)生兩個(gè)隨機(jī)數(shù)p，q∈[2，n-1]，交換兩個(gè)染色體i和j位于p和q之間的基因片段，映射交叉操作如圖6所示[12]。為了分散開染色體上的基因，不讓其聚集在一個(gè)小的范圍，交叉操作之后要檢驗(yàn)子代的染色體上相鄰基因的距離，兩個(gè)基因距離小于一定值時(shí)便認(rèn)為兩個(gè)基因重復(fù)，在原基因的鄰域產(chǎn)生一個(gè)新的基因替換原來的基因。

2.5變異算子設(shè)計(jì)

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

3仿真實(shí)驗(yàn)與分析

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

AGV的移動(dòng)路徑時(shí)間如表1所示。

通過Matlab進(jìn)行實(shí)驗(yàn)仿真，使用傳統(tǒng)的遺傳算法和本文設(shè)計(jì)的混合灰狼遺傳算法對緩沖區(qū)容量有限的AGV調(diào)度模型求解，得出AGV配送及加工完成所有制件的總時(shí)間。參數(shù)設(shè)置如下：初始種群規(guī)模為50；交叉概率Pc為0.6；變異概率Pm為0.01；在制件數(shù)不同的情況下，仿真結(jié)果如表2所示。標(biāo)記為HGWOGA最優(yōu)解、GA最優(yōu)

解的列表示為分別采用HGWOGA和GA算法進(jìn)行調(diào)度后AGV配送及加工完成所有制件的總時(shí)間（s），H/G列表示HGWOGA相對于GA算法提高AGV調(diào)度系統(tǒng)的比率。

由表2可看出，當(dāng)制件數(shù)小于15時(shí)，兩種算法都能得到相同的最優(yōu)解，但是隨著制件數(shù)的增加，當(dāng)制件數(shù)大于15時(shí)，HGWOGA算法的調(diào)度時(shí)間要遠(yuǎn)小于GA算法的調(diào)度時(shí)間，且平均能提高5%左右的調(diào)度效率，這能夠說明本文所提出的混合灰狼遺傳算法對緩沖區(qū)容量有限的AGV調(diào)度模型的改進(jìn)策略是有效的。

由圖8，圖9可以看出，當(dāng)制件數(shù)為15時(shí)，GA算法在20代左右收斂，HGWOGA算法在10代左右就已經(jīng)達(dá)到收斂；當(dāng)制件數(shù)為20時(shí)，GA算法在60代左右收斂，HGWOGA算法在20代左右就已經(jīng)達(dá)到收斂，HGWOGA算法的收斂速度要遠(yuǎn)遠(yuǎn)快于GA算法的收斂速度，且能得到更好的最優(yōu)解。這也能說明HGWOGA算法的有效性。

4結(jié)語

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

參考文獻(xiàn)：

[1]楊鋒英，劉會(huì)超.AGV作業(yè)調(diào)度模型及改進(jìn)的DE算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（9）：225-230.

[2]王皖君，張為公.自動(dòng)導(dǎo)引車導(dǎo)引技術(shù)研究現(xiàn)狀與發(fā)展趨勢[J].傳感器與微系統(tǒng)，2009，28（12）：5-7.

[3]任乃飛，于璐.基于混合遺傳算法的協(xié)同制造系統(tǒng)調(diào)度研究[J].電子科技，2016，29（6）：29-33.

[4]喬巖，錢曉明，樓佩煌.基于改進(jìn)時(shí)間窗的AGVs避碰路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18（12）：2683-2688.

[5]湯旻安，谷寶慧.改進(jìn)PSO在AGV系統(tǒng)路徑優(yōu)化調(diào)度中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（3）：261-265.

[6]劉旭，樓佩煌，錢曉明，等.基于改進(jìn)遺傳算法的物料配送多AGV調(diào)度優(yōu)化[J].機(jī)械設(shè)計(jì)與制造工程，2015（3）：16-21.

[7]NISHI T， HIRANAKA Y， GROSSMANN I E. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles[J]. Computers & Operations Research，2011，38（5）：876-888.

[8]杜亞江，鄭向東，亢麗君.基于遺傳禁忌搜索算法的AGV物料輸送調(diào)度問題研究[J].物流科技，2013，36（7）：1-4.

[9]周巧.面向緩存有限的柔性制造系統(tǒng)單AGV調(diào)度研究[D].廣東工業(yè)大學(xué)，2014.

[10]MIRJALILI S， MIRJALILI S M， LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software，2014，69（3）：46-61.

[11]龍文，趙東泉，徐松金.求解約束優(yōu)化問題的改進(jìn)灰狼優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2015，35（9）：2590-2595.

[12]黃英杰.基于目標(biāo)級聯(lián)法和智能優(yōu)化算法的車間調(diào)度問題研究[D].華南理工大學(xué)，2012.

[13]霍凱歌，張亞琦，胡志華.自動(dòng)化集裝箱碼頭多載AGV調(diào)度問題研究[J].大連理工大學(xué)學(xué)報(bào)，2016，56（3）：244-251.

（責(zé)任編輯：劉亭亭）endprint