一種成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略

鄧見(jiàn)光，趙躍龍，袁華強(qiáng)，劉 霖

(1.東莞理工學(xué)院工程技術(shù)研究院，廣東東莞523808;2.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東廣州510006)

云計(jì)算技術(shù)是互聯(lián)網(wǎng)迅速發(fā)展的必然結(jié)果.在云計(jì)算平臺(tái)中，用戶無(wú)需購(gòu)買和部署IT基礎(chǔ)設(shè)施，而只需按需租用各類硬件、軟件、計(jì)算設(shè)備以及存儲(chǔ)資源，并通過(guò)向云平臺(tái)提交任務(wù)來(lái)實(shí)現(xiàn)計(jì)算任務(wù)與存儲(chǔ)業(yè)務(wù).在進(jìn)行任務(wù)調(diào)度時(shí)，作為一種商業(yè)服務(wù)，云計(jì)算系統(tǒng)在滿足用戶QoS(quality of service)要求的同時(shí)，還應(yīng)盡可能地最大化其服務(wù)收益.給定任務(wù)和計(jì)算資源集，云計(jì)算任務(wù)調(diào)度問(wèn)題就是為了尋找一種調(diào)度策略，基于該策略，云平臺(tái)將用戶任務(wù)分別指派給不同的計(jì)算節(jié)點(diǎn)，以實(shí)現(xiàn)大量任務(wù)在計(jì)算資源之間的合理分配和高效執(zhí)行.任務(wù)調(diào)度是一個(gè)NP完全問(wèn)題，其不可能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)求得全局最優(yōu)解.目前，研究人員提出了多種方法來(lái)逼近其最優(yōu)解，然而現(xiàn)有調(diào)度方法大多耗時(shí)過(guò)長(zhǎng)且結(jié)果不可預(yù)測(cè)，很難應(yīng)用于實(shí)際的云計(jì)算環(huán)境.遺傳算法具有較好的全局搜索能力，可以快速遍歷一個(gè)較大的搜索空間，并且能夠避免陷入局部最優(yōu)解，可以很好地應(yīng)用于復(fù)雜的目標(biāo)優(yōu)化問(wèn)題.

根據(jù)上述分析，從云服務(wù)提供方的角度出發(fā)，基于遺傳算法，文中提出一種成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略.提出的方法充分考慮云服務(wù)的商業(yè)特性，在滿足用戶任務(wù)QoS要求的前提下，盡可能地最大化云環(huán)境單位計(jì)算開(kāi)銷的服務(wù)收益.

1 相關(guān)工作

近年來(lái)，任務(wù)調(diào)度問(wèn)題吸引了大量研究人員參與其中，在提出的眾多方法中，經(jīng)典的Min-min［1］和Max-min［2］算法常被用來(lái)作為評(píng)價(jià)一個(gè)調(diào)度算法優(yōu)劣的標(biāo)準(zhǔn).

云計(jì)算基于虛擬化技術(shù)，將分布在不同位置的資源進(jìn)行整合，形成統(tǒng)一的資源池，向廣大用戶提供各種計(jì)算或存儲(chǔ)服務(wù).云計(jì)算的服務(wù)器規(guī)模龐大，廣大用戶可按需購(gòu)買任意規(guī)模的資源或服務(wù)，以處理各類計(jì)算密集型或數(shù)據(jù)密集型任務(wù).根據(jù)不同的任務(wù)類型，目前有大量的調(diào)度方法被提出.對(duì)于計(jì)算密集型應(yīng)用，文獻(xiàn)［3］提出了一種高效的任務(wù)調(diào)度方法，該方法可并行處理分布于異構(gòu)平臺(tái)同時(shí)包含獨(dú)立任務(wù)袋的多個(gè)應(yīng)用.文獻(xiàn)［4］提出了一種預(yù)算約束的調(diào)度器，對(duì)于QoS要求各異的任務(wù)，該調(diào)度器可分別為其分配相應(yīng)性能指標(biāo)的計(jì)算資源;相對(duì)于固定的任務(wù)預(yù)算，該調(diào)度器可以最小化總的任務(wù)完成時(shí)間.文獻(xiàn)［5］提出了一種動(dòng)態(tài)云環(huán)境下的工作流任務(wù)調(diào)度策略，該策略充分考慮了科學(xué)工作流的任務(wù)特征，并基于概率機(jī)制不斷調(diào)整其調(diào)度定價(jià)模型以適應(yīng)云計(jì)算環(huán)境的動(dòng)態(tài)多變特性.考慮到在數(shù)據(jù)密集型應(yīng)用中，數(shù)據(jù)存儲(chǔ)之間往往相互關(guān)聯(lián)，文獻(xiàn)［6］開(kāi)發(fā)了一個(gè)數(shù)據(jù)重用模型，并在此基礎(chǔ)上提出了一個(gè)啟發(fā)式的任務(wù)調(diào)度算法;文獻(xiàn)［7］則通過(guò)同時(shí)考慮調(diào)度任務(wù)的數(shù)據(jù)需求和計(jì)算需求，提出了一種自適應(yīng)的任務(wù)調(diào)度方案.前述兩種方案均可以很好地應(yīng)用于數(shù)據(jù)密集型的任務(wù)調(diào)度.

