基于多種群遺傳算法的路徑柔性車間調(diào)度問題*

李運霞，杜 娟，孫王路

(太原科技大學(xué) 機(jī)電學(xué)院，太原 030024)

0 引言

路徑柔性的車間調(diào)度問題作為傳統(tǒng)作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem，JSP)的擴(kuò)展，具有靈活性、復(fù)雜性、約束性、非線性、多極小性等特點。路徑柔性車間調(diào)度作為工藝柔性的一個分支，在現(xiàn)代制造業(yè)中具有重要的應(yīng)用價值和理論意義，是亟需解決的一類調(diào)度問題。

路徑柔性的作業(yè)車間調(diào)度問題減少機(jī)器約束，增加工序可選機(jī)器的不確定性，是復(fù)雜的強(qiáng)NP 難題。目前，國內(nèi)外對此問題進(jìn)行了多方面的研究，并取得了一定成果。邵斌彬等［1］提出柔性車間的基于綜合分派規(guī)則的快速啟發(fā)式調(diào)度算法;賀仁杰等［2］提出用知識型協(xié)同演化方法求解柔性車間作業(yè)調(diào)度問題，優(yōu)化性能良好;王萬良等［3］針對局部收斂問題將粒子群法進(jìn)行改進(jìn)，求解柔性車間作業(yè)調(diào)度問題;Seyed Habib A.Rahmati［4］針對柔性作業(yè)車間調(diào)度，提出生物地理優(yōu)化算法(BBO);遺傳算法［5-7］在柔性車間調(diào)度中也取得了一定成果。針對路徑柔性的作業(yè)車間調(diào)度特點以及上述算法的局限性，本文提出一種多種群遺傳算法(Multiple Population Genetic Algorithm，MPGA)，采用整數(shù)編碼和自適應(yīng)遺傳算子，對各種群間進(jìn)行協(xié)同優(yōu)化，得到最優(yōu)解。通過文獻(xiàn)實例和實際應(yīng)用驗證算法的有效性。

1 路徑柔性車間調(diào)度模型

假設(shè)有n個工件分配至m臺設(shè)備上加工，每個工件i(i =1，…，n)有pi道工序{pi1，pi2，…pini}，工序pik的機(jī)器選擇集為mik(mik?m)。pik在mj(mj?mjk)上的加工時間為Tikj，Tsikj為工序pik在mj開始時間，Te ikj為工序pik在mj的完工時間。工件i最后一道工序的完成時間Ci。Ci通常指工件的最短完工時間為性能指標(biāo)，即:

模型需滿足條件如下:①每個工件包含多個工序且工序按事先確定順序加工;②一臺機(jī)器同一時刻僅能加工一個工件;③一個工序一旦開始加工不得中斷;④所有工件具有相同的加工優(yōu)先級。

2 多種群遺傳算法的設(shè)計

多種群遺傳算法(MPGA)以標(biāo)準(zhǔn)遺傳算法(Standard Genetic Algorithm ，SGA)為基礎(chǔ)，通過對多個種群賦予不同的控制參數(shù)及移民算子［8］對種群間的協(xié)同進(jìn)化，普通種群之間相互引入最優(yōu)個體，最終構(gòu)成精華種群。文中采用自適應(yīng)交叉、變異概率，保證各種群得到實時有效的控制參數(shù)。

2.1 遺傳基因編碼

合適的編碼是遺傳算法的首要和關(guān)鍵問題，且編碼需滿足健全性、完備性和非冗余性三準(zhǔn)則。路徑柔性的JSP 問題比一般的JSP 問題復(fù)雜，常用兩層編碼［6］、基于工序的編碼和機(jī)器的編碼［7］等方式編碼。本文采用整數(shù)編碼方式，前半部分為工件加工順序，后半部分為工序相應(yīng)的加工機(jī)器序號。例如:

即工件加工順序:工件3 的第一道工序→工件1的第一道工序→工件2 的第一道工序→工件1 的第二道工序→工件3 的第二道工序→工件2 的第二道工序。

