考慮節(jié)能降耗的關(guān)鍵機(jī)器調(diào)度問題研究.pdf

1、傳統(tǒng)的生產(chǎn)調(diào)度問題通常假定作業(yè)的準(zhǔn)備時(shí)間和加工時(shí)間等參數(shù)在調(diào)度的過程中是不變的，然而在冶金、化工等一些高耗能領(lǐng)域，它們的取值可能與作業(yè)消耗的能源量有關(guān)并影響調(diào)度結(jié)果。因此，對(duì)于這些領(lǐng)域中關(guān)鍵生產(chǎn)環(huán)節(jié)上的關(guān)鍵機(jī)器調(diào)度問題，在提高其生產(chǎn)效率的同時(shí)也應(yīng)盡量?jī)?yōu)化其用能效率，從而達(dá)到節(jié)能降耗的目的。
　　 作為受能耗約束調(diào)度問題的研究基礎(chǔ)，本文首先研究了無能耗約束的多個(gè)關(guān)鍵機(jī)器調(diào)度問題，然后研究了三類考慮節(jié)能降耗的多個(gè)關(guān)鍵機(jī)器調(diào)度問題，包

2、括作業(yè)準(zhǔn)備時(shí)間受能耗約束的多個(gè)關(guān)鍵機(jī)器調(diào)度問題、作業(yè)加工時(shí)間受能耗約束的多個(gè)關(guān)鍵機(jī)器調(diào)度問題以及作業(yè)準(zhǔn)備時(shí)間與加工時(shí)間同時(shí)受能耗約束的多個(gè)關(guān)鍵機(jī)器調(diào)度問題。由于這些問題均是NP-hard的，難以在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)解，本文為它們?cè)O(shè)計(jì)了用于評(píng)價(jià)解的精確度的問題下界，并構(gòu)建了亞啟發(fā)式算法，從而在合理的時(shí)間范圍內(nèi)為大規(guī)模的問題提供高質(zhì)量的滿意解。主要研究工作和創(chuàng)新點(diǎn)如下：
　　 (1)研究了作業(yè)準(zhǔn)備時(shí)間和加工時(shí)間均不受能耗約束的多個(gè)

3、關(guān)鍵機(jī)器調(diào)度問題，調(diào)度的目標(biāo)是最小化最大完工時(shí)間。分析了現(xiàn)有LPT-ECT算法和Koulamas&Kyparisis的算法的優(yōu)缺點(diǎn)，提出了改進(jìn)的MLPT算法。針對(duì)此問題最優(yōu)解的特征，設(shè)計(jì)了一種解的表示方法，不僅能夠有效簡(jiǎn)化插入鄰域和交換鄰域的實(shí)現(xiàn)，也縮小了解空間；進(jìn)而用可變鄰域搜索和模擬退火算法進(jìn)一步改進(jìn)了啟發(fā)式算法解的精確度?？紤]作業(yè)準(zhǔn)備時(shí)間分布疏密的十種情形，構(gòu)造了大量的隨機(jī)數(shù)據(jù)實(shí)驗(yàn)。實(shí)驗(yàn)表明，所構(gòu)造的模擬退火算法能夠?qū)⑵骄鄬?duì)誤差

4、收斂到0.363％。同時(shí)，對(duì)于此問題的一個(gè)特例，當(dāng)作業(yè)具有相同的準(zhǔn)備時(shí)間且機(jī)器速度相同時(shí)，該模擬退火算法在解的精確度和計(jì)算效率兩個(gè)方面均明顯優(yōu)于現(xiàn)有Lee et al.給出的模擬退火算法。
　　 (2)研究了作業(yè)準(zhǔn)備時(shí)間受能耗約束的多個(gè)關(guān)鍵機(jī)器調(diào)度問題，調(diào)度的目標(biāo)是在限定最大完工時(shí)間的前提下最小化能耗總量，并假定作業(yè)準(zhǔn)備時(shí)間的能耗約束函數(shù)為一般減函數(shù)。給出了此問題的形式化描述，分析了此問題最優(yōu)解應(yīng)具有的特征，設(shè)計(jì)了作業(yè)左移和右移

