滾動(dòng)時(shí)域調(diào)度方法及其性能分析研究.pdf

1、大規(guī)模調(diào)度問題的計(jì)算難處理性和實(shí)際調(diào)度環(huán)境的動(dòng)態(tài)不確定性是調(diào)度問題復(fù)雜性的重要體現(xiàn)。滾動(dòng)時(shí)域調(diào)度方法是處理這兩方面復(fù)雜調(diào)度環(huán)境的一種有效的通用方法，雖然已有一些關(guān)于滾動(dòng)時(shí)域調(diào)度方法應(yīng)用研究，但是初步和有限的，在其理論和應(yīng)用兩方面還存在很大的研究空間。 本論文研究處理靜態(tài)和動(dòng)態(tài)不確定下的大規(guī)模調(diào)度問題的滾動(dòng)時(shí)域方法，將滾動(dòng)時(shí)域調(diào)度方法的機(jī)理歸于預(yù)測控制的廣義原理之下。首先給出了滾動(dòng)時(shí)域調(diào)度策略的規(guī)范化描述。對單機(jī)調(diào)度問題，提出了一

2、種基于初始調(diào)度的滾動(dòng)調(diào)度策略，在其子問題中考慮了局部目標(biāo)和全局目標(biāo)的一致性，對這種滾動(dòng)調(diào)度策略進(jìn)行了性能分析。這是一種全局性能不斷改善的滾動(dòng)調(diào)度策略，本論文把它用于三種不同的信息環(huán)境：全局信息已知的確定性環(huán)境、全局信息不全的動(dòng)態(tài)環(huán)境和存在機(jī)器故障的動(dòng)態(tài)擾動(dòng)環(huán)境。最后將一類JobShop調(diào)度和重調(diào)度問題分解為單機(jī)調(diào)度問題來求解。歸納起來，本論文主要做了以下六個(gè)方面的研究工作： ●從預(yù)測控制的廣義原理出發(fā)，剖析滾動(dòng)時(shí)域調(diào)度方法的內(nèi)在

3、機(jī)理和關(guān)鍵技術(shù)，建立了滾動(dòng)時(shí)域調(diào)度策略的一般描述框架，規(guī)范滾動(dòng)時(shí)域調(diào)度方法的有關(guān)概念和參數(shù)的定義。 ●對已有滾動(dòng)時(shí)域調(diào)度方法的調(diào)度子問題進(jìn)行改進(jìn)。通過在調(diào)度子問題的局部目標(biāo)函數(shù)中加入一個(gè)終端懲罰項(xiàng)，在局部目標(biāo)中考慮了與全局目標(biāo)的一致性，并證明了一個(gè)已有分枝定界方法的修正算法可以精確求解終端懲罰調(diào)度子問題。大量的仿真實(shí)驗(yàn)比較了改進(jìn)的滾動(dòng)時(shí)域調(diào)度方法和已有方法，計(jì)算結(jié)果說明了子問題改進(jìn)的成功和有效。 ●對于全局信息已知的大規(guī)

4、模靜態(tài)調(diào)度問題提出了一種基于初始調(diào)度的滾動(dòng)調(diào)度策略，建立起滾動(dòng)調(diào)度進(jìn)程中對全局調(diào)度及其性能的描述。對一類性能指標(biāo)可分的單機(jī)調(diào)度模型采用終端約束調(diào)度子問題，對單機(jī)調(diào)度模型采用終端懲罰調(diào)度子問題，由于在局部子問題中考慮了全局目標(biāo)，可在滾動(dòng)進(jìn)程中控制全局調(diào)度性能的變化趨勢，從而保證了全局調(diào)度性能不斷改善，避免了最差調(diào)度解的可能。這是一種兩階段調(diào)度方法，大量的仿真實(shí)驗(yàn)結(jié)果表明，相對已有的兩階段算法和滾動(dòng)時(shí)域方法，在算法復(fù)雜度沒有增加的前提下，在

5、大多數(shù)情況下解的質(zhì)量皆有一致的改善。 ●將基于初始調(diào)度的終端懲罰滾動(dòng)調(diào)度策略用于全局信息不全的動(dòng)態(tài)調(diào)度問題，提出了一種兩級滾動(dòng)調(diào)度策略。首先提出了虛擬調(diào)度的概念，解決了信息不全時(shí)全局調(diào)度的描述問題。第一級滾動(dòng)調(diào)度是建立在預(yù)測窗口之上的預(yù)調(diào)度，第二級是建立在滾動(dòng)窗口之上的局部調(diào)度，性能分析表明兩級滾動(dòng)都能改善全局調(diào)度的性能。仿真實(shí)驗(yàn)表明在絕大多數(shù)情況下這一兩級滾動(dòng)調(diào)度相對已有滾動(dòng)時(shí)域方法有優(yōu)勢。 ●研究了機(jī)器故障擾動(dòng)下的大

6、規(guī)模單機(jī)重調(diào)度問題。考慮重調(diào)度的效率(調(diào)度性能)和穩(wěn)定性(與原始調(diào)度的偏離)兩個(gè)指標(biāo)，采用部分調(diào)度策略處理計(jì)算復(fù)雜性，在部分調(diào)度中反映全局的雙目標(biāo)。當(dāng)出現(xiàn)多次機(jī)器故障時(shí)，采用事件驅(qū)動(dòng)的滾動(dòng)部分重調(diào)度，性能分析的結(jié)論證明了歷次的部分重調(diào)度目標(biāo)與全局重調(diào)度目標(biāo)的一致性。計(jì)算結(jié)果表明，所提出的部分重調(diào)度策略可以對重調(diào)度質(zhì)量和計(jì)算代價(jià)進(jìn)行折中，相對右移重調(diào)度在保持調(diào)度的效率目標(biāo)或僅有微小犧牲的前提下，調(diào)度的穩(wěn)定性目標(biāo)可以大大改善。 ●對