對應(yīng)的加工機(jī)器順序:機(jī)器1→機(jī)器2→機(jī)器2→機(jī)器1→機(jī)器2→機(jī)器1。

2.2 選擇算子(Genetic Operator)

選擇算子通常采用輪盤賭法，該方法需對目標(biāo)值與適應(yīng)度值進(jìn)行轉(zhuǎn)換，但轉(zhuǎn)換參數(shù)選取對優(yōu)化結(jié)果有較大的影響。本文采用錦標(biāo)賽法［9］，即隨機(jī)選擇三個個體，將最優(yōu)的個體放入交叉池，其他個體返回種群重新參與選擇。其目標(biāo)值即適應(yīng)度值，不必轉(zhuǎn)換，以避免控制參數(shù)對結(jié)果的影響。

2.3 交叉算子(Crossover Operator)

交叉運算作是產(chǎn)生新個體的主要方法，提高全局搜索能力。對染色體的加工順序部分進(jìn)行單點順序交叉，將交叉后工件多余的工序替換為其他工件的缺失工序;加工機(jī)器部分按交叉前個體所用的機(jī)器進(jìn)行相應(yīng)調(diào)整以保證其子代染色體的合法性。文中使用自適應(yīng)交叉算子，其交叉概率PX為:

其中f為當(dāng)前個體適應(yīng)度值，favg為當(dāng)前代個體平均適應(yīng)度值，fmax為當(dāng)前代個體最大值。

2.4 變異算子(Mutation Operator)

變異操作改善SGA 局部搜索能力，維持種群多樣性。本文采用互換方式，對染色體中加工順序部分隨機(jī)選擇兩個變異位置，然后將兩位置互換，同時加工機(jī)器號也隨之對換。對換位置的加工機(jī)器號可由工序的機(jī)器集中隨機(jī)選擇與當(dāng)前值不同的機(jī)器號代替。文中變異概率PM為:

2.5 算法流程圖

圖1 多種群算法的流程圖

MPGA 算法是通過多個種群對解空間同時進(jìn)行協(xié)調(diào)搜索，同時使用自適應(yīng)交叉算子和變異算子對控制參數(shù)實時調(diào)整，以保證算法的局部和全局搜索，提高解的優(yōu)化質(zhì)量。本文以最大遺傳代數(shù)為終止條件。其算法流程圖如圖1 所示。

3 仿真實例與應(yīng)用

3.1 仿真實例

為驗證該算法的性能，本文用Matlab7.9(2009b)軟件編程，借用文獻(xiàn)［1］、文獻(xiàn)［3］及文獻(xiàn)［10］實例進(jìn)行多次實驗對比分析。

文獻(xiàn)［1］有6 個工件，每個工件6 道工序，在10 臺機(jī)器上加工，即6 ×6 ×10 調(diào)度問題，其甘特圖別如圖2 所示:

圖2 6 ×6 ×10 調(diào)度甘特圖

文獻(xiàn)［10］有5 個工件，每個工件4 道工序，在6 臺機(jī)器上加工，即5 ×4 ×6 調(diào)度問題，其機(jī)器甘特圖如圖3 所示。

圖3 5 ×4 ×6 調(diào)度問題

利用MPGA 算法分別對文獻(xiàn)［1］、文獻(xiàn)［3］和文獻(xiàn)［10］的案例進(jìn)行仿真，算法運行30 次時的最優(yōu)解、最差解及平均解如表1 所示。

表1 算法的比較結(jié)果

表1 可見，MPGA 算法明顯優(yōu)于文獻(xiàn)［1］和文獻(xiàn)［10］的算法，且與文獻(xiàn)［3］取得相同的最優(yōu)值。故MPGA 算法具有良好的可行性。

3.2 實例應(yīng)用

某作業(yè)車間可以加工車、銑、刨、磨等，同時存在多個并行機(jī)和加工中心，屬于柔性作業(yè)車間的范疇。現(xiàn)考慮一個10 臺機(jī)床，6 個件且每個工件均為6 道工序的實際問題。工序可選擇的機(jī)器如表2 所示，工序在機(jī)器的加工時間如表3 所示。

