一種求解作業(yè)車間調(diào)度問題的異步元胞遺傳算法*

陸曈曈，胡方軍，張 屹

(三峽大學a.經(jīng)濟與管理學院;b.水電機械設(shè)備設(shè)計與維護湖北省重點實驗室，湖北 宜昌 443002)

0 引言

作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem，JSP)是一類在一定的任務(wù)配置和約束要求前提下，合理安排生產(chǎn)資源和加工順序的問題。JSP 屬于典型的NP-hard 問題，也是最困難的組合優(yōu)化問題之一［1］，一直是國內(nèi)外學者研究的熱點與難點之一。為企業(yè)生產(chǎn)過程制定合理的調(diào)度計劃，能有效提高企業(yè)的資源利用率和生產(chǎn)效率，提高經(jīng)濟效益。因此，找到一種快速、高效地求解JSP 的算法，不僅具有重要的理論研究價值，而且能帶來巨大的經(jīng)濟效益。

近些年來，學者們對于求解JSP 的算法研究已取得不少研究成果，如運用模糊邏輯、模擬退火、神經(jīng)網(wǎng)絡(luò)、免疫算法、禁忌搜索和遺傳算法等智能優(yōu)化算法，為求解JSP 問題提供了一些可行的方法［2］。在遺傳算法求解JSP 問題方面，Davis L［3］最早將遺傳算法應(yīng)用于JSP 問題的求解。張長水等［4］提出一種改進的遺傳算法并應(yīng)用于JSP 問題求解。劉民等［5］提出運用遺傳算法求解并行多機調(diào)度問題。王萬良等［2］提出一種雙倍體遺傳算法，并應(yīng)用于作業(yè)車間調(diào)度問題求解。蔡良偉等［6］提出一種多種群遺傳算法用于解決作業(yè)車間調(diào)度問題。張守勝［7］對交叉和變異算子作了改進，提出了一種求解JSP 問題的改進遺傳算法。張超勇［8］等提出一種新的調(diào)度類型，并采用改進的遺傳算法求解作業(yè)車間調(diào)度問題。研究表明，傳統(tǒng)遺傳算法具有較強全局搜索能力，在求解規(guī)模較大的JSP 時往往容易陷入局部收斂而不能得到最優(yōu)解。元胞遺傳算法(Cellular Genetic Algorithm，cGA)是將遺傳算法與元胞自動機理論結(jié)合提出的一種新算法，自提出以來，不斷受到國內(nèi)外學者的關(guān)注，并相繼出現(xiàn)了很多研究成果。近些年來，元胞遺傳算法已成功地應(yīng)用于非常復(fù)雜的組合優(yōu)化問題，如VRP 與SAT 問題［9］，成為解決這些問題的新方法。元胞遺傳算法還應(yīng)用于其他如邏輯、信息、調(diào)度問題［10］等領(lǐng)域?；诖?，本文提出了一種異步元胞遺傳算法(asynchronous Cellular Genetic Algorithm，acGA)，建立作業(yè)車間調(diào)度模型，針對JSP設(shè)計合理的編碼解碼方案和交叉變異算子，將該算法、同步元胞遺傳算法(scGA)以及傳統(tǒng)遺傳算法(sGA)應(yīng)用于作業(yè)車間調(diào)度問題實例求解，將算法優(yōu)化結(jié)果進行比較驗證本文提出的異步元胞遺傳算法求解JSP的有效性。

1 作業(yè)車間調(diào)度問題描述

JSP 可描述為:n個工件要在m臺加工機器上加工，設(shè)J ={J1，J2，…，Jn}和M ={M1，M2，…，Mm}分別表示由n個工件和m臺加工機器組成的集合。工件集合J中的工件Ji(1 ≤i≤n)在各機器上按照其預(yù)先確定的工序順序Oi ={Oi1，Oi2，…，Oip}(p表示工件Ji的工序數(shù))進行加工，各工件之間無先后順序。約束要求:同一機器在同一時刻最多只能加工一個零件的一道工序;某個工件同時只能被一臺機器加工。且假設(shè)機器不發(fā)生故障，若以tijk和Cijk分別表示工件Ji的第j(1 ≤j≤p)道工序在機器Mk(1 ≤k≤m)上的加工時間和完成加工時間，以Cmax表示最后一個工件在最后一臺機器上完成加工的時間。優(yōu)化目標是在滿足各項約束的條件下，進行合理調(diào)度，確定各工件在各臺機器上的開工時間stijk，使得最大完工時間Cmax最小。JSP 數(shù)學模型如下:

2 異步元胞遺傳算法

