云環(huán)境下基于相關(guān)性的并行任務(wù)調(diào)度策略

段 菊，于治國(guó)

(山東管理學(xué)院 信息化工作辦公室,山東 濟(jì)南 250357)

0 引 言

云計(jì)算是近年來分布式計(jì)算、并行計(jì)算、網(wǎng)格存儲(chǔ)和虛擬化等技術(shù)相融合的產(chǎn)物[1]。作為一種新興的商業(yè)模式,其蘊(yùn)含著巨大的商業(yè)價(jià)值[2]。云計(jì)算主要是利用虛擬化技術(shù)將數(shù)據(jù)中心的各類資源虛擬化為資源池進(jìn)行統(tǒng)一的管理和對(duì)外服務(wù)，而且云計(jì)算是面向普通大眾提供服務(wù)的，其用戶群龐大、種類多樣，要處理的任務(wù)量也是非常巨大的，所以云計(jì)算資源的管理和作業(yè)調(diào)度成為了云計(jì)算中的關(guān)鍵技術(shù)，在提高資源的使用效率以及為客戶提供優(yōu)質(zhì)的服務(wù)中起著舉足輕重的作用[3]。

云計(jì)算利用虛擬技術(shù)等為用戶提供資源，包括計(jì)算資源、存儲(chǔ)資源等。用戶雖然免去了購(gòu)買物理處理機(jī)的費(fèi)用，但是依然需要支付租借云資源的費(fèi)用，租借費(fèi)用主要是由租借資源的數(shù)量、類型及時(shí)間決定的，因此，如何提高任務(wù)的執(zhí)行效率是降低執(zhí)行費(fèi)用的關(guān)鍵。

任務(wù)調(diào)度問題是關(guān)于云計(jì)算研究課題中的一個(gè)重要內(nèi)容，眾多研究學(xué)者也提出了很多算法，如遺傳算法[4]、蟻群算法[5]、粒子群算法[6]等。這些算法都有各自的優(yōu)缺點(diǎn)，后人也在這些算法的基礎(chǔ)上做了相應(yīng)改進(jìn)，但是目前應(yīng)用最廣泛的是基于啟發(fā)式的調(diào)度算法[7]。其中，由于基于任務(wù)復(fù)制的調(diào)度算法可以消除任務(wù)間的通信開銷，大大降低任務(wù)的等待時(shí)間，從而提高任務(wù)的執(zhí)行效率，使得基于任務(wù)復(fù)制的調(diào)度算法得到了廣泛關(guān)注。

目前任務(wù)復(fù)制算法已經(jīng)有很多，例如TDS[8](task duplication based scheduling)考慮join節(jié)點(diǎn)任務(wù)與前驅(qū)的關(guān)系，但是沒有考慮處理機(jī)的優(yōu)化問題；TANH[7](task duplication-based scheduling algorithm for network of heterogeneous systems)對(duì)TDS算法中的相關(guān)參數(shù)的定義做了改進(jìn)，使得計(jì)算最晚前驅(qū)的方法更合理；OSA[9](optimal task duplication based scheduling algorithm)將盡量多的父節(jié)點(diǎn)與子節(jié)點(diǎn)分配到同一個(gè)處理機(jī)上，以減少任務(wù)間的通信開銷，但是沒有考慮處理機(jī)的負(fù)載均衡問題。

隨著研究的不斷深入，任務(wù)復(fù)制算法也得到了很多改進(jìn)。DCPD[10](dynamic critical path duplication)先對(duì)任務(wù)劃分優(yōu)先級(jí)然后進(jìn)行調(diào)度，優(yōu)先級(jí)的劃分是根據(jù)任務(wù)的執(zhí)行時(shí)間和距離路徑的出口長(zhǎng)度來定義的，任務(wù)的優(yōu)先級(jí)制約著整個(gè)任務(wù)的流程；TDICMA[11](task-duplication and insertion based clustering and merging algorithm)充分考慮了任務(wù)復(fù)制的連鎖反應(yīng)，多次迭代得到合理的任務(wù)復(fù)制策略，該算法更多地關(guān)注靜態(tài)任務(wù)參數(shù)；TDMCP[12](task duplication multi critical path)主要考慮關(guān)鍵路徑上的任務(wù)對(duì)整體任務(wù)調(diào)度的影響，該算法只復(fù)制首任務(wù)來影響后續(xù)任務(wù)的執(zhí)行，達(dá)到提高整體任務(wù)調(diào)度效率的目的。

