多群體并行遺傳算法在動態(tài)車間調(diào)度中的應(yīng)用

［摘 要］ 生產(chǎn)調(diào)度對企業(yè)的生產(chǎn)作業(yè)過程具有重要的作用。有效的調(diào)度方法和優(yōu)化技術(shù)是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。本文論述利用多群體并行遺傳算法可滿足動態(tài)車間調(diào)度的應(yīng)用，采用一種特殊構(gòu)造遺傳編碼方法來改進(jìn)遺傳算法，提供有效的最優(yōu)化查詢。利用MATLAB工具以實(shí)例證明該算法的有效性。該算法特別適合于job-shop調(diào)度問題。

［關(guān)鍵詞］ 指派規(guī)則；遺傳算法； job-shop調(diào)度；多代遺傳算法

1 引 言

生產(chǎn)調(diào)度是對企業(yè)生產(chǎn)作業(yè)過程進(jìn)行計(jì)劃#65380;安排以及組織執(zhí)行，有效的調(diào)度方法和優(yōu)化技術(shù)是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵#65377;job-shop調(diào)度問題是許多生產(chǎn)調(diào)度問題的簡化模型，是生產(chǎn)調(diào)度領(lǐng)域研究的重要內(nèi)容，job-shop調(diào)度問題研究具有重要的理論意義和工程價(jià)值#65377;

當(dāng)前，job-shop調(diào)度方法大多采用指派規(guī)則和知識庫系統(tǒng)#65377;指派規(guī)則的缺陷是實(shí)用性差，局限于特定生產(chǎn)環(huán)境，同時(shí)需要人工選擇和更新#65377;知識庫系統(tǒng)利用有調(diào)度經(jīng)驗(yàn)的專家知識來解決問題，它需要建立一個(gè)龐大知識庫收集各種專家經(jīng)驗(yàn)，這種方法具有工作量巨大#65380;速度慢#65380;效果不明顯等缺陷#65377;本文提出一種并行多代遺傳算法(GA)，該算法應(yīng)用遷移模型和一些改進(jìn)的交叉和變異算子，處理動態(tài)job-shop調(diào)度問題，同時(shí)能夠克服簡單GA 的一些弱點(diǎn)，如計(jì)算時(shí)間長#65380;容易陷入局部最優(yōu)等#65377;

2 job-shop調(diào)度線性模型建立

job-shop研究i個(gè)工件在k臺機(jī)器上的加工，已知各操作的加工時(shí)間和i個(gè)工件在各機(jī)器上的加工次序約束，要求確定與工藝約束條件相容的各機(jī)器上所有工件的加工開始時(shí)間或完成時(shí)間或加工次序，使加工性能指標(biāo)達(dá)到最優(yōu)#65377;該問題的形式化如下:

設(shè)Cik表示工件i在機(jī)器k上的完成時(shí)間，tijk表示操作(k， j，i)的處理時(shí)間，Cik是基本決策變量#65377;每個(gè)job-shop操作都可以用(i， j，k)三變量描述為工件i操作j在機(jī)器k上執(zhí)行#65377;假設(shè)操作(i， j-1，h)需要機(jī)器h，操作(i， j，k)需要機(jī)器k，那么Cik在可行的值域內(nèi)描述優(yōu)先級的約束條件的不等式如下:

3 并行多代遺傳算法

job-shop調(diào)度問題屬于一類資源組合優(yōu)化問題，可以采用不同的優(yōu)化策略來進(jìn)行最優(yōu)解的搜索#65377;本文提出一種并行多代搜索策略解決job-shop調(diào)度優(yōu)化問題#65377;

3. 1初始化

初始化要為并行多代遺傳算法產(chǎn)生一些可行的初代群體，本文通過算法隨機(jī)產(chǎn)生初始代群體#65377;

3. 2編碼和目標(biāo)函數(shù)

3. 3交叉和變異

遺傳算法產(chǎn)生新個(gè)體的一個(gè)基本運(yùn)算是交叉，新個(gè)體具有父母某些遺傳屬性#65377;交叉的最簡單運(yùn)算是單點(diǎn)交叉#65377;

