預(yù)測調(diào)度的算法研究和性能分析.pdf

1、現(xiàn)代制造企業(yè)在經(jīng)濟全球化的環(huán)境下面臨著前所未有的競爭壓力，對生產(chǎn)管理提出了更高的要求。調(diào)度是對稀缺資源進行優(yōu)化分配。一個好的調(diào)度可以使生產(chǎn)企業(yè)提高生產(chǎn)效率、節(jié)約生產(chǎn)成本，從而為企業(yè)帶來巨大的經(jīng)濟效益。 大部分調(diào)度問題都是NP-hard的，求解這類問題，一種常用的方式就是找到有效的啟發(fā)式算法，以合理的計算代價求出較好的結(jié)果。過去大量的研究成果集中在離線算法和在線算法方面，對可以預(yù)測到部分未來信息的情況考慮較少。本文將預(yù)測控制的思想

2、應(yīng)用到調(diào)度問題中，提出了預(yù)測調(diào)度算法，并研究了其在三類典型的調(diào)度問題中對改善性能的作用。歸納起來，本論文主要做了以下三個方面的工作： 針對單機加工、有到達時間約束、最小化總加權(quán)完工時間的調(diào)度問題，提出了一種預(yù)測調(diào)度算法，證明了預(yù)測調(diào)度算法在該問題上的競爭比下界為2，和在線算法的競爭比相同。這表明，在性能保證方面預(yù)測調(diào)度算法和在線算法是相同的。但對一般情況的實例進行了大量的仿真，從統(tǒng)計的意義上說明預(yù)測調(diào)度算法優(yōu)于在線算法的。

3、 針對同速機，有到達時間約束，最小化最大完工時間的問題上，提出了一種預(yù)測調(diào)度算法。通過仿真，發(fā)現(xiàn)該算法在極差情況下的性能比小于原來最優(yōu)的在線算法，這說明該算法的性能保證可能優(yōu)于在線算法。對一般情況下的實例也做了大量的仿真，結(jié)果說明，預(yù)測調(diào)度算法的性能優(yōu)于在線算法。 針對一類信息不準確的Job shop 問題，提出了一種預(yù)測調(diào)度算法。在預(yù)測窗口內(nèi)，使用移動瓶頸算法求解子問題；在窗口外，用較簡單規(guī)則進行虛擬調(diào)度。通過仿真，與靜態(tài)算