鄧 希， 胡曉兵， 江代渝， 彭正超

(1.四川大學機械工程學院， 成都 610065; 2.四川大學宜賓園區(qū)， 宜賓 644000)

1 引 言

柔性制造系統(tǒng)(FMS)將加工設備與先進信息技術結合，實現(xiàn)了加工制造的柔性化和自動化加工[1].柔性作業(yè)車間中工件加工可有一種或多種機器可選，并有相應的加工時間，一道工序完成后由AGV運送到下一加工機器的位置加工下一道工序，不同的機器和路徑選擇則有不同的運輸時間，因此機器、AGV選擇和AGV路徑規(guī)劃都會影響整個生產調度周期，隨著自動引導車輛(AGV)在柔性作業(yè)車間的廣泛使用，考慮AGV運輸?shù)淖鳂I(yè)車間調度更能反映真實加工情況.解決柔性作業(yè)車間資源分配優(yōu)化問題，最大化地利用生產資源，提高生產效率，對提高柔性制造企業(yè)的核心競爭力具有重大意義.

國內外學者對考慮AGV的作業(yè)車間調度問題做了許多研究.李巖等[2]建立了可變工藝路徑、包含 AGV的FMS調度問題的模型，但其將返回成品區(qū)的時間包括在最后一道工序的時間內，忽略了AGV調度對時間的影響；柳賽男等[3]提出了基于遺傳算法的機器/AGV的調度算法，Lacomme等[4]建立了一種基于析取圖的機器/AGV聯(lián)合調度模型框架；這部分學者[2-7]假定AGV的路徑和行駛時間是確定的，但在調度中未考慮AGV行駛過程的碰撞沖突問題，以及不同路徑對運輸時長的影響.

Saidi-Mehrabad等[8]提出了一種二階段蟻群算法求解問題，討論了AGV的無沖突路徑規(guī)劃問題以及基本的車間作業(yè)調度(JSSP)問題，但所討論的每道工序加工機器都是唯一的，未討論柔性作業(yè)車間中零件的多臺可選加工機器的情況.賀長征等[9]針對柔性作業(yè)車間機器/AGV的雙資源調度設計了三鏈式編碼結構，提出了基于時間窗和Dijkstra算法的混合遺傳算法，但在AGV路徑規(guī)劃中未考慮小車靜止時的占用沖突問題.

遺傳算法在車間生產排產問題中有較為廣泛的應用[10]，本文針對柔性作業(yè)車間機器/AGV的雙資源集成調度問題，提出基于時間表和A*算法的混合遺傳算法，以工件每一道工序為基礎單元，以工件運回任務為特殊單元，設計了基于任務單元的染色體結構，分析解決了AGV小車在機器節(jié)點處等待的占用沖突問題，最終獲得柔性作業(yè)車間的機器/AGV完整調度分配方案.

2 問題描述和模型建立

假設生產車間有k臺可加工機器，v輛相同的AGV小車，當前總任務有n個待加工工件，每個工件有一道或多道工序，每道工序可在一臺或多臺機器上完成加工作業(yè)，并且有相應的加工時間.每臺空閑的AGV小車都可以運送工件，最終加工完成的工件需要全部送回成品區(qū).

本文引入表 1的符號定義，并假設條件如下.

1) 同一工件各工序的加工順序固定，不同工件的工序加工順序互不影響;2) 每個工件的每道工序只能在可選機器的一臺上加工完成，加工時長確定，加工開始后不允許中斷;3) 每臺機器一次只加工一個工件.機器的工件存放空間足夠大，待加工工件可提前送達，已加工工件可暫時存放.機器位置小車停靠會引起阻塞;4) 每臺AGV小車一次只運送一個工件，行駛速度穩(wěn)定不變;5) 所有AGV小車起始位置為毛坯庫，結束任務后停留在成品庫或機器旁;6) AGV小車結束當前運輸任務后從當前位置立即開始下一運輸任務，無空閑等待時間，運輸任務全部完成后返回裝卸點;7) 機器和AGV小車在零時刻都是可用的;8) 考慮AGV小車之間的碰撞沖突.

表1 符號定義

