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

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

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

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

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