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

關(guān)鍵詞：流水車間調(diào)度；遺傳算法；neh；****完成時間

中圖分類號：tp 27    文獻標識碼：a

    流水車間調(diào)度問題可簡述為：一些工件按照同一順序在幾臺機器上進行加工；每個工件在每臺機器上只加工一次，而且加工過程不能中斷。

    迄今為止，人們提出了各種各樣的優(yōu)化方法用來求解流水車間調(diào)度問題。這些優(yōu)化方法可以分成三大類：精確計算法、構(gòu)造法和智能計算法。精確計算法主要包括規(guī)劃法，一般只適用于中小規(guī)模問題。構(gòu)造法，是一種從局部****中尋找全局****的方法，適用于進行局部搜索。其中，neh是公認的****的構(gòu)造法。由于流水車問調(diào)度問題是np難問題，用智能優(yōu)化方法得到滿意解便成為近期研究關(guān)注的重點。它們包括模擬退火算法，遺傳算法，粒子群算法．蟻群算法，文化算法-1等。遺傳算法也許是被最為廣泛應(yīng)用的算法之一。遺傳算法可以為大規(guī)模問題給出一個合理滿意的解，但是有時候計算效率不高，并且合適的適應(yīng)度函數(shù)并不容易找到。與之相對的，neh算法能為車間調(diào)度問題更快地提供一個穩(wěn)定可靠的解。因此近年來，出現(xiàn)了不少算法與neh相結(jié)合取得了較好的結(jié)果。

  本文將遺傳算法和neh算法相結(jié)合，用來更好地解決流水車間調(diào)度問題。首先，用遺傳算法來縮小搜索范圍，當這個范圍達到一定程度時再用neh的方法進行搜索，以求得到一個更好的解，并把這個解返回給遺傳算法以改善染色體，再繼續(xù)進行搜索。此外，改進了遺傳算法和neh算法。

    1)流水車間調(diào)度問題的具體定義有n個工件需要在m臺機器上加工，第j個工件在第i臺機器上的加工時間與加工的順序無關(guān)，是一個固定的常數(shù)，為pij于是加工時間矩陣p就可以記為

    并且，在同一時刻，每個工件最多只在一臺機器上加工而且每臺機器最多只加工一個工件。問題的優(yōu)化目標便是找到一種所有工件加工順序使得從第一個工件在第一臺機器上加工開始到最后一個工件在最后一臺機器上加工完成所消耗的時間最短。若{ π1，π1，... ，πn-1，πn}表示一種工件加工順序，則依據(jù)reeves所述，完工時間c（i，πj）可以按照如下公式計算：

    由此，生產(chǎn)周期可以如下定義：

    記ⅱ是所有可能的加工順序集合，若π是****加工順序，則有：

    

    顯然，能很方便地用圖形來表達這個問題。對于rr eⅱ，對應(yīng)的圖形記為g（π）=(n，e)，如圖l所示。

   

    其中，n={l，2，…，m}．{l，2，…，n}是每個節(jié)點，(i，j)∈n權(quán)重為對應(yīng)處理時間p的節(jié)點。g（∈ⅱ）可看作一個m×n的矩形，且每個節(jié)點的權(quán)重由一決定。按照上述計算完成時間cmax的方法，可以對應(yīng)的在圖上找出相應(yīng)的一條從(1，1)到(m，n)的最長路徑，使之等于cmax(π)，稱為關(guān)鍵路徑。關(guān)鍵路徑中一定有(m—