柔性作業車間多自動導引小車和機器的集成調度

賀長征 宋豫川 雷 琦 呂向飛 劉軟香 陳 進

1.重慶大學機械傳動國家重點實驗室，重慶，400030 2.重慶電子工程職業學院，重慶，401331

0 引言

傳統的作業車間調度不考慮工件的轉移時間或將其假設成確定的時間值考慮在加工時間內，這不符合作業車間加工的實際情況。實際生產中工件的工序加工完成后，由自動導引小車(AGV)來實現工件在不同機器之間的轉移，并且不同小車和不同路徑的選擇會產生不同的轉移時間，進而影響工件的開工時間、整個生產調度周期和產品交貨期。因此，考慮含AGV的作業車間調度，成為當前研究的熱點之一。

目前，國內外學者紛紛對含AGV的作業車間調度展開研究，但大多研究割裂了機器調度和AGV路徑規劃，分兩種情況,一種是假設AGV路徑規劃已知，即在調度過程中不考慮路徑沖突問題進行AGV和機器的同時調度，對此問題大多學者采用的是遺傳算法、禁忌搜索等智能優化算法[1-10]，然而這些學者的研究沒有考慮小車碰撞或路徑沖突所導致的工件轉移時間的不確定性；另一種是先調度好機器加工序列后，再進行AGV的路徑規劃[11]，這種情況大多數學者采用的是動態規劃的方法[12-18]，但這是在已知任務的最優調度序列的情況下進行AGV的分配并進行路徑規劃，可以說上述情況并未實現真正意義上的集成調度，因為該問題中的路徑規劃對于任務調度結果有一定影響，同時任務的調度也會對AGV選擇及其路徑規劃產生一定的影響，所以二者是相互影響的。SAIDI-MEHRABAD等[19]在考慮了二者關系的情況下建立了該問題的數學模型，并提出兩階段蟻群算法來求解，但未考慮零件的可變工藝路徑約束。在零件具有可變工藝路徑的柔性作業車間中更能體現出工件轉移時間的不確定性，因為柔性作業系統中工件的每道工序都有不同的機器選擇，導致AGV的路線選擇也不同，進而有不同的工件轉移時間，并且所用機器的加工時間不同，導致這些不同的組合會有不同的結果，這也符合現代多品種小批量的生產方式，因此優化柔性作業車間多AGV和機器的集成調度具有重要意義。

小車出現碰撞或沖突的本質是兩輛小車在時間和空間上存在完全或部分重疊，所以采用為每個路段設置一個時間窗的方法來解決小車的碰撞或沖突問題。這里時間窗的含義是在該路段的時間窗內不允許存在兩輛不同小車同方向完全重疊和相反方向完全或部分重疊的情況，即時間窗具有一定的鎖定功能。然而在實際作業車間中關于小車路徑規劃問題，要求能夠準確地為AGV規劃出一條無碰撞無沖突的最短路徑，否則會出現因多個小車在同一時間段競爭同一路段而產生死鎖的現象。在最短路徑規劃中Dijkstra算法能夠從全局出發，具有較強的穩定性，且算法簡單[13]。雖然Dijkstra算法在地圖節點個數和弧數量比較多時求解效率較低，但能夠100%求出最短路徑，這符合實際柔性作業車間中多AGV路徑規劃的要求。再者，遺傳算法具有以下特點：①不直接表達解空間，采用編碼方式表示解空間簡化問題的處理難度；②具有快速隨機搜索能力和從種群出發進行尋優的隱含并行性；③具有可擴展性，容易與其他算法結合。

綜合以上考慮，為了避免割裂機器調度和AGV路徑規劃關系并求出在系統中工件轉移時間的最優值，實現真正意義上的同步集成調度，將時間窗和Dijkstra算法相結合進行AGV 路徑規劃并嵌入遺傳算法的解碼操作過程中，提出了基于時間窗和Dijkstra算法的混合遺傳算法求解柔性作業車間多AGV和機器的集成調度問題。

1 問題描述及數學模型

