李 辰

（大連交通大學(xué)軟件學(xué)院 116052）

0 引言

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

1 車間調(diào)度問(wèn)題概述

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

2 車間調(diào)度問(wèn)題的數(shù)學(xué)模型

車間調(diào)度問(wèn)題 研究 n 個(gè)工件在 m 臺(tái)機(jī)器上的加工。每個(gè)工件在各個(gè)機(jī)器上的加工次序和每個(gè)工件的各個(gè)工序的加工時(shí)間為已知，要求確定與約束條件相容的各機(jī)器上所有工件的加工開(kāi)始時(shí)間，完成時(shí)間和加工次序，使加工性能指標(biāo)達(dá)到最優(yōu)。則 n個(gè)工件m 臺(tái)機(jī)器的車間調(diào)度問(wèn)題的一般性定義如下:

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

約束：

2.1 每個(gè)工件的每個(gè)工序的加工工時(shí)Tij為已知。

2.2 每個(gè)工件包擴(kuò)一個(gè)由多道工序組成的工序集合，工件的工序順序已知。

2.3 同一臺(tái)機(jī)床僅能同一時(shí)間加工一個(gè)工件的一道工序。

2.4 不同工件的工序之間沒(méi)有約束。相同工件工序滿足先后順序約束關(guān)系。

2.5 工序之間沒(méi)有時(shí)間間隔。

2.6 各個(gè)工件的每到工序的開(kāi)工時(shí)間大于或等于零，且一個(gè)工件的前一道工序加工完后才能進(jìn)行下一道工序。

目標(biāo)函數(shù)值為Min(Max{ C1, C2, C3,…, Cn}) Ci為工件Ni 加工時(shí)間。即第n個(gè)工件的最后一道工序的完成時(shí)間T，但是第n個(gè)工件的完工時(shí)間不一定是所有工件的最小完工時(shí)間，需要先求出每個(gè)工件每道工序在機(jī)器上的加工時(shí)間段，再?gòu)倪x定的加工機(jī)器依次計(jì)算每臺(tái)機(jī)器最后的工件完成時(shí)間，取其中的最大值就是目標(biāo)函數(shù)值。

3 改進(jìn)的貪心遺傳混合算法求解過(guò)程

3.1 編碼方式

編碼問(wèn)題是設(shè)計(jì)遺傳算法的首要和關(guān)鍵問(wèn)題。對(duì)遺傳算法的編碼技術(shù)必須考慮染色體的合法性、可行性、有效性以及對(duì)解空間表征的完全性，對(duì)于車間調(diào)度也是這樣。由于車間調(diào)度問(wèn)題的組合特性以及

工藝約束性，染色體的 Lamarkian 特性、解碼的復(fù)雜性、編碼的空間特性和存儲(chǔ)量的需求是設(shè)計(jì)遺傳算法編碼通常要考慮的問(wèn)題。

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

3.1.2 解碼的復(fù)雜性。就解碼的有效性而言，我們希望 GA搜索用的碼能夠解碼成活動(dòng)調(diào)度，甚至搜索所采用的碼跟活動(dòng)調(diào)度一一對(duì)應(yīng)。就解碼復(fù)雜性而言，將不需要解碼的相應(yīng)編碼歸為0 類復(fù)雜性；通過(guò)簡(jiǎn)單映射關(guān)系實(shí)現(xiàn)解碼的相應(yīng)編碼歸為 1 類復(fù)雜性；通過(guò)簡(jiǎn)單啟發(fā)式方法才能實(shí)現(xiàn)解碼的相應(yīng)編碼歸為 2類復(fù)雜性；只有通過(guò)復(fù)雜啟發(fā)式方法才能實(shí)現(xiàn)解碼的相應(yīng)編碼歸為 3 類復(fù)雜性。

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

3.1.4 存儲(chǔ)量需求。就 n個(gè)工件 m 臺(tái)機(jī)器的 Job Shop調(diào)度問(wèn)題而言，通常用碼長(zhǎng)來(lái)反映編碼對(duì)存儲(chǔ)量的需求。稱 n ×m為 GA 染色體的標(biāo)準(zhǔn)長(zhǎng)度，即操作的總數(shù)量?；诖耍蓪⒕幋a分為三類：其一，碼長(zhǎng)等于標(biāo)準(zhǔn)長(zhǎng)度；其二，碼長(zhǎng)大于標(biāo)準(zhǔn)長(zhǎng)度；其三，碼長(zhǎng)小于標(biāo)準(zhǔn)長(zhǎng)度。

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

圖1 編碼示例

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

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

3.3 選擇算子