總調度任務為確定每一個任務單元的執(zhí)行順序，加工機器和AGV小車，規(guī)劃AGV小車的最佳行駛路徑，獲得各工件工序的最佳開始加工時間和加工完成時間，以及最早運回成品區(qū)的時間.

目標函數(shù)：

(1)

約束條件：

(2)

(3)

Sijk+A×aiji′j′k≥Si′j′k+ti′j′k

(4)

Si′j′k+A(1-aiji′j′k)≥Sijk+tijk

(5)

(6)

式(1)表示模型以最大總運輸時間最短為目標；式(2)表示工件的每道工序可也僅可在一臺機器上加工完成；式(3)表示每個任務只能由一臺AGV小車運送；式(4)和式(5)中A為一個特別大的數(shù)，公式表示在同一機器上后加工的工序必須等待前一工序加工完成才能開始加工；式(6)表示負載行程要等待小車到達且工件加工完成后才能開始，運輸工件第一道工序任務時，無加工等待時間.

以每個工件的每道工序為一個任務單元，并考慮加工完成后將工件運回成品區(qū)的任務，每個工件有Pi+1個任務單元，其中，最后一個任務單元只含有運輸任務，其余則包含運輸任務和加工任務.任務及資源調度解析圖如圖1所示.

圖1 柔性作業(yè)車間任務及資源調度解析

圖1中，TAiu表示一個作業(yè)任務，Oij，Mk，Vv表示該任務所處理的工件工序，以及需要的機器和AGV資源，如任務TA11表示由V2運輸工件N1到機器M1，在機器M1上加工O11，TA14表示由V2運輸加工完成的工件N1到成品區(qū).

3 路徑規(guī)劃沖突類型及解決策略

使用柵格地圖[11]表示柔性作業(yè)車間布局環(huán)境，如圖2所示 ，LU1表示毛坯倉庫上貨點，LU2表示成品倉庫卸貨點，標有Mk的柵格為機器Mk所在的節(jié)點位置.

圖2 柵格地圖Fig.2 Raster map

在小車的一次運輸任務周期內，包含空載行程，等待負載，負載行程三個狀態(tài)，如圖3所示，負載行程結束后立即進入下一任務等待狀態(tài)，當前一任務結束時小車所在位置和下一任務起始位置相同時，AGV小車無空載行程.

圖3 AGV小車作業(yè)周期示意圖Fig.3 Operation cycle of AGV

3.1 A*算法

A*算法是一種啟發(fā)式的搜索算法，通常采用f(n)=g(n)+h(n)作為啟發(fā)式評估函數(shù)[12].本文采用曼哈頓距離作為啟發(fā)函數(shù)，曼哈頓距離的啟發(fā)式函數(shù)為

h(n)=abs(n.x-goal.x)+abs(n.y-goal.y)

(7)

A*能快速搜索出起點和終點之間的全局最優(yōu)路徑，具有結構簡單、搜索精度高等優(yōu)點[13].但是在多小車運輸?shù)穆窂揭?guī)劃中，由于存在交通沖突，A*算法并不完全適用，因此需要使用改進的基于時間表的A*算法進行路徑規(guī)劃.

3.2 AGV行走狀態(tài)沖突及解決策略

在AGV路徑規(guī)劃的問題中，常見的交通阻塞有相向阻塞，交叉阻塞和節(jié)點占用3種.假設起始時間t，每拓展一個節(jié)點時間增加Δt，在A*算法中拓展節(jié)點N時，根據(jù)時間表查詢待拓展節(jié)點的占用情況，并判斷阻塞類型.

若為交叉阻塞，小車以當前點當作一個臨時目標點，查詢節(jié)點N占用結束時間為t1，以當前節(jié)點C為新的起始點，起始時間t=t1進行路徑規(guī)劃，更新時間表.

若為相向阻塞和節(jié)點占用，則將被占用節(jié)點N設為不可行點，并繼續(xù)拓展新的節(jié)點，若無可拓展節(jié)點，則起始時間t=t+Δt，重新進行路徑規(guī)劃.

由于AGV小車完成單個任務后停靠于機器旁，而其他任務優(yōu)先級的小車若要訪問此機器則不允許其長時間占用，因而產生的機器節(jié)點位置占用沖突.

圖4 AGV等待狀態(tài)沖突示意圖Fig.4 Conflict of AGV waiting state

