一種改進的貪心遺傳混合算法在車間調度中的應用與研究

李 辰

（大連交通大學軟件學院 116052）

0 引言

作業車間調度問題是困難的組合優化問題，它是一類滿足任務配置和順序約束要求的資源分配問題。車間作業調度作為CIMS體系結構中連接生產控制層和生產計劃的中間環節，在兩方面的發揮著重要作用：一方面接受計劃決策信息，在資源形成具體生產實施方案和時間和空間上合理配置任務，驅動整個生產系統高效運作，是計劃實現的保證；另一方面，通過統計分析，有機協調整個生產系統，接受生產過程的實際信息，并向決策層反饋計劃執行情況。目前為止，車間調度問題的研究日益深入。從靜態調度到動態調度，從最初的單機調度發展到多機調度，從確定性調度到隨機性調度等。本文提出了一種將貪心算法融入遺傳算法中的一種混合遺傳算法，以提高求解質量，通過算例分析，可以看出本文提出的混合遺傳算法有顯著優勢。

1 車間調度問題概述

車間作業調度問題是一類典型的實際生產調度問題的簡化模型,它是一個典型的NP難問題,同時也是最有名的復雜組合優化問題之一,因此對其研究具有很重要的理論意義和工程價值。目前解決車間調度問題的方法主要分為兩大類,有精確算法和近似算法兩類,精確算法主要包括拉格朗日松弛法、分支定界法、基于析取圖模型的枚舉方法等,近似算法包括優先權規則調度算法、鄰域搜索算法、瓶頸轉移啟發式算法和人工智能算法等。精確算法能夠得到全局最優解,但是只適合解決小規模調度問題,對于大規模調度問題無實際應用價值。這些年來,鄰域搜索算法相繼應用于解決車間調度問題。其中,遺傳算法由于其良好的全局搜索性能和內在的并行處理能力,越來越受到車間調度研究人員的關注,傳統的遺傳算法容易陷入局部最優收斂速度慢的狀況,本人提出一種改進的遺傳算法,對以最小工件完工時間和平均工件完工時間為目標的車間調度問題進行了研究。

2 車間調度問題的數學模型

車間調度問題 研究 n 個工件在 m 臺機器上的加工。每個工件在各個機器上的加工次序和每個工件的各個工序的加工時間為已知，要求確定與約束條件相容的各機器上所有工件的加工開始時間，完成時間和加工次序，使加工性能指標達到最優。則 n個工件m 臺機器的車間調度問題的一般性定義如下:

假設機器共有m個 (M1, M2, M3……Mm)，需要加工的工件一共有n個(N1, N2, N3……Nn)，Si表示工件Ni的工序數，工件Ni的加工工序為 Ni1m,Ni2m,Ni3m…… NiSim, 其中NiSim表示 工件Ni的第Si道工序是在第m個機器上加工，加工工時為Tij。

約束：

2.1 每個工件的每個工序的加工工時Tij為已知。

2.2 每個工件包擴一個由多道工序組成的工序集合，工件的工序順序已知。

2.3 同一臺機床僅能同一時間加工一個工件的一道工序。

2.4 不同工件的工序之間沒有約束。相同工件工序滿足先后順序約束關系。

2.5 工序之間沒有時間間隔。

2.6 各個工件的每到工序的開工時間大于或等于零，且一個工件的前一道工序加工完后才能進行下一道工序。

目標函數值為Min(Max{ C1, C2, C3,…, Cn}) Ci為工件Ni 加工時間。即第n個工件的最后一道工序的完成時間T，但是第n個工件的完工時間不一定是所有工件的最小完工時間，需要先求出每個工件每道工序在機器上的加工時間段，再從選定的加工機器依次計算每臺機器最后的工件完成時間，取其中的最大值就是目標函數值。

3 改進的貪心遺傳混合算法求解過程

3.1 編碼方式

編碼問題是設計遺傳算法的首要和關鍵問題。對遺傳算法的編碼技術必須考慮染色體的合法性、可行性、有效性以及對解空間表征的完全性，對于車間調度也是這樣。由于車間調度問題的組合特性以及

工藝約束性，染色體的 Lamarkian 特性、解碼的復雜性、編碼的空間特性和存儲量的需求是設計遺傳算法編碼通常要考慮的問題。

