最小化總完工時間預(yù)測調(diào)度算法的設(shè)計(jì)與分析.pdf

1、調(diào)度算法的性能分析，由于其在實(shí)際應(yīng)用中對提高生產(chǎn)效率起著至關(guān)重要的作用，從而吸引了眾多學(xué)者的興趣。而預(yù)測調(diào)度算法由于可以充分利用生產(chǎn)過程中的任務(wù)信息，所以能比只利用當(dāng)前時刻信息的在線算法更有效地進(jìn)行調(diào)度。而相比起必須提前知道所有信息進(jìn)行優(yōu)化的離線算法，預(yù)測調(diào)度算法對加工環(huán)境的信息約束又有著很強(qiáng)的適應(yīng)性。然而，目前已有文獻(xiàn)針對預(yù)測調(diào)度算法的性能分析還幾乎是空白。 本文主要借鑒在線算法性能分析的手段和方法，并發(fā)展出實(shí)例轉(zhuǎn)換的全新分析

2、方法，對預(yù)測調(diào)度算法在最小化完工時間問題中的設(shè)計(jì)與性能分析進(jìn)行了研究。首先，通過算法集劃分和構(gòu)造相應(yīng)極端實(shí)例，我們得到了1|rj|∑ C j 問題預(yù)測調(diào)度算法的競爭比下界，從而確定預(yù)測調(diào)度算法針對該問題的性能極限。之后，我們分別針對1|rj|∑ C j和 P r|rj|∑ C j 問題設(shè)計(jì)了三種單步預(yù)測調(diào)度算法，從競爭比和平均性能比角度進(jìn)行了性能分析，發(fā)現(xiàn)它們都遠(yuǎn)優(yōu)于在線算法。1）對于1|rj|∑ C j 問題，從在線算法D-SPT

3、出發(fā)，設(shè)計(jì)出兩種單步預(yù)測調(diào)度算法，在性能上大大改善了原在線算法。2）在對單步預(yù)測調(diào)度算法P-SPT1 競爭比的求解中，創(chuàng)造性地提出了實(shí)例轉(zhuǎn)換的求解思想，并獲得了成功。這也是本文的重要理論貢獻(xiàn)。3）通過劃分算法集和構(gòu)造特殊實(shí)例的手段，求解了1|rj|∑ C j 問題預(yù)測調(diào)度算法的競爭比下界。從相反的角度，刻畫了預(yù)測調(diào)度算法隨著預(yù)測步長的性能極限。4）對于更復(fù)雜的1|rj|∑ C j 問題，通過借鑒OMPR 算法的兩層調(diào)度結(jié)構(gòu)，并利用已構(gòu)造