劉紅軍，趙 帥

LIU Hong-jun, ZHAO Shuai

（沈陽理工大學(xué) 機(jī)械工程學(xué)院，沈陽 110168）

0 引言

隨著科學(xué)技術(shù)的不斷發(fā)展與提高，社會(huì)節(jié)奏的不斷加快，將科學(xué)的管理調(diào)度技術(shù)與車間生產(chǎn)調(diào)度緊密結(jié)合起來，在現(xiàn)代加工車間中已得到了普遍應(yīng)用。而如何將科學(xué)技術(shù)與車間生產(chǎn)調(diào)度更好的融合到一起，成為了當(dāng)今科學(xué)領(lǐng)域普遍重視的一個(gè)問題。車間調(diào)度問題實(shí)質(zhì)上就是研究在已有的資源條件和一定的約束條件下，對(duì)加工任務(wù)進(jìn)行的加工時(shí)間、機(jī)器和順序等的合理分配，從而使生產(chǎn)加工達(dá)到最優(yōu)化的狀態(tài)。

對(duì)于運(yùn)用到車間調(diào)度中的算法現(xiàn)在普遍采用的是：遺傳算法（GA）、模擬退火算法(SA) 、禁忌搜索算法(TS)、蟻群優(yōu)化算法(ant colony optimization algorithms)和人工神經(jīng)網(wǎng)絡(luò)(artificial neural networks)等優(yōu)化算法。雖然這些算法都能夠在車間調(diào)度中應(yīng)用，但是對(duì)于以上各種算法，在單獨(dú)的使用過程中都會(huì)有一定的局限性，比如遺傳算法可能出現(xiàn)早熟收斂，而禁忌搜索對(duì)于初始種群的選取和領(lǐng)域的結(jié)構(gòu)有著較高的要求，如果初始種群過小，可能會(huì)無法得到最優(yōu)解等。

本文針對(duì)遺傳算法的局部搜索能力差、易限于局部最優(yōu)等缺點(diǎn)，提出了一種適合運(yùn)用于車間調(diào)度系統(tǒng)研究中的混合遺傳算法（GA-SA-TS），即將模擬退火算法、禁忌搜索算法與遺傳算法結(jié)合使用。這種算法的核心在于：在遺傳算法的交叉機(jī)制中引入模擬退火算法的思想，形成模擬退火-交叉機(jī)制，從而避免遺傳本身易早熟的缺點(diǎn)。在變異機(jī)制中使用禁忌搜索算法的思想，形成禁忌搜索-變異機(jī)制，以此解決遺傳算法變異壓力問題。通過這些方面的改進(jìn)，提高了遺傳算法的優(yōu)化效率。

1 車間調(diào)度問題的描述

車間調(diào)度問題就是研究N(N1,N2,...,NN)個(gè)工件在M(M1,M2,...,MM)臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件具有一定數(shù)量的工序J(J1,J2,...,JJ)，每道工序可以在若干臺(tái)機(jī)器上加工，加工的過程按照工件的工藝順序完成。工件在加工的過程中要遵循以下約束：

1）每臺(tái)機(jī)器在每個(gè)時(shí)刻只能加工一個(gè)工件的一道工序；

2）每道工序只能被一臺(tái)機(jī)器加工；

3）每個(gè)工件按給定的工藝路線和指定的次序在機(jī)器上進(jìn)行加工；

4）每個(gè)工件在每臺(tái)機(jī)器上開始加工后不可停止，直到完成該道工序的加工；

5）每個(gè)工件只能在上道工序加工完成后才能開始下一道工序的加工[1]。

車間調(diào)度主要是針對(duì)工件的加工，研究在盡可能滿足一些約束條件(如交貨期、工藝路線、資源情況)的前提下，通過下達(dá)生產(chǎn)指令，安排其組成部分使用哪些生產(chǎn)資源、其加工時(shí)間及加工的先后順序等，從而獲得產(chǎn)品制造時(shí)間或成本的最優(yōu)化[2]。

2 改進(jìn)的遺傳算法

遺傳算法（GA-genetic algorithms）是Holland教授在20世紀(jì)70年代初期首先提出的。GA主要是借鑒了生物進(jìn)化過程中的“適者生存”的規(guī)律，并將算法的整個(gè)過程都與生物進(jìn)化過程的各概念對(duì)應(yīng)了起來，例如：遺傳算法中的解稱為個(gè)體，算法中對(duì)解進(jìn)行的編碼稱為染色體，算法中的適應(yīng)度函數(shù)值稱為適應(yīng)性，根據(jù)條件選定的一組解稱為種群等等。圖1為遺傳算法的流程圖。