5、兩種基本操作，討論了交換鄰域和插入鄰域生成對(duì)能耗總量影響的計(jì)算方法，構(gòu)建了此問題的可變鄰域搜索算法和模擬退火算法。為評(píng)價(jià)算法解的精確度，松弛了作業(yè)開始時(shí)間與其能耗約束函數(shù)之間的對(duì)應(yīng)關(guān)系，從而形成了一個(gè)指派問題，進(jìn)而可以用匈牙利方法獲得此松弛問題最優(yōu)解，并因此設(shè)計(jì)了一個(gè)下界。以線性遞減能耗約束函數(shù)為例，通過大量實(shí)驗(yàn)驗(yàn)證了算法的性能。另外，此模擬退火算法在求解具有線性遞減能耗約束函數(shù)或凸減能耗約束函數(shù)的單個(gè)關(guān)鍵機(jī)器調(diào)度問題時(shí)，其解的精確度也

6、分別優(yōu)于現(xiàn)有Janiak以及Kaspi&Shabtay等人的算法。
　　 (3)研究了加工時(shí)間受能耗約束的多個(gè)關(guān)鍵機(jī)器調(diào)度問題，調(diào)度的目標(biāo)是在限定可用能源總量的前提下最小化最大完工時(shí)間。給出了具有一般遞減能耗約束函數(shù)的該類問題的形式化描述和最優(yōu)解特征分析。為構(gòu)建快速的模擬退火算法，定義了決定性機(jī)器和非決定性機(jī)器，并重點(diǎn)對(duì)由某一決定性機(jī)器和最大完工時(shí)間最小的非決定性機(jī)器形成的局部解進(jìn)行優(yōu)化，從而使得搜索具有很強(qiáng)的針對(duì)性。對(duì)于具有線

7、性遞減能耗約束函數(shù)的該類問題，構(gòu)造的模擬退火算法能夠在0.875秒內(nèi)有效解決1000個(gè)作業(yè)規(guī)模的問題并將相對(duì)誤差控制在0.019946％以內(nèi)。對(duì)于具有凸減能耗約束函數(shù)的此類問題，借鑒了Shabtay&Kaspi的相關(guān)結(jié)論，將各機(jī)器加工的作業(yè)對(duì)應(yīng)到串聯(lián)并聯(lián)圖的等價(jià)工作量，建立的模擬退火算法能夠在0.1秒內(nèi)有效求解1000個(gè)作業(yè)規(guī)模的問題，其相對(duì)誤差也能夠控制在0.01％以內(nèi)。
　　 (4)研究了作業(yè)準(zhǔn)備時(shí)間與加工時(shí)間同時(shí)受能耗約束

8、的多個(gè)關(guān)鍵機(jī)器調(diào)度問題，調(diào)度的目標(biāo)是在限定最大完工時(shí)間的前提下最小化能耗總量，其中假定作業(yè)準(zhǔn)備時(shí)間和加工時(shí)間的能耗約束函數(shù)均為線性減函數(shù)。給出了此問題的形式化描述和最優(yōu)解特征分析，設(shè)計(jì)了作業(yè)左移、右移、壓縮和解壓縮四種基本操作，討論了交換、插入、壓縮和解壓縮四種鄰域生成方式及其對(duì)能耗總量影響的計(jì)算方法，構(gòu)建了相應(yīng)的可變鄰域搜索算法和模擬退火算法，設(shè)計(jì)了用于評(píng)價(jià)解的精確度的問題下界。大量隨機(jī)數(shù)據(jù)實(shí)驗(yàn)表明，所構(gòu)造的模擬退火算法能夠有效解決該