陸 遠，馮睽睽，胡 瑩

(南昌大學(xué) 機電工程學(xué)院，南昌 330031)

0 引言

目前在柔性制造系統(tǒng)中的物流控制系統(tǒng)往往由多個AGV小車構(gòu)成，而在中小型柔性制造系統(tǒng)中，由于加工中心數(shù)量少，多個AGV小車會增加小車的等待時間，易發(fā)生因調(diào)度路線重疊而出現(xiàn)小車沖撞的情況。因此，可采用單個AGV小車處理多個搬運請求的調(diào)度模式。

針對AGV小車的車間調(diào)度方案，目前國內(nèi)外許多學(xué)者主要通過動態(tài)調(diào)度的優(yōu)化算法來搜索AGV小車的調(diào)度路徑的最優(yōu)值。文獻[1]中提出通過機床/AGV小車約束下的遺傳算法，搜索小車的最優(yōu)值，驗證了該算法的可行性。文獻[2]提出通過混合啟發(fā)式算法，最小化小車的最大完工時間。文獻[8]基于模糊滿意度的遺傳算法調(diào)度規(guī)則，計算總體滿意度水平以得到最優(yōu)值。以上算法能保證搜索到最優(yōu)值，但求解過程久，搜索范圍大，計算規(guī)模往往呈指數(shù)倍上漲。因此，可在優(yōu)化算法的基礎(chǔ)上引入小車搬運優(yōu)先級策略，將算法的搜索區(qū)域分割成幾部分，求解出每一部分的最優(yōu)值并進行比較，從而使搜索結(jié)果更接近最優(yōu)值。

本文通過分析AGV小車的車間調(diào)度機制，根據(jù)AGV小車搬運優(yōu)先級的幾種設(shè)定對工序進行編碼，并設(shè)計適應(yīng)度函數(shù)，選擇、交叉和變異方法，通過對遺傳算法的仿真分析，確定哪種托盤搬運優(yōu)先級下小車的最大完工時間最短，為單個AGV小車的調(diào)度問題提供一種有效的解決途徑。

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

柔性制造系統(tǒng)根據(jù)生產(chǎn)計劃制訂如下加工任務(wù)：有n個工件在臺機床上加工，每個工件都有k道工序，工件的每道工序都可以在任一機床上進行加工。由此可得出：

(1)工件集N={n1,n2,···,nn}，ni(i=1,2,···,n)為第i個工件；

(2)工序集P={p1,p2,···,pn}，pi={pi1,pi2,···,pik},pij為第i(i=1,2,···,n)個工件的第j(j=1,2,···,k)道工序；

(3)機床集M={m1,m2,···,mm},mq(q=1,2,···,n)為第q臺機床；

在小車調(diào)度過程中，應(yīng)滿足如下約束條件：

(1)每臺機床都只能一次加工一個工件；

(2)工序的加工時間為常數(shù)；

(3)每個工件加工工序的順序不能改變；

(4)小車從上料臺取件往機床搬運的時刻為所有工件的起始加工時間；

(5)當所有工件加工完成后，小車將所有工件搬至下料臺后搬運任務(wù)才算結(jié)束。

(6)小車搬運工件的優(yōu)先級條件為：①向加工中心上料的工件；②加工中心已加工完的工件；③接近最后工序的工件。按照以上三條件隨機組合成6種優(yōu)先級策略。

根據(jù)以上優(yōu)化約束條件，小車調(diào)度方案的優(yōu)化目標為所有工件的最大加工時間最小化，其數(shù)學(xué)模型為：

min{max(ci)}，i=1,2,···,n。

其中，ci為工件ni的完工時間。

2 算法的設(shè)計

由于遺傳算法可全局搜索且收斂速度快，因此在目標函數(shù)的求解過程中，采用遺傳算法求解目標函數(shù)的最優(yōu)解。基于遺傳算法的機床-AGV 小車的調(diào)度算法的流程如圖1所示。

圖1 機床-AGV小車調(diào)度算法流程圖

2.1 工序編碼

在車間生產(chǎn)調(diào)度過程中，將所有工件的工序集看作一條染色體，每個工件的每一道工序看作染色體中的一個基因，在確保每個工件的工序順序不變的情況下將基因隨機組合，且同一個工件的編碼相同。假設(shè)有4個工件，每個工件有3道工序，則其中一種染色體編碼方式如表1所示。

根據(jù)染色體的編碼排序可得出染色體集Q={Q1,Q2,···,Qn}。

表1 染色體編碼

2.2 確定適應(yīng)度函數(shù)

對于染色體集Q中的第i個染色體Qi，可根據(jù)染色體解碼后機床對應(yīng)工序的加工工時和搬運工時得出該染色體對應(yīng)的完工時間，由此可確定適應(yīng)度函數(shù)：

F(i)=T-ci其中，為所有工序加工時間和小車搬運時間的最大值，保證F(i)>0 。

2.3 選擇、交叉和變異運算

2.3.1 選擇運算

在進行種群繁殖前，需要在種群中選擇優(yōu)良的個體直接遺傳到下一代，以保證優(yōu)良基因的延續(xù)，其選擇策略可選用輪盤賭法，即計算出各個個體的F(i)在整個種群中所占的比重，根據(jù)比重的大小從低到高劃分對應(yīng)的區(qū)域，最后產(chǎn)生一個0～1之間的隨機數(shù)，該隨機數(shù)落在哪個區(qū)域，該區(qū)域所對應(yīng)的各體被選中。因此，對于任意個體j，其被選中的概率為：

2.3.2 交叉運算

