求解工件車間調(diào)度問題的一種高效近似算法.pdf

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

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

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

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

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

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