基于狀態(tài)圖的車間作業(yè)遺傳調(diào)度

華北電力大學(xué)自動化系 白 康

基于狀態(tài)圖的車間作業(yè)遺傳調(diào)度

華北電力大學(xué)自動化系 白 康

針對車間作業(yè)調(diào)度問題，利用有向圖模型對系統(tǒng)中工件和資源之間的交互關(guān)系建模，并應(yīng)用遺傳算法進行最優(yōu)調(diào)度的求解。遺傳算法采用多維矩陣的編碼方式，解碼后生成加工流程有向圖，根據(jù)有向變遷圖的更新最終獲取每個染色體的適應(yīng)度。每一代種群在遺傳算子的作用下，按照適者生存和優(yōu)勝劣汰的原理，逐代演化得到越來越好的近似解。

車間作業(yè)調(diào)度；狀態(tài)圖；遺傳算法

1.調(diào)度問題描述

n種工件J={Ji|i=1，…，n}在一個由m臺不同的加工機器R={mi|i=1，…，m}組成的制造系統(tǒng)中進行加工，機器的容量為C(m)。每個工件的工序順序預(yù)先確定，即工件Ji必須按照一定的工藝順序Oi={Oij|j=1，…，p(i)}(p(i)為工件Ji的工序數(shù)量)進行加工。假設(shè)：

1)每個工件只能訪問同一臺機器一次；

2)各工件經(jīng)過準備時間后即可開始加工；

3)每個工件在某一個時刻只能在一臺機器上加工，中途不能打斷；

4)不考慮工件之間的加工優(yōu)先權(quán)；

5)系統(tǒng)無緩沖。

2.遺傳算子設(shè)計

2.1 選擇

染色體適應(yīng)度值由公式(1)給出，其中C是一個大的正整數(shù)。

2.2 編碼

定義染色體為二維矩陣ch[3][op]，其中，op為所有工件工序數(shù)量總和。

第一行是基于工序的編碼：為工件賦予1到n的編號，即數(shù)字i代表工件Ji。從左到右掃描，i的第j次出現(xiàn)代表工序Oij。

第二行是基于機器的編碼：[k11，k12，…，k1p(1)，…，kn1，kn2，…，knp(n)]。其中，kij表示工序Oij所選擇的機器號碼。

第三行提供了加工時間的信息：[t11，t12，…，t1p(1)，…，tn1，tn2，…，tnp(n)]。其中，tij代表工序Oij在機器kij進行加工所需要的加工時間。

2.3 交叉與變異

為了避免交叉操作之后產(chǎn)生非法個體(某道工序選擇了不可用的機器)，規(guī)定僅僅對染色體的第二行、第三行數(shù)據(jù)，以概率pc進行兩點交叉操作。

設(shè)計兩種變異算子。對染色體第一行數(shù)據(jù)，以概率pmop進行互逆變異操作，其目的在于生成新的調(diào)度。對染色體第二行數(shù)據(jù)，以概率pmch改變某基因的值，注意要保證選擇的機器合法。之后改變?nèi)旧w第三行相應(yīng)位置上的值，賦予其新機器上的加工時間。

以上的編碼方式結(jié)合交叉、變異操作可使得生成的染色體在工序和機器選擇方面都是合法染色體。

2.4 選擇

采用適應(yīng)度比例方法，并執(zhí)行保優(yōu)策略。即當(dāng)進行交叉、變異等操作時，生成的子代種群和父代種群合并成一個新的種群，對新種群應(yīng)用適應(yīng)度比例方法，即輪盤賭方法進行選擇，且保存當(dāng)代最優(yōu)個體，即適應(yīng)度最大且所有機器的總完工時間最小的染色體。

3.狀態(tài)圖

記圖為G=。

N是頂點集合，規(guī)定圖中各頂點編號與系統(tǒng)中的各臺機器的編號一致，同時增加一個虛擬結(jié)點代表虛擬設(shè)備re，其編號為m+1。該點表示系統(tǒng)的輸出，其容量無限大，且隨時可用。工件完成加工后均進入re。以下各圖中的頂點集合均為此定義。

E是變遷集合，即邊集合。變遷euvG，表示該變遷連接頂點u和v。

