柔性作業(yè)車間多自動(dòng)導(dǎo)引小車和機(jī)器的集成調(diào)度

賀長征 宋豫川 雷 琦 呂向飛 劉軟香 陳 進(jìn)

1.重慶大學(xué)機(jī)械傳動(dòng)國家重點(diǎn)實(shí)驗(yàn)室，重慶，400030 2.重慶電子工程職業(yè)學(xué)院，重慶，401331

0 引言

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

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

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

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

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

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

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

假設(shè)條件如下：

(1)任意時(shí)刻每臺機(jī)器只能加工一個(gè)工件；

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

(3)每臺機(jī)床的工件緩沖區(qū)無限大，但只允許?？恳惠v小車；

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

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

(6)每輛小車每次只能運(yùn)送一個(gè)工件；

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

(8)一道工序被加工完后被空閑AGV運(yùn)送到下一個(gè)機(jī)器位置進(jìn)行下一道工序的加工；

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

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

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

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

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

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

(1)

約束條件：

(2)

Spqk+M(1-βijpqk)≥Cijk

其中，Spqk為工序Opq在機(jī)器k上的開始加工時(shí)間。?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)表示模型以工件的最大完工時(shí)間最小；式(2)表示工件的一道工序只能選擇一臺機(jī)器加工；式(3)表示工件一旦開始加工不允許中斷；式(4)表示一個(gè)任務(wù)只能選擇一臺小車；式(5)、式(6)及式(7)表示小車的時(shí)間約束，其中式(5)表示一臺小車在某一時(shí)刻只能運(yùn)送一個(gè)任務(wù)，式(6)和式(7)表示小車的空載和負(fù)載完成時(shí)間大于等于空載和負(fù)載開始時(shí)間加上各自的運(yùn)行時(shí)間；式(8)和式(9)表示工序與運(yùn)送任務(wù)之間的約束，其中式(8)表示只有工件的前一個(gè)工序加工完成并且小車到達(dá)后，才能開始該工件下一工序的運(yùn)送任務(wù)，式(9)表示只有工件的本道工序運(yùn)送任務(wù)完成后，才能開始加工本道工序。

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

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

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

2 沖突類型及解決策略

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

圖2 電子地圖Fig.2 Electronic Map

在進(jìn)行路徑規(guī)劃時(shí)，小車在行進(jìn)的過程中可能出現(xiàn)的沖突類型，包括以下4種基本沖突類型[15]：路口沖突、相向沖突、節(jié)點(diǎn)占用沖突以及趕超沖突。由于前提假設(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)地求解小車行駛的最短的路徑，將第三種策略進(jìn)行量化處理如下：設(shè)T1為AGV原沖突路徑行駛時(shí)間，Δt是采用基于速度調(diào)節(jié)多花費(fèi)的時(shí)間，T2是通過基于幾何路徑調(diào)節(jié)策略新生成路徑行駛時(shí)間。通過下述公式判斷采用何種策略：

T1+Δt>T2

(10)

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

3 算法描述

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

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

3.1 編碼

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

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

3.2 選擇操作

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

3.3 交叉操作

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

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

3.4 變異操作

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

3.5 解碼操作

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

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

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

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

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

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

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

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

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

3.6 算法流程

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

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

4 算法對比分析

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

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

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

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

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

表3 工件加工時(shí)間表

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

表4 小車運(yùn)輸時(shí)間表

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

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

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

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

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

5 結(jié)論

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