3.1.1 染色體的 Lamarkian 特性。該特性考慮在所設計的編碼技術下，染色體的優點是否可通過一般的遺傳操作傳到后代種群。如果后代通過遺傳操作可有效繼承父代的優點 ，則 稱所采用的編碼具有 Lamarkian 特性 ；若后代種群不能夠 從父代繼承任何有用信息，則稱所采用的編碼不具有 Lamarkian 特性；若后代所繼承的片段中只有部分與父代相同，則稱所采用的編碼具有半 Lamarkian 特性。鑒于遺傳算法的優化機制，我們希望所設計的編碼具有 Lamarkian 特性。

3.1.2 解碼的復雜性。就解碼的有效性而言，我們希望 GA搜索用的碼能夠解碼成活動調度，甚至搜索所采用的碼跟活動調度一一對應。就解碼復雜性而言，將不需要解碼的相應編碼歸為0 類復雜性；通過簡單映射關系實現解碼的相應編碼歸為 1 類復雜性；通過簡單啟發式方法才能實現解碼的相應編碼歸為 2類復雜性；只有通過復雜啟發式方法才能實現解碼的相應編碼歸為 3 類復雜性。

3.1.3 編碼的空間特性。編碼必須考慮碼的可行性、所表征空間的完全性和冗余性。就可行性而言，編碼空間通常分為兩類：僅包含可行解的空間，可包含非法解的空間。就完全性而言，有的編碼僅表征部分調度空間，而有的編碼則可表征整個調度空間，就冗余性而言，有的編碼使碼與調度一一對應，而有的則是一到多或多到一的關系，這會影響解碼和搜索的效率。

3.1.4 存儲量需求。就 n個工件 m 臺機器的 Job Shop調度問題而言，通常用碼長來反映編碼對存儲量的需求。稱 n ×m為 GA 染色體的標準長度，即操作的總數量。基于此，可將編碼分為三類：其一，碼長等于標準長度；其二，碼長大于標準長度；其三，碼長小于標準長度。

用遺傳算法求解車間調度問題，編碼形式有以下幾種：基于工序的編碼，基于操作的編碼，基于工件的編碼，基于工件對關系的編碼，基于先后表的編碼，基于設備的編碼，基于優先規則的編碼，基于完成時間的編碼，基于析取圖的編碼，隨機鍵編碼等。本文采用基于工序的編碼，這種表達法將調度編碼為工序的序列，每個基因代表一道工序。它有兩種可能的方式來命名每道工序，一種自然的方式像TSP的順序表達法是自然數來命名工序，但是因為車間調度問題是受加工路線的約束的，不是所有自然數組合都可以定義為可行的調度。另一種方式由Gen，Tsujimura和Kubot提出:給所有同一個工件的工序指定相同符號，然后再根據他們在給定染色體中的出現順序給以解釋。對于由n個工件在m臺機器上生產的問題，一個染色體包括總共n x m個基因，每個工件出現在染色體中的次數為m次，每個基因不表明一個工件的具體工序，而是指有上下依賴關系的工序。很容易看出任意的染色體的排列總能產生可行調度。在圖1中為一個3×3作業車間調度問題的編碼示例方式。

圖1 編碼示例

3.2 適應度函數

Min(Max{ C1, C2, C3,…, Cn}) Ci為工件Ni加工時間。

3.3 選擇算子

選擇是遺傳算法實現優勝劣汰的關鍵過程，為了保證當前種群中的最優解被選擇，同時不失種群的多樣性。本文采取貪心算法和適應度比例法兩種方法結合，即：通過貪心算法將局部適應度最大的個體直接選擇到下一代，再通過適應度比例法選擇出下一代種群的個體。

貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。在選擇算子中引入貪心算法，可以加快算法的收斂速度。

貪心變換方法可以看做是一種算子。在算法每一次迭代演化過程中，首先執行交叉算子和變異算子，接下來執行貪心算子，最后再執行選擇算子，可以加快算法的收斂。

3.4 交叉算子

每一代的個體按一定的交叉概率交換其部分基因,能產生新的基因組合,并且使各個解有機會交流他們的優秀基因,可以獲得比父代更好的解結構。根據本文所用的編碼方式特點,使用了線性次序交叉,其方法步驟如下。

3.4.1 使用Random函數隨機產生兩個交叉位,根據交叉位的選取將每個父代染色體分為三個子集分別為s1, s2, s3。

3.4.2 交換兩個父代中的s2。

3.4.3 在每個染色體的初始基因位中依次刪除已獲取s2中的各基因,得子集s4。

3.4.4 將s4中的基因依次替代父代染色體中的s1、s3對應的基因位。