本文中，圖采用鄰接表的形式進行存儲：對頭頂點i，定義holdnum(i)表示當(dāng)前狀態(tài)下頂點i被占據(jù)的數(shù)量，即機器i正在加工的工件數(shù)量，初始化holdnum(i)=0(i=1，…，n)；對于各個變遷表結(jié)點，除了頂點域adjvex和鏈域next，再增加一個信息域info，存儲此變遷對應(yīng)的加工信息，即工件號碼、工序號碼、加工開始時間、加工操作時間和加工結(jié)束時間。

對于工件Ji來說，它的加工路徑可以用其需要的資源序列wi=WP(i)來表示。若有w1={m2，m3，m4，re}，表示工件J1按加工工藝順序依次訪問了機器m2，m3，m4后完成所有加工操作，進入系統(tǒng)輸出設(shè)備re。

3.1 加工流程有向圖

加工流程有向圖，記為DW(Working Procedure Digraph)。DW=(N，EW)是靜態(tài)圖，表示了各個工件的加工路徑。根據(jù)初始生成的染色體來構(gòu)造圖DW如下：

頂點集N：如前所述。

變遷集EW：將染色體解碼得到各工件的加工路徑wi(i=1，…，n)，據(jù)此得到各個變遷，并賦予其相應(yīng)的加工信息。如，若有w1={m2，m3，m4，re}，則變遷e23，e34，e4reEW。

圖1中，隨機產(chǎn)生一個染色體chrom[1]，并建立其加工流程有向圖DW，頂點i之后的字符串“k[i-j]”表示工序Oij由變遷eik來表征。

3.2 有向變遷圖

圖1 加工流程有向圖示例

圖2 圖DW以及對應(yīng)的DTr(0)(a)加工流程有向圖DW；(b)初始有向變遷圖DTr(0)

有向變遷圖DTr(Transition Digraph)是動態(tài)的系統(tǒng)狀態(tài)演化圖，也可稱為狀態(tài)圖。它可以清楚地描述系統(tǒng)當(dāng)前狀態(tài)q下工件和資源的交互關(guān)系[9]，即正在進行加工的工件、這些工件正在占據(jù)的資源以及下一步工序請求的資源。

令q狀態(tài)下的有向變遷圖為DTr(q)=[N，ETr(q)]。

頂點集N：如前所述。

變遷集ETr：ETr也被稱為可行變遷集合，其中的元素稱為可行變遷。Jq表示當(dāng)前狀態(tài)q下，系統(tǒng)中正在進行加工的工件集合。

3.2.1 變遷的構(gòu)造

變遷的構(gòu)造情況與三種驅(qū)動事件一一

表1 6機器、4工件的加工信息表

圖3 有向變遷圖DTr(q)的更新演變示意圖

根據(jù)圖1中的染色體chrom[1]構(gòu)造的加工流程有向圖DW見圖2(a)，對應(yīng)的初始有向變遷圖DTr( 0)見圖2(b)。

圖2(b)表示在0時刻、初始狀態(tài)下，工件3沒有開始加工操作(工序O31選用機器1，而機器1上的頭道工序是O22，因此工序O31在初始狀態(tài)時被阻止加工)；變遷e31、e35和e46是可行變遷，對應(yīng)的工序分別為O21、O11和O41；變遷上的數(shù)字表示變遷發(fā)射時刻，實際對應(yīng)工序的加工結(jié)束時間。

(2)有向變遷圖的更新時刻

在有向變遷圖DTr(q)和加工流程有向圖DW中，每個變遷e上都賦予了三個時間信息：加工開始時間e.str、加工操作時間e.op和加工結(jié)束時間e.fini。其中，一旦工序選定了機器，e.op就是定值，而e.str和e.fini將隨著系統(tǒng)狀態(tài)的演化而更新。

三個時間信息之間的關(guān)系為：

由圖DTr(q)更新到圖DTr(q+1)的時刻記為time。狀態(tài)q(q>0)下，圖DTr(q)中變遷數(shù)量為t1，即t1=|ETr|。設(shè)之前狀態(tài)k(k=0，…，q-1)下被拒絕請求的變遷集合為Tn，t2=|Tn|。令t=t1–t2，q狀態(tài)下使能變遷ei滿足公式(3)。

更新完成后，圖DTr(q+1)中新加入的變遷滿足公式(5)。

