基于混合遺傳算法的柔性作業(yè)車間機(jī)器和AGV規(guī)劃

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

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

1 引 言

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

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

Saidi-Mehrabad等[8]提出了一種二階段蟻群算法求解問(wèn)題，討論了AGV的無(wú)沖突路徑規(guī)劃問(wèn)題以及基本的車間作業(yè)調(diào)度(JSSP)問(wèn)題，但所討論的每道工序加工機(jī)器都是唯一的，未討論柔性作業(yè)車間中零件的多臺(tái)可選加工機(jī)器的情況.賀長(zhǎng)征等[9]針對(duì)柔性作業(yè)車間機(jī)器/AGV的雙資源調(diào)度設(shè)計(jì)了三鏈?zhǔn)骄幋a結(jié)構(gòu)，提出了基于時(shí)間窗和Dijkstra算法的混合遺傳算法，但在AGV路徑規(guī)劃中未考慮小車靜止時(shí)的占用沖突問(wèn)題.

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

2 問(wèn)題描述和模型建立

假設(shè)生產(chǎn)車間有k臺(tái)可加工機(jī)器，v輛相同的AGV小車，當(dāng)前總?cè)蝿?wù)有n個(gè)待加工工件，每個(gè)工件有一道或多道工序，每道工序可在一臺(tái)或多臺(tái)機(jī)器上完成加工作業(yè)，并且有相應(yīng)的加工時(shí)間.每臺(tái)空閑的AGV小車都可以運(yùn)送工件，最終加工完成的工件需要全部送回成品區(qū).

本文引入表 1的符號(hào)定義，并假設(shè)條件如下.

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

表1 符號(hào)定義

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

目標(biāo)函數(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)表示模型以最大總運(yùn)輸時(shí)間最短為目標(biāo)；式(2)表示工件的每道工序可也僅可在一臺(tái)機(jī)器上加工完成；式(3)表示每個(gè)任務(wù)只能由一臺(tái)AGV小車運(yùn)送；式(4)和式(5)中A為一個(gè)特別大的數(shù)，公式表示在同一機(jī)器上后加工的工序必須等待前一工序加工完成才能開(kāi)始加工；式(6)表示負(fù)載行程要等待小車到達(dá)且工件加工完成后才能開(kāi)始，運(yùn)輸工件第一道工序任務(wù)時(shí)，無(wú)加工等待時(shí)間.

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

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

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

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

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

圖2 柵格地圖Fig.2 Raster map

在小車的一次運(yùn)輸任務(wù)周期內(nèi)，包含空載行程，等待負(fù)載，負(fù)載行程三個(gè)狀態(tài)，如圖3所示，負(fù)載行程結(jié)束后立即進(jìn)入下一任務(wù)等待狀態(tài)，當(dāng)前一任務(wù)結(jié)束時(shí)小車所在位置和下一任務(wù)起始位置相同時(shí)，AGV小車無(wú)空載行程.

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

3.1 A*算法

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

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

(7)

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

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

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

若為交叉阻塞，小車以當(dāng)前點(diǎn)當(dāng)作一個(gè)臨時(shí)目標(biāo)點(diǎn)，查詢節(jié)點(diǎn)N占用結(jié)束時(shí)間為t1，以當(dāng)前節(jié)點(diǎn)C為新的起始點(diǎn)，起始時(shí)間t=t1進(jìn)行路徑規(guī)劃，更新時(shí)間表.

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

由于AGV小車完成單個(gè)任務(wù)后?？坑跈C(jī)器旁，而其他任務(wù)優(yōu)先級(jí)的小車若要訪問(wèn)此機(jī)器則不允許其長(zhǎng)時(shí)間占用，因而產(chǎn)生的機(jī)器節(jié)點(diǎn)位置占用沖突.

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

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

(8)

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

采用一個(gè)實(shí)例來(lái)描述遺傳操作的過(guò)程.工件加工信息如表2所示.

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

4.1 編 碼

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

(9)

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

(10)

第三部分為AGV編碼，表示執(zhí)行各工件各工序運(yùn)輸任務(wù)的AGV小車，順序?qū)?yīng)任務(wù)編碼中的各任務(wù)運(yùn)輸所需AGV號(hào)，基因串長(zhǎng)度為L(zhǎng)1.

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

圖5 染色體編碼方式

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

4.2 初始化

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

4.3 選擇操作

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

4.4 交叉操作

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

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

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

4.5 變異操作

針對(duì)任務(wù)基因串，從染色體P1中隨機(jī)選擇兩個(gè)位置的基因，然后將它們的位置互換.任務(wù)基因串變異過(guò)程見(jiàn)圖7(a).

針對(duì)機(jī)器基因串，隨機(jī)選擇機(jī)器編碼的基因串上的一個(gè)基因，在該工序的加工機(jī)器集中隨機(jī)選取另外一個(gè)不同的機(jī)器替換掉當(dāng)前機(jī)器，并按0.2的概率選擇加工時(shí)間最短的機(jī)器.機(jī)器基因串變異過(guò)程見(jiàn)圖7(b).

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

圖7 染色體變異示意圖

4.6 精英保留策略

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

F=F+0.0001×T

(11)

對(duì)個(gè)體進(jìn)行排序，保留AGV小車的總運(yùn)行時(shí)間最小的個(gè)體為最優(yōu)解.

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

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

4.7 解碼和適應(yīng)度計(jì)算

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

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

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

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

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

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

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

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

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

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

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

步驟10重復(fù)步驟1～步驟9，直至所有任務(wù)都解碼完成，得到各工件的加工方案，小車的調(diào)度方案和適應(yīng)度值F.

算法的具體流程如圖8.

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

5 算法對(duì)比分析

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

表3 不同算法求解結(jié)果對(duì)比表

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

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

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

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

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

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

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

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

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

6 結(jié) 論

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