假設有n個待加工工件，k臺可用于加工工件的機器，w臺相同的AGV在車間運送工件。每個工件有一道或多道工序，每道工序有若干臺可選機器對其進行加工，且工序在不同機器上的加工時間不一定相同，取決于機器的加工性能。每臺AGV可在任意兩臺機器之間運送工件，小車的運送路線選擇通過實時計算兩臺機器間的可通路徑，運送時間取決于兩臺機器之間的實際物理距離和路況。

AGV小車在整個調度系統中存在兩種行走狀態：一是空載，就是小車從第一臺機器Ml空載行駛到第二臺機器Mk′裝載將要在第三臺機器Mk進行加工的工件的過程；二是負載，就是小車從第二臺機器Mk′裝載著將要被加工的工件行駛到第三臺機器Mk的位置的過程。與一般的作業車間調度相比，增加了AGV資源的約束條件，即雙資源約束的調度問題，使得工件的轉移時間值存在不確定性，但每道工序的轉移一定會存在最優時間值，因此，調度目標是為每道工序選擇最合適的加工機器和搬運小車，盡可能減少小車的空載行程，縮短工件的轉移時間，使每道工序盡可能早地開工，最終確定各工件的各道工序的最佳搬運路徑、最佳加工順序和開工、完工時間。

假設條件如下：

(1)任意時刻每臺機器只能加工一個工件；

(2)任意時刻每個工件的每道工序只能在一臺機器上加工，一旦開始加工不允許中斷，裝/卸貨時間算在加工時間內，加工時間已知；

(3)每臺機床的工件緩沖區無限大，但只允許停靠一輛小車；

(4)負載或空載不影響小車的行駛速度；

(5)不同工件之間加工順序沒有約束；

(6)每輛小車每次只能運送一個工件；

(7)所有小車和所有工件都在小車起點和毛坯庫；

(8)一道工序被加工完后被空閑AGV運送到下一個機器位置進行下一道工序的加工；

(9)小車執行完任務停靠在剛執行完任務的機器旁，并不回到原來的位置；

(10)路段是雙向單通道，同一時刻在每個節點和路段只允許通過一輛小車；

(11)考慮AGV之間的碰撞和沖突等問題；

(12)不考慮小車充電、故障等問題。

對于優化目標為最大完工時間Cmax最小的含AGV的柔性作業車間調度問題，建立的數學模型如下。

目標函數：

(1)

約束條件：

(2)

Spqk+M(1-βijpqk)≥Cijk

其中，Spqk為工序Opq在機器k上的開始加工時間。?i,p∈{1,2,…,n}，j，q∈{1,2,…,Pi}，k∈{1,2,…,m}，使得

Cijk=Sijk+tijk

(3)

(4)

(5)

(6)

?l,?k′∈{1,2,…,m}j>1

(7)

(8)

Sijk≥max(CTijν,max(Cpqk|p≠i,?p=1，2，…，n),

?q=1，2，…，Pp)

(9)

式(1)表示模型以工件的最大完工時間最小；式(2)表示工件的一道工序只能選擇一臺機器加工；式(3)表示工件一旦開始加工不允許中斷；式(4)表示一個任務只能選擇一臺小車；式(5)、式(6)及式(7)表示小車的時間約束，其中式(5)表示一臺小車在某一時刻只能運送一個任務，式(6)和式(7)表示小車的空載和負載完成時間大于等于空載和負載開始時間加上各自的運行時間；式(8)和式(9)表示工序與運送任務之間的約束，其中式(8)表示只有工件的前一個工序加工完成并且小車到達后，才能開始該工件下一工序的運送任務，式(9)表示只有工件的本道工序運送任務完成后，才能開始加工本道工序。

由于假設條件工件緩沖區無限大，因此不存在因工件緩沖區不足引起的系統死鎖現象。

本文采用網絡圖表示該問題中工件和運送任務之間的約束關系及可行的集成調度方案，見圖1。方框表示小車的運輸任務，圓圈表示工件的加工工序，實線箭頭表示約束關系，虛線所連接的表示使用的資源，如工序O11,O22,O33都在機器M1上進行加工，運輸任務T11,T22,T14,T23,T31,T32都采用AGV1來運送。

