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

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

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

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