圖1 遺傳算法流程圖

模擬退火算法（SA-simulated annealing）作為局部搜索算法的擴(kuò)展，是以一定的接受概率選擇鄰域中的較優(yōu)值，從而使其成為一個(gè)全局最優(yōu)算法。SA是基于固體退火的原理，固體加熱到一定的溫度后，其內(nèi)部的分子在某個(gè)空間中自由運(yùn)動(dòng)，隨著溫度的不斷下降，固體內(nèi)部的分子會(huì)逐漸停留在不同的狀態(tài)，而當(dāng)溫度降到最低點(diǎn)時(shí)，固體內(nèi)部的分子會(huì)以一種新的狀態(tài)重新排列。

禁忌搜索算法（TS-tabu search）是局部鄰域搜索算法的推廣，它的特點(diǎn)是采用了禁忌技術(shù)，即禁止重復(fù)前面的工作。TS用一個(gè)禁忌表將已經(jīng)遍歷過的局部最優(yōu)點(diǎn)或達(dá)到局部最優(yōu)的一些過程記錄下來，以便在后面的搜索中不再或者有選擇的對(duì)已經(jīng)記錄在禁忌表中的數(shù)據(jù)進(jìn)行搜索操作，從而跳出局部最優(yōu)點(diǎn)。

本文提出的混合遺傳算法（GA-SA-TS）是基于遺傳算法的整體流程，在其交叉機(jī)制中引入模擬退火算法的思想，在變異機(jī)制中引入禁忌搜索算法的思想。從而改善遺傳算法的局部搜索能力差的特點(diǎn)，進(jìn)一步提高優(yōu)化質(zhì)量和搜索效率，彌補(bǔ)單一算法在優(yōu)化方面的不足，達(dá)到取長補(bǔ)短的作用。

2.1 編碼方式

運(yùn)用到車間調(diào)度系統(tǒng)中的編碼方式有：基于“串”的編碼、基于位置“列表”的編碼、基于工序的編碼、基于工件的編碼、基于偏好列表的編碼、基于優(yōu)先規(guī)則的編碼、基于機(jī)器的編碼和基于完成時(shí)間的編碼等。

針對(duì)車間調(diào)度的實(shí)際情況，本文選擇的是基于工件的編碼方式。這種表達(dá)法把調(diào)度編碼為工序的序列，每個(gè)基因代表一道工序。一般采取用自然數(shù)來命名工序。由于基于工序的編碼方式本身就能滿足車間作業(yè)調(diào)度問題中的占用約束和順序約束關(guān)系，因此基于工件的編碼經(jīng)常被用于車間作業(yè)調(diào)度問題中。

2.2 適應(yīng)度函數(shù)

遺傳算法主要就是依靠對(duì)各染色體的適應(yīng)度函數(shù)的數(shù)值來確定染色體的優(yōu)劣。因而適應(yīng)度函數(shù)的確定對(duì)于優(yōu)化過程起著至關(guān)重要的作用。適應(yīng)度值高的染色體被保留操作的幾率就高，反之就低。

本文將工件的加工時(shí)間作為調(diào)度的評(píng)定標(biāo)準(zhǔn)，即加工完成的時(shí)間越少越好，所以車間調(diào)度問題為最小值問題，而根據(jù)適應(yīng)度函數(shù)的種類，可確定其適應(yīng)度函數(shù)為：

式中，cmax為一個(gè)適當(dāng)?shù)南鄬?duì)比較大的數(shù)，是f(x)的最大值估計(jì)，可以是一個(gè)合適的輸入值[3]。

2.3 選擇操作

選擇操作是在群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新的群體的過程。通過對(duì)每條染色體進(jìn)行選擇概率的計(jì)算，選擇概率較高的個(gè)體被保留下來遺傳到下一代進(jìn)行操作的概率就高，反之就低。選擇操作算子包括輪盤賭選擇、隨機(jī)競爭選擇、最佳保留選擇、無回放隨機(jī)選擇、確定性選擇、柔性分段選擇、均勻排序、穩(wěn)態(tài)復(fù)制和復(fù)制評(píng)價(jià)等，本文選擇最佳保留選擇算子進(jìn)行選擇操作，因?yàn)檫@種算子能夠保證迭代終止結(jié)果為歷代最高適應(yīng)度個(gè)體。選擇操作的基本流程為：

2）將各條染色體按照計(jì)算出的fi進(jìn)行由高到低的排序；

