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

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

0 引言

傳統(tǒng)的作業(yè)車間調(diào)度不考慮工件的轉(zhuǎn)移時間或?qū)⑵浼僭O(shè)成確定的時間值考慮在加工時間內(nèi)，這不符合作業(yè)車間加工的實際情況。實際生產(chǎn)中工件的工序加工完成后，由自動導(dǎo)引小車(AGV)來實現(xiàn)工件在不同機器之間的轉(zhuǎn)移，并且不同小車和不同路徑的選擇會產(chǎn)生不同的轉(zhuǎn)移時間，進而影響工件的開工時間、整個生產(chǎn)調(diào)度周期和產(chǎn)品交貨期。因此，考慮含AGV的作業(yè)車間調(diào)度，成為當(dāng)前研究的熱點之一。

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

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

綜合以上考慮，為了避免割裂機器調(diào)度和AGV路徑規(guī)劃關(guān)系并求出在系統(tǒng)中工件轉(zhuǎn)移時間的最優(yōu)值，實現(xiàn)真正意義上的同步集成調(diào)度，將時間窗和Dijkstra算法相結(jié)合進行AGV 路徑規(guī)劃并嵌入遺傳算法的解碼操作過程中，提出了基于時間窗和Dijkstra算法的混合遺傳算法求解柔性作業(yè)車間多AGV和機器的集成調(diào)度問題。

1 問題描述及數(shù)學(xué)模型

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

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

假設(shè)條件如下：

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

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

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

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

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

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

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

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

(9)小車執(zhí)行完任務(wù)?？吭趧倛?zhí)行完任務(wù)的機器旁，并不回到原來的位置；

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

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

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

對于優(yōu)化目標(biāo)為最大完工時間Cmax最小的含AGV的柔性作業(yè)車間調(diào)度問題，建立的數(shù)學(xué)模型如下。

目標(biāo)函數(shù)：

(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)表示一個任務(wù)只能選擇一臺小車；式(5)、式(6)及式(7)表示小車的時間約束，其中式(5)表示一臺小車在某一時刻只能運送一個任務(wù)，式(6)和式(7)表示小車的空載和負(fù)載完成時間大于等于空載和負(fù)載開始時間加上各自的運行時間；式(8)和式(9)表示工序與運送任務(wù)之間的約束，其中式(8)表示只有工件的前一個工序加工完成并且小車到達后，才能開始該工件下一工序的運送任務(wù)，式(9)表示只有工件的本道工序運送任務(wù)完成后，才能開始加工本道工序。

由于假設(shè)條件工件緩沖區(qū)無限大，因此不存在因工件緩沖區(qū)不足引起的系統(tǒng)死鎖現(xiàn)象。

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

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

2 沖突類型及解決策略

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

圖2 電子地圖Fig.2 Electronic Map

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

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

T1+Δt>T2

(10)

如果成立則采用新生成路徑，否則采用基于速度調(diào)節(jié)策略。特別地，當(dāng)采用基于速度調(diào)節(jié)策略失效時，則采用基于幾何路徑調(diào)節(jié)策略。

3 算法描述

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

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

3.1 編碼

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

圖3 三鏈?zhǔn)饺旧w編碼方式Fig.3 The coding patterns of three chain chromosomes

3.2 選擇操作

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

3.3 交叉操作

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

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

3.4 變異操作

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

3.5 解碼操作

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

(1)將染色體中基于工序編碼的基因串轉(zhuǎn)換成對應(yīng)的工序串。

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

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

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

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

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

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

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

3.6 算法流程

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

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

4 算法對比分析

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

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

表2 不同算法求解算例對比結(jié)果

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

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

表3 工件加工時間表

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

表4 小車運輸時間表

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

圖6 調(diào)度方案的甘特圖Fig.6 The Gantt chart of scheduling scheme

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

整個算法的搜索過程見圖8，從中可以看出工件的最大完工時間是逐漸減小并收斂的。從求解過程可以看出算法在17代時開始收斂，說明了算法能夠有效、快速地獲得最優(yōu)解?？梢姳疚乃崴惴ㄊ强尚械?，收斂速度較快，并且能夠反映出所提出的智能優(yōu)化算法在求解柔性作業(yè)車間多AGV和機器雙資源集成調(diào)度的優(yōu)越性。

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

5 結(jié)論

考慮實際車間中工件在不同機器之間的轉(zhuǎn)移存在不確定性的問題，本文設(shè)計了三鏈?zhǔn)降木幋a結(jié)構(gòu)和提出基于時間窗和Dijkstra的混合遺傳算法求解此問題，最后證明了本文所提算法在解決中小規(guī)模的柔性作業(yè)車間多AGV和機器雙資源的集成調(diào)度方面的優(yōu)越性。但是，隨著問題規(guī)模的增大，該算法求解效率有所下降，因此改進大規(guī)模問題的求解效率是今后算法的研究方向。