4.4.5 重復以上步驟(1)～(4),得到所需要的新種群。交叉概率控制交叉操作的使用頻率,取交叉概率為0.3-0.8。

3.5 變異算子

遺傳算法采用變換順序的方法進行變異操作，即首先在個體中隨機選擇部分基因，再顛倒這些基因的順序。但是，如果被交換的基因是最近的兩個，變異操作產生的個體將同它的父代個體一樣。為了防止這種情況的發生，在變異操作中設定選取的基因塊的數量不能少于2個，這樣就可以避免無效變異操作的產生。變異操作的實現方法如下所述:

3.5.1 隨機的在6和L-1之間選擇一個值作為變異長度。其中L表示染色體的長度。

3.5.2 在父代個體中隨機選擇一個位置，第二個位置將等于第一個位置的值與之前選擇值的和。這樣變異塊就由這兩個變異塊之間的基因組成。

3.5.3 將變異塊中的基因變換順序得到新的基因塊，用這個基因塊取代第2步中產生的基因快。新的染色體就是子代染色體。

3.6 算法過程

3.6.1 初始化參數群體規模n,終止代數T,置代數t=0;

3.6.2 通過啟發式的調度算法產生初始種群P(t)一半個體的染色體編碼串;

3.6.3 通過貪心算法生成初始群體P(t)的另一半個體的染色體編碼;

3.6.4 計算群體中個體適應度,判斷是否滿足其終止條件,滿足終止算法,不滿足進入下步;

3.6.5 根據計算出來的適應度選擇雙親,通過交叉操作產生兩個后代;

3.6.6 計算新生成后代的適應度;

3.6.7 若后代的質量優于雙親,則后代進入P(t+1);反之,雙親進入P(t+1).

3.6.8 重復步驟(5)～(7),直至P(t+1)中的個體數達到n-1個,將P(t)中最優秀的個體接進入P(t+1), t=t+1;

(9)回到步驟(5)直至達到目標要求,得到最優解.

4 實驗結果

通過實驗把改進的GSA算法(MGSA)和傳統遺傳算法(GA)相比較。我們分別將MGSA和GA應用到FT 10x10 和 FT20X5中，結果如圖2所示。改進后的算法比傳統的遺傳算法效率上有很大提高。

圖2 結果分析

5 結束語

車間調度問題已經證明為 NP 問題，目前來說，難以找到能夠求得最優解的確定性調度算法。由于遺傳算法的優良特性，采用遺傳算法對車間調度問題進行求解的研究相當普遍，有關文獻的描述也較多。提出的基于混合遺傳算法的調度算法結合貪心算法，可以避免傳統遺

產算法陷入局部最優和收斂速度慢的缺陷。仿真實驗的計算表明了該改進算法是可行的、效果是明顯的、該算法具有較強的搜索能力。

[1]鄭蓋漢，鄭曉明.算法設計與分析(高等學校計算機教材)[M].北京：清華大學出版社，2005

[2]陳國良，王煦法，莊鎮全，等.遺傳算法及其應用[M].北京：人民郵電出版社，1996

[3]Alsuw Alyel M H.算法設計技巧與分析研究[M].北京：電子工業出版社，2004

[4]黃與林.0-1背包問題的貪心算法[J].鄂州大學學報，2006，13(6)：38-40

[5]周明.孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社，1999：85-89.

[6]Bellman R E，Dreyfus S E.Applied Dynamic Programming ［M］.Princeton，New Jersey ： Princeton University Press，1962

[7]Kolonko M.Some new results on simulated annealing applied tothe job-shop scheduling problem［J］.European Journal of Op-erational Research，1999，113( 1)

[8]Pezzella F，Merelli E.A tabu search method guided by shiftingbottleneck for the jobshop scheduling problem［J］.EuropeanJournal of Operational Research，2000，120( 2)

[9]鄔文堯,蔡鴻明,姜麗紅.柔性作業車間調度中的組合遺傳優化研究[J].計算機工程與應用.2009

[10]徐曉紅，曾令李，付躍文.求解柔性作業車間調度的混合PSO 算法與實現[J].計算機仿真.2010

[11]嚴蔚敏,吳偉民.數據結構(C語言版)[M].北京:清華大學出版社, 1997.

[12]M.H.ALSUWAIYEL.算法設計技巧與分析[M].北京:電子工業出版社, 2004.

[13]譚浩強.C++面向對象程序設計[M].北京:清華大學出版社, 2006.