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

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

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

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