圖4 調(diào)度結(jié)果的甘特圖(C(m)=2)

(c)第三步：處理未開始加工的工件。

前兩步都由有向變遷圖DTr(q-1)更新得來。查找是否還有工件沒有開始加工。若有，加工流程圖DW中對應(yīng)變遷為eij，對應(yīng)工序為Op1(Op1在機器i上必然是中間工序)。若機器i空閑，則在加工流程圖DW中標識變遷eij虛擬發(fā)射，并在圖DTr(q-1)中加入變遷eij

(a)至(c)三步中，某臺機器t空閑分兩種情況：

情況1：機器t上的前道工序O正在加工且holdnum(i)

情況2：機器t上 的工序O已經(jīng)加工完畢。

經(jīng)過三步構(gòu)造，有向變遷圖DTr(q-1)就更新成為了有向變遷圖DTr(q)。

圖3給出了對應(yīng)染色體chrom[1]的有向變遷圖DTr(q)的部分演化過程。圖3(a)中，因e35.fini最小，e35成為使能變遷，應(yīng)在time=4時刻發(fā)射。變遷e35代表工序O11，根據(jù)加工流程圖DW遷得知，工序O12在機器5上并不是頭道工序，所以最終變遷e35的發(fā)射被阻止，在time=4時刻，狀態(tài)圖推進到有向變遷圖DTr(1)，見圖3(b)。圖3(b)中，使能變遷是e31，代表工序O21，而工序O22是機器1的頭道工序，變遷e31在時刻time=5時正常發(fā)射；而初始狀態(tài)時，工序O31被阻止加工，此時阻止的理由消失，代表工序O31的變遷e14也隨之成為可行變遷，狀態(tài)圖更新到有向變遷圖DTr(2)，即圖3(c)。

4.實例仿真

以表1所示調(diào)度問題為例。遺傳算法的參數(shù)設(shè)置為：交叉概率Pc=0.85，Pmop=0.012，Pmch=0.2。種群規(guī)模popsize=50，運行最大進化代數(shù)maxgen=100，得到的調(diào)度結(jié)果makespan=17。

圖4給出了運算結(jié)果對應(yīng)的甘特圖中，“i-j-k”表示工件i的第j道工序在機器k上加工。從甘特圖中可以看出，每個工件只在一臺機器上加工了一次，對于機器4和機器6，當(dāng)首道工序正在加工且機器空閑時，允許第二道工序開始加工。

[1]Wysk RA,Yang NS,Joshi S.Detection of deadlocks in fexible manufacturing cells[J].IEEE Transactions on Robotics and Automation,1991,7(6):853-589.

[2]Fanti MP,Maione G,Turchiano B.Deadlock detection and recovery in fl exible production systems with multiple capacityresources[J].IEEE Transaction on Automatic Control,1996,1(1):237-241.

[3]Fanti MP,Maione B,Mascolo S,et al.Event-based feedback control for deadlock avoidance in flexible production systems[J].IEEE Transactions on Robotics and Automation,1997,13(3):347-363.

[4]Hyuenbo Cho,Kumaran TK,Wysk RA.Graphtheoretic deadlock detection and resolution for flexible manufacturing systems[J].IEEE Transactions on Robotics and Automation,1995,11(3):413-421.

[5]Kumaran TK,Wysk RA,Chang W,et al.A structured approach to deadlock detection,avoidance and resolution in fl exible manufacturing systems[J].International Journal of Production Research,1994,32(10):2361-2379.

[6]徐剛,吳智銘.考慮緩沖區(qū)的自動生產(chǎn)單元的無死鎖調(diào)度策略[J].控制理論與應(yīng)用,2005,4,22(2):229-236.

[7]席衛(wèi)東,喬兵,朱劍英.基于改進遺傳算法的柔性作業(yè)車間調(diào)度[J]哈爾濱工業(yè)大學(xué)學(xué)報,2007,39(7):1151-1153.

[8]Fanti MP,Maione B,Mascolo S,et al.Event-based feedback control for deadlock avoidance in flexible production systems[J].IEEE Transactions on Robotics and Automation,1997,13(3):347-363.

白康（1982—），女，河北保定人，碩士研究生，華北電力大學(xué)自動化系講師，研究方向：智能調(diào)度與優(yōu)化。