不僅如此，現(xiàn)有方法常常應(yīng)用計(jì)算資源屬性和調(diào)度任務(wù)的QoS參數(shù)來(lái)對(duì)任務(wù)的完成時(shí)間進(jìn)行預(yù)測(cè)，以輔助調(diào)度決策.文獻(xiàn)［8］基于統(tǒng)計(jì)分析的觀點(diǎn)，通過(guò)對(duì)基準(zhǔn)測(cè)試集和編譯器進(jìn)行分析，提出了一種任務(wù)完成時(shí)間的預(yù)測(cè)方法.文獻(xiàn)［9］通過(guò)對(duì)一個(gè)時(shí)間序列內(nèi)的歷史數(shù)據(jù)進(jìn)行統(tǒng)計(jì)建模，基于一個(gè)K近鄰的方法來(lái)實(shí)現(xiàn)對(duì)任務(wù)完成時(shí)間的預(yù)測(cè).文獻(xiàn)［10］提出了一種多策略的協(xié)同預(yù)測(cè)模型，并引入一個(gè)預(yù)測(cè)精度保障的概念來(lái)對(duì)任務(wù)完成時(shí)間的預(yù)測(cè)精度進(jìn)行定量評(píng)估.

云計(jì)算本質(zhì)上是一種商業(yè)服務(wù)模型，其在滿足廣大用戶任務(wù)調(diào)度QoS要求的同時(shí)，還應(yīng)盡可能地增加其服務(wù)收益.因此，上述的調(diào)度策略雖能夠滿足用戶調(diào)度的QoS要求，但并不太適應(yīng)于云計(jì)算這一商業(yè)計(jì)算模式.文中基于云的商業(yè)特性，從云服務(wù)提供方的角度出發(fā)，提出一種成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略.

2 成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略

2.1 相關(guān)符號(hào)及約束條件

集合C={c1，c2，…，cn}表示云計(jì)算資源集，其中n表示計(jì)算節(jié)點(diǎn)數(shù);集合T={t1，t2，…，tm}表示系統(tǒng)中待調(diào)度的任務(wù)集，m表示待調(diào)度的任務(wù)數(shù).X是一個(gè)m×n的任務(wù)分配矩陣，若任務(wù)ti被分配給計(jì)算節(jié)點(diǎn)cj，則X中的元素xi，j=1，否則xi，j=0.文中假設(shè)一個(gè)任務(wù)只能被指派到一個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行調(diào)度，且任務(wù)調(diào)度不能搶占執(zhí)行.

Budgeti表示任務(wù)ti的預(yù)算，即云服務(wù)方在約定時(shí)間內(nèi)完成ti的調(diào)度時(shí)所獲得的收益;Deadlinei表示任務(wù)ti的調(diào)度時(shí)間底線，當(dāng)云服務(wù)方在該底線之前完成ti的調(diào)度時(shí)，無(wú)需支付賠償金，否則需向用戶支付賠償金;I-counti表示任務(wù)ti的指令數(shù)，即任務(wù)規(guī)模，其由預(yù)處理模塊估算獲得;T-finii表示任務(wù)ti的預(yù)期完成時(shí)間;I-costj表示計(jì)算節(jié)點(diǎn)cj執(zhí)行單條指令的開(kāi)銷成本;D-costi表示任務(wù)ti單位時(shí)間的延遲成本，即云服務(wù)方超過(guò)時(shí)間底線Deadlinei后，每延遲一個(gè)時(shí)間單位需向用戶支付的賠償金額;L-line表示任務(wù)ti所能接受的最遲完成時(shí)間，在該時(shí)間點(diǎn)，云服務(wù)方需要向用戶支付的賠償金達(dá)到最大值.不失一般性，文中約定任務(wù)的調(diào)度完成時(shí)間超過(guò)L-line時(shí)，云服務(wù)方的收益為0.