元胞遺傳算法(cGA)將種群個體分布在一個環(huán)形聯(lián)通的網(wǎng)狀空間拓撲結(jié)構(gòu)中，種群個體的遺傳操作僅限制在與其相鄰的個體(鄰居)之間進行。cGA 不僅繼承了傳統(tǒng)遺傳算法全局搜索能力強的優(yōu)勢，而且結(jié)合元胞自動機的優(yōu)點，使局部尋優(yōu)能力得到增強，且易于并行化，算法收斂速度加快，搜索能力得到提高。

2.1 種群空間結(jié)構(gòu)和個體鄰居

在元胞遺傳算法中，種群中的個體通常分布于二維網(wǎng)狀結(jié)構(gòu)中，在這種網(wǎng)狀結(jié)構(gòu)中同行或同列的邊界個體進行首尾相連，如圖1 所示。在元胞模型中，在網(wǎng)格中的每個個體擁有一個鄰居結(jié)構(gòu)，且與其鄰近個體的鄰居相互重疊，種群中所有個體的鄰居結(jié)構(gòu)有相同的尺寸和形狀。如圖2 為元胞遺傳算法中六種常用的鄰居結(jié)構(gòu)形狀，其定義如下:Ln(線型)表示個體的鄰居是由其在東、南、西、北方向的n個最近的個體組成;而Cn(緊湊型)通常指個體的鄰居由其在水平、垂直和對角線方向的n -1 個鄰近個體組成。在這六種結(jié)構(gòu)中，最常用的兩種鄰居結(jié)構(gòu)為:①L5 型，也稱為馮·諾依曼(Von Neumann)型或NEWS 鄰居結(jié)構(gòu);②C9型，也稱為Moore 型［11］。本文提出的acGA 就是采用Moore 型鄰居結(jié)構(gòu)。

圖1 種群空間結(jié)構(gòu)

圖2 典型元胞鄰居結(jié)構(gòu)

2.2 異步元胞遺傳算法過程

本文所提出的acGA 在傳統(tǒng)元胞遺傳算法的基礎(chǔ)上引入異步更新策略，即在算法迭代過程中，以一個特定的順序逐個產(chǎn)生并更新子代個體，本文采用的的異步更新策略是固定線性掃描方法［12］:以逐行逐個個體掃描的方式相繼地更新元胞個體。其種群個體更新過程如圖3 所示。

圖3 acGA 的個體更新示意圖

為了更詳細描述算法過程，下面給出異步元胞遺傳算法偽代碼，如下表1 所示:

表1 acGA 偽代碼

2.3 編碼與解碼

編碼表示個體的遺傳基因，合理的編碼方式是實現(xiàn)高效率遺傳操作的前提，也是算法成功應(yīng)用于實際問題關(guān)鍵之一。本文對JSP 問題采用基于工序的編碼方式，對于n個工件在m臺機器上加工的調(diào)度問題，其染色體由n × m個基因組成，是所有工件工序的一個排列，每個工件的工序都用其工件號表示。

本文采用基于工序的解碼方式，該方法具有在置換染色體總能得到可行調(diào)度方案、避免死鎖的優(yōu)點。對于n個工件在m臺機器上加工的調(diào)度問題的編碼，每個工件號在染色體中出現(xiàn)m次，染色體中出現(xiàn)第k次(k≤m)的工件號表示該工件的第k道工序。以下表2 中的3 個工件在3 臺機器上加工的JSP 調(diào)度問題為例:

表2 一個3 個工件3 臺機器的JSP 實例

圖4 基于工序編碼的解碼方式

如圖4 所示，若表2 實例中的一條染色體為［2 3 1 3 1 1 2 2 3］，染色體中1，2，3 分別表示工件J1、J2、J3。染色體中的3 個1 從前到后依次為工件J1的工序1、工序2、工序3，同理可得染色體中的2 和3 意義。該染色體對應(yīng)的機器序列為［3 2 1 3 2 3 1 2 1］，對應(yīng)的加工時間序列為［2 2 3 2 2 3 3 4 3］。按照該解碼方式將染色體上的工件工序依次安排在對應(yīng)的機器上，即為該染色體對應(yīng)的調(diào)度方案。

2.4 遺傳操作

2.4.1 選擇操作

選擇操作的作用是根據(jù)一定規(guī)則從種群中選擇進行遺傳操作的父代個體，合理的選擇操作能有效提高算法收斂的效率。針對JSP 問題，本文算法采用二元錦標制選擇算子。

2.4.2 交叉操作

交叉操作是遺傳算法中獲得子代個體的重要遺傳操作，它決定了算法的性能的優(yōu)劣。對于JSP 問題，在進行交叉算子設(shè)計時需考慮到交叉所得個體的合法性。設(shè)兩個父代個體染色體分別為P1、P2，交叉后產(chǎn)生的子代個體染色體分別為S1、S2，本文設(shè)計的交叉算子具體步驟如下:

步驟1:隨機產(chǎn)生兩個不相同的隨機數(shù)n1、n2(n1、n2小于染色體長度，不妨設(shè)n1＜n2);

步驟2:初步交叉。將父代個體P1中第n1到第n2位的基因復(fù)制到子代S‘1對應(yīng)位置，將父代個體P2中第n1到第n2為的基因復(fù)制到子代S’2的對應(yīng)位置;

步驟3:調(diào)整。將P1中其它位上的基因按其在P1中的順序依次插入S’2中的剩余位置，然后從左至右檢查如果某基因出現(xiàn)次數(shù)多于合法數(shù)目，則按其先后順序刪掉除了第n1到第n2位的基因之外多余數(shù)目的該基因;若某基因出現(xiàn)次數(shù)少于合法數(shù)目，則按順序在刪除多余基因的位置插入短缺數(shù)目的該基因。以此種方式進行調(diào)整直到子代染色體中所有基因數(shù)目合法化，得到可行的子代S2;同理可得可行的子代S1。

以表2 中的3 個工件在3 臺機器上加工的JSP 調(diào)度問題的某兩條染色體為例，其交叉過程如圖5 所示。

圖5 交叉操作

如圖5 所示的交叉操作過程，對于父代個體染色體P1、P2，隨機選擇的交叉基因位n1、n2為3、6，經(jīng)過交叉后，得到的子代染色體體中存在有基因數(shù)目不合法情況，因此需要調(diào)整。對于S‘1，基因1 的數(shù)目多出2 個，基因2 的數(shù)目少了2 個，故將S‘1中除了第3 到第6 位基因之外的多余基因1 按順序刪掉2 個，即刪除位于第7 和第9 位上的基因1，再在第7 和第9 位上分別插入基因2，得到合法染色體S1;同理可得合法染色體S2?？梢钥闯?，經(jīng)過交叉后，子代S1、S2分別保留了P1、P2第3 到第6 位的基因及其順序，既保留了父代的優(yōu)良特征，又得到了可行的子代個體。

2.4.3 變異操作

變異操作在遺傳算法中用于對染色體進行較小變動以獲得新的個體，能增強種群多樣性，有效防止算法陷入局部收斂。針對JSP 問題，本文采用交換變異算子。以表2 中的JSP 調(diào)度問題的某條染色體為例，其變異過程如下圖6 所示:

圖6 交換變異操作

如圖6 所示變異過程，染色體P經(jīng)過交換變異操作，第2 和第5 位上的染色體進行互換，得到新的染色體O。

3 實例計算及結(jié)果分析

為驗證提出的異步元胞遺傳算法(acGA)求解作業(yè)車間調(diào)度問題的性能，以最快完工時間最少為優(yōu)化目標，采用acGA、一種采用同步更新策略的傳統(tǒng)元胞遺傳算法(scGA)、以及傳統(tǒng)遺傳算法(sGA)對JSP 問題的兩個標準測試實例FT06(6 個工件6 臺機器)和LA01(10 個工件5 臺機器)進行求解，并進行結(jié)果對比。算法的參數(shù)設(shè)置:初始種群大小設(shè)為100;交叉概率為Pc =0.9 ;變異概率為Pm =0.2 ;算法在FT06 問題上迭代代數(shù)為100 代，在LA01 問題上為500 代。FT06 和LA01 兩個JSP 實例的已知最優(yōu)解分別為55和666。acGA 和sGA 在兩個實例上運行的收斂曲線如下圖7、圖8 所示。

圖7 acGA 和sGA 的收斂曲線(FT06)

圖8 acGA 和sGA 的收斂曲線(LA01)

由圖7、圖8 可以看出，在相同的條件參數(shù)下，ac-GA、scGA 與sGA 最終都能收斂到最優(yōu)解，但acGA 與scGA 兩種元胞遺傳算法與sGA 相比具有明顯的優(yōu)勢，搜索效率更高，能夠更快地收斂到最優(yōu)解，特別是當算法運行到接近最優(yōu)解時，acGA 和scGA 比sGA 更快地搜索到最優(yōu)解，sGA 則容易陷入局部最優(yōu)而不容易得到最優(yōu)解，說明采用元胞結(jié)構(gòu)的遺傳算法局部搜索能力更強。而acGA 與scGA 相比，acGA 能更快收斂到最優(yōu)解，說明本文采取的異步更新策略提高了算法的搜索效率，使得算法的全局和局部搜索能力增強。并且對于規(guī)模更大的LA01 實例，acGA 的搜索效率與收斂效果的優(yōu)勢更明顯。對于FT06 和LA01 兩個實例，acGA 計算所得到的調(diào)度方案的甘特圖如圖9、圖10 所示:

圖9 FT06 實例甘特圖

圖10 LA01 實例甘特圖