圖1 多AGV和機器的雙資源集成調度析取圖Fig.1 Dual resource integration scheduling disjunctive graph of multi AGV and machine

2 沖突類型及解決策略

在柔性制造系統中，AGV沿著導引路徑在車間進行來回穿梭運送工件、物料或托盤等，因此導引路徑的布局對AGV來說即為地圖。將其抽象成點與邊的形式，點表示路口或者機器以及倉庫位置，邊表示兩個節點的可通路段，箭頭表示是小車可行駛方向，邊上數字表示實際的物理距離或通行時間，見圖2。

圖2 電子地圖Fig.2 Electronic Map

在進行路徑規劃時，小車在行進的過程中可能出現的沖突類型，包括以下4種基本沖突類型[15]：路口沖突、相向沖突、節點占用沖突以及趕超沖突。由于前提假設小車是按照固定的行駛速度行駛的，所以不存在趕超沖突。

在多AGV系統中碰撞或沖突的類型是復雜多樣的，但大多都是由上述3種基本沖突類型所組成。 要解決多AGV系統沖突問題， 首先要處理好上述3種基本沖突[15]。因此針對以上沖突類型，采用基于速度調節、基于幾何路徑調節以及基于速度和幾何路徑相結合調節的3種沖突解決策略[18]。為了能夠更優地求解小車行駛的最短的路徑，將第三種策略進行量化處理如下：設T1為AGV原沖突路徑行駛時間，Δt是采用基于速度調節多花費的時間，T2是通過基于幾何路徑調節策略新生成路徑行駛時間。通過下述公式判斷采用何種策略：

T1+Δt>T2

(10)

如果成立則采用新生成路徑，否則采用基于速度調節策略。特別地，當采用基于速度調節策略失效時，則采用基于幾何路徑調節策略。

3 算法描述

這里采用一個實例來描述遺傳操作的過程。工件加工信息見表1。

表1 柔性作業車間工件加工及運輸信息

3.1 編碼

此處采用擴展的基于工序的編碼[20]，該編碼由三部分組成，第一部分為基于工序的編碼，第二部分為基于機器的編碼，第三部分為AGV小車編碼且與工序編碼一一對應，基因值表示的是對應工序搬運時所需的AGV號。基于上述實例編碼信息見圖3，工序編碼基因串中的數字表示工件號，出現的次數表示工件的第幾道工序，如第一個2表示的工件2的第一道工序，第二個2表示的工件2的第二道工序，以此類推；機器編碼基因串中工件1的范圍表示的工件1的三道工序依次采用5、1、3號機器進行加工，依此類推；AGV編碼基因串中第二位置上數字為3表示工件1的第一道工序采用的AGV小車號為3，依此類推，這種編碼方式就可以得到柔性作業車間多AGV和機器雙資源調度問題的一個可行解。

圖3 三鏈式染色體編碼方式Fig.3 The coding patterns of three chain chromosomes

3.2 選擇操作

選擇操作體現了優勝劣汰的思想。選擇性過強可能會導致早熟收斂，陷入局部最優；選擇性過弱，則會使尋優過程太慢。本文采用因以隨機等距方式抽取個體而被認為能相對持久保持多樣性的隨機遍歷選擇法。

3.3 交叉操作

交叉操作是模擬生物進化過程中的兩個染色體通過交配重組得到新的染色體的過程，在遺傳算法中起核心作用。根據所采用的編碼的特點，采用兩種交叉操作，第一種是IPOX[20]交叉操作，用于基于工序編碼；為了保證AGV鏈交叉后小車的數量不變，AGV鏈的交叉也采用第一種交叉方式； 設P1和P2表示的調度實例中的兩條父代染色體，C1和C2是交叉后產生的兩條子代染色體。IPOX交叉過程為：隨機將所有工件分為J1和J2兩個工件集合，復制P1包含在J1中的工件C1，復制P2包含在J2中的工件到C2，并保留他們的位置，復制P2包含在J2中的工件到C1，復制P1包含子在J1中的工件到C2，并保留他們的順序,其交叉過程見圖4a。第二種是MPX[20]交叉操作，用于基于機器編碼部分的交叉。設父代P1和P2交叉產生子代C1和C2。MPX交叉操作的過程為：首先隨機產生一個由整數0，1組成與染色體長度相等的集合R，依次在P1和P2中選出與R中的1位置對應的工序，交換它們分配的機器，P1和P2中的其他機器保留到子代，這樣產生了子代C1和C2，其過程見圖4b。

