基于Memetic算法的RGV動(dòng)態(tài)調(diào)度模型

王 帥

（長春光華學(xué)院基礎(chǔ)教研部，吉林長春 130033）

1 簡述

RGV引導(dǎo)車在工作周期內(nèi)不會出現(xiàn)故障等情況,其連續(xù)移動(dòng)1 個(gè)單位,2 個(gè)單位和3 個(gè)單位的時(shí)間不同,每臺數(shù)控機(jī)床CNC 一次只能加工一個(gè)物料[1]。利用TS算法處理RGV運(yùn)行軌跡如圖1所示。

圖1 RGV運(yùn)行軌跡圖

采用Memetic算法處理流程圖如圖2。

圖2 Memetic算法處理流程圖

對于基于Memetic 算法的調(diào)度模型研究很多主要將算法的求解結(jié)果和設(shè)定問題的下界進(jìn)行比較[2-3]。為了對模型的實(shí)用性進(jìn)行檢驗(yàn),可以利用相關(guān)的數(shù)據(jù)進(jìn)行處理,分析比較兩個(gè)算法的數(shù)據(jù),運(yùn)用問題一所建立的模型將智能加工系統(tǒng)作業(yè)的三組參數(shù)分別代入模型求解。數(shù)據(jù)代入模型,由此可得,RGV的平均流經(jīng)時(shí)間,CNC 完成一個(gè)兩道工序的物料所需的總時(shí)間,RGV 上下物料的總時(shí)間,清洗作業(yè)的時(shí)間。然后求和總用時(shí)和CNC的效率。

2 模型假設(shè)與約定

模型建立假設(shè)8 臺數(shù)控機(jī)床CNC 分別標(biāo)號si,i=1,2,3,4,5,6,7,8;RGV 引導(dǎo)車在工作時(shí)間內(nèi)不會停止工作。xrli為物料Ji存儲在上時(shí)其值為1 否則為0;yrKi為當(dāng)物料Ji是機(jī)床N上第k次加工的物料時(shí)其值為1否則為0;為當(dāng)物料Ji完成處理到下料傳送ωie帶上時(shí),e值為1 否則其值為0;ziv為當(dāng)運(yùn)送i由RGV 來執(zhí)行時(shí)v值為1否則其值為0。

3 RGV動(dòng)態(tài)調(diào)度模型建立

給定一組物料在機(jī)床上加工序列在確定RGV 搬運(yùn)物料時(shí)間后決策變量,xrli,yrKi,ωie與ziv的值都能確定此時(shí)直線往復(fù)RGV 調(diào)度問題的模型可構(gòu)建如下:當(dāng)有RGV 在軌道上有序的給任意CNC 機(jī)床按放生料,在加工過程中CNC未出現(xiàn)故障的情況下利用題目中給定的系統(tǒng)作業(yè)參數(shù)計(jì)算,利用TS 算法對該過程求解。以下約束成立條件組為:

r=1,…,m;l=1,…,n;i=1,…,NUM;

e=1,…,N;v=1,2,

使得Gi-1≤Gi,i=2,…NUM;

以上約束給出了RGV 的上料順序和RGV 運(yùn)送的開始時(shí)間、完成時(shí)間、開始位置和完成位置的計(jì)算方式;當(dāng)任意CNC 發(fā)生故障時(shí)，將可能發(fā)生CNC 故障的情況進(jìn)行歸納總結(jié)分為以下4類故障處理，約束其中故障i和故障j為兩個(gè)不同的機(jī)床發(fā)生故障,滿足i≠j,當(dāng)有故障機(jī)床i分配給其他CNC1,故障機(jī)床j分派給其他CNC2,待機(jī)床修復(fù)后重新進(jìn)行工作。具體TS算法流程圖如圖3。

圖3 TS算法流程圖

對于兩道加工過程的物料加工作業(yè)情況,利用以工序?yàn)闃?biāo)準(zhǔn)的編碼方式進(jìn)行工序編號,即每一道工序都對應(yīng)相應(yīng)的工號,要保證每個(gè)物料號出現(xiàn)的次數(shù)與物料的工序總數(shù)相等,然后利用Memetic 算法中的染色體次序方法進(jìn)行編譯,第k次出現(xiàn)的物料序號,就是該物料的第k次工序。對于m個(gè)物料在n臺上加工的調(diào)度問題,記任務(wù)i是在CNC 上的操作為Oicnc每個(gè)操作所需時(shí)間為Ticnc,T(Oicnc)為操作Oicnc的開始時(shí)間,m(i)為在第i個(gè)CNC 上加工的物料總數(shù)目,目標(biāo)是最小化最大完工時(shí)間。即數(shù)學(xué)表達(dá)式為:min{max(T(Oi,m(i))+Ti,m(i))}i=1,2,…,n式中約束條件有，同一物料不同操作之間的時(shí)間約束:

T(Oi+1,m(i))-Tij≥T(Oij)，

同一CNC不同操作之間的時(shí)間約束:

T(Oi,m(i)+1)-Tij≥T(Oij)，

每個(gè)操作的開始時(shí)間為正T(Oij)≥0。假設(shè)當(dāng)出現(xiàn):機(jī)床3 出現(xiàn)故障,導(dǎo)致加工時(shí)間延誤10～20 分鐘,利用Memetic 算法要對所有工序進(jìn)行重新調(diào)度,來解決出現(xiàn)故障情況下的RGV調(diào)度和CNC。

4 模型求解