執(zhí)行調(diào)度時(shí)，用戶向云平臺(tái)提交調(diào)度請(qǐng)求.云服務(wù)提供方根據(jù)任務(wù)預(yù)算及其QoS要求來(lái)估算收益情況，以判斷是否接受該任務(wù).接受調(diào)度請(qǐng)求之后，如云服務(wù)方未能在用戶要求的時(shí)間內(nèi)完成調(diào)度，則需根據(jù)其延遲時(shí)間向用戶支付賠償金.

就用戶而言，其任務(wù)的預(yù)期完成時(shí)間T-fini最遲不能超過(guò)L-line，否則不僅其QoS得不到滿足，云服務(wù)方也得不到任何收益.另一方面，在滿足調(diào)度任務(wù)QoS要求的條件下，假設(shè)任務(wù)ti被指派給計(jì)算節(jié)點(diǎn)cj，即xi，j=1，則節(jié)點(diǎn)cj調(diào)度任務(wù)ti的計(jì)算開(kāi)銷為

相對(duì)于上述開(kāi)銷，節(jié)點(diǎn)cj調(diào)度任務(wù)ti取得的服務(wù)收益為，其中為節(jié)點(diǎn)cj調(diào)度任務(wù)ti的延遲賠償金，具體為

進(jìn)一步地，整個(gè)云系統(tǒng)調(diào)度任務(wù)集T={t1，t2，…，tm}的總收益為總的計(jì)算開(kāi)銷為

在滿足用戶QoS要求的前提下，云計(jì)算應(yīng)以盡可能小的成本獲得盡可能多的收益.因此，提出的成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略應(yīng)盡可能地最大化其單位計(jì)算開(kāi)銷的服務(wù)收益，即其求解目標(biāo)為

很顯然，上述求解目標(biāo)是一個(gè)NP完全問(wèn)題，其不可能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)求得全局最優(yōu)解.

2.2 成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度模型

成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度模型如圖1所示.

圖1 成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度模型

用戶首先發(fā)出任務(wù)調(diào)度請(qǐng)求，預(yù)處理單元根據(jù)任務(wù)屬性及其QoS要求對(duì)任務(wù)規(guī)模進(jìn)行估算.調(diào)度器接收到調(diào)度請(qǐng)求之后，將任務(wù)屬性信息、QoS參數(shù)以及從云資源管理器獲取的計(jì)算資源信息等一并發(fā)送至任務(wù)調(diào)度模塊.調(diào)度模塊根據(jù)任務(wù)及計(jì)算資源信息建立調(diào)度目標(biāo)，并基于遺傳算法進(jìn)行目標(biāo)優(yōu)化，最后將優(yōu)化的調(diào)度方案返回至調(diào)度器.調(diào)度器在獲得調(diào)度方案之后，在云計(jì)算資源層執(zhí)行調(diào)度操作.調(diào)度結(jié)束后，由云計(jì)算資源層將任務(wù)調(diào)度結(jié)果返回至調(diào)度器.

3 基于遺傳算法的目標(biāo)求解

應(yīng)用遺傳算法，在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)對(duì)前述調(diào)度目標(biāo)進(jìn)行近似求解，其求解過(guò)程如圖2所示.

圖2 基于遺傳算法的目標(biāo)求解過(guò)程

3.1 初始化種群

首先確定遺傳算法的種群規(guī)模N和迭代計(jì)算器Count，Count的初始值為0.為了應(yīng)用遺傳算法對(duì)提出的任務(wù)調(diào)度策略進(jìn)行全局求解，需要將每一種可能的調(diào)度方案編碼成染色體.例如，對(duì)于m=7，n=4的云計(jì)算環(huán)境，根據(jù)其任務(wù)分配矩陣X，可采用下述方法進(jìn)行染色體編碼:

在上述變換中，用00，01，10，11依次表示相應(yīng)的任務(wù)被指派到計(jì)算節(jié)點(diǎn)c1，c2，c3，c4.將用二進(jìn)制表示的任務(wù)分配矩陣按行展開(kāi)即得到相應(yīng)調(diào)度方案的染色體編碼.根據(jù)指定的種群規(guī)模N，將相應(yīng)數(shù)量隨機(jī)生成的調(diào)度策略基于上述方法進(jìn)行染色體編碼，即得到初始種群P(0).

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評(píng)價(jià)染色體的好壞，其函數(shù)值越大，相應(yīng)的染色體在遺傳算法的進(jìn)化迭代中越有利于被保留下來(lái).文中遺傳算法以云計(jì)算單位計(jì)算開(kāi)銷的服務(wù)收益作為其適應(yīng)度函數(shù)，表示如下:

對(duì)于一條染色體，其適應(yīng)度函數(shù)值越大，則它對(duì)應(yīng)的調(diào)度方案的單位計(jì)算開(kāi)銷的服務(wù)收益越多.

3.3 遺傳迭代操作

獲得初始種群P(0)之后，應(yīng)用交叉、變異、選擇等遺傳操作算子對(duì)P(0)中的染色體進(jìn)行迭代進(jìn)化操作，重復(fù)上述過(guò)程，直至種群進(jìn)化到一個(gè)可接受的解.首先確定交叉概率pc和變異概率pm.

交叉:從當(dāng)前種群P(g)中隨機(jī)選取兩個(gè)染色體，然后對(duì)選取的兩個(gè)染色體的部分基因座以某種特定的方式進(jìn)行交換，即實(shí)現(xiàn)染色體的交叉繁殖.其中，g表示種群的代數(shù)，對(duì)于初始種群，g=0;每條染色體均以概率pc的幾率被選取參與交叉操作.經(jīng)交叉操作生成的新染色體集合記作Scrossover.

變異:以變異概率pm從當(dāng)前種群P(g)中隨機(jī)選取一定數(shù)量的染色體，對(duì)選取染色體的個(gè)別基因座以某種特定方式進(jìn)行變異，即生成新的染色體.經(jīng)變異操作生成的新染色體集合記作Smutation.

選擇:對(duì)經(jīng)交叉和變異操作生成的新染色體集合以及當(dāng)前種群進(jìn)行合并，得到集合Scrossover∪Smutation∪P(g)，對(duì)于該集合中的元素，分別計(jì)算其適應(yīng)度函數(shù)值，并選擇適應(yīng)度函數(shù)值最大的前N個(gè)染色體作為下一代種群保留下來(lái)，記作P(g+1)，并令Count=Count+1.

3.4 算法終止

經(jīng)過(guò)上述迭代操作，可得到新一代種群P(g+1)，接下來(lái)根據(jù)調(diào)度策略的求解目標(biāo)，即公式(3)來(lái)對(duì)新一代種群進(jìn)行評(píng)估.若算法迭代次數(shù)超過(guò)預(yù)先設(shè)置的最大迭代次數(shù)iteration，或者在連續(xù)的多代種群中，適應(yīng)性最好的染色體的適應(yīng)度函數(shù)值沒(méi)有改進(jìn)，則終止條件得到滿足，算法終止;否則令g=g+1，并繼續(xù)上述遺傳迭代操作，直至算法的終止條件得到滿足.

4 試驗(yàn)測(cè)試與分析

為驗(yàn)證成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略的性能，作者對(duì)該策略進(jìn)行了模擬測(cè)試，同時(shí)將測(cè)試結(jié)果與傳統(tǒng)Min-min算法［1］以及改進(jìn)的QoS約束的Minmin 算法［11］分別進(jìn)行比較.

4.1 試驗(yàn)環(huán)境與參數(shù)設(shè)置

基于Cloudsim［12］對(duì)提出的任務(wù)調(diào)度策略、Minmin算法以及改進(jìn)的QoS約束的Min-min算法分別進(jìn)行模擬測(cè)試.整個(gè)云計(jì)算仿真環(huán)境共有10個(gè)計(jì)算節(jié)點(diǎn)，各節(jié)點(diǎn)擁有的處理單元數(shù)量、處理單元的計(jì)算效率以及單位時(shí)間的計(jì)算成本如表1所示.

表1 云計(jì)算環(huán)境計(jì)算資源列表

請(qǐng)求調(diào)度的任務(wù)屬性包括I-count，Budget，Deadline，L-line，D-cost.試驗(yàn)共用到 10 組一共 100個(gè)任務(wù)，各組任務(wù)的數(shù)量及參數(shù)設(shè)置見(jiàn)表2.

表2 請(qǐng)求調(diào)度的任務(wù)列表

