ＪＳＰ問題的遺傳算法解決途徑

摘要：針對車床作業調度問題，討論了應用于車床作業調度的遺傳算法設計，給出了主要的編碼、解碼、以及死鎖問題的算法模型。結合應用實例，說明了設計的可行性與有效性。

關鍵詞：車床調度；遺傳算法

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2009)04-0857-03

Solving JSP Problem by Genetic Algorithm

WANG Tao

(Information Dep， Shanghai Maritime University， Shanghai 200135， China)

Abstract: This article bases the genetic theory and use its algorithm to set the formulation of the JSP problem then discuss the method of solving problem， merging the instance to show the importance and the efficiency of the design.

Key words: JSP; genetic algorithm

1 引言

車床調度簡稱JSP（Job Shop Scheduling Problem），是一個典型的NP難問題，也是CIMS領域中研究的重要課題，其研究不僅具有重大的現實意義，而且具有深遠的理論意義。這是一個歷史悠久的問題，對應于生產管理系統的短期計劃的安排，即實施層次，調度主要解決車床資源的最優安排，優化計劃安排，為計劃的執行和控制提供指導。通常指車床生產過程的作業計劃，解決如何合理地分配車床有限的資源，使資源利率最高以及成本最小等問題。

隨著社會競爭的加劇，調度決策水平的高低己經成為現代制造企業中決定生產經營過程能否實現降低成本，對市場實現快速響應，從而實現穩定高效地運轉的決定性因素之一。良好的車床調度能夠預先解決生產中的干擾，能夠縮短產品在車床的流動時間，減少在制品庫存，保證準時交貨。

此問題通常被描述為：車床有一些機器，這些機器分屬于不同的類型。有一些工作要安排在這些機器上完成，每個工作都由一些有序的操作組成，每個操作必須在某一種指定類型的機器上完成。每一臺機器在同一時刻只能進行一個操作。每個操作在每臺機器上不可以被中斷。適當安排每個工序在每臺機器上的順序，以達到某種目標的最優。

2 車床調度問題的提出和數學化描述

車床調度問題的實例邏輯模型化可以描述為：設有N 個工件在M 臺機器上加工，由于工件的加工工藝的要求，每個工件使用機器的順序及其每道工序所花時間已給定，調度問題就是如何安排在每臺機器上工件的加工順序，使得某種指標最優。具體滿足下面條件：

1) 每一工件在機器上的加工順序一定。

2) 每一臺機器每次只能加工一個工件。

3) 機器與工件可能開始時間都為0。

4) 工件在機器上被加工時不允許被打斷。

5) 每一工件在機器上的加工時間固定。

如圖1舉例所示。

以數學模型化來定義一個調度問題可以描述為如下的一個三元組

Q ( M ， R ， J )

M 是一個集合，其中的每一個元素為：M1， M2 ...Mm.

R 是集合M 上的一個劃分，其中每一個元素Ri 都是集合M 的一個子集，對應一個機器類型。在這里將其稱為一種資源。集合J 為工作集合，其中的每一個元素J i 是一個序列( ti ，1 ...ti ， k) ，對應一個工作，其中ti ，j表示工作J i 的第j 個任務。ti ，j的值為一個序偶：( Ri ， x) ，Ri 表示此任務需要在哪一個資源上完成，x 表示完成此任務所需的時間。J i 中的任務之間存在著某種有序關系。

問題的解是要將所有任務，按照合理的順序分配在各個機器上，每臺機器上的任務順序可以用一個序列組成。所有機器上的任務序列構成一個列表F。其中Fi 對應第i 臺機器上的任務序列。

3遺傳算法介紹引入

3.1 遺傳算法

遺傳算法(Genetic Algorithms) 是一種大致基于進化論優勝劣汰、適者生存的物種遺傳思想的搜索算法。通過變異和重組當前一致的最好假設來生成后續的假設，每一步，更新被稱為當前群體的一組假設，方法是通過使用目前適應度最高的假設的后代替代群體的某個部分。遺傳算法的普及主要考慮以下因素：

1) 在生物系統中，進化被認為是一種成功的自適應方法，且具有很好的健壯性；

2) 遺傳算法搜索的假設空間中，假設的各個部分相互作用，每一部分對總的假設適應度的影響難以建模；

3) 遺傳算法易于并行化。

遺傳算法的不同實現在細節上有所不同，但它們都具有以下的共同結構：算法迭代更新一個假設池，這個假設池稱為群體。在每一次迭代中，根據適應度函數評估群體中的所有成員，然后從當前群體中用概率方法選取適應度最高的個體產生新一代群體。

在這些被選中的個體中，一部分保持原樣地進入下一代群體，其他的被用作產生后代個體的基礎。其中應用像交叉和變異這樣的遺傳方法。其中的重點在于如何表示解空間、遺傳算子的設計和適應度函數的計算。

3.2 模擬退火算法

模擬退火算法（simulated annealing，簡稱SA）的思想算基于Mente Carlo迭代求解策略的一種隨機尋優算法，其出發點是基于物理中固體物質的退火過程與一般組合優化問題之間的相似性。

模擬退火算法在某一初溫下，伴隨溫度參數的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數的全局最優解，即在局部優解能概率性地跳出并最終趨于全局最優。

3.3 GASA混合算法

GASA混合算法。GA 和SA 兩種算法均屬于基于概率分布機制的優化算法。不同的是，SA 通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效地避免陷入局部極小并最終趨于全局最優；GA 則通過概率意義下的基于“優勝劣汰”思想的群體遺傳操作來實現優化。對選擇優化機制上如此差異的兩種算法進行混合，有利于豐富優化過程的搜索行為，增強全局和局部意義下的搜索能力和效率。是一種優化能力、效率和可靠性較高的優化方法。

