面向時間和費用約束的云工作流調(diào)度研究.pdf

1、云計算作為一種新型計算模式和商業(yè)服務(wù)模型，可以滿足不同用戶對計算和存儲多樣化服務(wù)質(zhì)量需求，而云工作流調(diào)度是實現(xiàn)這些服務(wù)質(zhì)量需求的重要支撐?，F(xiàn)有云工作流相關(guān)研究主要存在兩個問題：
　　1、在云環(huán)境的調(diào)度中，大部分基于費用和時間約束調(diào)度問題的研究致力于如何優(yōu)化最終的調(diào)度費用，而將工作流的完成時間作為約束條件，對完成時間目標(biāo)的優(yōu)化被忽略或效果優(yōu)化不理想；
　　2、基于隨機搜索算法的調(diào)度策略搜索方法雖然搜索結(jié)果精度較高，但是在較大規(guī)

2、模工作流的情況下，算法的執(zhí)行時間較長，搜索效率仍存在提升的空間。
　　針對上述兩個問題，本文的主要研究內(nèi)容包括：
　?。?）通過調(diào)研現(xiàn)有的云工作流調(diào)度研究成果，從用戶的服務(wù)質(zhì)量約束入手研究時間和費用約束下的云工作流調(diào)度問題，采用有向無環(huán)圖（Directed Acyclic Graph，DAG）來描述工作流的結(jié)構(gòu)，建立了工作流模型、計算資源模型、時間和費用模型等，為后續(xù)的研究工作打下基礎(chǔ)。
　　（2）為了滿足用戶對工作流

3、完成時間的優(yōu)化需求，并且考慮到用戶有限的費用預(yù)算，即能在滿足用戶的費用預(yù)算約束的條件下最小化工作流的完成時間，本文針對費用約束工作流調(diào)度問題，提出了基于粒子群優(yōu)化算法的云工作流調(diào)度方法，尋找較優(yōu)的調(diào)度策略。本文使用不同規(guī)模的科學(xué)工作流作為實驗對象，將本文提出的方法同近年來提出的啟發(fā)式算法進行實驗評估對比后，可以發(fā)現(xiàn)，基于粒子群的調(diào)度方法能夠?qū)ふ业骄容^高的結(jié)果，但在算法的執(zhí)行效率上要低于基于啟發(fā)式的調(diào)度方法。
　?。?）為了提高算

4、法的搜索效率，快速找到較優(yōu)的調(diào)度方案，即能在滿足用戶的截止時間約束的條件下最小化調(diào)度費用，本文針對時間約束工作流調(diào)度問題，提出了融合關(guān)鍵路徑思想的粒子群優(yōu)化算法。該算法利用關(guān)鍵路徑進行粒子初始化和搜索階段的篩選處理，進而達到快速搜索的效果，不但顯著提高搜索結(jié)果的精度，而且減少了搜索的計算時間。本文將改進算法和傳統(tǒng)粒子群優(yōu)化算法從準(zhǔn)確度、算法效率和兩個階段所占時間比三個方面進行了實驗對比。實驗數(shù)據(jù)證明，改進算法不僅在運行時間上少于傳統(tǒng)粒子