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

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

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

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

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

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

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