在進行基因交叉運算過程中，父代染色體兩兩交叉運算，改變?nèi)旧w中工序的順序，從而形成新的子代染色體。假設(shè)有兩個父代染色體Q1和Q2，則交叉運算的操作步驟如下：

(1)在父代染色體Q1中隨機選擇一個基因pik，該基因所對應(yīng)的工件為ni；

(2)將Q1中含有ni的基因去掉,得到基因片段σ1；

(3)找出父代染色體Q2中ni所對應(yīng)的位置，將除ni之外的基因編碼全部改寫為0，得到基因片段σ2；

(4)將基因片段σ1依次覆蓋基因片段σ2中編碼為0的基因，得到子代染色體Q1′；

(5)在父代染色體Q2中隨機選擇一個基因pik，該基因所對應(yīng)的工件為nj，按照上述交叉運算得出子代染色體Q2′。

染色體的交叉運算原理如圖2所示。

2.3.3 變異運算

在變異運算中，在保證每個工件的加工順序不變的同時，將兩個不同工件的工序進行調(diào)換，得到新的染色體。如圖3所示。

2.4 算法解析

在算法中，設(shè)定tij為小車將第i個工件搬運到指定機床進行第j道工序的搬運時間；pij為第i個工件進行第j道工序的加工時間；Tds為小車進行第d個任務(wù)的開始時間；Tde為小車進行第d個任務(wù)的結(jié)束時間；sij為工件i第j道工序的開始加工時間；eij為工件i第j道工序的結(jié)束加工時間；mq為機床q的空閑開始時間；fi為工件i的完成時間。因此，sij=tij+Tds，T1s=0，pij=eij-sij

根據(jù)前文問題描述中給定的工件搬運優(yōu)先級的設(shè)定，按照6種調(diào)度策略，每個工件依次選擇完工時間最短且空閑的機床進行加工，并計算出完工時間，在滿足搬運優(yōu)先級的條件下進行遺傳運算，直到迭代結(jié)束。

圖2 交叉運算原理

圖3 變異運算原理

3 仿真實驗與分析

假設(shè)該調(diào)度系統(tǒng)共有5臺機床可供加工，有4個工件，第1個工件有3道工序，第2個工件有2道工序，第3個工件有4道工序，第4個工件有3道工序。每道工序在各個機床上的加工時間如表2所示(0表示該機床無法加工此道工序)；小車在上料臺和各機床間的搬運時間如表3所示。

表2 機床加工時間表(單位：min)

生產(chǎn)線各機床和上下料區(qū)的分布如圖4所示，AGV小車的搬運時間如表3，上下料區(qū)和相鄰的機床以及各相鄰機床間的搬運時間均為0.5min。

遺傳算法的初始參數(shù)：種群規(guī)模P-size=40，遺傳代數(shù)Generation=50，交叉率pc=0.7，變異率pm=0.05。由表2、表3可知，所有工序加工時間和小車搬運時間之和T=95。

小車搬運優(yōu)先級①為：向加工中心上料的工件>加工中心已加工完的工件>接近最后工序的工件。當優(yōu)先級相同時，按工件號從小到大依次搬運。

圖4 機床分布圖

上料臺m1m2m3m4m5下料臺上料臺00.511.510.50m10.500.511.510.5m210.500.511.51m31.510.500.511.5m411.510.500.51m50.511.510.500.5下料臺00.511.510.50

根據(jù)小車搬運優(yōu)先級，通過遺傳算法得到小車調(diào)度結(jié)果的甘特圖如圖5所示。

所有工件在22.5min加工完畢，m5取出工件n3，并將其搬運至下料臺，則小車的最短完工時間為t1=23min。根據(jù)小車搬運優(yōu)先級，一共有6種調(diào)度策略，再分別得出其他5種優(yōu)先級的調(diào)度策略下的甘特圖如圖6所示。

圖5 小車調(diào)度甘特圖

圖6 其余5種調(diào)度策略甘特圖

優(yōu)先級②的調(diào)度策略下，所有工件在23.5min加工完畢，小車在機床m5取出工件n3，并將其搬運至下料臺，則小車的最短完工時間為t2=24min；優(yōu)先級③的調(diào)度策略下，所有工件在24min加工完畢，小車在機床m2取出工件n4，并將其搬運至下料臺，則小車的最短完工時間為t3=25min；優(yōu)先級④⑤⑥的調(diào)度策略下，所有工件均在24.5min加工完畢，小車在機床m5取出工件n3，并將其搬運至下料臺，則小車的最短完工時間為t4=t5=t6=25min。因此，在優(yōu)先級①的調(diào)度策略下小車完工時間最短，故在實際生產(chǎn)過程中可采用向加工中心上料的工件>加工中心已加工完的工件>接近最后工序的工件的優(yōu)先級策略進行AGV小車調(diào)度。

根據(jù)優(yōu)先級①的調(diào)度策略，AGV小車的搬運路線如圖7所示，共32條路線，則AGV小車的搬運時間td=16min,等待時間tw=t1-td=7min。

圖7 AGV小車調(diào)度路線圖

4 結(jié)束語

通過遺傳算法來求解單個AGV小車在處理多個搬運請求時的調(diào)度問題，在求解過程中加入AGV小車搬運優(yōu)先級的設(shè)定來縮小求解范圍，以快速搜索到最優(yōu)解，仿真結(jié)果表明該算法下的AGV小車調(diào)度方案可用于中小型柔性生產(chǎn)線的加工生產(chǎn)。而通過不同優(yōu)先級的調(diào)度策略對AGV小車調(diào)度結(jié)果的影響，也為AGV小車車間調(diào)度提供了一種可供參考的解決途徑。