為了進(jìn)一步提高云環(huán)境下任務(wù)的執(zhí)行效率、降低執(zhí)行費(fèi)用，文中提出一種基于相關(guān)性的并行任務(wù)調(diào)度算法(parallel task scheduling algorithm based on correlation，PTSAC)。該算法在任務(wù)調(diào)度之前根據(jù)任務(wù)間的通信開銷進(jìn)行隊(duì)列劃分，以提高任務(wù)劃分的效率，在此基礎(chǔ)上，根據(jù)相關(guān)性進(jìn)行任務(wù)復(fù)制，相關(guān)性由任務(wù)間的通信開銷和計(jì)算開銷來量化，在該過程中設(shè)置閾值，若相關(guān)性大于閾值則進(jìn)行任務(wù)復(fù)制，否則不予復(fù)制。

1 問題模型分析

1.1 相關(guān)定義

一般來講，多個(gè)任務(wù)協(xié)作完成一個(gè)工作流，任務(wù)之間是相互聯(lián)系的，這種制約關(guān)系可以用DAG圖表示，即G={V,E,M,C}，其中：V={ti|ti(i=1,2,…,n)是工作流中的任務(wù)}；E={eij|eij表示ti、tj間的邊，ti是tj的父節(jié)點(diǎn)，表明ti、tj間有通信}；M={mij|mij表示ti與tj間的通信開銷，ti是tj的父節(jié)點(diǎn)}；C={ci|ci表示ti的計(jì)算開銷}。

定義1：參數(shù)statime(ti)、fintime(ti)分別表示任務(wù)ti的開始時(shí)間和完成時(shí)間，并且有：fintime(ti)= statime(ti)+ci。

定義2：tend表示結(jié)束任務(wù)，fintime(tend)表示整個(gè)隊(duì)列的完成時(shí)間，如果結(jié)束任務(wù)不止一個(gè)，則maxfintime(tend)=max{fintime(tend)j|j=1,2,…}。

定義3：參數(shù)pred(ti)、maxpred(ti)分別表示任務(wù)ti的前驅(qū)節(jié)點(diǎn)和最晚到達(dá)的前驅(qū)節(jié)點(diǎn)，如果任務(wù)ti沒有前驅(qū)節(jié)點(diǎn)，說明其可以作為一個(gè)隊(duì)列的開始節(jié)點(diǎn)；如果任務(wù)ti有多個(gè)前驅(qū)節(jié)點(diǎn)，則maxpred(ti)=max{M(pred(ti))ij+ fintime(pred(ti))|j=1,2,…}。

定義4：參數(shù)statime(ti)、fintime(ti)分別表示任務(wù)ti的開始時(shí)間和完成時(shí)間，并且有：fintime(ti)= statime(ti)+ci，參數(shù)indegree(ti)表示任務(wù)ti的入度，如果indegree(ti)≥2，說明任務(wù)為關(guān)鍵任務(wù)。

1.2 任務(wù)初次劃分

為了減少不同處理機(jī)上任務(wù)之間的通信開銷，在分配任務(wù)時(shí)相互間通信開銷大的任務(wù)分配到同一個(gè)處理機(jī)上以提高任務(wù)執(zhí)行效率。這里因同一處理機(jī)上不同任務(wù)間的通信開銷很小，可忽略不計(jì)。

任務(wù)劃分的意義在于盡量使相互間通信開銷大的任務(wù)劃分到同一任務(wù)集隊(duì)列，然后任務(wù)調(diào)度階段分配合理的處理機(jī)，以減少由通信開銷帶來的任務(wù)的等待時(shí)間，極大地縮短了整體任務(wù)隊(duì)列的執(zhí)行時(shí)間，進(jìn)而減少租借資源的時(shí)間，降低執(zhí)行費(fèi)用。