在任務TAiu中，如圖4所示，小車Vv取件(空載)時，根據(jù)路徑規(guī)劃獲得到達機器Mk的時間VET′iuv，根據(jù)式(6)計算小車Vv運輸Oij(負載)開始時間VSTiuv.

(8)

4 基于遺傳算法的車間作業(yè)規(guī)劃

采用一個實例來描述遺傳操作的過程.工件加工信息如表2所示.

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

4.1 編 碼

采用擴展的基于工序的編碼[7]，編碼由三部分組成，第一部分為任務編碼，表示工件的工序加工任務順序，和工件加工完成后運回成品區(qū)任務的順序，基因串長度為

(9)

第二部分為機器編碼，表示各工件各工序的加工機器，基因串長度為總工序數(shù)為

(10)

第三部分為AGV編碼，表示執(zhí)行各工件各工序運輸任務的AGV小車，順序對應任務編碼中的各任務運輸所需AGV號，基因串長度為L1.

根據(jù)表1實例信息編碼的染色體編碼方式如圖5所示.

圖5 染色體編碼方式

按從左到右的順序計數(shù)，任務編碼基因串中的數(shù)字表示工件號，出現(xiàn)的次數(shù)n表示執(zhí)行工件的第n道工序的任務，最后一次出現(xiàn)的數(shù)字表示運回該工件的任務.如第一個1表示執(zhí)行工件1的第一道工序任務，第二個1表示執(zhí)行工件1的第二道工序任務，第四個1即最后一次出現(xiàn)的1表示運回工件1的任務，以此類推；AGV編碼中第三個的數(shù)字為2，表示任務編碼中第三個任務即加工工件3的第一道工序使用的AGV小車號為3，以此類推；機器編碼中工件1的范圍內表示工件1的三道工序依次由機器1、2、2加工，以此類推.此編碼方式可得到柔性作業(yè)車間一個完整加工和運輸作業(yè)中多機器和多AGV調度問題的可行解.

4.2 初始化

初始種群的質量對遺傳算法求解FJSP問題有較大影響，由于本文以最短完工時間為目標函數(shù)，在機器編碼中按0.2的概率選擇加工工序Oij時長最短的機器，在AGV編碼中按0.2的概率將AGV小車較為均勻的分配，減少部分小車的閑置.在保持初始種群多樣性的同時提高初始化種群個體質量.

4.3 選擇操作

使用隨機遍歷選擇法，根據(jù)隨機生成的序號選擇選擇種群中相應位置的個體進行交叉和變異操作，保證種群的多樣性.

4.4 交叉操作

根據(jù)染色體編碼的不同，針對任務基因串使用OX交叉算子，隨機取兩條P1,P2父代染色體和隨機的兩個點，分別將P1,P2兩點之間的基因段G1，G2提取到子代兩條染色體C1,C2的相同位置，將P1按順序刪除G2中存在的基因，按順序填入C2的基因空位中，將P2按順序刪除G1中存在的基因，按順序填入C1的基因空位中.任務編碼基因串交叉過程見圖6(a).

針對機器基因串和AGV基因串使用MPX交叉算子.隨機生成一條與機器基因串長度相同的0、1序列M，將父代染色體P1,P2中數(shù)字1位置的基因互相交換，即交換所使用的機器或AGV小車.AGV基因串交叉過程見圖6(b)，機器基因串交叉過程見圖6(c).

圖6 染色體交叉示意圖Fig.6 The crossing process of chromosome

4.5 變異操作

針對任務基因串，從染色體P1中隨機選擇兩個位置的基因，然后將它們的位置互換.任務基因串變異過程見圖7(a).

針對機器基因串，隨機選擇機器編碼的基因串上的一個基因，在該工序的加工機器集中隨機選取另外一個不同的機器替換掉當前機器，并按0.2的概率選擇加工時間最短的機器.機器基因串變異過程見圖7(b).

針對AGV基因串的變異采用和任務基因串相同的變異方式，在其基礎上按0.2的概率隨機選擇AGV編碼基因串上的一個基因，選擇出現(xiàn)次數(shù)最少的AGV小車號替換當前基因，以平均AGV小車的利用率，且較為均勻的小車數(shù)量分配能減少總運輸時間.AGV基因串變異過程見圖7(c).