在應(yīng)用遺傳算法對(duì)提出的調(diào)度目標(biāo)進(jìn)行優(yōu)化求解時(shí)，設(shè)定初始種群規(guī)模為100，交叉概率為0.7，變異概率為0.15，最大迭代次數(shù)為300，連續(xù)3次迭代種群的最小進(jìn)化速率為0.3%.

4.2 測(cè)試結(jié)果與分析

基于上述試驗(yàn)環(huán)境及參數(shù)設(shè)置，依次對(duì)成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略、傳統(tǒng)的Min-min算法以及改進(jìn)的QoS約束的Min-min算法分別進(jìn)行測(cè)試，并對(duì)測(cè)試結(jié)果進(jìn)行比較分析.在每組測(cè)試中，參與調(diào)度的用戶任務(wù)數(shù)量依次為10，20，…，100，它們均從表2所示的任務(wù)列表中隨機(jī)選取，每組測(cè)試結(jié)果均通過(guò)多次試驗(yàn)并取平均值獲得.

任務(wù)的調(diào)度完成時(shí)間與參與調(diào)度的任務(wù)數(shù)量之間的關(guān)系如圖3所示.

圖3 不同任務(wù)數(shù)量下的調(diào)度完成時(shí)間

由圖3可見(jiàn)，隨著調(diào)度任務(wù)數(shù)量的增加，3種方法的調(diào)度完成時(shí)間均呈上升趨勢(shì).相比之下，QoS約束的Min-min算法優(yōu)于傳統(tǒng)的Min-min，這是由于前者的調(diào)度決策兼顧了任務(wù)的Deadline約束.進(jìn)一步地，成本驅(qū)動(dòng)的調(diào)度方法明顯優(yōu)于前兩類方法，這是由于成本驅(qū)動(dòng)的方法將計(jì)算開(kāi)銷作為調(diào)度決策的關(guān)鍵因素，其以最大化單位計(jì)算開(kāi)銷的服務(wù)收益作為調(diào)度目標(biāo)，使得其總是從全局出發(fā)，盡可能地將全部任務(wù)均指派給最為合適的計(jì)算資源;另一方面，Min-min及QoS約束的Min-min算法總是趨向于將任務(wù)指派給具有最小最早完成時(shí)間的計(jì)算資源，導(dǎo)致負(fù)載不均，增大了部分任務(wù)的等待時(shí)間，最終延遲了任務(wù)的調(diào)度完成時(shí)間.

隨著參與調(diào)度的任務(wù)數(shù)量的增加，調(diào)度完成時(shí)間超過(guò)其Deadline的任務(wù)數(shù)占全部任務(wù)數(shù)比例的變化趨勢(shì)如圖4所示.

圖4 不同任務(wù)數(shù)量下調(diào)度完成時(shí)間超越Deadline的比例

由圖4可見(jiàn)，成本驅(qū)動(dòng)的調(diào)度方法優(yōu)于另外兩種方法.如前所述，成本驅(qū)動(dòng)的方法總是從全局出發(fā)，盡可能地將任務(wù)指派給最為合適的計(jì)算資源;而Min-min及其改進(jìn)算法容易導(dǎo)致負(fù)載不均，增大了部分任務(wù)的等待時(shí)間，從而使得調(diào)度的完成時(shí)間超過(guò)其Deadline的任務(wù)數(shù)量增多.改進(jìn)的QoS約束的Min-min算法由于更多地考慮了調(diào)度任務(wù)的Deadline約束，也使得其調(diào)度完成時(shí)間超過(guò)Deadline的任務(wù)比例明顯低于傳統(tǒng)的Min-min算法.就3種算法而言，由于任務(wù)之間的資源競(jìng)爭(zhēng)，調(diào)度完成時(shí)間超過(guò)Deadline的任務(wù)比例隨著參與調(diào)度的任務(wù)數(shù)量的增加均呈上升趨勢(shì).

在不同數(shù)量的調(diào)度任務(wù)下，3種算法單位計(jì)算開(kāi)銷的服務(wù)收益情況如圖5所示.

圖5 不同任務(wù)數(shù)量下單位計(jì)算開(kāi)銷的服務(wù)收益

