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

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

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

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

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

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

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

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

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