1、工件車間調度問題具有很高的理論價值和實際價值。人們的經驗表明，它是最難的組合優(yōu)化問題之一。當前學者們的研究重點是設計求解該問題的高效近似算法。 當前文獻中工件車間調度問題的問題描述很難理解。擬物方法可用來克服這個困難。擬物方法來源于物理世界。工件車間調度問題在用擬物方法進行描述后，變得很容易理解。 雙前沿貪心算法是一種新的基本算法。它依次指定所有工序的開工時刻。該算法指定雙前沿工序在其最早合法開工時刻開工。聯絡圖算法是文

2、獻中經常出現的一種基本算法。雙前沿貪心算法生成調度的質量一致地高于等于聯絡圖算法。雙前沿貪心算法的計算時間比聯絡圖算法略長。 鄰域搜索算法是以雙前沿貪心算法為基礎的。鄰域結構的定義是基于關鍵路徑的。精心設計的鄰域結構是鄰域搜索算法的一個關鍵所在。這種鄰域搜索算法的創(chuàng)新之處在于當算法搜索到局部最優(yōu)解時，并不是消極地停止搜索，而是在鄰域中最好的三個鄰點中均勻地隨機選取一個鄰點，接受這個鄰點，積極地繼續(xù)搜索。 單機調度算法恰好

3、改變一臺機器上的工序的排列，保持其它機器上的工序的排列不變。單機調度算法可推廣到雙機調度算法。雙機調度算法恰好改變兩臺機器上的工序的排列，保持其它機器上的工序的排列不變。 鄰域搜索算法容易陷入局部最優(yōu)解。單機調度/雙機調度和隨機擾動這三種跳坑策略可用于跳出局部最優(yōu)解，把搜索引向有希望的區(qū)域，從而提高搜索效率。 以雙前沿貪心算法為基礎，結合了鄰域搜索算法/單機調度算法和跳坑策略而形成的混合算法可用于求解工件車間調度問題。用

4、這種混合算法計算了138個國際公認的標準問題實例。這些標準問題實例中規(guī)模最小的是工件數和機器數均為6的問題實例，規(guī)模最大的是工件數和機器數分別為100和20的問題實例。 這種混合算法的計算結果可概括為以下三點。 第一，所得混合算法生成解的質量比當前國際文獻中最好的近似算法BV-best高。BV-best算法共計算了131個標準問題實例。其中27個實例混合算法生成解的質量比BV-best高，16個實例混合算法生成解的質量比

5、BV-best低，88個實例混合算法生成解的質量和BV-best相等。 第二，對一個名為TA15的標準問題實例，混合算法給出了一個makespan為1339的調度。這個調度優(yōu)于當前文獻中報導的最好的調度。在當前文獻中，計算TA15所得到的最好的調度的makespan是1340。 第三，這種混合算法是確定的，具有強烈的統(tǒng)一性，其中不包含任何隨具體問題而變的待調參數。BV-best是不確定的。 混合算法的研究是一個很

6、有希望的領域。 另外，置換流水車間調度問題和貨郎擔問題是和工件車間調度問題相關的兩個問題。置換流水車間調度問題可用一種鄰域搜索算法來求解。這種鄰域搜索算法計算了一組共29個國際公認的標準問題實例。計算結果表明，鄰域搜索算法的效率比當前國際文獻中的一種改進的遺傳算法高。改進的鄰域搜索算法結合了構造型算法和鄰域搜索算法。改進的鄰域搜索算法的效率比鄰域搜索算法高。貨郎擔問題可用一種鄰域搜索算法來求解。這種鄰域搜索算法基于一種新的貪心式