任務(wù)初次劃分的算法如下：

步驟1：if(pred(ti)==?){初始化statime(ti)=0；fintime(ti)=statime(ti)+ci；單獨(dú)成為一個(gè)隊(duì)列{ti}}。

else執(zhí)行步驟2

步驟2：如果前驅(qū)只有一個(gè)tj，直接把任務(wù)ti加入到前驅(qū)tj所在隊(duì)列，此時(shí)，statime(ti)=fintime(tj)，fintime(ti)=statime(ti)+ci；否則執(zhí)行步驟3。

步驟3：計(jì)算pred(ti)的最晚到達(dá)時(shí)間并排序，找到maxpred(ti)并把任務(wù)加入到maxpred(ti)所在的隊(duì)列，此時(shí)，statime(ti)=fintime(maxpred(ti))-M(pred(ti))，fintime(ti)=statime(ti)+ci。

步驟4：從總的任務(wù)集中刪除已劃分隊(duì)列的任務(wù)。

步驟5：重復(fù)步驟1～4，直至結(jié)束。

步驟6：輸出任務(wù)隊(duì)列P。

下面通過圖1說明任務(wù)初次劃分算法的過程，系統(tǒng)任務(wù)間的關(guān)系圖可用DAG圖表示。圖中圓圈表示任務(wù)頂點(diǎn)，在圓圈中的1～15表示任務(wù)t1～t15，頂點(diǎn)旁邊的數(shù)字表示任務(wù)的計(jì)算開銷，邊上的數(shù)字代表任務(wù)間的通信開銷。

圖1 DAG圖

根據(jù)步驟1可知，圖1中t1、t2、t3都沒有前驅(qū)，因此它們的初始時(shí)間都為0，各自加入隊(duì)列為{t1}、{t2}、{t3}。t1的前驅(qū)只有t1，所以把t1加入到隊(duì)列1{t1}，以此類推，把t7、t11也加入到隊(duì)列1{t1，t4，t7，t11}，當(dāng)出現(xiàn)多個(gè)前驅(qū)時(shí)，則比較fintime(ti)+mij的大小，加入到值最大的前驅(qū)所在隊(duì)列，例如t12的前驅(qū)有兩個(gè)t7、t8，fintime(t7)+m7,12=7+7=14，fintime(t8)+m8,12=5+6=11，所以t12加入隊(duì)列1，最終的三個(gè)隊(duì)列分別為P(1)={t1，t4，t7，t11，t12，t14}、P(2)={t2，t5，t8}、P(3)={t3,t6,t9,t10,t13,t15}。

任務(wù)初次劃分的詳細(xì)過程如表1所示，任務(wù)劃分結(jié)果如圖2所示。

圖2 任務(wù)劃分結(jié)果

任務(wù)maxpred(ti)cistatime(ti)fintime(ti)P(i)t1-202{t1}t2-202{t2}t3-404{t3}t4t1325{t1,t4}t5t2123{t2,t5}t6t3347{t3,t6}t7t4257{t1,t4,t7}t8t5235{t2,t5,t8}t9t6279{t3,t6,t9}t10t63710{t3,t6,t9,t10}t11t73710{t1,t4,t7,t11}t12t7279{t1,t4,t7,t11,t12}t13t92911{t3,t6,t9,t10,t13}t14t1131013{t1,t4,t7,t11,t12,t14}t15t1341115{t3,t6,t9,t10,t13,t15}

由圖1可知，t10，t14，t15是結(jié)束任務(wù)，根據(jù)定義2可知maxfintime(tend)=fintime(t15)=15，即整個(gè)任務(wù)隊(duì)列完成的時(shí)間為15，但實(shí)際完成時(shí)間為16，這是因?yàn)橛?jì)算過程是按照理論上的最早完成時(shí)間計(jì)算的，程序運(yùn)行的過程實(shí)際是尋找最長(zhǎng)路徑的過程，然后通過隊(duì)列的劃分縮短完成時(shí)間，在完全并行的情況下得到最早的完成時(shí)間，而實(shí)際執(zhí)行時(shí)是按照次晚路徑計(jì)算完成時(shí)間，即在圖2中是按照c2+c5+c8+m8,12+c12+c14=16計(jì)算完成時(shí)間。

