惡化環(huán)境下帶多個(gè)維修活動(dòng)的調(diào)度算法研究.pdf

1、調(diào)度問(wèn)題這些年已經(jīng)成為計(jì)算機(jī)科學(xué)中的一個(gè)重要問(wèn)題，其中計(jì)算復(fù)雜度分析，CPU調(diào)度算法的選擇，云計(jì)算與網(wǎng)格計(jì)算中的資源調(diào)度和任務(wù)調(diào)度等問(wèn)題已經(jīng)成為研究熱點(diǎn)。以上都和經(jīng)典的調(diào)度問(wèn)題有著緊密聯(lián)系。
　　 隨著調(diào)度理論的不斷發(fā)展，不同學(xué)科的不斷交叉，調(diào)度各個(gè)不同領(lǐng)域之間也有了越來(lái)越多的聯(lián)系，越來(lái)越多的學(xué)者現(xiàn)在開(kāi)始把經(jīng)典調(diào)度理論與計(jì)算機(jī)應(yīng)用背景結(jié)合起來(lái)考慮，試圖利用經(jīng)典調(diào)度模型來(lái)模擬計(jì)算機(jī)真實(shí)情況，然后利用經(jīng)典的解析方法來(lái)設(shè)計(jì)算法并求解問(wèn)

2、題。
　　 本文從磁盤整理和系統(tǒng)運(yùn)行速度之間的一系列關(guān)系描述入手，提出了一個(gè)具有現(xiàn)實(shí)意義的調(diào)度問(wèn)題，并對(duì)該調(diào)度問(wèn)題進(jìn)行建模，發(fā)現(xiàn)該模型在相關(guān)實(shí)際生產(chǎn)等領(lǐng)域都具有一定的適用，通過(guò)對(duì)國(guó)內(nèi)外研究進(jìn)行綜述提煉其理論價(jià)值和現(xiàn)實(shí)意義，并且設(shè)計(jì)了多項(xiàng)式時(shí)間最優(yōu)算法求解該問(wèn)題。
　　 對(duì)相應(yīng)調(diào)度問(wèn)題進(jìn)行建模后，分別針對(duì)單處理器環(huán)境和多處理器環(huán)境各自的一些目標(biāo)設(shè)計(jì)最優(yōu)算法進(jìn)行求解。對(duì)單處理器問(wèn)題，本文研究的是最小化所有任務(wù)的最大完成時(shí)間和

3、最小化所有任務(wù)的總完成時(shí)間;對(duì)多處理器器問(wèn)題，本文只研究了最小化所有任務(wù)的總完成時(shí)間。
　　 本文的主要研究工作分為下面幾個(gè)方面:
　　 (1)對(duì)國(guó)內(nèi)外相關(guān)問(wèn)題的調(diào)度模型進(jìn)行研究，包括研究問(wèn)題模型中所涉及的各個(gè)子模型和他們研究問(wèn)題的相關(guān)求解算法。其中前者主要工作是總結(jié)歸納前人提出的各個(gè)子模型的不同表達(dá)式，明白它們之間的不同和各自表達(dá)的意義。
　　 (2)針對(duì)從磁盤整理中延伸出的擴(kuò)展問(wèn)題，對(duì)其建立相應(yīng)的模型，其中多

4、處理器環(huán)境的模型是單處理器模型的擴(kuò)充，并給出模型中用到的數(shù)學(xué)符號(hào)。
　　 (3)經(jīng)過(guò)預(yù)備工作，首先對(duì)簡(jiǎn)單的單處理器環(huán)境模型進(jìn)行分析、推導(dǎo)、歸納，將問(wèn)題的原始調(diào)度模型最終巧妙地轉(zhuǎn)化為等價(jià)的指派問(wèn)題，從而推斷出單處理器下最小化所有任務(wù)總完成時(shí)間的目標(biāo)和最小化所有任務(wù)最大完成時(shí)間的目標(biāo)是多項(xiàng)式時(shí)間內(nèi)能夠解決的，并給出了各自問(wèn)題的計(jì)算時(shí)間復(fù)雜度。然后擴(kuò)展到相對(duì)復(fù)雜的多處理器模型，證明該環(huán)境下最小化所有任務(wù)總完成時(shí)間的目標(biāo)是多項(xiàng)式時(shí)間能夠