已知RGV工作以及CNC機(jī)床調(diào)度對于一道工序和兩道工序的物料加工情況（包含CNC 故障時(shí)的調(diào)度情況）,依據(jù)所建立的模型以及求解方案可以有以解決策略。

當(dāng)加工生料i分配給CNCS1,加工生料j分派給CNCS2，且加工生料i的開始位置大于等于加工生料j的開始位置時(shí),約束3 保證了加工生料j開始后加工生料i開始前S2有足夠的時(shí)間載貨駛過并上料;加工生料i的開始位置S1到達(dá)加工生料i的開始位置的最早時(shí)間為Gj+u+,此時(shí)CNCS1與CNCS2不會發(fā)生沖突,當(dāng)加工生料i的開始位置大于等于加工生料j的完成位置時(shí),約束4 保證了加工生料j完成后加工生料i開始前v2 有足夠的時(shí)間空行駛過上料;加工生料i的開始位置,當(dāng)加工生料i的完成位置大于等于加工生料j的開始位置時(shí),約束5 保證了在加工生料j開始后加工生料完成前v2 有足夠的時(shí)間載貨駛過上料,加工生料i的完成位置v1到加工生料i的完成位置的最早時(shí)間為Gj+u+,加工生料i的最早完成時(shí)間為Gj+u+,當(dāng)加工生料i的完成位置大于等于加工生料j的完成位置時(shí)，約束6保證了在運(yùn)送j完成后加工生料i完成前，S2有足夠的時(shí)間空行駛過加工生料i的完成位置。具體RGV調(diào)度求解如下:

利用TS 算法處理兩道工序的物料加工如圖4所示。

圖4 TS算法處理兩道工序的物料過程圖

對于給定系統(tǒng)作業(yè)參數(shù)的三組數(shù)據(jù)，由平均流經(jīng)時(shí)間方程可知

由工序完成時(shí)間方程可知，完成一道工序的物料所需時(shí)間:T1=c1；完成兩道工序的物料所需總時(shí)間:T11=c11+C12。假設(shè)任務(wù)開始的時(shí)間為:T(Oij)=0，根據(jù)題目給出的RGV在各個(gè)CNC上下料的時(shí)間,RGV完成一個(gè)物料清洗的時(shí)間S以及公式:

Tmin=min{max(T(Oij)+T1+T11+S)},

代入求解,CNC 加工完成一個(gè)一道工序物料所需的最小總時(shí)間為:Tmin1，CNC 加工完成一個(gè)一道工序物料所需的最小總時(shí)間為:Tmin12。

依據(jù)所給的系統(tǒng)作業(yè)參數(shù)對問題一建立的兩類模型進(jìn)行相應(yīng)的實(shí)用性檢驗(yàn)和算法的有效性校驗(yàn)。

5 模型檢驗(yàn)

模型采用TS（禁忌搜索）算法,將連續(xù)8 小時(shí)作業(yè)情況繪制成圖5和圖6所示。

圖5 一道物料加工順序

圖6 兩道物料加工順序

從圖5-6 可以看出8 小時(shí)對于一道工序的作業(yè)情況,該流程較為效率合適。在一個(gè)工作周期內(nèi),不能夠有效的處理故障情況,對于TS 算法處理兩道工序該算法的效率較低。對于使用TS算法進(jìn)行直線的RGV部分調(diào)度情況如圖7所示。

圖7 兩道物料加工順序

圖7所示RGV 調(diào)度搜索過程是根據(jù)CNC 發(fā)出的請求搜尋最近的目標(biāo),當(dāng)出現(xiàn)故障情況時(shí),對RGV 調(diào)度影響較大,對其工作會效率影響較大。

同樣為驗(yàn)證算法的有效性將TS算法的求解結(jié)果與設(shè)定問題的下界進(jìn)行比較。記為TS算法求得的解的平均值則與下界的定義下表給出了9 組算例的計(jì)算結(jié)果如表1所示。

表1 組算例的計(jì)算結(jié)果

以兩道工序?yàn)榛A(chǔ),采用Memetic 算法對RGV 引導(dǎo)車進(jìn)行調(diào)度和數(shù)控機(jī)床CNC 的分配。圖示說明了利用Memetic 算法進(jìn)行兩道工序的操作是相對高效的,能夠在作業(yè)時(shí)間內(nèi)對物料進(jìn)行合理的一道工序加工，其效率和TS算法比較是更高效的，從圖中清晰可見完成一道工序的數(shù)量上也領(lǐng)先于TS算法。

RGV調(diào)度搜索過程的最優(yōu)解,和平均解之間有較小的差距,說明故障情況對RGV 調(diào)度影響較小,相應(yīng)的工作效率較高。為了驗(yàn)證算法的有效性本文同樣將Memetic 算法的求解結(jié)果也和設(shè)定問題的下界進(jìn)行比較。記Cts為TS 算法求得的解的平均值則Cts與下界的gap定義為：gap=(Cts-LB)/LB。

表2給出了9組算例的計(jì)算結(jié)果。

表2 組算例的計(jì)算結(jié)果

通過對TS 算法和Memetic 算法的校驗(yàn)?zāi)軌蚩闯鯩emetic 算法更適用于該種情況的智能RGV 動(dòng)態(tài)調(diào)度,其中TS 算法對于故障的處理能力要遠(yuǎn)低于Memetic算法,Memetic 算法對于發(fā)生故障時(shí)對RGV 小車的重新調(diào)度和CNC的重新分配更為穩(wěn)定。