李運(yùn)霞，杜 娟，孫王路

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

0 引言

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

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

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

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

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

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

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

2.1 遺傳基因編碼

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

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

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

2.2 選擇算子(Genetic Operator)

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

2.3 交叉算子(Crossover Operator)

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

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

2.4 變異算子(Mutation Operator)

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

2.5 算法流程圖

圖1 多種群算法的流程圖

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

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

3.1 仿真實(shí)例

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

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

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

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

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

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

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

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

3.2 實(shí)例應(yīng)用

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

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

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

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

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

圖4 MPGA 算法的搜索過(guò)程

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

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

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

4 結(jié)論

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

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

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

［3］王萬(wàn)良，趙澄，熊婧，等. 基于改進(jìn)蟻群算法的柔性作業(yè)車(chē)間調(diào)度問(wèn)題的求解方法［J］. 系統(tǒng)仿真學(xué)報(bào)，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è)車(chē)間調(diào)度優(yōu)化［J］. 組合機(jī)床與自動(dòng)化加工技術(shù)，2004(4):32 -34.

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

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

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

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