2 基于閾值的任務(wù)復(fù)制策略

2.1 任務(wù)復(fù)制算法

這一節(jié)的重點(diǎn)是通過任務(wù)復(fù)制提高任務(wù)的并行性，進(jìn)一步提前次晚路徑的完成時(shí)間。第一節(jié)通過隊(duì)列的劃分可以縮短最晚路徑的完成時(shí)間，最晚路徑的完成時(shí)間被提前之后如果依然大于次晚路徑的完成時(shí)間，則這時(shí)整個(gè)隊(duì)列的完成時(shí)間就是最后得到的時(shí)間maxfintime(tend)，如果最晚路徑的完成時(shí)間被提前之后小于次晚路徑的完成時(shí)間，則整個(gè)隊(duì)列的完成時(shí)間就要大于最后得到的時(shí)間maxfintime(tend)，正如上面的例子就是第二種情況。

針對(duì)第二種情況，文中提出基于閾值的任務(wù)復(fù)制算法，解決計(jì)算完成時(shí)間與實(shí)際完成時(shí)間不一致的問題。由第一節(jié)可知，計(jì)算得到的完成時(shí)間是最早完成時(shí)間，比文獻(xiàn)[13-14]中的最早完成時(shí)間還要早，因此如何使實(shí)際完成時(shí)間與計(jì)算完成時(shí)間一致，是提高任務(wù)執(zhí)行效率的關(guān)鍵。

閾值由通信開銷和計(jì)算開銷共同決定：

結(jié)果有以下三種情況：

(1)TSV>0說明與tj不在同一隊(duì)列中的前驅(qū)任務(wù)的計(jì)算開銷總和和通信開銷相加之和大于同一隊(duì)列中的任務(wù)計(jì)算開銷總和，則可以復(fù)制從隊(duì)列的開始到ti所有的任務(wù)到tj所在的處理器上，減少任務(wù)的等待時(shí)間；

(2)TSV=0說明兩種開銷和一樣大，則不需要復(fù)制任務(wù)，此時(shí)若復(fù)制任務(wù)，不但不能減小時(shí)間開銷，而且會(huì)增加空間開銷；

(3)TSV<0說明與tj不在同一隊(duì)列中的前驅(qū)任務(wù)的計(jì)算開銷總和和通信開銷相加之和小于同一隊(duì)列中的任務(wù)計(jì)算開銷總和，則不需要復(fù)制任務(wù)，此時(shí)若復(fù)制任務(wù)，不但不能減小時(shí)間開銷，反而會(huì)增加時(shí)間開銷和空間開銷。

任務(wù)復(fù)制算法：

步驟1：計(jì)算P(i)中任務(wù)的入度indegree(tj)

步驟2：if(indegree(tj)≥2)

/*檢查tj的所有前驅(qū)是否在同一隊(duì)列*/

if在一個(gè)隊(duì)列，執(zhí)行步驟3；

else

/*計(jì)算TSV*/

if(TSV>0)

復(fù)制任務(wù)；

else不復(fù)制；

else執(zhí)行步驟3

步驟3：j++；//直到隊(duì)列任務(wù)結(jié)束

步驟4：i++；//直到隊(duì)列任務(wù)結(jié)束

步驟5：重復(fù)步驟1～4

步驟6：輸出任務(wù)隊(duì)列

