盛立綱，顧幸生

華東理工大學自動化研究所 上海

摘      要： 針對流水車間調度問題提出一種混合遺傳NEH算法，以提高求解效率。NEH算法是一種高效的構造性算法具有很強的鄰域搜索能力，而遺傳算法則能有效的提供全局搜索。據此，新算法首先通過選擇、交叉和變異操作，經過迭代獲得一個較好解，然后在這個解所在的特定鄰域內進行改進的NEH搜索，以獲得更好解，經過NEH搜索后求得的較好解作為一個新個體加入下一代種群中，繼續進行遺傳操作。通過對流水車間調度的較小化較大完成時間問題的仿真實驗結果表明，新算法有明顯改進。

關  鍵  詞：流水車間調度；遺傳算法；NEH；較大完成時間

1 引言
流水車間調度問題可簡述為：一些工件按照同一順序在幾臺機器上進行加工；每個工件在每臺機器上只加工一次，而且加工過程不能中斷。迄今為止，人們提出了各種各樣的優化方法以求解流水車間調度問題。這些優化方法可以分成三大類：精確計算法、構造法和智能計算法[1]。精確計算法主要包括規劃法[2]，一般只適用于中小規模問題。構造法，是一種從局部較優中尋找全局較優的方法，適用于進行局部搜索。其中NEH是公認的較好的構造法[3]。由于流水車間調度問題是NP難問題，用智能優化方法得到滿意解便成為近期研究關注的重點。它們包括：模擬退火算法，遺傳算法[4]，粒子群算法，蟻群算法，文化算法[5]等等。遺傳算法也許是被較為廣泛應用的算法之一。遺傳算法可以為大規模問題給出一個合理滿意的解，但是有時候計算效率不高，并且合適的適應度函數并不容易找到。與之相對的，NEH算法能為車間調度問題更快的提供一個穩定可靠的解。近年來，出現了不少算法與NEH相結合取得了較好的結果[6]。本文將遺傳算法和NEH算法相結合，用來更好的解決流水車間調度問題。首先，用遺傳算法來縮小搜索范圍，當這個范圍達到一定程度時再用NEH的方法進行搜索，以求得到一個更好的解，并把這個解返回給遺傳算法以改善染色體，再繼續進行搜索。此外，改進了遺傳算法和NEH算法。

登錄網站后可下載文件