摘要：針對車床作業(yè)調(diào)度問題，討論了應(yīng)用于車床作業(yè)調(diào)度的遺傳算法設(shè)計(jì)，給出了主要的編碼、解碼、以及死鎖問題的算法模型。結(jié)合應(yīng)用實(shí)例，說明了設(shè)計(jì)的可行性與有效性。

關(guān)鍵詞：車床調(diào)度；遺傳算法

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 引言

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

隨著社會(huì)競爭的加劇，調(diào)度決策水平的高低己經(jīng)成為現(xiàn)代制造企業(yè)中決定生產(chǎn)經(jīng)營過程能否實(shí)現(xiàn)降低成本，對市場實(shí)現(xiàn)快速響應(yīng)，從而實(shí)現(xiàn)穩(wěn)定高效地運(yùn)轉(zhuǎn)的決定性因素之一。良好的車床調(diào)度能夠預(yù)先解決生產(chǎn)中的干擾，能夠縮短產(chǎn)品在車床的流動(dòng)時(shí)間，減少在制品庫存，保證準(zhǔn)時(shí)交貨。

此問題通常被描述為：車床有一些機(jī)器，這些機(jī)器分屬于不同的類型。有一些工作要安排在這些機(jī)器上完成，每個(gè)工作都由一些有序的操作組成，每個(gè)操作必須在某一種指定類型的機(jī)器上完成。每一臺(tái)機(jī)器在同一時(shí)刻只能進(jìn)行一個(gè)操作。每個(gè)操作在每臺(tái)機(jī)器上不可以被中斷。適當(dāng)安排每個(gè)工序在每臺(tái)機(jī)器上的順序，以達(dá)到某種目標(biāo)的最優(yōu)。

2 車床調(diào)度問題的提出和數(shù)學(xué)化描述

車床調(diào)度問題的實(shí)例邏輯模型化可以描述為：設(shè)有N 個(gè)工件在M 臺(tái)機(jī)器上加工，由于工件的加工工藝的要求，每個(gè)工件使用機(jī)器的順序及其每道工序所花時(shí)間已給定，調(diào)度問題就是如何安排在每臺(tái)機(jī)器上工件的加工順序，使得某種指標(biāo)最優(yōu)。具體滿足下面條件：

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

2) 每一臺(tái)機(jī)器每次只能加工一個(gè)工件。

3) 機(jī)器與工件可能開始時(shí)間都為0。

4) 工件在機(jī)器上被加工時(shí)不允許被打斷。

5) 每一工件在機(jī)器上的加工時(shí)間固定。

如圖1舉例所示。

以數(shù)學(xué)模型化來定義一個(gè)調(diào)度問題可以描述為如下的一個(gè)三元組

Q ( M ， R ， J )

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

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

問題的解是要將所有任務(wù)，按照合理的順序分配在各個(gè)機(jī)器上，每臺(tái)機(jī)器上的任務(wù)順序可以用一個(gè)序列組成。所有機(jī)器上的任務(wù)序列構(gòu)成一個(gè)列表F。其中Fi 對應(yīng)第i 臺(tái)機(jī)器上的任務(wù)序列。

3遺傳算法介紹引入

3.1 遺傳算法

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

1) 在生物系統(tǒng)中，進(jìn)化被認(rèn)為是一種成功的自適應(yīng)方法，且具有很好的健壯性；

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

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

遺傳算法的不同實(shí)現(xiàn)在細(xì)節(jié)上有所不同，但它們都具有以下的共同結(jié)構(gòu)：算法迭代更新一個(gè)假設(shè)池，這個(gè)假設(shè)池稱為群體。在每一次迭代中，根據(jù)適應(yīng)度函數(shù)評估群體中的所有成員，然后從當(dāng)前群體中用概率方法選取適應(yīng)度最高的個(gè)體產(chǎn)生新一代群體。

在這些被選中的個(gè)體中，一部分保持原樣地進(jìn)入下一代群體，其他的被用作產(chǎn)生后代個(gè)體的基礎(chǔ)。其中應(yīng)用像交叉和變異這樣的遺傳方法。其中的重點(diǎn)在于如何表示解空間、遺傳算子的設(shè)計(jì)和適應(yīng)度函數(shù)的計(jì)算。

3.2 模擬退火算法

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

模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。

3.3 GASA混合算法

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

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

4 調(diào)度問題的遺傳算法實(shí)現(xiàn)

為了進(jìn)行JSP 調(diào)度問題遺傳算法的具體設(shè)計(jì)，主要包括以下幾個(gè)方面的設(shè)計(jì)：

4.1 遺傳算法染色體編碼

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

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

4.2 基于置換的遺傳算子

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

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

4.3 適應(yīng)度函數(shù)的選擇

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

遺傳算法中使用適應(yīng)度這個(gè)概念來度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到、接近或有助于找到最優(yōu)解的優(yōu)良程度。一般來說，在運(yùn)行的初期階段，適應(yīng)度差距比較大，有可能導(dǎo)致在選擇過程中幾個(gè)個(gè)體占有很高比例，從而使遺傳算法產(chǎn)生早熟現(xiàn)象。而在運(yùn)行的后期階段，群體的個(gè)體適應(yīng)度可能非常接近，大部分個(gè)體的競爭力和最佳個(gè)體相差無幾，可能進(jìn)入隨機(jī)選擇過程。由此，本文采用線性尺度變換，從而能實(shí)現(xiàn)在運(yùn)行的不同階段，對個(gè)體的適宜度進(jìn)行適當(dāng)?shù)?/p>

調(diào)整，擴(kuò)大或縮小，避免早熟現(xiàn)象的發(fā)生。具體操作如下：

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

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

如下是一個(gè)標(biāo)準(zhǔn)比較實(shí)例?？紤]一個(gè)具有6 臺(tái)機(jī)器，6 個(gè)工件的標(biāo)準(zhǔn)問題。本例使用最小加工時(shí)間作為目標(biāo)函數(shù)。試用計(jì)算過程與計(jì)算結(jié)果把基于工序編碼方法與優(yōu)先列表的編碼方法的兩種遺傳算法進(jìn)行比較。

6 結(jié)束語

本文通過對車床調(diào)度問題的提出以及刻畫出其數(shù)學(xué)模型，提出了調(diào)度問題的遺傳算法解決模型，設(shè)計(jì)了遺傳算法的初始解空間，提出了基于置換的遺傳算子，最后，對適應(yīng)度函數(shù)的選擇進(jìn)行了深入的討論。經(jīng)過驗(yàn)證，在多次迭代的過程后，遺傳算法可以產(chǎn)生非常優(yōu)秀的解決方案，尤其適用于大規(guī)模的調(diào)度問題。

參考文獻(xiàn)：

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

[2] 玄光男，程潤偉.遺傳算法與工程設(shè)計(jì)[M].北京:科學(xué)出版社，2000.

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

[4] 于海斌，薛勁松，王浩波.一種基于神經(jīng)網(wǎng)絡(luò)的生產(chǎn)調(diào)度方法[J].自動(dòng)化學(xué)報(bào)，1999，25(4).

[5] 童剛.Job-Shop 調(diào)度問題理論及方法的應(yīng)用研究[D].天津:天津大學(xué)，2000.