由圖5可見(jiàn)，成本驅(qū)動(dòng)的方法優(yōu)于另外兩種方法，這是因?yàn)槌杀掘?qū)動(dòng)的方法以最大化單位計(jì)算開(kāi)銷的服務(wù)收益為求解目標(biāo)，負(fù)載較為均衡，調(diào)度更為合理.Min-min算法容易導(dǎo)致系統(tǒng)負(fù)載不均，增大了部分任務(wù)的等待時(shí)間，最終導(dǎo)致系統(tǒng)單位計(jì)算開(kāi)銷的服務(wù)收益受損.相比之下，QoS約束的Min-min算法在調(diào)度決策時(shí)兼顧了任務(wù)的Deadline要求，這使得其單位計(jì)算開(kāi)銷的服務(wù)收益情況要優(yōu)于傳統(tǒng)Min-min算法.隨著參與調(diào)度的任務(wù)數(shù)量增多，任務(wù)之間的資源競(jìng)爭(zhēng)加劇，3種算法單位計(jì)算開(kāi)銷的服務(wù)收益均呈下降趨勢(shì).

5 結(jié)論

從云服務(wù)提供方的角度出發(fā)，提出了一種成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略，并在Cloudsim模擬器上做了一系列仿真測(cè)試，結(jié)論如下:

1)提出的策略在任務(wù)完成時(shí)間上優(yōu)于傳統(tǒng)的Min-min算法和改進(jìn)的QoS約束的Min-min算法.

2)相比于另外兩種算法，提出的調(diào)度策略調(diào)度完成時(shí)間超越截止時(shí)間底線的任務(wù)比例總體上更低，這一優(yōu)勢(shì)在任務(wù)數(shù)量較多時(shí)更為明顯.

3)提出的調(diào)度策略系統(tǒng)負(fù)載更為均衡，其單位計(jì)算開(kāi)銷的服務(wù)收益明顯優(yōu)于另外兩種方法.

References)

［1］Braun T D，Siegel H J，Beck N，et al.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2001，61(6):810-837.

［2］Bhoi U，Ramanuj P N.Enhanced Max-min task scheduling algorithm in cloud computing［J］.International Journal of Application or Innovation in Engineering and Management，2013，2(4):259-264.

［3］Benoit A，Marchal L，Pineau J F，et al.Scheduling concurrent bag-of-tasks applications on heterogeneous platforms［J］.IEEE Transactions on Computers，2010，59(2):202-217.

［4］Oprescu A M，Kielmann T.Bag-of-tasks scheduling under budget constraints［C］∥Proceedings of2nd IEEE International Conference on Cloud Computing Technology and Science.Indianapolis，USA:IEEE Computer Society，2010:351-359.

［5］Zhou Amelie Chi，He Bingsheng，Liu Cheng.Probabilistic scheduling of scientific workflows in dynamic cloud environments［R］.Singapore:Nanyang Technological University，2013.

［6］Santos-Neto E，Cirne W，Brasileiro F，et al.Exploiting replication and data reuse to efficiently schedule data-intensive applications on grids［C］∥Proceedings of the10th International Workshop on Job Scheduling Strategies for Parallel Processing.New York:Springer Verlag，2005:210-232.

［7］Liu Wantao，Kettimuthu R，Li Bo，et al.An adaptive strategy for scheduling data-intensive applications in grid environments［C］∥Proceedings of2010 17th International Conference on Telecommunications.Doha，Qatar:IEEE Computer Society，2010:642-649.

［8］Kiran M，Hashim A-H A，Kuan L M，et al.Execution time prediction of imperative paradigm tasks for grid scheduling optimization［J］.International Journal of Computer Science and Network Security，2009，9(2):155-163.

［9］Phinjaroenphan P，Bevinakoppa S，Zeephongsekul P.A method for estimating the execution time of a parallel task on a grid node［J］.Lecture Notes in Computer Science，2005，3470:226-236.

［10］Tao Ming，Dong Shoubin，Zhang Liping.A multi-strategy collaborative prediction model for the runtime of online tasks in computing cluster/grid［J］.Cluster Computing，2011，14(2):199-210.

［11］Liu Juefu，Li Gang.An improved MIN-MIN grid tasks scheduling algorithm based on Qos constraints［C］∥Proceeding of2010International Conference on Optics，Photonics and Energy Engineering. Wuhan， China:IEEE Computer Society，2010:281-283.

［12］Calheiros R N，Ranjan R，de Rose C A F，et al.CloudSim:a novel framework for modeling and simulation of cloud computing infrastructures and services［R］.Australia:Grid Computing and Distributed Systems Laboratory，University of Melbourne，2009.