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

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

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

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

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

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

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

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

1)每個(gè)工件只能訪問同一臺(tái)機(jī)器一次；

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

3)每個(gè)工件在某一個(gè)時(shí)刻只能在一臺(tái)機(jī)器上加工，中途不能打斷；

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

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

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

2.1 選擇

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

2.2 編碼

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

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

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

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

2.3 交叉與變異

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

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

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

2.4 選擇

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

3.狀態(tài)圖

記圖為G=。

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

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

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

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

3.1 加工流程有向圖

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

頂點(diǎn)集N：如前所述。

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

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

3.2 有向變遷圖

圖1 加工流程有向圖示例

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

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

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

頂點(diǎn)集N：如前所述。

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

3.2.1 變遷的構(gòu)造

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

表1 6機(jī)器、4工件的加工信息表

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

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

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

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

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

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

由圖DTr(q)更新到圖DTr(q+1)的時(shí)刻記為time。狀態(tài)q(q>0)下，圖DTr(q)中變遷數(shù)量為t1，即t1=|ETr|。設(shè)之前狀態(tài)k(k=0，…，q-1)下被拒絕請(qǐng)求的變遷集合為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中對(duì)應(yīng)變遷為eij，對(duì)應(yīng)工序?yàn)镺p1(Op1在機(jī)器i上必然是中間工序)。若機(jī)器i空閑，則在加工流程圖DW中標(biāo)識(shí)變遷eij虛擬發(fā)射，并在圖DTr(q-1)中加入變遷eij

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

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

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

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

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

4.實(shí)例仿真

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

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

[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ū)的自動(dòng)生產(chǎn)單元的無死鎖調(diào)度策略[J].控制理論與應(yīng)用,2005,4,22(2):229-236.

[7]席衛(wèi)東,喬兵,朱劍英.基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度[J]哈爾濱工業(yè)大學(xué)學(xué)報(bào),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é)自動(dòng)化系講師，研究方向：智能調(diào)度與優(yōu)化。