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

李運霞，杜 娟，孫王路

(太原科技大學 機電學院，太原 030024)

0 引言

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

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

1 路徑柔性車間調度模型

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

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

2 多種群遺傳算法的設計

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

2.1 遺傳基因編碼

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

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

對應的加工機器順序:機器1→機器2→機器2→機器1→機器2→機器1。

2.2 選擇算子(Genetic Operator)

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

2.3 交叉算子(Crossover Operator)

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

其中f為當前個體適應度值，favg為當前代個體平均適應度值，fmax為當前代個體最大值。

2.4 變異算子(Mutation Operator)

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

2.5 算法流程圖

圖1 多種群算法的流程圖

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

3 仿真實例與應用

3.1 仿真實例

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

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

圖2 6 ×6 ×10 調度甘特圖

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

圖3 5 ×4 ×6 調度問題

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

表1 算法的比較結果

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

3.2 實例應用

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

表2 工序可選擇的機器

表3 工序在機器的加工時間表

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

規定種群規模為40，遺傳代數300。應用MPGA算法搜索過程如圖4 所示，調度甘特圖如圖5 所示。

圖4 MPGA 算法的搜索過程

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

圖5 MPGA 算法的調度甘特圖

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

4 結論

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

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

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

［3］王萬良，趙澄，熊婧，等. 基于改進蟻群算法的柔性作業車間調度問題的求解方法［J］. 系統仿真學報，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］余琦瑋，趙亮，潘雙夏. 基于遺傳算法的柔性作業車間調度優化［J］. 組合機床與自動化加工技術，2004(4):32 -34.

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

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

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

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