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

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

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

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