job-shop調(diào)度問題是一個(gè)極其復(fù)雜的過程，普通交叉和變異運(yùn)算是無效的#65377;本文采用順序交叉和多點(diǎn)交叉有效結(jié)合構(gòu)造子代，在串的前半部分采用順序交叉，后半部分采用多點(diǎn)交叉#65377;

順序交叉首先隨機(jī)確定兩個(gè)交叉切點(diǎn)，然后把在這兩個(gè)切點(diǎn)之間的部分傳遞給兩子女#65377;接著運(yùn)算器開始構(gòu)建左邊和右邊的剩下部分#65377;第一代子女的構(gòu)建是越過第2個(gè)父母，消除與第一代父母的傳送部分相同的數(shù)值，并根據(jù)第2個(gè)父母出現(xiàn)的順序裝滿空缺的左邊和右邊#65377;過程如圖1所示#65377;

子串后半部分采用多點(diǎn)交叉，使用戶能夠選擇交叉點(diǎn)的數(shù)值#65377;與單點(diǎn)交叉比較，采用多點(diǎn)交叉的優(yōu)點(diǎn)在于:它支持搜索空間的探測，而不是對搜索過程中最早適合個(gè)體的支持，因此能使搜尋具有很好的魯棒性#65377;

圖2顯示基于工件順序交叉的例子是如何逐步執(zhí)行這些操作的#65377;

當(dāng)交叉操作的后代適應(yīng)性不再進(jìn)化，達(dá)到最優(yōu)時(shí)，就需要對編碼串進(jìn)行變異運(yùn)算#65377;變異運(yùn)算將個(gè)體染色體編碼串中基因座的某些基因值用該基因座的其他位來替換，形成新個(gè)體#65377;其目的是探索新的環(huán)境或者從再生控制器中追回?fù)p失的基因結(jié)構(gòu)，通過隨機(jī)改變基因位使發(fā)現(xiàn)的新基因結(jié)構(gòu)完成最優(yōu)化#65377;

變異運(yùn)算有位置變異和順序變異#65377;位置變異是將兩個(gè)基因位隨機(jī)交換;順序變異是將一個(gè)隨機(jī)選擇的基因挪到另一個(gè)隨機(jī)選擇基因的前面#65377;如圖3#65380;圖4所示，每個(gè)變異操作都可能是在編碼串的前半部分或者后半部分，這取決于最優(yōu)化搜尋如何進(jìn)行#65377;

3. 4替換

種群替換有整體替換和部分替換兩種策略，整體替換是將新種群完全覆蓋原先種群，部分替換則用新個(gè)體替換部分舊個(gè)體#65377;

3. 5遷移

遷移模型將一個(gè)大群分為若干子群，這些子群一般獨(dú)立地進(jìn)化，即它們在自身內(nèi)部進(jìn)行各種遺傳操作，只是經(jīng)過一定的代數(shù)才在子群體間交流一些信息#65377;遷移個(gè)體的數(shù)量(遷移比率)#65380;遷移個(gè)體的選擇方法和遷移采用的方案決定了在子群中產(chǎn)生差異個(gè)體的多少，以及在各子群之間的信息交換的多少#65377;

運(yùn)行表明，與單群體遺傳算法相比，遷移模型的并行多代不僅縮短了計(jì)算時(shí)間，而且需要更少的目標(biāo)函數(shù)運(yùn)算量，更容易找到全局最優(yōu)#65377;

如圖5所示，本文的遷移個(gè)體的選擇基于它們的適應(yīng)度和所有子群之間個(gè)體發(fā)生遷移的結(jié)構(gòu)( 無限制的遷移拓?fù)?#65377;

3. 6終止條件

交叉#65380;變異和替換過程不斷重復(fù)，直到滿足終止標(biāo)準(zhǔn)#65377;最簡單的標(biāo)準(zhǔn)是達(dá)到預(yù)定的最大值，如果被計(jì)算的值低于某一臨界值，GA將被終止#65377;