選擇是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的關(guān)鍵過(guò)程，為了保證當(dāng)前種群中的最優(yōu)解被選擇，同時(shí)不失種群的多樣性。本文采取貪心算法和適應(yīng)度比例法兩種方法結(jié)合，即：通過(guò)貪心算法將局部適應(yīng)度最大的個(gè)體直接選擇到下一代，再通過(guò)適應(yīng)度比例法選擇出下一代種群的個(gè)體。

貪心算法是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。在選擇算子中引入貪心算法，可以加快算法的收斂速度。

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

3.4 交叉算子

每一代的個(gè)體按一定的交叉概率交換其部分基因,能產(chǎn)生新的基因組合,并且使各個(gè)解有機(jī)會(huì)交流他們的優(yōu)秀基因,可以獲得比父代更好的解結(jié)構(gòu)。根據(jù)本文所用的編碼方式特點(diǎn),使用了線性次序交叉,其方法步驟如下。

3.4.1 使用Random函數(shù)隨機(jī)產(chǎn)生兩個(gè)交叉位,根據(jù)交叉位的選取將每個(gè)父代染色體分為三個(gè)子集分別為s1, s2, s3。

3.4.2 交換兩個(gè)父代中的s2。

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

3.4.4 將s4中的基因依次替代父代染色體中的s1、s3對(duì)應(yīng)的基因位。

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

3.5 變異算子

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

3.5.1 隨機(jī)的在6和L-1之間選擇一個(gè)值作為變異長(zhǎng)度。其中L表示染色體的長(zhǎng)度。

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

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

3.6 算法過(guò)程

3.6.1 初始化參數(shù)群體規(guī)模n,終止代數(shù)T,置代數(shù)t=0;

3.6.2 通過(guò)啟發(fā)式的調(diào)度算法產(chǎn)生初始種群P(t)一半個(gè)體的染色體編碼串;

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

3.6.4 計(jì)算群體中個(gè)體適應(yīng)度,判斷是否滿足其終止條件,滿足終止算法,不滿足進(jìn)入下步;

3.6.5 根據(jù)計(jì)算出來(lái)的適應(yīng)度選擇雙親,通過(guò)交叉操作產(chǎn)生兩個(gè)后代;

3.6.6 計(jì)算新生成后代的適應(yīng)度;

3.6.7 若后代的質(zhì)量?jī)?yōu)于雙親,則后代進(jìn)入P(t+1);反之,雙親進(jìn)入P(t+1).

3.6.8 重復(fù)步驟(5)～(7),直至P(t+1)中的個(gè)體數(shù)達(dá)到n-1個(gè),將P(t)中最優(yōu)秀的個(gè)體接進(jìn)入P(t+1), t=t+1;

(9)回到步驟(5)直至達(dá)到目標(biāo)要求,得到最優(yōu)解.

4 實(shí)驗(yàn)結(jié)果

通過(guò)實(shí)驗(yàn)把改進(jìn)的GSA算法(MGSA)和傳統(tǒng)遺傳算法(GA)相比較。我們分別將MGSA和GA應(yīng)用到FT 10x10 和 FT20X5中，結(jié)果如圖2所示。改進(jìn)后的算法比傳統(tǒng)的遺傳算法效率上有很大提高。

圖2 結(jié)果分析

5 結(jié)束語(yǔ)

車間調(diào)度問(wèn)題已經(jīng)證明為 NP 問(wèn)題，目前來(lái)說(shuō)，難以找到能夠求得最優(yōu)解的確定性調(diào)度算法。由于遺傳算法的優(yōu)良特性，采用遺傳算法對(duì)車間調(diào)度問(wèn)題進(jìn)行求解的研究相當(dāng)普遍，有關(guān)文獻(xiàn)的描述也較多。提出的基于混合遺傳算法的調(diào)度算法結(jié)合貪心算法，可以避免傳統(tǒng)遺

產(chǎn)算法陷入局部最優(yōu)和收斂速度慢的缺陷。仿真實(shí)驗(yàn)的計(jì)算表明了該改進(jìn)算法是可行的、效果是明顯的、該算法具有較強(qiáng)的搜索能力。

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

[2]陳國(guó)良，王煦法，莊鎮(zhèn)全，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996

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

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

[5]周明.孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，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]鄔文堯,蔡鴻明,姜麗紅.柔性作業(yè)車間調(diào)度中的組合遺傳優(yōu)化研究[J].計(jì)算機(jī)工程與應(yīng)用.2009

[10]徐曉紅，曾令李，付躍文.求解柔性作業(yè)車間調(diào)度的混合PSO 算法與實(shí)現(xiàn)[J].計(jì)算機(jī)仿真.2010

[11]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出版社, 1997.

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

[13]譚浩強(qiáng).C++面向?qū)ο蟪绦蛟O(shè)計(jì)[M].北京:清華大學(xué)出版社, 2006.