3）按照種群操作數(shù)目n的要求，從排序好的染色體群中按由高到低的順序選擇出n條染色體，并將這n條染色體完整的復(fù)制到下一代群體中。

2.4 模擬退火-交叉

本文通過對(duì)模擬退火算法的研究，提出一種模擬退火-交叉機(jī)制，所謂模擬退火-交叉，就是在遺傳算法的交叉機(jī)制中引用模擬退火的思想，完成遺傳算法中的交叉操作。而模擬退火算法之所以成為全局尋優(yōu)算法是因?yàn)槠洳捎昧薓etropolis準(zhǔn)則，該準(zhǔn)則也被稱為接受準(zhǔn)則，其內(nèi)容為：

接受概率計(jì)算公式為：

設(shè)初始狀態(tài)為i，該狀態(tài)的能量為Ei，然后從i的鄰域N(i)中隨機(jī)選一個(gè)新狀態(tài)j，新狀態(tài)的能量為Ej。如果Ei≥Ej，那么接受當(dāng)前狀態(tài)i為新狀態(tài)；如果Ei＜Ej，則隨機(jī)產(chǎn)生一個(gè)數(shù)?∈(0,1)，如果?＜Pij，就以j取代i成為當(dāng)前狀態(tài)。再重復(fù)以上新狀態(tài)的產(chǎn)生過程，直到系統(tǒng)趨于能量較低的平衡狀態(tài)。

本文提出的模擬退火-交叉機(jī)制就是借鑒了以上的思想，其具體操作流程如下：

就全國而言，通商口岸以外地區(qū)的新式教育在清末新政期間仍然處于起步階段。而以上海為中心的通商口岸城市新式教育的推進(jìn)明顯，特別是工商實(shí)業(yè)各門類的技能教育及高等院校的設(shè)立，“清末十年間，上海至少就培養(yǎng)了13萬多名新學(xué)學(xué)生”。[11]

2）從區(qū)域D中選取兩條染色體father1，father2；

3）判斷是否滿足終止條件（終止條件可以分為零度法，循環(huán)總數(shù)控制法，基于不改進(jìn)規(guī)則的控制法，接受概率控制法，鄰域法，Lundy和Mees法，Aarts和van Laarhoven法等[3]。本文選擇循環(huán)總數(shù)控制法，即給定一個(gè)溫度下降次數(shù)K，當(dāng)溫度迭代次數(shù)達(dá)到該值時(shí)，停止運(yùn)算），若滿足則退出交叉操作，輸出結(jié)果；否則轉(zhuǎn)至4）；

4）對(duì)染色體father1，father2進(jìn)行交叉操作，產(chǎn)生新的染色體son1，son2；

5）計(jì)算染色體father1，father2，son1，son2的適應(yīng)度值；

6）根據(jù)Metropolis準(zhǔn)則判定son1是否替代father1，son2是否替代father2；

7）計(jì)算退溫函數(shù)：tk=λ.tk-1(其中k＞0，0＜λ＜1，λ取值越接近1，溫度下降越慢，所以可以取λ=0.95,0.9,...)，轉(zhuǎn)至3）。

2.5 禁忌搜索-變異

采用了禁忌技術(shù)是禁忌搜索算法的一大特點(diǎn)，所謂禁忌，就是禁止重復(fù)之前的工作。為了避免局部搜索過早陷入局部最優(yōu)的缺點(diǎn)，禁忌搜索算法用一個(gè)禁忌表將已經(jīng)到達(dá)過的局部最優(yōu)點(diǎn)或者到達(dá)局部最優(yōu)的過程記錄下來，以便在后面的搜索中不再或者有選擇的對(duì)禁忌表中的這些點(diǎn)進(jìn)行搜索，從而跳出局部最優(yōu)。禁忌搜索是在一個(gè)染色體所產(chǎn)生的鄰域中進(jìn)行尋優(yōu)搜索操作的，而產(chǎn)生的鄰域中的染色體是否替代原有染色體，需要運(yùn)用特赦準(zhǔn)則（也成為藐視準(zhǔn)則）進(jìn)行判定。特赦準(zhǔn)則保證了搜索過程在全部候選解被禁或是有優(yōu)于當(dāng)前最優(yōu)解的候選解（或狀態(tài)）被禁時(shí)，能夠釋放特定解（或狀態(tài)）。從而實(shí)現(xiàn)高效的全局優(yōu)化搜索[4]。

本文通過對(duì)禁忌搜索算法的研究，提出一種禁忌搜索-變異機(jī)制，所謂禁忌搜索-變異，就是在遺傳算法的變異機(jī)制中融入禁忌搜索的思想。