4 仿真與結(jié)果分析

在一個(gè)動態(tài)的框架內(nèi)，任何一個(gè)新工件進(jìn)入系統(tǒng)，都會是一個(gè)靜態(tài)的問題#65377;在這一時(shí)刻，假設(shè)每個(gè)操作之間都有連續(xù)的先后順序，每次操作所需要的機(jī)器和操作處理時(shí)間是確定的#65380;可知的，不容許在任何機(jī)器上搶先奪取操作#65377;假設(shè)一個(gè)工作站配置了4臺機(jī)器(A，B，C，D)，在給定的時(shí)間點(diǎn)上，工作站中有8個(gè)期限一樣的工件(如表1所示)正在等待處理#65377;

可以看到工件4的預(yù)定時(shí)間是29個(gè)小時(shí)，并且它首先要在機(jī)器C上處理6小時(shí)，機(jī)器B上處理4小時(shí)，機(jī)器A上處理3小時(shí)，最后在機(jī)器D上處理4小時(shí)#65377;采用MATLAB工具，在P4 256MB計(jì)算機(jī)上幾分鐘就實(shí)現(xiàn)了收斂#65377;仿真過程及參數(shù)分別如圖6，圖7，圖8及表2所示#65377;得出的最優(yōu)解決方案如下:

基于該遺傳算法的最優(yōu)調(diào)度方案如圖9所示#65377;

為證明該算法的優(yōu)越性，在調(diào)度要求相似的條件下用該算法與傳統(tǒng)優(yōu)先調(diào)度規(guī)則進(jìn)行的結(jié)果比較，結(jié)果如圖10所示#65377;

圖中，

EDD(earliest due date)表示選擇交貨期最早工作;

SPT(shortest processing time)表示選擇加工時(shí)間最短操作;

FCFS(first come first served)表示選擇同臺機(jī)器上工件隊(duì)列中最先的操作;

LSF(least slack first)表示選擇總剩余操作數(shù)最少的工件;

LWR(least work remaining)表示選擇總剩余加工時(shí)間最長的工件#65377;

顯然，本文提出的遺傳算法在處理動態(tài)調(diào)度要求過程中顯示出更高的可靠性，因此該算法在性能標(biāo)準(zhǔn)上勝過常用的優(yōu)先調(diào)度規(guī)則，從而證明了本算法的優(yōu)越性和實(shí)用性#65377;

5 結(jié)束語

本文提出遺傳算法可以滿足生產(chǎn)調(diào)度的動態(tài)性要求#65377;模擬和比較結(jié)果都證明:該算法具有實(shí)用性和有效性，為生產(chǎn)應(yīng)用提供一個(gè)強(qiáng)有力的輔助工具，不需要做過多的改變就能滿足其他類似調(diào)度應(yīng)用#65377;與指派規(guī)則相比，該遺傳算法對job-shop問題大有改進(jìn);同簡單GA相比，縮短了計(jì)算時(shí)間，減少目標(biāo)函數(shù)運(yùn)算量#65377;

主要參考文獻(xiàn)

[1] 董朝陽，孫樹棟，張波. 免疫遺傳算法求解工藝規(guī)程及作業(yè)調(diào)度協(xié)同優(yōu)化[J]. 機(jī)械科學(xué)與技術(shù)，2007(6):761-766.

[2] 王凌，鄭大鐘. 基于遺傳算法的job-shop調(diào)度研究進(jìn)展[J]. 控制與決策，2001(16):641-646.

[3] 郭彤城，慕春棣. 并行遺傳算法的新進(jìn)展[J]. 系統(tǒng)工程理論與實(shí)踐，2002(2):15-23.

[4] 張群會. 工序排序問題的遺傳算法[J]. 煤礦機(jī)械，2001(5):34-35.

[5] 楊紅紅，吳智銘. 遺傳算法在job-shop調(diào)度中的應(yīng)用[J]. 系統(tǒng)工程，2000(5):49-54.