根據(jù)任務(wù)復(fù)制算法對(duì)上一小節(jié)中得到的任務(wù)隊(duì)列進(jìn)行處理。首先從隊(duì)列P(1)開始，任務(wù)t12的入度為2，存在前驅(qū)任務(wù)t8不與其在同一隊(duì)列，根據(jù)定義5計(jì)算閾值TSV=c2+c5+c8+m8,12-(c1+c3+c7)=2+1+2+6-(2+3+2)=4>0，即復(fù)制任務(wù)隊(duì)列P(2)={t2，t5，t8}到隊(duì)列P(1)，t14的前驅(qū)都在同一隊(duì)列；查看隊(duì)列P(3)，任務(wù)t13的入度為2，同t12的方法，TSV=10-9=1>0，復(fù)制任務(wù)隊(duì)列P(2)={t2，t5，t8}到隊(duì)列P(3)；經(jīng)過任務(wù)復(fù)制后的隊(duì)列如圖3所示。

圖3 任務(wù)復(fù)制結(jié)果

經(jīng)過任務(wù)復(fù)制目前上述例子中的完成時(shí)間為15，達(dá)到了理想中的最早完成時(shí)間，任務(wù)復(fù)制算法降低了任務(wù)的等待時(shí)間，提高了任務(wù)的并行性。經(jīng)過任務(wù)復(fù)制，每個(gè)處理機(jī)上的任務(wù)隊(duì)列基本都是相互獨(dú)立的，還有少數(shù)的有關(guān)聯(lián)但對(duì)多個(gè)處理機(jī)進(jìn)行并行處理沒有太大影響。這樣就可以在每個(gè)處理機(jī)上獨(dú)立應(yīng)用任務(wù)調(diào)度算法，只有在遇到個(gè)別任務(wù)時(shí)才需要與其他處理機(jī)進(jìn)行通信，大大降低了通信開銷，提高了任務(wù)執(zhí)行效率。文中提到的處理機(jī)為處理機(jī)集群。

2.2 任務(wù)調(diào)度算法

通過任務(wù)初次劃分及任務(wù)復(fù)制，對(duì)任務(wù)隊(duì)列進(jìn)行了合理的劃分，得到了一個(gè)一個(gè)的任務(wù)集，任務(wù)集間的相關(guān)性大大降低，有的可以完全并行運(yùn)行，為此，需要把任務(wù)集調(diào)度到合理的處理機(jī)上執(zhí)行。任務(wù)集的數(shù)目決定了租借處理機(jī)的數(shù)目，通過對(duì)任務(wù)的復(fù)制，可以有效地減少任務(wù)集的數(shù)目，進(jìn)而減少租借處理機(jī)的數(shù)目；另一方面，處理機(jī)數(shù)目的減少意味著處理機(jī)利用率的提高，合理利用處理機(jī)的空閑時(shí)間是提高處理機(jī)利用率的最佳途徑，因此，任務(wù)調(diào)度算法的主要目的是為任務(wù)集查找合理的空閑時(shí)間，然后進(jìn)行任務(wù)調(diào)度。

任務(wù)調(diào)度算法：

步驟1：初始化隊(duì)列L，用于存放有空閑時(shí)間段的處理機(jī)，初始化變量count=0，用于記錄處理機(jī)的數(shù)目；

步驟2：計(jì)算處理機(jī)空閑時(shí)間段的大小，并設(shè)置標(biāo)記flag=0,按照空閑時(shí)間段升序排列，放入隊(duì)列L；

步驟3：從隊(duì)列L中查找合適的最小處理機(jī)空閑時(shí)間，若存在則把任務(wù)集調(diào)度至此處理機(jī)上執(zhí)行，從任務(wù)隊(duì)列中把此任務(wù)集刪除，若flag=0，則count=count+1,并修改flag=1;

步驟4：重新計(jì)算flag=1的處理機(jī)的空閑時(shí)間段，如果還有空閑時(shí)間段，則根據(jù)時(shí)間段的大小插入到隊(duì)列中；

步驟5：若不存在合適的空閑時(shí)間段則把任務(wù)集拆分，然后查找空閑時(shí)間段；

步驟6：輸出count及flag=1的處理機(jī)的空閑時(shí)間。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證文中提出的基于相關(guān)性的并行任務(wù)調(diào)度算法的有效性，對(duì)TDMCP算法、EOSWCA算法和文中算法從任務(wù)的完成時(shí)間、處理機(jī)的使用數(shù)目及利用率三個(gè)方面進(jìn)行對(duì)比分析。