禁忌搜索-變異的操作流程如下：

1）選擇一組染色體進(jìn)入禁忌搜索棧中等待操作；

2）從禁忌搜索棧中選出一條染色體A1，并令A(yù)best=A1，將禁忌表中內(nèi)容清零；

3）由A1產(chǎn)生N個(gè)候選解（x1,x2,x3,...,xi），形成一個(gè)以A1為基礎(chǔ)的鄰域；

4）計(jì)算出3）產(chǎn)生的鄰域中所有染色體的適應(yīng)度函數(shù)f，然后根據(jù)特赦準(zhǔn)則判定新產(chǎn)生的染色體是否替代原有染色體，成為Abest，本文設(shè)定的特赦準(zhǔn)則為：

如果f(Abest)≥f(xi)，則Abest值不變，并同時(shí)將xi放入禁忌表中，禁忌長度設(shè)為L=n；如果f(Abest)＜f(xi)，則Abest=xi，同時(shí)將原來的Abest的值放入禁忌表中，禁忌長度設(shè)為L=n；

5）判定是否滿足本文提出的終止條件：禁忌搜索次數(shù)n；如果滿足轉(zhuǎn)至6），否則轉(zhuǎn)至3）；

6）判定禁忌搜索棧中的染色體是否全部完成禁忌搜索-變異操作，如果是，轉(zhuǎn)至7），否則轉(zhuǎn)至2）；

7）輸出禁忌搜索-變異操作的結(jié)果。

3 經(jīng)典算例的研究

以MATLAB2010a為開發(fā)語言，對(duì)10個(gè)不同規(guī)模的經(jīng)典車間調(diào)度問題運(yùn)用GA-SA-TS混合遺傳算法進(jìn)行了算例仿真，并將運(yùn)行得到的結(jié)果與一些相關(guān)權(quán)威文獻(xiàn)得到的結(jié)果進(jìn)行了數(shù)據(jù)比對(duì)，結(jié)果如表1所示。

表1 經(jīng)典算例運(yùn)行結(jié)果比對(duì)

通過比對(duì)表格中的數(shù)據(jù)可知，運(yùn)用GA-SA-TS算法對(duì)這些經(jīng)典算例進(jìn)行運(yùn)算除了LA21得到的結(jié)果比TS得到的結(jié)果稍大一點(diǎn)以外，其余算例的結(jié)果都是目前出現(xiàn)的數(shù)據(jù)中的最優(yōu)值。所以通過運(yùn)算結(jié)果可知，運(yùn)用GA-SA-TS算法到車間調(diào)度系統(tǒng)中進(jìn)行優(yōu)化運(yùn)算是可行的。

4 結(jié)論

基于對(duì)遺傳算法易早熟和搜索能力差等缺點(diǎn)的考慮，本文提出了一種以遺傳算法為主體，融模擬退火算法和禁忌搜索算法思想于其中的混合遺傳算法（GA-SA-TS）。即在遺傳算法的交叉機(jī)制中融入模擬退火算法的思想，形成模擬退火-交叉機(jī)制。在遺傳算法的變異機(jī)制中融入禁忌搜索算法的思想，形成禁忌搜索-變異機(jī)制。并通過對(duì)車間調(diào)度生產(chǎn)的經(jīng)典算例仿真得到的數(shù)據(jù)可知，運(yùn)用這種混合遺傳算法，對(duì)于解決車間調(diào)度系統(tǒng)的問題，不但提高了運(yùn)算的效率，較單純的GA、SA、TS算法而言，在解的質(zhì)量方面也有所提高。

[1]陶思南,傅鸝,蔡斌.一種求解車間作業(yè)調(diào)度的自適應(yīng)混合遺傳算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2010,4(19):53-57.

[2]何燕.基于遺傳算法的車間調(diào)度優(yōu)化及其仿真[D].湖北:武漢理工大學(xué),2006.

[3]雷英杰,張善文,李續(xù)武,周創(chuàng)明.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2009.

[4]董宗然,周慧.禁忌搜索算法評(píng)述.技術(shù):96-98.

[5]Corce F D,Tadei R,Volta G.A genetic algorithm for the job shop problem[J].Computers and Operations Research,1995,22:15-24.

[6]Laarhoven P V,Aarts E, Lenstra J K.Job shop scheduling by simulated annealing[J].Operations Research,1992,40:113-125.

[7]Amico M D,Trubian M.Applying tabu search to the job shop scheduling problems[J].Annual Operations Research,1993,40:231-252.