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

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

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

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

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