為了體現(xiàn)算法的公平性和有效性，采用前期實(shí)驗(yàn)仿真平臺(tái)CloudSim[15]和參數(shù)設(shè)置，編程工具采用Myeclipse8.0[16]，任務(wù)數(shù)分別設(shè)為10、20、30、40、50、60、70、80、90、100等10種類型的任務(wù)隊(duì)列，每種類型的任務(wù)隊(duì)列產(chǎn)生10個(gè)，計(jì)算它們的完成時(shí)間maxfintime、處理機(jī)數(shù)目、處理機(jī)利用率。任務(wù)的計(jì)算時(shí)間ci和通信時(shí)間mij是在[1,20]中隨機(jī)產(chǎn)生的。

由圖4可以看出，TDMCP算法的完成時(shí)間要遠(yuǎn)遠(yuǎn)高于PTSAC算法，隨著任務(wù)數(shù)的增加差距也越來越明顯，TDMCP算法僅僅復(fù)制首任務(wù)而沒有對(duì)后面的任務(wù)進(jìn)行處理，在任務(wù)并行性方面明顯處于劣勢(shì)。EOSWCA算法也是采用任務(wù)復(fù)制的方法，縮短關(guān)鍵路徑上任務(wù)的完成時(shí)間，其最早完成時(shí)間為次關(guān)鍵路徑的完成時(shí)間。而PTSAC算法不僅縮短了關(guān)鍵路徑上任務(wù)的等待時(shí)間，而且有效減少了次關(guān)鍵路徑的完成時(shí)間。隨著任務(wù)數(shù)的增加，PTSAC算法的優(yōu)勢(shì)越發(fā)明顯。

從圖5可以看出，在處理機(jī)使用數(shù)目方面，EOSWCA算法和PTSAC算法要絕對(duì)優(yōu)于TDMCP算法。EOSWCA算法和PTSAC算法在任務(wù)劃分之后，都進(jìn)行了相當(dāng)于任務(wù)聚簇的操作，也就是合并任務(wù)隊(duì)列的過程，在任務(wù)調(diào)度階段任務(wù)集的個(gè)數(shù)，決定了處理機(jī)的數(shù)目，因此，有效減少任務(wù)集的數(shù)目對(duì)降低租借處理機(jī)個(gè)數(shù)顯得尤為重要。TDMCP算法沒有進(jìn)行此類操作，由圖也可以看出，EOSWCA算法和PTSAC算法在處理機(jī)使用數(shù)目方面變化趨勢(shì)相似，但PTSAC算法仍有優(yōu)勢(shì)，尤其是在任務(wù)數(shù)增長(zhǎng)到60以后，優(yōu)勢(shì)明顯。

圖4 任務(wù)的完成時(shí)間

圖5 處理機(jī)使用數(shù)目

處理機(jī)利用率的對(duì)比采用比值的方式，TDMCP算法的處理機(jī)總空閑時(shí)間作為基數(shù)，即TDMCP算法的處理機(jī)利用率作為單位“1”，EOSWCA算法和PTSAC算法的處理機(jī)總空閑時(shí)間分別與TDMCP算法的處理機(jī)總空閑時(shí)間作比，比值作為處理機(jī)利用率。由圖6可以看出，隨著任務(wù)數(shù)的增加，比值在減小，說明隨著任務(wù)數(shù)的增加，EOSWCA算法和PTSAC算法的處理機(jī)利用率不斷提高。任務(wù)數(shù)增加到60之后，PTSAC算法的處理機(jī)利用率明顯高于EOSWCA算法。

圖6 處理機(jī)利用率

綜合以上三個(gè)方面，PTSAC算法整體要優(yōu)于TDMCP算法和EOSWCA算法。

4 結(jié)束語

