本文關(guān)鍵詞： 網(wǎng)格 網(wǎng)格工作流 調(diào)度 預(yù)算受限 蟻群算法　出處：《南京大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：網(wǎng)格作為一種新型計算模式,已經(jīng)成為新一代電子科研的計算基礎(chǔ)設(shè)施,世界各地學(xué)者為其巨大潛力所吸引,投入大量精力并取得了豐碩成果。作為網(wǎng)格環(huán)境中一項重要的基本服務(wù),網(wǎng)格工作流對網(wǎng)格應(yīng)用的構(gòu)建、執(zhí)行調(diào)度和管理監(jiān)控有著重要意義,極大地提高了網(wǎng)格應(yīng)用的自動化程度與效率。網(wǎng)格工作流調(diào)度是網(wǎng)格工作流系統(tǒng)的核心部分之一,也是網(wǎng)格高性能計算的重要支撐。它將工作流中的活動(計算任務(wù))分配到合適的網(wǎng)格資源上執(zhí)行(計算),協(xié)調(diào)各個活動的執(zhí)行以達(dá)到最好的目標(biāo)。網(wǎng)格工作流調(diào)度已被證明為NP困難問題,卻吸引著廣大工作流問題研究者。由于研究人員的突出貢獻(xiàn),網(wǎng)格工作流調(diào)度已獲得重要進(jìn)展,出現(xiàn)了如Min-Min、Max-Min、HEFT、表調(diào)度、聚簇調(diào)度等經(jīng)典的啟發(fā)式調(diào)度算法,也引進(jìn)了如遺傳算法、模擬退火算法、蟻群算法等元啟發(fā)式搜索算法。工作流調(diào)度者在使用網(wǎng)格資源執(zhí)行活動時,往往需要付出與執(zhí)行時間成正比的費(fèi)用。對于某些場景,用于支付資源所需的費(fèi)用是有限的,這就形成了預(yù)算受限的網(wǎng)格工作流。上述經(jīng)典或元啟發(fā)式算法都是性能驅(qū)動的調(diào)度算法,并不適用于預(yù)算受限的網(wǎng)格工作流。本文提出了一種基于蟻群優(yōu)化的算法以解決預(yù)算受限網(wǎng)格工作流調(diào)度問題。在應(yīng)用蟻群算法的過程中,為排除無效解對解空間的負(fù)面影響和對求解速度的干擾,本文創(chuàng)造性地提出了奢侈資金和奢侈率的概念,并給出了一種全新的計算節(jié)點(diǎn)之間距離的公式,綜合考慮預(yù)算的限制以及活動前驅(qū)的完成時間、數(shù)據(jù)通信時間、活動本身的執(zhí)行時間,使算法的求解質(zhì)量有了較大提升：經(jīng)本算法調(diào)度,計算密集型工作流的完工時間降低了約8%,而通信密集型工作流的完工時間則降低了約11%。
[Abstract]:Grid, as a new computing model, has become the computing infrastructure of the new generation of electronic scientific research, and scholars around the world are attracted by its great potential. As an important basic service in grid environment, grid workflow plays an important role in the construction, execution, scheduling and management of grid applications. Grid workflow scheduling is one of the core parts of grid workflow system. It is also an important support for grid high performance computing, which assigns the activities (computing tasks) in the workflow to the appropriate grid resources to execute (compute). Grid workflow scheduling has been proved to be a NP hard problem, but it attracts a large number of workflow problem researchers. Due to the outstanding contributions of researchers. Grid workflow scheduling has made important progress, such as Min-Min-Max-Min-HEFTT, table scheduling, clustering scheduling and other classical heuristic scheduling algorithms, such as genetic algorithms have been introduced. Simulated annealing algorithm, ant colony algorithm and other meta-heuristic search algorithms. Workflow schedulers often have to pay a cost proportional to the execution time when using grid resources to execute activities. For some scenarios. The cost required to pay for resources is limited, which results in a grid workflow with budget constraints. The classical or meta heuristic algorithms mentioned above are both performance-driven scheduling algorithms. This paper proposes an ant colony optimization algorithm to solve the scheduling problem of budget constrained grid workflow. In order to eliminate the negative effect of invalid solution on solution space and the interference of solution speed, this paper creatively puts forward the concepts of luxury capital and luxury rate, and gives a new formula to calculate the distance between nodes. Considering the limitation of the budget, the time of completion of the activity precursor, the time of data communication, and the execution time of the activity itself, the solution quality of the algorithm has been greatly improved: the algorithm is scheduled by this algorithm. The completion time of computationally intensive workflow is reduced by about 8 percent, while that of communication intensive workflow is reduced by about 11 percent.
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.02

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 沈慧云,王于同;一種新型網(wǎng)格工作流模型的研究[J];杭州電子科技大學(xué)學(xué)報;2005年05期