為了進一步驗證所提出的acGA 求解JSP 問題的穩(wěn)定性以及計算精度，在相同的硬件條件下分別采用acGA、scGA 和sGA 分別對FT06 和LA01 兩個JSP 實例獨立計算10 次，每次運行均采用上述同樣的參數(shù)設(shè)置。對計算結(jié)果進行統(tǒng)計分析，對比結(jié)果如表3 所示。

表3 計算結(jié)果對比

從表3 可看出，對于FT06 和LA01 兩個JSP 實例，acGA、scGA 和sGA 均能搜索到最優(yōu)解。在10 次獨立計算中，對于FT06 實例，sGA 得到最優(yōu)解得次數(shù)為7次，少于scGA 的8 次和acGA 的10 次;sGA 和scGA得到的最差解為58，acGA 最差解55;sGA 的10 次計算平均解為55.7，scGA 的平均解55.5，而acGA 每次都收斂到最優(yōu)解55，平均解為55。對于LA01 實例，sGA 的最優(yōu)解得次數(shù)僅為5 次，scGA 的最優(yōu)解次數(shù)為7 次，acGA 達到最優(yōu)解次數(shù)最多，為9 次;sGA 得到的最差解為690，scGA 得到最差解為696，而acGA 最差解667;sGA 的10 次計算平均解為673.2，scGA 的平均解為671.5，都差于acGA 的平均解666.1。可看出，在求解JSP 問題時，本文提出的acGA 比scGA 和sGA 具有更強的搜索能力和更高的搜索效率，算法的收斂精度更高，算法穩(wěn)定性更好，acGA 在求解JSP 問題時具有明顯的優(yōu)勢。

4 結(jié)論

元胞遺傳算法不僅能繼承遺傳算法的全局搜索優(yōu)勢，而且結(jié)合了元胞自動機的優(yōu)點，提高了算法的局部搜索能力，能有效避免遺傳算法陷入局部收斂。本文提出的異步元胞遺傳算法(acGA)引入了一種異步更新策略，針對JSP 問題設(shè)計了適合JSP 問題的交叉算子，并采用二元錦標賽選擇算子和交換變異算子，進一步避免了算法陷入早熟收斂，提高了算法的搜索能力和收斂效率。分別采用acGA、scGA 和sGA 對JSP 問題的兩個標準測試實例FT06 和LA01 進行求解，結(jié)果對比表明在求解JSP 問題時，acGA 比scGA、sGA 的搜索效率更高，收斂速度更快，算法的穩(wěn)定性也更好，表明acGA 是一種能快速、高效地求解JSP 問題的算法。

［1］張國輝，高亮，李培根.基于遺傳規(guī)劃的作業(yè)車間調(diào)度算法研究［J］.控制與決策，2008，23(8):924 -928.

［2］王萬良，宋毅，吳啟迪.求解作業(yè)車間調(diào)度問題的雙倍體遺傳算法與軟件實現(xiàn)［J］.計算機集成制造系統(tǒng)，2004，10(1):65 -69.

［3］Davis L. Job-shop Scheduling with genetic algorithms［C］.

Proc. of International Conference on Genetic Algorithms and Their Applications，1985，136 -149.

［4］張長水，沈剛，閻平凡. 解Job-shop 調(diào)度問題的遺傳算法［J］.電子學報，1995，23(7):1 -5.

［5］劉民，吳澄，蔣新松.用遺傳算法解決并行多機調(diào)度問題［J］.系統(tǒng)工程理論與實踐，1998，18(1)1:14 -17.

［6］蔡良偉，張基宏，李霞.作業(yè)車間調(diào)度的多種群遺傳算法［J］.電子學報.2005，33(6):991 -994.

［7］張守勝.求解作業(yè)車間調(diào)度問題的改進的遺傳算法［J］.計算機與現(xiàn)代化.2007，32(11):32 -35.

［8］張超勇，管在林，劉瓊，等.一種新調(diào)度類型及其在作業(yè)車間調(diào)度中的應(yīng)用［J］.機械工程學報，2008，44(10):24 -31.

［9］E. Alba，B. Dorronsoro，and H. Alfonso. Advanced models of cellular genetic algorithms evaluated on SAT，in Genetic and Evolutionary Computation Conference (GECCO)，Washington，D.C. USA，2005(6):1123 -1130.

［10］E. Alba，B. Dorronsoro，F(xiàn). Luna，et al.A cellular multiobjective genetic algorithm for optimal broadcasting strategy in metropolitan manets［J］. Computer Communications，2006.

［11］SARMA J.，JONG K. DE. An analysis of the effects of neighbourhood size and shape on local selection algorithms［C］. Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN IV)，1996:236 -224.

［12］SCH NFISCH BIRGITT，DE ROOS ANDR Synchronous and asynchronous updating in cellular automata［J］. BioSystems，1999，51(3):123.