針對(duì)云環(huán)境下任務(wù)調(diào)度的問題，在前期研究的基礎(chǔ)上，從執(zhí)行時(shí)間、處理機(jī)數(shù)目及利用率方面作了進(jìn)一步的研究，提出一種基于閾值的任務(wù)復(fù)制策略。該策略對(duì)復(fù)制任務(wù)的方法做了優(yōu)化，通過設(shè)置閾值的方式，判斷是否需要進(jìn)行任務(wù)復(fù)制以減少任務(wù)的等待時(shí)間；然后對(duì)得到的任務(wù)集進(jìn)行合理調(diào)度。實(shí)驗(yàn)結(jié)果表明，該算法在提前任務(wù)的完成時(shí)間、降低處理機(jī)的使用數(shù)目及提高處理機(jī)利用率等方面有很大的改善。下一步將對(duì)云環(huán)境下科學(xué)工作流的數(shù)據(jù)復(fù)制策略進(jìn)行研究。

參考文獻(xiàn):

[1] CHEN Wanghu,ALTINTAS I,WANG Jianwu,et al.Enhancing smart re-run of kepler scientific workflows based on near optimum provenance caching in cloud[C]//IEEE world congress on services.Anchorage,AK,USA:IEEE,2014:378-384.

[2] 李 強(qiáng),郝沁汾,肖利民,等.云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào),2011,34(12):2253-2264.

[3] ALI M,KHAN S U,VASILAKOS A V.Security in cloud computing:opportunities and challenges[J].Information Sciences,2015,305:357-383.

[4] ZHU Nuo,SHAO Chunfu.Vehicle routing problem with simultaneous delivery and pick-up based on the improved genetic algorithm[C]//Fourth international conference on genetic and evolutionary computing.Shenzhen,China:IEEE,2010:312-316.

[5] CHAHARSOOGHI S K,KERMANI A H M.An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)[J].Applied Mathematics & Computation,2008,200(1):167-177.

[6] TAGHIYEH S,XU Jie.A new particle swarm optimization algorithm for noisy optimization problems[J].Swarm Intelligence,2016,10(3):161-192.

[7] BAJAJ R,AGRAWAL D P.Improving scheduling of tasks in a heterogeneous environment[J].IEEE Transactions on Parallel & Distributed Systems,2004,15(2):107-118.

[8] RANAWEERA A,AGRAWAL D P.Task duplication based scheduling algorithm for heterogeneous systems[C]//Proceedings of 14th international parallel and distributed processing symposium.Cancun,Mexico:IEEE,2000:445-450.

[9] PARK C I,CHOE T Y.An optimal scheduling algorithm based on task duplication[C]//Eighth international conference on parallel and distributed systems.[s.l.]:IEEE,2001:9-14.

[10] LIU Chun-Hsien,LI Chia-Feng,LAI Kuanchou,et al.A dynamic critical path duplication task scheduling algorithm for distributed heterogeneous computing systems[C]//Proceedings of the 12th international conference on parallel and distributed systems.Washington,DC,USA:IEEE,2006:365-374.

[11] 潘志舟.基于任務(wù)復(fù)制和插入的分布式任務(wù)調(diào)度算法研究[D].武漢:華中科技大學(xué),2015.

[12] 李靜梅,尤曉非,韓啟龍.基于任務(wù)復(fù)制的多關(guān)鍵路徑任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(5):1639-1645.

[13] 段 菊,陳旺虎,王潤(rùn)平,等.云環(huán)境下基于聚簇的科學(xué)工作流執(zhí)行優(yōu)化策略[J].計(jì)算機(jī)應(yīng)用,2015,35(6):1580-1584.

[14] 陳旺虎,段 菊,俞茂義.允許違反局部時(shí)間約束的科學(xué)工作流調(diào)度策略[J].計(jì)算機(jī)工程與科學(xué),2016,38(11):2165-2171.

[15] 何婧媛.云計(jì)算仿真工具CloudSim的研究與應(yīng)用[J].科技資訊,2016,14(2):32-33.

[16] 劉彥君,金飛虎.JavaEE開發(fā)技術(shù)與案例教程[M].北京：人民郵電出版社，2014.