求解單機調(diào)度問題的啟發(fā)式算法研究.pdf

1、單機調(diào)度問題一直是調(diào)度領域的研究熱點，是生產(chǎn)調(diào)度問題的基礎及核心問題之一。大多數(shù)單機調(diào)度問題已經(jīng)被證明是NP難度的，因此，單機調(diào)度問題的研究不論是在當今國際學術界還是在實際生產(chǎn)領域都是一項具有挑戰(zhàn)性的重要課題。求解NP難度的問題一般有三種方法：精確算法、近似算法和啟發(fā)式算法。精確算法在求解規(guī)模較大的問題時，時間復雜度呈指數(shù)級增長，計算時間讓人無法忍受；近似算法雖然能在較短的時間內(nèi)找到解，但是，解的質(zhì)量跟實際需求相差較遠；啟發(fā)式算法在解決

2、大規(guī)模復雜問題時，有可能在合理的時間范圍內(nèi)給出一個滿意的解。啟發(fā)式算法在各個領域已經(jīng)受到越來越多的關注，逐漸成為求解NP難度問題的有力工具。本文的研究重點是設計求解單機調(diào)度問題的高效啟發(fā)式算法，并通過實驗對算法進行了分析和評價。
　　本研究主要內(nèi)容包括：⑴提出了一種新的“塊移動”的鄰域結(jié)構(gòu)（NBlock Move），該鄰域結(jié)構(gòu)擴大了鄰域的搜索空間，并且通過限制相關參數(shù)的取值范圍來提高搜索的有效性。⑵針對塊移動的鄰域結(jié)構(gòu)，提出了一種

3、高效的快速增量評估技術，提高了搜索效率。⑶在塊移動鄰域結(jié)構(gòu)以及對塊移動鄰域結(jié)構(gòu)的快速增量評估技術基礎上，提出了一種新的迭代局部搜索算法BILS來求解單機調(diào)度問題。⑷提出了一種基于“公共塊”概念的交叉算子BOX（Block Order Crossover Operator）。⑸提出了一種新的基于相似性和質(zhì)量的優(yōu)度函數(shù)的種群更新策略。⑹對比了不同的交叉算子和種群更新策略的組合在混合進化算法中處理單機調(diào)度問題時的表現(xiàn)，提出了一種高效的求解單機

4、調(diào)度問題的混合進化算法LOX⊕B。⑺用帶準備時間的單機加權(quán)延遲調(diào)度問題的120個公共算例對BILS進行了測試，BILS找到了所有120個算例的最優(yōu)解。對于算例18和24，BILS找到最優(yōu)解分別需要8586.6秒（≈2.4小時）和150169.22秒（≈41.7小時），而Tanaka和Araki的精確算法找到最優(yōu)解則分別需要兩個星期和30天。與其它幾種優(yōu)秀的啟發(fā)式算法組成的當前最好解比，BILS改進了34個算例的當前最好解，82個算例的解

5、與當前最好解持平。⑻用帶準備時間的單機加權(quán)延遲調(diào)度問題的120個公共算例對LOX⊕B進行測試，結(jié)果與當前文獻中最優(yōu)秀的啟發(fā)式算法的最好解OBK、ACO AP、DPSO、DDE、GVNS相比，改進最好解的個數(shù)分別為94、84、66、52、44。與本文新提出的BILS算法比，在平均值的優(yōu)度和找到最好解的平均時間上都有較大的提高，表明了LOX⊕B相對于BILS更加穩(wěn)定和高效。⑼用帶準備時間不帶權(quán)的單機延遲調(diào)度問題的64個公共算例對LOX⊕B進

6、行測試。LOX⊕B算法用6037.93秒（≈1.7小時）找到算例prob855的最好解“256”，改進了由Tanaka和Araki的精確算法用超過30天時間找到的當前最好解“258”，并找到了其余63個算例的最優(yōu)解或當前最好解。其中，對于算例prob751和prob851，LOX⊕B找到最優(yōu)解或當前最好解的時間分別為33678.64秒（≈9.4小時）和84405.88秒（≈23.4小時），而Tanaka和Araki的精確算法卻分別需要3