圖7 染色體變異示意圖

4.6 精英保留策略

父代種群通過交叉變異產生子代種群，將種群合并后得到規(guī)模大于P的臨時種群，為保證進化過程中種群規(guī)模一致，需對種群內個體進行篩選.首先保存父代種群中的最優(yōu)解，當存在多個最優(yōu)個體相等時，以AGV行走時間最短為第二目標，計算AGV小車的總運行時間T，根據(jù)下式.

F=F+0.0001×T

(11)

對個體進行排序，保留AGV小車的總運行時間最小的個體為最優(yōu)解.

通過輪盤賭法根據(jù)適應度占比在臨時種群中隨機選擇個體，生成規(guī)模為P的新種群，最后采用精英保留策略，用保存的父代種群最優(yōu)解替換新種群中的最差解，得到下一代的父代種群.

既保證種群的多樣性又保留種群中最優(yōu)的個體，加快全局收斂性和計算效率.

4.7 解碼和適應度計算

根據(jù)染色體的編碼可以獲得任務信息，包括加工工件工序Oij，所使用機器Mk和運輸?shù)腁GV小車Vv.將信息作為基于時間窗的A*路徑算法的初始條件，結合沖突檢測和解決方案，得到一條無沖突無阻塞的路徑和相應的運輸時間，將已加工完成的工件最后運送到達成品庫的最晚時間max(VETv)，為完成所有任務的最大時長，即染色體適應度值F.路徑規(guī)劃具體步驟如下.

步驟1讀取信息.從左到右依次讀取任務染色體中的一個基因，判斷任務類型.若為加工任務，對應工序為Oij，加工機器為Mk，加工時間為tijk，前一道工序Oi(j-1)的完工時間Ci(j-1)，小車可用時間VRTijv；若為運回任務，則無加工機器和加工時長信息.對應工件為Ni，工件最后一道工序OiPi的完工時間CiPi，小車執(zhí)行運輸任務TAi(Pi+1)可用時間VRTi(Pi+1)v.

根據(jù)相應信息和運輸起始位置SP，終點位置EP，選用的AGV小車Vv，小車當前位置Pv，執(zhí)行步驟2.

步驟2空載路徑規(guī)劃.根據(jù)地圖和時間表，小車Vv的可使用時間VRTijv，起點小車位置Pv，空載任務終點SP，進行空載路徑規(guī)劃，執(zhí)行步驟5，獲得最短路徑和相應的時間表，執(zhí)行步驟3.

步驟3等待狀態(tài)沖突判斷.根據(jù)時間表查詢是否存在機器節(jié)點占用沖突，若有，執(zhí)行AGV等待狀態(tài)沖突解決方案，返回步驟2，若無，執(zhí)行步驟4.

步驟4負載路徑規(guī)劃.根據(jù)負載開始運輸時間VSTijv，起點SP，終點EP， 由基于時間表的A*算法求解出最短可行路徑，執(zhí)行步驟5；獲得最短路徑和相應的時間表，執(zhí)行步驟10.

步驟5基于時間表的A*算法搜索路徑，根據(jù)輸入的起始時間t，起始節(jié)點S，目標節(jié)點G進行路徑搜索，當前節(jié)點為C，拓展節(jié)點N，每拓展一個節(jié)點時間增加Δt.

步驟6沖突檢測.通過時間表查詢t+Δt時刻節(jié)點N占用情況，若未被占用，更新時間表，執(zhí)行步驟7，若占用，執(zhí)行步驟8.

步驟7判斷節(jié)點N是否為目標節(jié)點G，若是，輸出最短路徑和相應的時間表，返回相應調用步驟2或步驟4.若不是，則繼續(xù)拓展下一節(jié)點，執(zhí)行步驟6.

步驟8判斷阻塞類型.執(zhí)行AGV行走狀態(tài)沖突解決方案，拓展新的節(jié)點，執(zhí)行步驟6，若無可拓展節(jié)點，則起始時間t=t+Δt，重新進行路徑規(guī)劃，執(zhí)行步驟5.