2 韓宗芬;何康;章勤;石宣化;;基于帶權(quán)有向圖的網(wǎng)格工作流數(shù)據(jù)傳輸策略[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2005年12期

3 李維宏;張紹華;祝精薈;;網(wǎng)格工作流研究現(xiàn)狀及存在問題[J];計算機(jī)科學(xué);2005年11期

4 余波;周龍驤;鐘錫昌;張倪;;網(wǎng)格工作流技術(shù)綜述[J];計算機(jī)工程;2006年02期

5 孫滿囤;李俊山;韓先鋒;;基于擴(kuò)展計算網(wǎng)的分層動態(tài)網(wǎng)格工作流研究[J];系統(tǒng)工程與電子技術(shù);2006年03期

6 鄭然;金海;章勤;;網(wǎng)格工作流資源層次模型與訪問機(jī)制[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2006年S1期

7 王莉;李志蜀;殷鋒;;基于網(wǎng)格工作流的政務(wù)協(xié)同研究[J];微電子學(xué)與計算機(jī);2006年S1期

8 王勇;胡春明;杜宗霞;;服務(wù)質(zhì)量感知的網(wǎng)格工作流調(diào)度[J];軟件學(xué)報;2006年11期

9 馮紅;王陸;楊卉;;網(wǎng)格工作流技術(shù)及其在教師專業(yè)發(fā)展中的應(yīng)用研究[J];電化教育研究;2007年05期

10 王勇;;網(wǎng)格工作流中轉(zhuǎn)移概率的計算方法研究[J];計算機(jī)工程與應(yīng)用;2007年21期

相關(guān)會議論文 前6條

1 吳宇進(jìn);劉家茂;李煒;顧寧;;支持輸入反饋和健壯性增強(qiáng)的網(wǎng)格工作流自動生成方法[A];第二十一屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2004年

2 劉雁飛;梁正友;;網(wǎng)格工作流研究問題與現(xiàn)狀[A];2007北京地區(qū)高校研究生學(xué)術(shù)交流會通信與信息技術(shù)會議論文集（下冊）[C];2008年

3 向培素;田珂;黃勤珍;;網(wǎng)格工作流動態(tài)調(diào)度研究[A];2007年全國開放式分布與并行計算機(jī)學(xué)術(shù)會議論文集(下冊)[C];2007年

4 趙正德;王曉華;石秀麗;;網(wǎng)格工作流模型和協(xié)同機(jī)制的研究與實現(xiàn)[A];2005年全國開放式分布與并行計算學(xué)術(shù)會議論文集[C];2005年

5 張紹華;丁志剛;宗宇偉;顧寧;;網(wǎng)格工作流動態(tài)調(diào)度算法研究[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2006年

6 王莉;李志蜀;殷鋒;;基于網(wǎng)格工作流的政務(wù)協(xié)同研究[A];2006年全國開放式分布與并行計算機(jī)學(xué)術(shù)會議論文集（三）[C];2006年

相關(guān)博士學(xué)位論文 前10條

1 張紹華;網(wǎng)格工作流關(guān)鍵技術(shù)研究[D];復(fù)旦大學(xué);2004年

2 李璽;面向可靠性的網(wǎng)格工作流調(diào)度模型與算法研究[D];中南大學(xué);2011年

3 余波;網(wǎng)格工作流中服務(wù)選擇策略的研究[D];中國科學(xué)院研究生院（計算技術(shù)研究所）;2006年

4 程渤;服務(wù)網(wǎng)格工作流管理技術(shù)研究[D];電子科技大學(xué);2006年

5 袁逸萍;制造網(wǎng)格工作流研究及實現(xiàn)[D];上海大學(xué);2006年

6 郭文彩;面向服務(wù)的網(wǎng)格工作流關(guān)鍵技術(shù)研究[D];北京科技大學(xué);2006年

7 曹雷;基于Agent的網(wǎng)格工作流技術(shù)研究[D];上海交通大學(xué);2007年

8 劉兵;基于Web服務(wù)組合的網(wǎng)格工作流研究[D];中國科學(xué)技術(shù)大學(xué);2007年

9 曹海軍;面向服務(wù)的網(wǎng)格工作流關(guān)鍵問題研究[D];華中科技大學(xué);2009年

10 鄭然;網(wǎng)格計算環(huán)境下工作流關(guān)鍵技術(shù)的研究[D];華中科技大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

1 楊歡;基于預(yù)算受限的網(wǎng)格工作流調(diào)度算法研究[D];南京大學(xué);2014年

2 陸海燕;網(wǎng)格工作流中的資源評估與選擇策略分析與實現(xiàn)[D];內(nèi)蒙古大學(xué);2008年

3 趙小偉;網(wǎng)格工作流可靠性仿真與評測[D];山東科技大學(xué);2009年

4 鄭凱;網(wǎng)格工作流的研究與完善[D];太原理工大學(xué);2006年

5 喬宏;網(wǎng)格工作流復(fù)合技術(shù)[D];上海交通大學(xué);2007年

6 薛巧麗;網(wǎng)格工作流驗證方法的研究[D];華北電力大學(xué)（河北）;2008年

7 田國忠;基于資源預(yù)測的網(wǎng)格工作流調(diào)度算法研究[D];新疆大學(xué);2008年

8 王亞東;網(wǎng)格工作流在鐵路超限超重貨物運(yùn)輸中的應(yīng)用研究[D];北京交通大學(xué);2009年

9 王琴;基于負(fù)載均衡的網(wǎng)格工作流調(diào)度算法的研究[D];廈門大學(xué);2009年

10 鄧定蘭;截止期約束的網(wǎng)格工作流費(fèi)用優(yōu)化算法研究[D];新疆大學(xué);2010年

，

本文編號：1488271