圖4 IPOX與MPX交叉過程示意圖Fig.4 The cross process of IPOX and MPX

3.4 變異操作

變異操作模擬生物進化過程中的變異過程，是為了增加種群的多樣性，在一定程度上能避免陷入過早收斂，跳出局部極小。此處采用兩種變異操作，第一種是針對基于工序編碼的交換變異，即從染色體中隨機選擇兩個位置的基因，然后將它們的位置互換，同時為了保證AGV鏈變異后小車的數量不變，AGV鏈的變異也采用交換變異方式。第二種是針對基于機器編碼的變異操作，即隨機選擇一個基于機器編碼的基因串上的一個基因，在該工序的加工機器集中隨機選取另外一個不同的機器替換掉當前機器。

3.5 解碼操作

依據染色體的編碼方法可以獲得每條染色體中每個基因位的信息，包括工序P、采用的加工機器號Mk，運送工件的AGV號Rv及所在機器位置l以及運送的起始位置節點S和T。將獲取的信息作為基于時間窗的Dijkstra路徑算法的輸入條件，由Dijkstra路徑算法和時間窗信息結合沖突檢測及解決策略，規劃出一條無沖突無碰撞的路徑，并得到對應的行駛時間。最后由行駛時間和加工時間計算染色體適應度值。具體步驟如下。

(1)將染色體中基于工序編碼的基因串轉換成對應的工序串。

(5)依據鄰接可達矩陣AdjM，小車號Rv及其運送任務負載可開始時間STij，起點S、終點T，由Dijkstra路徑算法計算到下一最短路徑節點N。

(6)路段沖突檢測。結合各路段時間窗檢測路段是否可行，若可行，執行步驟(7)；反之，執行步驟(8)。

(7)更新各路段時間窗，若空載路段判斷N是否等于S，則負載路段判斷N是否等于T；若等于S，則結束，輸出最短路徑及各路段時間窗，返回步驟(4)；若等于T，則結束，輸出最短路徑及各路段時間窗，執行步驟(10)；否則，繼續由Dijkstra路徑算法計算到下一最短路徑，返回步驟(6)。

(8)路段沖突類型檢測。若沖突類型是相向沖突，則采用基于幾何路徑調節策略。若沖突類型是路口或節點沖突類型，依公式T1+Δt>T2選擇沖突解決策略，若成立，選擇基于速度調節策略，反之選擇基于幾何路徑調節策略。

(9)判斷是否到達終點S或T；若等于S，則結束，輸出最短路徑及各路段時間窗，返回步驟(4)；若等于T，則結束，輸出最短路徑及各路段時間窗，執行步驟(10)；否則，考察次優路段，返回步驟(6)。

(10)由最優路徑及加工時間計算得出本道工序的開始運送時間、運送結束時間以及開始加工和完工時間。

(11)重復步驟(2)～步驟(10)，直到所有的工序被操作，得到每個工件的每道工序的具體執行的開始加工時間和完成時間的集合，即調度方案。

3.6 算法流程

基于時間窗和Dijkstra算法的混合遺傳算法求解柔性作業車間多AGV和機器的集成調度算法的具體流程見圖5。

圖5 算法流程圖Fig.5 the flow chart of algorithm

4 算法對比分析

由于本文與文獻[19]處理的是相同問題，因此采用此文獻中的算例在MATLAB 2014a仿真環境平臺上對本文算法進行對比驗證。算例中的工件、小車以及機器等信息見文獻[19]，且將文獻中的算法及本文算法分別命名為GAMS、ACA和HGA。采用上述所提混合遺傳算法，仍以總的完工時間最小為目標對其進行計算，程序運行5次所測結果最優值見表1。本文混合遺傳算法的基本參數設置分別為：初始化種群PopSize為30，最大進化代數MaxGen為30，交叉概率Pc為0.7，變異概率Pm為0.05。