遺傳算法利用生物進化機制，在一個較大的初始解空間中通過優勝劣汰的方法進行優化求解，和其它優化方法相比不僅尋優能力強而且計算速度快。本文在研究經典JSP 問題的基礎上，提出一種用遺傳算法優化JSP 過程的算法，通過仿真可以得到較為令人滿意的結果。

4 調度問題的遺傳算法實現

為了進行JSP 調度問題遺傳算法的具體設計，主要包括以下幾個方面的設計：

4.1 遺傳算法染色體編碼

在解JSP問題時，如果編碼方式選擇不當，容易出現死鎖現象。在產生初始染色體或交叉、變異時都有可能產生死鎖染色體，難以避免。產生這樣的染色體，在解碼時就會遇到困難。設計一個合適的表達解的方法和基于特定問題的遺傳算子，使得不管在初期還是在進化過程中產生的所有染色體都將產生可行調度，將是影響遺傳算法的各個子階段的關鍵步驟。

這里采用的是基于工序的表達方法。這種表達法將調度編碼為工序的序列，給所有同一工件的工序指定相同的符號，然后根據它們在給定染色體中出現的順序加以解釋。由于這種編碼方式在編碼的時候就考慮了工件的順序約束，因此再解碼時就不會出現死鎖現象。

4.2 基于置換的遺傳算子

在選取的初始假設空間中進行搜索以生成后代，需要一系列的算子。我們選取常用的交叉算子來從兩個雙親中產生后代。簡單遺傳算法中用簡單的二進制位串作為交叉算子。由于本文的假設空間由序列而不是簡單的位串組成，用普通的二進制位串交叉算子會產生大量的解空間之外的元素，即新串不是一個序列。因此本文提出了一種基于置換的遺傳算子，來解決這個問題。由于候選解的結構由若干子串組成，每一個子串都是一個排列，不同的候選解之間的差異在于每一個子串中任務的順序不同，而不同子串之間則不會有任務交換。因此可以把候選解看做幾個獨立的部分分別進行運算。交叉算子的目的在于組合雙親的各部分產生后代，因此選用的交叉算子產生的后代的各部分應該取自于雙親。即保留雙親的共性，在雙親中的差異性中隨機選取雙方的特點。這樣產生的后代既保留了雙親的特征，同時又和每一個雙親都具有一些差異。

由于每一個雙親都是一個排列，而每一個排列都對應著任務集上的一個置換。而這些置換構成了一個置換群。因此，可以利用置換群的特點來構造交叉算子。設F1 和F2 為兩個雙親，則F1 和F2 是一個置換群中的兩個元素。因此，必存在著一個置換X 使得F1*X = F2 。我們可以把X 看做為F1 和F2 的差異性。而X 可以表示成若干個對換的乘積。為了避免生成的所有候選解構成一個子群。選取變異算子按照一定的概率對候選解進行運算。變異算子同樣基于置換，隨機選取兩個位，對他們進行交換，即可完成變異運算。這個算子相當于在原有的置換上乘以一個對換，使其奇偶性改變。

4.3 適應度函數的選擇

適應度函數的計算應該根據最后的工序結果來進行，但是解空間中的元素形式并不適宜計算。因此，應該對候選解中的序列進行處理，加上每一任務開始的時間，轉化為一個真正可以執行的序列，然后才可以進行計算。比如，按照生產效率最高為約束條件，需要將候選解中的序列轉化為實際生產中的時間表，然后計算總生產效率，根據生產效率的高低來制定適應度函數的取值。

遺傳算法中使用適應度這個概念來度量群體中各個個體在優化計算中有可能達到、接近或有助于找到最優解的優良程度。一般來說，在運行的初期階段，適應度差距比較大，有可能導致在選擇過程中幾個個體占有很高比例，從而使遺傳算法產生早熟現象。而在運行的后期階段，群體的個體適應度可能非常接近，大部分個體的競爭力和最佳個體相差無幾，可能進入隨機選擇過程。由此，本文采用線性尺度變換，從而能實現在運行的不同階段，對個體的適宜度進行適當的

調整，擴大或縮小，避免早熟現象的發生。具體操作如下：

F'= aF + b ，其中a=1/(Favg-Fmin)，b=-Fmin/(Favg-Fmin)

5 應用實例

如下是一個標準比較實例。考慮一個具有6 臺機器，6 個工件的標準問題。本例使用最小加工時間作為目標函數。試用計算過程與計算結果把基于工序編碼方法與優先列表的編碼方法的兩種遺傳算法進行比較。

6 結束語

本文通過對車床調度問題的提出以及刻畫出其數學模型，提出了調度問題的遺傳算法解決模型，設計了遺傳算法的初始解空間，提出了基于置換的遺傳算子，最后，對適應度函數的選擇進行了深入的討論。經過驗證，在多次迭代的過程后，遺傳算法可以產生非常優秀的解決方案，尤其適用于大規模的調度問題。

參考文獻：

[1] Lejtman Y， Shayan E.Design of a Suitable Production Management System for a Manufacturing Company[J].Computers IndustialEngineering，2002.

[2] 玄光男，程潤偉.遺傳算法與工程設計[M].北京:科學出版社，2000.

[3] 王凌.車間調度及其遺傳算法[M].北京:清華大學出版社，2002.

[4] 于海斌，薛勁松，王浩波.一種基于神經網絡的生產調度方法[J].自動化學報，1999，25(4).

[5] 童剛.Job-Shop 調度問題理論及方法的應用研究[D].天津:天津大學，2000.