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