表2中算例號0的是文獻[19]在算法分析中進行舉例驗證的算例，空格表示求解用時較長，無法求得結果。特別地，文獻中算例3和11的求解結果是不合理的，因為算例3中工件2的總的加工時間是36，工序的總的轉移時間17，因此工件2的總的完工時間是53，所以文獻中的最大完工時間49和50.2是不合理的；算例11中工件在機器3上的加工時間總和等于95，因此最大完工時間必然大于等于95，所以文獻中最大完工時間72.1是不合理的，而本文算法的求解結果更加合理。

表2 不同算法求解算例對比結果

從表2對比結果中可以看出，當小規模作業車間調度時(如算例1)，PGA法得到的結果是和GAMS、ACA兩種方法一致的；隨著規模的增大，采用本文方法的最大完工時間平均減少15%左右，最大改善是算例2，減少了45%的時間。當規模足夠大時，由于可行解的空間太大，所求目標的優劣取決于算法的求解效率。由于文獻的算例是中等規模的，所以從對比分析來看，本文算法在求解中等規模的作業車間多AGV和機器的集成調度中相比文獻中的算法要優越。因此，可以證明本文算法的可行性、有效性和優越性。

上述算例都是基于非柔性作業車間的，若采用柔性作業車間的算例更能體現出所提算法的優勢。因為在柔性作業系統中工件的每道工序都有不同的機器選擇，導致小車的路線選擇也不同，進而有不同的運送時間，并且各個機器的加工時間不同，結果就是這些不同的組合會有不同的結果，因此，更能從中選擇出較優的個體。以下是通過對離散制造企業進行調研處理后的數據：系統中待加工工件有4件，機床設備的數量為8臺，其中工件的工序數依次分別為5、4、5、6，每道工序在不同機器上的加工時間不一定相同，具體的加工時間和可選機器見表3，AGV的數量為3臺，且任何一輛小車都可為任何一臺機床服務。依據電子地圖構建出節點間鄰接可達矩陣，見表4。表4數據代表了AGV在任意兩節點間的行駛時間，其中不在矩陣對角上位置為零值的表示兩點不可通行。

表3 工件加工時間表

注：“—”表示不可加工。

表4 小車運輸時間表

遺傳算法的基本參數設置和上文一致，由于柔性作業車間調度的可行解空間范圍相對較大，所以增加了初始種群的規模，將初始種群設置為60，進行5次計算，實驗獲得的最優調度方案甘特圖見圖6，該生產調度最佳調度周期為89。圖7為每輛小車行走路段的時間窗，從圖中可以看出在同一路段不存在有多輛小車的時間窗是重疊的，可見算法在多AGV的路徑規劃方面是有效的。

圖6 調度方案的甘特圖Fig.6 The Gantt chart of scheduling scheme

圖7 各路段時間窗Fig.7 The time window of each path section

整個算法的搜索過程見圖8，從中可以看出工件的最大完工時間是逐漸減小并收斂的。從求解過程可以看出算法在17代時開始收斂，說明了算法能夠有效、快速地獲得最優解。可見本文所提算法是可行的，收斂速度較快，并且能夠反映出所提出的智能優化算法在求解柔性作業車間多AGV和機器雙資源集成調度的優越性。

圖8 算法搜索過程曲線Fig.8 The algorithm search process curve

5 結論

考慮實際車間中工件在不同機器之間的轉移存在不確定性的問題，本文設計了三鏈式的編碼結構和提出基于時間窗和Dijkstra的混合遺傳算法求解此問題，最后證明了本文所提算法在解決中小規模的柔性作業車間多AGV和機器雙資源的集成調度方面的優越性。但是，隨著問題規模的增大，該算法求解效率有所下降，因此改進大規模問題的求解效率是今后算法的研究方向。