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

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

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

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

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

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

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