面向緩沖區容量有限的AGV系統調度研究

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

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

關鍵詞：柔性制造系統；AGV配送；緩沖區容量有限；AGV系統調度；混合灰狼遺傳算法

DOIDOI：10.11907/rjdk.172156

中圖分類號：TP319

文獻標識碼：A文章編號文章編號：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引言

在柔性制造系統（Flexible Manufacturing System，FMS）中，自動化搬運系統有顯著地位。常見的自動化搬運設備有堆垛機、傳送帶和自動導引小車（Automatic Guided Vehicle，AGV）等[1]，而AGV有代替人工、節省成本；充電、驅動系統耗能少；能源利用率高、噪音低等優點[2]。在集成化生產環境中，AGV是連接倉庫和生產車間的重要環節，成為FMS中不可或缺的重要組成部分。

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

上述研究中有多數未考慮加工區緩沖區容量有限的情況，針對AGV在物料配送、AGV路徑最優的方面進行研究，而在實際生產應用中，很多情況下加工區的緩沖區是有限的，并且存在大量的單AGV的生產系統，因此對FMS中的加工區緩沖區容量的單AGV調度進行研究具有十分重要的理論和應用價值[9]。

本文對緩沖區容量有限的單AGV系統調度問題進行了分析，建立了問題優化模型，分析了模型的特點。針對優化模型提出了混合灰狼遺傳算法，在傳統遺傳算法的選擇算子中引入了灰狼優化算法中灰狼社會等級、狩獵機制理念進行求解。模擬實驗結果顯示：本文提出的混合灰狼遺傳算法具有有效性。

1AGV調度問題

1.1問題描述

一個典型的柔性制造系統作業車間包括AGV小車、緩沖區有限的加工區、導向網絡和倉庫，其平面構造圖如圖1所示。AGV進入FMS的先后順序是確定的，并視作AGV在系統中的流動路線為一個循環，制件從倉庫出發，按加工次序依次流經各個加工機器進行加工最終回到倉庫。AGV小車將制件w從當前加工區移動到目標加工區m上的一個過程定義為一次搬運任務。endprint

在一個給定的柔性制造系統中，有一臺自動導引車和一個制件集，目標是使得完成整個過程的時間最短，計算每個制件在每臺機器的加工時間和每個輸入/輸出緩沖區的時間，確定每個機器與機器之間所走路程的起始和完成時間。

為了便于研究，作如下假設：

（1）AGV一次僅執行一次任務。

（2）每個加工區每次只加工一個制件。

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

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

（5）自動導引車的起始位置處于倉庫緩沖區內，等待自動導引車執行完當前任務后，駛入并停在剛執行完的任務的緩沖區內，等待指令，準備執行另一個任務。

1.2調度模型

M：加工區集：

W：制件集；

A：搬運任務集；

N：任務次序集；

G：系統允許的最大制件量；

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

w：制件編號，w∈W；

A：任務編號，a∈A；

n：任務執行的次序編號，n∈N；

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

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

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

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

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

Cm：加工區m的輸出緩沖區上的制件數；

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

Twm：制件w在加工區m上的加工時間；

Uwm：表示制件w在加工區m上加工；

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

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

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

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

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

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

Xwa：搬運任務a開始時制件w所在的加工區；

Ya：AGV的搬運任務a開始時AGV所在的加工區；

Tb（m1，m2）：AGV從加工區m1移動到m2的所用時間；

Ta：AGV執行任務a所用的時間。

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

2混合灰狼遺傳算法

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

本文將GWO算法中灰狼社會等級、狩獵機制引入至標準遺傳算法的選擇算子中，來克服了傳統的遺傳算法易早熟的缺點，從而提高了算法全局搜索的效率。新算法流程如圖2所示。

2.1編碼與解碼

本文研究的是AGV任務排序問題，則選擇加工區的序數方式進行編碼，將搬運任務集內的任務數中加工區進行排序，AGV小車任務的先后順序按照加工區序號執行，同一個加工區使用相同的編號。例如：某染色體的編碼為“3 5 1 4 3 6 2 3”（如圖3所示）。

2.2適應度函數

緩沖區容量有限的AGV 調度模型適應度函數設計為：

2.3選擇算子設計

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

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

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

改進后的選擇步驟如下：

step1：初始化隨機狼群。endprint

step2：計算出每頭狼對應的適應度值。

step3：將適應度排列前三的灰狼個體位置分別記為α，β，δ。

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

step5：更新參數a，A，C等參數的值。

step6：如不滿足結束條件，轉到第二步。

step7：導出α狼的位置。

step8：按輪盤賭規則選擇個體復制到下一代

2.4交叉算子設計

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

2.5變異算子設計

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

3仿真實驗與分析

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

AGV的移動路徑時間如表1所示。

通過Matlab進行實驗仿真，使用傳統的遺傳算法和本文設計的混合灰狼遺傳算法對緩沖區容量有限的AGV調度模型求解，得出AGV配送及加工完成所有制件的總時間。參數設置如下：初始種群規模為50；交叉概率Pc為0.6；變異概率Pm為0.01；在制件數不同的情況下，仿真結果如表2所示。標記為HGWOGA最優解、GA最優

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

由表2可看出，當制件數小于15時，兩種算法都能得到相同的最優解，但是隨著制件數的增加，當制件數大于15時，HGWOGA算法的調度時間要遠小于GA算法的調度時間，且平均能提高5%左右的調度效率，這能夠說明本文所提出的混合灰狼遺傳算法對緩沖區容量有限的AGV調度模型的改進策略是有效的。

由圖8，圖9可以看出，當制件數為15時，GA算法在20代左右收斂，HGWOGA算法在10代左右就已經達到收斂；當制件數為20時，GA算法在60代左右收斂，HGWOGA算法在20代左右就已經達到收斂，HGWOGA算法的收斂速度要遠遠快于GA算法的收斂速度，且能得到更好的最優解。這也能說明HGWOGA算法的有效性。

4結語

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

參考文獻：

[1]楊鋒英，劉會超.AGV作業調度模型及改進的DE算法研究[J].計算機工程與應用，2014，50（9）：225-230.

[2]王皖君，張為公.自動導引車導引技術研究現狀與發展趨勢[J].傳感器與微系統，2009，28（12）：5-7.

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

[4]喬巖，錢曉明，樓佩煌.基于改進時間窗的AGVs避碰路徑規劃[J].計算機集成制造系統，2012，18（12）：2683-2688.

[5]湯旻安，谷寶慧.改進PSO在AGV系統路徑優化調度中的應用研究[J].計算機工程與應用，2016，52（3）：261-265.

[6]劉旭，樓佩煌，錢曉明，等.基于改進遺傳算法的物料配送多AGV調度優化[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物料輸送調度問題研究[J].物流科技，2013，36（7）：1-4.

[9]周巧.面向緩存有限的柔性制造系統單AGV調度研究[D].廣東工業大學，2014.

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

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

[12]黃英杰.基于目標級聯法和智能優化算法的車間調度問題研究[D].華南理工大學，2012.

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

（責任編輯：劉亭亭）endprint