表2 工序可選擇的機(jī)器

表3 工序在機(jī)器的加工時間表

其中，機(jī)床號1、2 車床;3、4 為銑床;5 為刨床;6為磨床;7、8 為鉆床;9 為鏜床;10 為加工中心。

規(guī)定種群規(guī)模為40，遺傳代數(shù)300。應(yīng)用MPGA算法搜索過程如圖4 所示，調(diào)度甘特圖如圖5 所示。

圖4 MPGA 算法的搜索過程

圖4 表示MPGA 算法可迅速收斂到最優(yōu)解，且均值變化比較平穩(wěn)，可靠性高。驗證了MPGA 算法優(yōu)良的尋優(yōu)能力，提高優(yōu)化效率。

圖5 MPGA 算法的調(diào)度甘特圖

圖5 表示各工件已被均勻合理的分配到可選擇的加工機(jī)器上，且同一工件前后工序的銜接比較緊湊，如工件2、3、6 各工序的等待時間均為0。MPGA 算法獲得全部工件的最短完工時間C =40 s，加工工序得到優(yōu)化，有效地解決了實際調(diào)度系統(tǒng)中的路徑柔性車間調(diào)度問題。

4 結(jié)論

針對路徑柔性的作業(yè)車間調(diào)度問題，提出MPGA算法，將其與文獻(xiàn)［1］、文獻(xiàn)［3］及文獻(xiàn)［10］案例進(jìn)行仿真實驗和對比，該算法避免了早熟收斂，提高優(yōu)化效率，證實了該算法具有良好的可行性;仿真實例的實際應(yīng)用，進(jìn)一步證實了該算法的有效性和實用性。因此，MPGA 是路徑柔性作業(yè)車間調(diào)度問題的可行、高效的算法，適合于復(fù)雜問題的求解優(yōu)化，值得推廣。

［1］邵斌彬，蔡鴻明，姜麗紅. 一種柔性車間快速啟發(fā)式調(diào)度算法［J］. 計算機(jī)應(yīng)用與軟件，2009，26(3):32 -34.

［2］賀仁杰，陳宇寧，姚鋒，等. 求解柔性車間作業(yè)調(diào)度的知識型協(xié)同演化方法［J］. 計算機(jī)集成制造系統(tǒng)，2011，17(2):310 -315.

［3］王萬良，趙澄，熊婧，等. 基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題的求解方法［J］. 系統(tǒng)仿真學(xué)報，2008，20(16):4326 -4329.

［4］Seyed Habib A. Rahmati，M. Zandieh.A new biogeographybased optimization (BBO)algorithm for the flexible job shop scheduling problem［J］. Int J Adv Manuf Technol，2012，58:1115 -1129.

［5］F. Pezzella，G. Morganti，G. Ciaschetti. A Genetic Algorithm for the Flexible Job-shop Scheduling Problem［J］. Computers＆ Operations Research，2008，35:3202 -3212.

［6］余琦瑋，趙亮，潘雙夏. 基于遺傳算法的柔性作業(yè)車間調(diào)度優(yōu)化［J］. 組合機(jī)床與自動化加工技術(shù)，2004(4):32 -34.

［7］張超勇，饒運清，李培根，等. 柔性作業(yè)車間調(diào)度問題的兩級遺傳算法［J］. 機(jī)械工程學(xué)報，2007，43(4):119 -124.

［8］葉在福，單淵達(dá). 基于多種群遺傳算法的輸電系統(tǒng)擴(kuò)展規(guī)劃［J］. 電力系統(tǒng)自動化，2000，24(5):24 -27.

［9］張國輝，高亮，李培根，等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題［J］. 機(jī)械工程學(xué)報，2009，45(7):145-151.

［10］柳毅，馬慧民，葉春明. 免疫遺傳算法在柔性Job shop調(diào)度問題中的應(yīng)用［J］. 上海理工大學(xué)學(xué)報，2005，27(5):393 -396.