無等待調(diào)度的鄰域搜索方法研究.pdf

1、無等待流水車間調(diào)度問題是一類應(yīng)用廣泛的組合優(yōu)化問題。在常用優(yōu)化目標函數(shù)下，無等待流水車間調(diào)度都是NP難問題，最優(yōu)化算法由于具有指數(shù)時間復(fù)雜度，從而只適用于中小規(guī)模實例；對大規(guī)模實例，常采用啟發(fā)式方法以在合理時間求得次優(yōu)解。鄰域搜索算法是一類最為常用的啟發(fā)式方法。
　　 本文針對最大誤工時間、總完工時間以及最大完工時間三個目標函數(shù)，研究無等待流水車間調(diào)度問題的鄰域搜索算法，主要工作有：(1)基于任務(wù)塊分解的分析方法。通過將當前解分

2、解為任務(wù)塊，給出了四個常用基本操作在最大誤工時間目標函數(shù)下的加速性質(zhì)，并設(shè)計了一個對偶倒置鄰域。借助這些性質(zhì)，搜索插入、交換、倒置以及對偶倒置鄰域的時間復(fù)雜度以及NEH構(gòu)造算法的時間復(fù)雜度均從O(n3)降至O(n2)。(2)鄰域擴展及其加速性質(zhì)。通過將任務(wù)塊分解方法推廣到鄰域設(shè)計，給出了三個新的較大規(guī)模鄰域：D(n4)規(guī)模的不相鄰任務(wù)塊交換鄰域以及O(n3)規(guī)模的相鄰任務(wù)塊對換鄰域和擴展單任務(wù)交換鄰域，分析了三個鄰域基本操作在最大誤工時

3、間和總完工時間目標函數(shù)下的加速性質(zhì)。這些鄰域亦可作為通用鄰域派生出新的O(n2)規(guī)模的鄰域。(3)基于最短路徑的鄰域搜索算法。針對最大完工時間目標函數(shù)，為指數(shù)規(guī)模的動態(tài)規(guī)劃鄰域，設(shè)計了一個O(n2)時間復(fù)雜度的動態(tài)規(guī)劃搜索算法；為O(n4)規(guī)模的不相鄰任務(wù)塊交換鄰域，通過重用中間計算結(jié)果，設(shè)計了一個O(n2)時間復(fù)雜度的搜索算法。兩個算法均等價于搜索對應(yīng)有向無環(huán)圖中的一條最短路徑。(4)有效的元啟發(fā)方法。通過選取合適的禁忌屬性及鄰域基本

4、操作禁忌狀態(tài)的條件，給出了一個有效的禁忌搜索算法：選取相鄰任務(wù)對作為禁忌屬性，鄰域基本操作的禁忌狀態(tài)是該基本操作試圖添加到當前解的相鄰任務(wù)對的禁忌狀態(tài)的合??；采用二維矩陣作為禁忌表的數(shù)據(jù)結(jié)構(gòu)，使得該禁忌表可以容納多種鄰域并可在常量時間內(nèi)判鄰域基本操作的禁忌狀態(tài)。通過在迭代局部搜索中使用變換鄰域下降，提出了一個迭代變換鄰域搜索算法，并比較了不同鄰域組合用于迭代變換鄰域搜索算法求解總完工時間以及最大完工時間目標函數(shù)時的相對性能。