陸曈曈，胡方軍，張 屹

(三峽大學(xué)a.經(jīng)濟(jì)與管理學(xué)院;b.水電機(jī)械設(shè)備設(shè)計(jì)與維護(hù)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 宜昌 443002)

0 引言

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

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

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

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

2 異步元胞遺傳算法

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

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

在元胞遺傳算法中，種群中的個(gè)體通常分布于二維網(wǎng)狀結(jié)構(gòu)中，在這種網(wǎng)狀結(jié)構(gòu)中同行或同列的邊界個(gè)體進(jìn)行首尾相連，如圖1 所示。在元胞模型中，在網(wǎng)格中的每個(gè)個(gè)體擁有一個(gè)鄰居結(jié)構(gòu)，且與其鄰近個(gè)體的鄰居相互重疊，種群中所有個(gè)體的鄰居結(jié)構(gòu)有相同的尺寸和形狀。如圖2 為元胞遺傳算法中六種常用的鄰居結(jié)構(gòu)形狀，其定義如下:Ln(線型)表示個(gè)體的鄰居是由其在東、南、西、北方向的n個(gè)最近的個(gè)體組成;而Cn(緊湊型)通常指?jìng)€(gè)體的鄰居由其在水平、垂直和對(duì)角線方向的n -1 個(gè)鄰近個(gè)體組成。在這六種結(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ǔ)上引入異步更新策略，即在算法迭代過程中，以一個(gè)特定的順序逐個(gè)產(chǎn)生并更新子代個(gè)體，本文采用的的異步更新策略是固定線性掃描方法［12］:以逐行逐個(gè)個(gè)體掃描的方式相繼地更新元胞個(gè)體。其種群個(gè)體更新過程如圖3 所示。

圖3 acGA 的個(gè)體更新示意圖

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

表1 acGA 偽代碼

2.3 編碼與解碼

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

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

表2 一個(gè)3 個(gè)工件3 臺(tái)機(jī)器的JSP 實(shí)例

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

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

2.4 遺傳操作

2.4.1 選擇操作

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

2.4.2 交叉操作

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

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

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

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

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

圖5 交叉操作

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

2.4.3 變異操作

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

圖6 交換變異操作

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

3 實(shí)例計(jì)算及結(jié)果分析

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

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

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

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

圖9 FT06 實(shí)例甘特圖

圖10 LA01 實(shí)例甘特圖

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

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

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

4 結(jié)論

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

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

［2］王萬良，宋毅，吳啟迪.求解作業(yè)車間調(diào)度問題的雙倍體遺傳算法與軟件實(shí)現(xiàn)［J］.計(jì)算機(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］.電子學(xué)報(bào)，1995，23(7):1 -5.

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

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

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

［8］張超勇，管在林，劉瓊，等.一種新調(diào)度類型及其在作業(yè)車間調(diào)度中的應(yīng)用［J］.機(jī)械工程學(xué)報(bào)，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.