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

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

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

1 引 言

生產(chǎn)調(diào)度是對企業(yè)生產(chǎn)作業(yè)過程進行計劃#65380;安排以及組織執(zhí)行，有效的調(diào)度方法和優(yōu)化技術(shù)是實現(xià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)度問題研究具有重要的理論意義和工程價值#65377;

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

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

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

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

3 并行多代遺傳算法

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

3. 1初始化

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

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

3. 3交叉和變異

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

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

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

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

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

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

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

3. 4替換

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

3. 5遷移

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

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

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

3. 6終止條件

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

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

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

可以看到工件4的預(yù)定時間是29個小時，并且它首先要在機器C上處理6小時，機器B上處理4小時，機器A上處理3小時，最后在機器D上處理4小時#65377;采用MATLAB工具，在P4 256MB計算機上幾分鐘就實現(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ī)則進行的結(jié)果比較，結(jié)果如圖10所示#65377;

圖中，

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

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

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

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

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

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

5 結(jié)束語

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

主要參考文獻

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

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

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

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

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