混合遺傳neh算法在流水車間調(diào)度中的應(yīng)用
盛立綱，顧幸生
（華東理工大學(xué)自動(dòng)化研究所，上海200237）
摘 要：針對流水車間調(diào)度問題提出一種混合遺傳neh算法，以提高求解效率。neh算法是一種高效的構(gòu)造性算法具有很強(qiáng)的鄰域搜索能力，而遺傳算法則能有效地提供全局搜索。據(jù)此，新算法首先通過選擇、交叉和變異操作，經(jīng)過迭代獲得一個(gè)較好解，然后在這個(gè)解所在的特定鄰域內(nèi)進(jìn)行改進(jìn)的neh搜索，以獲得更好解，經(jīng)過neh搜索后求得的****解作為一個(gè)新個(gè)體加入下一代種群中，繼續(xù)進(jìn)行遺傳操作：通過對流水車間調(diào)度的最小化****完成時(shí)間問題的仿真實(shí)驗(yàn)結(jié)果表明，新算法有明顯改進(jìn)。
關(guān)鍵詞：流水車間調(diào)度；遺傳算法；neh；****完成時(shí)間
中圖分類號：tp 27 文獻(xiàn)標(biāo)識(shí)碼：a
l引言
流水車間調(diào)度問題可簡述為：一些工件按照同一順序在幾臺(tái)機(jī)器上進(jìn)行加工；每個(gè)工件在每臺(tái)機(jī)器上只加工一次，而且加工過程不能中斷。
迄今為止，人們提出了各種各樣的優(yōu)化方法用來求解流水車間調(diào)度問題。這些優(yōu)化方法可以分成三大類：精確計(jì)算法、構(gòu)造法和智能計(jì)算法。精確計(jì)算法主要包括規(guī)劃法，一般只適用于中小規(guī)模問題。構(gòu)造法，是一種從局部****中尋找全局****的方法，適用于進(jìn)行局部搜索。其中，neh是公認(rèn)的****的構(gòu)造法。由于流水車問調(diào)度問題是np難問題，用智能優(yōu)化方法得到滿意解便成為近期研究關(guān)注的重點(diǎn)。它們包括模擬退火算法，遺傳算法，粒子群算法．蟻群算法，文化算法-1等。遺傳算法也許是被最為廣泛應(yīng)用的算法之一。遺傳算法可以為大規(guī)模問題給出一個(gè)合理滿意的解，但是有時(shí)候計(jì)算效率不高，并且合適的適應(yīng)度函數(shù)并不容易找到。與之相對的，neh算法能為車間調(diào)度問題更快地提供一個(gè)穩(wěn)定可靠的解。因此近年來，出現(xiàn)了不少算法與neh相結(jié)合取得了較好的結(jié)果。
本文將遺傳算法和neh算法相結(jié)合，用來更好地解決流水車間調(diào)度問題。首先，用遺傳算法來縮小搜索范圍，當(dāng)這個(gè)范圍達(dá)到一定程度時(shí)再用neh的方法進(jìn)行搜索，以求得到一個(gè)更好的解，并把這個(gè)解返回給遺傳算法以改善染色體，再繼續(xù)進(jìn)行搜索。此外，改進(jìn)了遺傳算法和neh算法。
2問題和算法
1)流水車間調(diào)度問題的具體定義有n個(gè)工件需要在m臺(tái)機(jī)器上加工，第j個(gè)工件在第i臺(tái)機(jī)器上的加工時(shí)間與加工的順序無關(guān)，是一個(gè)固定的常數(shù)，為pij于是加工時(shí)間矩陣p就可以記為
并且，在同一時(shí)刻，每個(gè)工件最多只在一臺(tái)機(jī)器上加工而且每臺(tái)機(jī)器最多只加工一個(gè)工件。問題的優(yōu)化目標(biāo)便是找到一種所有工件加工順序使得從第一個(gè)工件在第一臺(tái)機(jī)器上加工開始到最后一個(gè)工件在最后一臺(tái)機(jī)器上加工完成所消耗的時(shí)間最短。若{ π1，π1，... ，πn-1，πn}表示一種工件加工順序，則依據(jù)reeves所述，完工時(shí)間c（i，πj）可以按照如下公式計(jì)算：
由此，生產(chǎn)周期可以如下定義：
記ⅱ是所有可能的加工順序集合，若π是****加工順序，則有：
顯然，能很方便地用圖形來表達(dá)這個(gè)問題。對于rr eⅱ，對應(yīng)的圖形記為g（π）=(n，e)，如圖l所示。
其中，n={l，2，…，m}．{l，2，…，n}是每個(gè)節(jié)點(diǎn)，(i，j)∈n權(quán)重為對應(yīng)處理時(shí)間p的節(jié)點(diǎn)。g（∈ⅱ）可看作一個(gè)m×n的矩形，且每個(gè)節(jié)點(diǎn)的權(quán)重由一決定。按照上述計(jì)算完成時(shí)間cmax的方法，可以對應(yīng)的在圖上找出相應(yīng)的一條從(1，1)到(m，n)的最長路徑，使之等于cmax(π)，稱為關(guān)鍵路徑。關(guān)鍵路徑中一定有(m— |