步驟9根據(jù)空載和負載行程的最優(yōu)路徑和時間表計算此任務中工序Oij的開始運送時間VSTijv，運送結束時間VETijv，當任務為加工任務時，計算開始加工時間Sijk和加工完成時間Cijk，當任務為運回任務時，得到小車運回工件到成品庫的時間.

步驟10重復步驟1～步驟9，直至所有任務都解碼完成，得到各工件的加工方案，小車的調度方案和適應度值F.

算法的具體流程如圖8.

圖8 算法流程圖Fig.8 The flow chart of algorithm

5 算法對比分析

采用文獻[8]中的算例(1～8)在MATLAB 2016a 對本文算法進行對比驗證.算例中布局環(huán)境信息，工件、小車及機器信息見文獻[8],將該文獻中的算法命名為GAMS，ACA，一般遺傳算法記為GA，本文改進的混合遺傳算法算法命名為HGA.以總任務完成時間最小為目標進行計算，程序運行5次結果平均值見表3.一般遺傳算法與本文改進遺傳算法的基本參數(shù)設置分別為：初始化種群popsize=30,最大進化代數(shù)mgen=30交叉概率pc=0.6，變異概率pm=0.2.

表3 不同算法求解結果對比表

表中“-”表示求解時間較長，無法求得結果，對比結果可以看出本算法在解決中小規(guī)模JSP問題時相較于文獻[8]中的算法有較優(yōu)的結果，使用本文算法獲得的最大完工時間比ACA算法平均減少了20%左右，相較于一般的遺傳算法，在求解規(guī)模增大后也逐漸產生優(yōu)勢，因此可以證明本算法的可行性和優(yōu)越性.

應用本文算法求解柔性作業(yè)車間的算例，以下是通過對離散制造企業(yè)進行調研處理后獲得的柔性作業(yè)車間中多加工機器選擇的算例數(shù)據(jù).車間待加工工件為5個，機器6臺，AGV小車3輛，具體工序和加工機器時間如表4所示.車間布局如圖2柵格地圖所示，假設AGV小車行走每一柵格的時間為1 min.

設置基本參數(shù)分別為：初始化種群popsize=60,最大進化代數(shù)mgen=50,交叉概率pc=0.6，變異概率pm=0.2.計算5次獲得的最優(yōu)調度方案甘特圖見圖9，該生產調度最佳調度周期為144，三輛AGV小車行走時長依次為99、111、117.小車每一時刻所在節(jié)點位置情況如圖10 所示，數(shù)字1、2、3分別表示三臺AGV小車，從圖中可以看出AGV小車在行走和等待的狀態(tài)下都沒有節(jié)點占用沖突，符合算法設計要求.

表4 工件加工時間表(min)

圖9 調度方案的甘特圖Fig.9 The Gantt graph of scheduling scheme

圖10 AGV位置節(jié)點時間表Fig.10 Time table of AGV location

圖11 HGA算法搜索過程曲線Fig.11 The process curve of HGA algorithm

圖12 一般遺傳算法搜索過程曲線Fig.12 The process curve of simple genetic algorithm

改進的混合遺傳算法和一般遺傳算法的搜索過程曲線分別如圖11和圖12所示.從圖中可以看出適應度值逐漸減小并收斂，改進的混合遺傳算法在20代開始收斂，比一般遺傳算法收斂速度更快，且獲得的最優(yōu)解更好.仿真結果表明，本文使用的基于時間表和A*算法的混合遺傳算法在處理柔性作業(yè)車間機器/AGV雙資源調度問題是有效的，算法收斂速度較快，能夠得到完整柔性車間工藝和物流集成規(guī)劃方案.

6 結 論

本文針對柔性作業(yè)車間機器/AGV雙資源調度問題，使用柵格地圖模擬車間機器布局和AGV運行環(huán)境，分析了AGV小車在運動和靜止兩種狀態(tài)時的沖突情況并提出解決方案.提出基于時間表和A*算法的混合遺傳算法，設計了以任務為單元的染色體結構，提出相應的交叉變異操作和精英保留策略.以AGV行走時間最短為第二目標，在適應度值相等的個體中優(yōu)先選擇AGV行走時間最短的個體，減少資源浪費.最后實驗證明本文算法在解決中小規(guī)模柔性作業(yè)車間機器/AGV雙資源調度問題的有效性和優(yōu)越性.