基于云遺傳算法的軟件項目資源調(diào)度研究

《基于云遺傳算法的軟件項目資源調(diào)度研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、第2頁武漢科技大學(xué)碩士學(xué)位論文順序，以及各項任務(wù)的開始、結(jié)束和持續(xù)時間。雖然這種方法比較形象直觀，容易掌握，但是不能完全體現(xiàn)工作間的相互依賴關(guān)系，如果工作過早開始或者過晚開始，則不能體現(xiàn)其所造成的后果。在20世紀(jì)50年代中期，隨著網(wǎng)絡(luò)計劃技術(shù)發(fā)展，這種技術(shù)迅速滲透到項目調(diào)度領(lǐng)域中，以網(wǎng)絡(luò)圖的形式來展示項目的進(jìn)度計劃。它能比較明確的反映各活動時間的先后順序以及相互制約的邏輯關(guān)系，通過計算項目各項任務(wù)的時間參數(shù)，可找出整個計劃中的關(guān)鍵活動以及關(guān)鍵路線，反映出各活動的時差。這種方法的思想是通過縮短關(guān)鍵工作路線的持續(xù)時間，從而達(dá)到使工程的工期和費用優(yōu)化的效果。在實際的項

2、目執(zhí)行過程中一般都包含有大量不同的活動和各種人力、物力資源，在項目各項活動的組織安排中，有的活動是可以并發(fā)進(jìn)行的，有些活動則是必須在等待其他若干活動完成之后才能進(jìn)行的，這就構(gòu)成了資源受限項目調(diào)度問題。資源受限項目調(diào)度問題的研究初期，學(xué)者們主要集中于用數(shù)學(xué)規(guī)劃方法對這類優(yōu)化調(diào)度問題進(jìn)行建立模型和求解，并采用整數(shù)規(guī)劃手段來求解這一類優(yōu)化調(diào)度問題的精確解。在這之后提出了分支定界方法，這種方法能在較低計算成本的情況下獲得規(guī)模比較小的問題的精確解。在經(jīng)過很多學(xué)者的不斷努力和計算機(jī)技術(shù)快速發(fā)展的基礎(chǔ)上，分支定界法的求解能力和求解速度都得到了較大幅度的提高。Christofi

3、des等人引入沖突工作集和替代集概念，并提供了新的分支定界算[6]法研究方向。Demeulemeester等人發(fā)展了替代集的思想，提出基于最小延遲替代集概念的分支定界算法，并結(jié)合先進(jìn)的計算機(jī)技術(shù)對算法進(jìn)行了改進(jìn)，取得了[7]很好的效果。Patterson等人提出了基于緊前關(guān)系樹概念的分支定界算法，Sprecher等人針對對這種分支定界的方法又提出了多種定界的算法，他們采用PSPLIB中單目標(biāo)資源受限項目調(diào)度問題的480個問題進(jìn)行的求解實驗表明了該[8]算法是最好的精確算法之一。啟發(fā)式算法主要包括傳統(tǒng)的基于優(yōu)先規(guī)則的啟發(fā)式算法、采樣算法和智能算法等。Kelly提出

4、了串行調(diào)度方案和并行調(diào)度方案，并指出了重要的研究方向。隨后陸續(xù)有學(xué)者在這個基礎(chǔ)上提出了采用不同優(yōu)先規(guī)則的調(diào)度算法。采樣算法采用了與傳統(tǒng)基于優(yōu)先規(guī)則的算法不同的優(yōu)先權(quán)系數(shù)利用方式，并且引入了概率式選擇的方式。許多學(xué)者都在這方面進(jìn)行了研究，先后提出了隨機(jī)采樣算法(RandomSampling，RS)、帶有偏好的隨機(jī)采樣算法(BiasedRandomSampling，BRS)、基于后悔值的隨機(jī)采樣算法(Regret-basedRandomSampling，RBRS)，等等。在求解RCPSP時所用的智能優(yōu)化算法主要有模擬退火(SimulatedAnnealing，SA)

5、、禁忌搜索(TabuSearch，TS)和遺傳算法(GeneticAlgorithm，GA)等方法。另外，以色列學(xué)者高德拉特將約束理論(TheoryofConstraints，TOC)應(yīng)用于項目管理的領(lǐng)域，提出了基于關(guān)鍵鏈的項目管理理論，并由此發(fā)展出了一種新型項目調(diào)武漢科技大學(xué)碩士學(xué)位論文第3頁[9]度理論：基于關(guān)鍵鏈的項目調(diào)度理論。1.2.2國內(nèi)研究現(xiàn)狀項目資源調(diào)度優(yōu)化問題作為一個具有一定實踐意義的研究課題，很早就獲得國內(nèi)學(xué)者的廣泛關(guān)注，并開始不斷的在進(jìn)行各項研究工作。在使用早期的數(shù)學(xué)模型方法處理比較復(fù)雜的項目問題時，經(jīng)常很難入手。后來發(fā)展的一種直觀推斷法，即

6、線性規(guī)劃方法和網(wǎng)絡(luò)計劃技術(shù)，是現(xiàn)在應(yīng)用最廣的技術(shù)，但是這種方法過度依賴于問題本身，在應(yīng)用時針對“工期固定，資源平衡”和“資源有限，工期最短”這兩方面的問題，必須采取不同的方法來解決。并且，雖然在多數(shù)情況下這些方法可以產(chǎn)生出十分可靠的可行解，但是根據(jù)這種方法來獲得解的最優(yōu)性不容易判定。目前，項目管理資源優(yōu)化問題仍然主要集中于單目標(biāo)資源優(yōu)化，即在一些既定約束條件下，按照某一個目標(biāo)，通過不斷對進(jìn)度計劃進(jìn)行改進(jìn)來尋求滿意的方案。在對工期固定，資源均衡的進(jìn)行優(yōu)化調(diào)整的過程中，通常采用資源方差來判斷資源的均衡性，如果方差越小則資源均衡性越好，但是這種調(diào)整的過程通常要經(jīng)過一系

7、列非常繁瑣的推斷過程。自從資源受限項目調(diào)度問題被提出來之后，出現(xiàn)了非常多種類的資源受限項目調(diào)度問題。其中辛潤勤通過以下幾個方面對資源受限項目調(diào)度問題進(jìn)行了分類。(1)根據(jù)項目調(diào)度的目標(biāo)分類可以分為：項目工期的最小化；項目凈現(xiàn)值的最大化；資源均衡問題。(2)根據(jù)項目中資源的類型可以分為：非可再生資源，即資源的總量在整個項目工期內(nèi)具有一定約束條件，資源被消耗完后就不能再生；可再生資源，即這類資源的可使用量只在項目進(jìn)行的每個階段受到約束，比如某個階段的數(shù)量有限，但這個階段的任務(wù)一旦結(jié)束，資源使用完被釋放就可以再生；雙重資源約束：資源的可使用量除了在整個項目整個工期內(nèi)具

8、有約束，并且在項目工期中