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

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

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

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

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