陳愛國，王 玲，任金勝，羅光春

(電子科技大學計算機科學與工程學院 成都 611731)

基于資源分組的多約束云工作流調度算法

陳愛國，王 玲，任金勝，羅光春

(電子科技大學計算機科學與工程學院 成都 611731)

已有的云工作流調度算法采用全局搜索方式進行資源選取，存在計算成本高、對大規(guī)模云系統(tǒng)適應性差的問題。該文提出了基于資源分組的多約束云工作流調度算法，采用有向無環(huán)圖的方法，對云工作流中的多任務之間的執(zhí)行順序和數(shù)據(jù)交換等屬性進行量化建模；使用模糊聚類方法實現(xiàn)基于資源多維特征的分組處理，降低工作流任務到資源匹配過程中的搜索空間；并引入執(zhí)行時間和成本預算約束，將工作流的任務調度問題轉化為有約束條件的極小極大問題進行快速求解。仿真測試表明，該算法顯著降低了任務執(zhí)行完成時間和成本。

云計算; 云工作流; 模糊聚類; 資源分配; 調度算法

云計算模式中，云數(shù)據(jù)中心具有大規(guī)模軟硬件資源，通過網絡服務的方式向多用戶提供強大的計算能力。因此，云計算平臺中面臨大量動態(tài)的計算任務請求。這些特點使得云計算環(huán)境中的任務調度比傳統(tǒng)分布式環(huán)境中的任務調度要面臨更多更復雜的問題[1]。特別是隨著網絡功能虛擬化(network function virtualization, NFV)等技術的發(fā)展，云環(huán)境中的工作流任務越來越多，其調度成為云計算領域的一個研究熱點[2-3]。并且，云環(huán)境中用戶按資源使用進行付費，如何權衡性能和成本成為一個普遍問題。越來越多的混合云環(huán)境下存在更復雜的資源使用成本和性能規(guī)格。這些都給云工作流調度提出了更多的挑戰(zhàn)[3]。典型的需求場景如公安系統(tǒng)需要對跨地域分布存儲的多源數(shù)據(jù)進行多層關聯(lián)分析。為了提高計算效率，完整業(yè)務被設計成多個計算步驟，構成了工作流任務。各個任務節(jié)點之間有先后關系和數(shù)據(jù)交換，通常單個任務節(jié)點還需要加載存量歷史數(shù)據(jù)。在可以實現(xiàn)就近資源征用的基礎上，如何從大規(guī)模資源中為完整工作流計算任務選擇合適的資源、降低整體計算成本并提高響應時間具有重要的應用價值。

本文主要針對云工作流調度中如何實現(xiàn)時間和成本的約束問題開展算法研究。滿足時間約束是指確保工作流在用戶指定截止時間前完成，成本約束則要求工作流的執(zhí)行要在一定的成本預算范圍內。造成任務整體調度時間和成本提高的原因多種多樣，包括工作流中多任務的調度順序、資源規(guī)模以及算法本身的執(zhí)行效率等。針對已有的工作流調度算法存在的搜索成本高等問題，本文提出了基于資源分組的多約束云工作流調度算法，利用模糊聚類的方法對云資源進行預處理，并將列表調度和任務調度機制相結合，在為任務搜索合適的資源時，降低搜索成本。同時為了實現(xiàn)任務調度過程中最小化完成時間和最小化執(zhí)行成本這兩個目標，采用有向無環(huán)圖方法求解資源分配策略。該算法在資源聚類的基礎上對工作流中的任務進行調度，考慮任務執(zhí)行的時間與成本預算，有效地降低任務執(zhí)行時間和執(zhí)行成本，實現(xiàn)了最小化完成時間和最小化執(zhí)行成本兩個目標。

1 相關研究

關于云調度算法的研究有很多，包括基于列表的調度策略的最小完成時間算法、Sufferage算法、Min-min算法和Max-min算法等算法[4-6]。典型的處理器關鍵路徑算法(critical path on processor, CPOP)[7]和異構最早完成時間算法(heterogeneous earliest finish time, HEFT)[8]都是基于列表的啟發(fā)式算法，其中HEFT就完成時間而言優(yōu)于上述所有的算法。HEFT算法對任務劃分優(yōu)先級，對優(yōu)先級較高的優(yōu)先為其分配處理資源，在任務調度最小化最早完成時間上取得了良好的效果。但是，HEFT算法在任務調度過程中并沒有考慮成本的因素。

文獻[9]詳細描述了云計算環(huán)境下任務調度中成本和截止時間約束的重要性，并提出了相應的算法。但是，所提出的資源模型和算法僅針對同類資源。文獻[10]提出了云環(huán)境下分段式工作流調度算法：一階段算法IC-PCP和兩階段算法IC-PCPD2。這兩個階段算法在調度大的工作流時都有一個多項式時間復雜度，并在最后期限約束下最小化工作流執(zhí)行成本。文獻[11]也提出了一個算法集來調度截止時間約束的任務以最小化成本執(zhí)行，但是這同樣只最小化了一個目標。所有這些啟發(fā)式算法的主要問題是，他們中大多數(shù)解決的是計算環(huán)境中的單目標優(yōu)化的問題，不能同時針對計算成本和執(zhí)行時間進行優(yōu)化。

文獻[12]提出了BHEFT算法，充分考慮了用戶對成本預算和截止時間的要求。但在進行資源分配時，采用全局資源搜索方法造成了過高的時間成本和額外計算成本。特別是當云計算環(huán)境資源規(guī)模較大時，全局搜索計算的搜索空間也在攀升。其他研究成果也存在類似問題。

如何在為任務分配合適資源的同時，降低資源搜索空間，節(jié)約搜索時間成本和執(zhí)行成本，是工作流調度中一個需要進一步研究的問題?；谏鲜龇治觯瑸榱私鉀Q在任務調度之初由于搜索空間比較大造成的搜索時間和執(zhí)行成本的問題，本文提出利用模糊聚類的方法對云資源根據(jù)資源特征屬性進行分類的策略。

2 問題模型

云工作流是由一系列關聯(lián)的任務構成的，將工作流調度轉換成具有依賴關系的任務拓撲，而工作流調度的核心就是計算任務到資源的映射策略。調度目標主要關注兩方面：1) 從任務提交到任務執(zhí)行完成所花費的時間最小化，即最小化完成時間；2) 從任務提交到任務執(zhí)行完成所花費的成本最小化，即最小化執(zhí)行成本。本文著重討論基于資源預處理的任務調度模型。假設向云計算系統(tǒng)提交一個工作流WF，其包含n個任務，系統(tǒng)內存在m個空閑資源。其中，對于提交的n個任務，用戶規(guī)定了成本預算B和任務執(zhí)行完成時間限制D。

工作流任務調度問題可以描述為：將n個任務分配到m個資源調度執(zhí)行，并確保在時間限制D范圍內取得任務的最小完成時間，在預算B范圍內取得任務的最小執(zhí)行成本。若預測任務執(zhí)行完成后，最小完成時間大于時間限制D或最小執(zhí)行成本大于預算B，則任務調度失敗。如何將任務分配給恰當?shù)馁Y源，以取得執(zhí)行時間和執(zhí)行成本的最小化，問題定義如下。

定義 1 用戶提交的包含n個任務的工作流WF，用有向無環(huán)圖(direct acyclic graph, DAG)描述為：WF=(T, E)，其中T={t1, t2,…,tn}代表任務集合，集合中有n個任務。E={eij}為邊集，代表任務之間的依賴關系，若eij=0代表任務ti和tj之間并不存在執(zhí)行順序的先后關系；若eij≠0代表任務ti執(zhí)行完成后，任務tj才可以執(zhí)行，eij的值代表了任務ti和tj之間需要傳輸?shù)臄?shù)據(jù)量。典型工作流具有單一的首節(jié)點t1和尾節(jié)點tn，任務t2～tn?1可泛化為多個任務路徑P={p1, p2,…,pL}。

定義 2 云計算系統(tǒng)中存在的可供調度的資源用R={r1, r2,…,rm}表示，m為資源的總數(shù)。

定義 3 矩陣W=TR是任務執(zhí)行時間代價矩陣，其中wij代表任務ti在資源rj上執(zhí)行花費的時間。

定義 4 矩陣C=R2是衡量兩個資源之間的通信能力即數(shù)據(jù)傳輸能力的矩陣，其中cij代表資源ir和資源rj之間的傳輸帶寬，即數(shù)據(jù)傳輸能力。

定義 5 任務資源分配策略定義為X。對于給定的任務集合T和資源集合R，分配策略為：

式中，xij取值為0或1，表示是否將任務ti分配給資源rj。所有任務的總執(zhí)行時間定義為：

式中，xijwij表示任務ti分配給資源rj的執(zhí)行時間。所有任務的總執(zhí)行成本cost為：

式中，pricej表示分配給特定資源rj的單位時間定價。

根據(jù)任務分配策略X，將任務ti分配給資源rk執(zhí)行，任務tj分配給資源lr執(zhí)行。對于所有的任務，其總數(shù)據(jù)傳輸時間為：

根據(jù)式(2)和式(4)，可以得出所有任務執(zhí)行完成時間為：

式中，S表示資源搜索時間。

根據(jù)以上分析，任務資源分配模型以數(shù)學的形式表示為：對于給定的任務集合T和資源集合R，如何找到一個最優(yōu)的分配策略，使得任務的完成時間和執(zhí)行成本最小。根據(jù)式(3)和式(5)，目標函數(shù)定義為：

定義式(3)～式(6)的目的是為了準確刻畫成本，用于最小化求解，其約束條件為：

約束條件表明，在成本最小化、完成時間最小化的同時，不能超過預算限制和時間限制。根據(jù)式(3)、式(5)和式(6)，影響優(yōu)化目標的主要因素是式(5)中的資源搜索時間S、所有任務的執(zhí)行完成時間TET和所有的任務的總數(shù)據(jù)傳輸時間DTT受調度算法本身的影響。因此如何減小S、TET、DTT是調度算法的首要考慮因素。

3 基于資源分組工作流調度算法

針對已有算法的不足，本算法首先進行資源分組預處理，通過選擇最優(yōu)分組解決全局資源搜索成本的問題。并定義了時間和成本約束量化模型，最小化任務執(zhí)行時間和成本。

3.1 資源分組處理

分組處理將大量各種類型的云計算資源根據(jù)其特征和對任務的支持能力劃分為若干小類，以解決資源搜索空間大而帶來的效率低下、資源浪費、時間復雜度高等問題。

模糊聚類主要是對資源特征矩陣進行處理。完整的模糊聚類過程首先需要采集云計算資源的特征數(shù)據(jù)，根據(jù)資源特征屬性，建立每個資源的多重屬性特征初始矩陣。由于每個資源的特征屬性的數(shù)量級與量綱存在差異，需要對初始數(shù)據(jù)矩陣進行適當?shù)淖儞Q，即數(shù)據(jù)歸一化操作，將標準矩陣中的值限定在0～1之間，方便后續(xù)的聚類劃分。

本文使用S={s1, s2,…,sM}表示需要被聚類的資源集合，其中M表示資源個數(shù)；使用向量S′(si)={si1,si2,…,siV}(i=1,2,…,M)表示第i個資源的特征屬性，其中sij表示第i個資源在第j個特征屬性上的度量值，V表示特征屬性個數(shù)。

特征屬性是指面向任務處理能力的云計算資源特征或性質，主要包括計算能力、傳輸能力、內存大小、存儲能力、網絡位置、連接數(shù)等特征。確定特征屬性后，再依據(jù)特征屬性對云計算資源進行聚類，將具有相似特性的資源歸到一起。針對不同的任務需求，特征屬性的選擇會有所不同。結合混合云場景中的典型業(yè)務場景，本算法考慮下面4個特征屬性：

1) c1代表計算能力屬性，表示資源的平均計算能力，即資源節(jié)點的計算性能。性能的高低直接關系到任務的執(zhí)行時間，對任務調度過程中的時間成本有著至關重要的影響。

2) c2代表計算節(jié)點間的數(shù)據(jù)傳輸能力屬性，表示云資源節(jié)點間的聯(lián)通邊權值的平均值，即連接鏈路的通信能力的平均值，描述了資源與資源間的數(shù)據(jù)傳輸性能，數(shù)據(jù)傳輸性能的高低直接影響數(shù)據(jù)傳輸?shù)臅r間成本。

3) c3表示計算節(jié)點與歷史數(shù)據(jù)資源節(jié)點間的數(shù)據(jù)傳輸能力屬性。在跨地域的混合云中，數(shù)據(jù)資源節(jié)點到不同混合云計算資源節(jié)點間的數(shù)據(jù)傳輸能力差異交大。該能力主要體現(xiàn)為對歷史數(shù)據(jù)的傳輸加載時間需求。

4) c4代表連接數(shù)屬性，表示連接到該資源節(jié)點的其他資源的數(shù)目。分派到該資源的任務可以與其他多個資源的任務進行數(shù)據(jù)傳輸。

模糊聚類資源分組處理分為3個步驟：

1) 數(shù)據(jù)標準化處理

此步驟主要是消除數(shù)據(jù)量綱差異。對于原始數(shù)據(jù)表S′，使用平均值和標準差來處理目標系統(tǒng)中的數(shù)據(jù)從而獲得標準化數(shù)據(jù)，每個數(shù)據(jù)的標準化值為：

式中，ck代表原始數(shù)據(jù)中第k個特征向量，是ck的平均值；Sck是ck的標準化方差。由于標準化值pik′并非全屬于[0,1]，采用極差標準化方法將pik′轉化得到pik′。極差標準化方法定義如下：

式中， pk′min是最小值； pk′max是p1′k,p2′k,…,p′Nk的最大值。

2) 模糊矩陣實現(xiàn)

此步驟的主要目的是便于后續(xù)根據(jù)云計算資源特征屬性的相似性對資源進行聚類。利用指數(shù)相似系數(shù)法可以計算處理單元S={s1, s2,…,sN}的模糊相似關系Rs。經過測試，指數(shù)相似系數(shù)法具有更好的效果，計算方法如下：

3) 聚類信息評估

采用基于割集的聚類方法，可以得到一組聚類結果，用CLUSTER={CL1,CL2,…,CLK}表示，CLj表示第j個資源群組。每個群組的整體性能表示為：

式中，w代表群組中處理單元的個數(shù)；iα代表處理單元第i個特征向量的權重，它的值一般可以通過歷史數(shù)據(jù)或經驗獲得。通過對每個群組的整體性能的計算，根據(jù)性能高低重新排序。任務調度時，優(yōu)選排序靠前的資源群組。

3.2 時間成本約束定義

在問題模型描述和資源屬性建模的基礎上，進一步引入工作流的任務時間約束和成本預算約束量化方法，并通過算法模型實現(xiàn)完成時間和執(zhí)行成本這兩個目標的權衡優(yōu)化。

3.2.1 執(zhí)行時間約束

用戶提交工作流給云平臺執(zhí)行，并指定期望的總體執(zhí)行完成時間D。在調度過程中，調度粒度落到工作流中的任務層面，需要將執(zhí)行時間約束加入到任務調度選擇條件中。為此，定義以下3個變量：

1) 工作流剩余執(zhí)行時間要求SWD：描述工作流中尚未執(zhí)行任務的執(zhí)行時間要求。

2) 執(zhí)行時間適應因子DAF：用于調整當前任務的執(zhí)行時間限制。

3) 當前任務執(zhí)行時間CTD：描述當前任務的執(zhí)行時間限制。

對于任務ti，其剩余截止時間為：

任務的執(zhí)行時間ET(tk)根據(jù)資源分配策略X計算如下：

根據(jù)式(13)，任務ti的截止時間適應因子為：

任務tk的平均執(zhí)行時間為任務tk在所有資源上的執(zhí)行時間的平均值：

根據(jù)式(12)～式(15)，ti的當前任務執(zhí)行時間為：

3.2.2 執(zhí)行成本約束

前面問題模型描述中約定工作流規(guī)定的成本預算為B。根據(jù)對工作流執(zhí)行總成本的要求，需要將成本約束加入到任務選擇條件中。為此，引入以下3個變量。

1) 剩余成本預算SWB：描述未執(zhí)行的任務的成本限制。

2) 成本預算適應因子BAF：用于調整當前任務的預算限制。

3) 當前任務成本預算CTB：描述當前任務的執(zhí)行成本限制。

對于任務ti，其剩余成本預算為：

執(zhí)行成本EC(tk)為：

任務ti的成本預算適應因子為：

任務tk的平均執(zhí)行成本為任務tk在所有資源上的執(zhí)行成本的平均值：

根據(jù)式(17)～式(20)，任務ti的當前任務預算為：

3.2.3 約束條件引入

基于任務ti對執(zhí)行時間和成本預算的要求，構建可為任務ti分配的資源集合BSi。通過預測任務ti在資源rp所需要的執(zhí)行成本與執(zhí)行時間是否滿足條件EC(i, p)≤CTBi和ET(i, p)≤CTDi，將滿足條件的資源保留下來，構成可為任務ti分配的資源集合CLj,i，表示為：

集合BSi表示所有CLj,i中的資源所構成的可分配資源集合：

在進行任務調度時，從BSi中選擇合適的資源分配給任務。

3.3 調度過程

3.3.1 調度準備

調度準備階段的工作主要是為任務級調度做準備。包含根據(jù)優(yōu)先級構造任務列表、資源聚類、依據(jù)工作流總體時間和成本約束量化任務粒度的時間和成本約束、構造可分配資源集合等操作。這些操作節(jié)省了搜索資源空間所花費的時間，同時也降低了后續(xù)任務調度執(zhí)行的時間成本和預算成本。

3.3.2 任務-資源求解與分配

基于3.1和3.2節(jié)描述的算法模型，優(yōu)化求解任務-資源分配策略。引入時間成本平衡因子，以平衡用戶對時間和成本的要求定義如下分配規(guī)則。

1) 如果BSi≠?，使得最小的資源優(yōu)先被選擇，即優(yōu)化函數(shù)：式中，α是時間成本平衡因子，取值范圍為[0,1]，代表了用戶偏好的執(zhí)行時間和執(zhí)行成本敏感度。如果對于任務ti的多個備選資源節(jié)點，度量值iF相等，則優(yōu)選任務ti前序任務所在的資源節(jié)點。

2) 如果BSi=?且SWB≥0，所有的可用資源只要滿足式(24)，均可以被選擇。因為即使局部節(jié)點的可用資源不滿足約束條件，但完整工作流的約束也有可能是滿足的。

3) 如果BSi=?且SWB＜0，SWD＜0，則選擇可用資源中價格最小整體性能最高的資源。

完整工作流中多個任務路徑P可以并行化執(zhí)行，各個路徑的執(zhí)行時間和執(zhí)行成本分別用ET(pi)和EC(pi)表示，用路徑上各個任務的執(zhí)行時間和執(zhí)行成本求和得到?？紤]到路徑是可以并行執(zhí)行的，因此最優(yōu)化函數(shù)為：

則工作流WF的優(yōu)化求解目標為：

通過將問題建立成數(shù)學模型，將工作流的任務調度問題轉化為有約束條件的極小極大問題的求解。該目標函數(shù)的最優(yōu)化結果是由多個任務構成的調度策略，通過求解該目標函數(shù)的最優(yōu)值，可得到相應的最優(yōu)化的資源分配策略，也就是滿足用戶提交的工作流任務的最優(yōu)化調度策略。

4 實驗與分析

基于云計算仿真軟件CloudSim開發(fā)了實驗系統(tǒng)，核心擴展了工作流調度模塊。通過實驗對比分析了本文提出的算法與HEFT算法[8]、BHEFT算法[12]在運行時間和成本方面的性能。設置任務節(jié)點數(shù)分別為10、20、50、100、150、200、250、300的情況下，分別運行20次的模擬實驗，并取得實驗結果的平均值進行對比分析。

4.1 執(zhí)行時間對比

根據(jù)文獻[13]，選擇正常調度長度(normalized schedule length, NSL)作為評價算法在調度任務時的時間性能指標，正常調度長度NSL計算如下：

式中，Tfast是工作流在最快的資源上執(zhí)行所有任務的執(zhí)行時間。NSL的值越大，表示任務執(zhí)行的時間越長。本算法與BHEFT算法、HEFT算法在運行時間方面的性能對比結果如圖1所示。

可以看出，隨著任務數(shù)量的增加，3個算法的NSL值均呈上升趨勢。但是，相比于BHEFT算法和HEFT算法，本算法仍然具有相對較小的NSL值；并且隨著任務數(shù)量的增加，在資源夠用的情況下本算法的NSL值上升趨勢并不明顯。這是由于本算法根據(jù)工作流任務屬性，首先進行了資源分組處理策略，有效減少了資源搜索空間，從而降低了資源搜索時間；其次，將工作流全局資源調度問題轉化成了極小極大問題，可以通過數(shù)學公式求解得到優(yōu)化的資源分配策略。

圖1 不同算法在不同任務數(shù)量下的NSL值

4.2 執(zhí)行成本對比

根據(jù)文獻[14]，選擇正常調度成本(normalized schedule cost, NSC)作為評價算法在調度任務時的成本性能指標，計算如下：

式中，ConCheap是所有任務在最廉價資源上的執(zhí)行成本。NSC的值越大，表示耗費的成本越大。本算法與BHEFT算法和HEFT算法在運行成本方面的性能對比結果圖2所示。

圖2 不同算法在不同任務數(shù)量下的NSC值

可以看出，在對工作流任務進行調度時，本算法在成本方面的調度性能明顯優(yōu)于HEFT算法，略優(yōu)于BHEFT算法。這是由于本算法引入了成本約束的限制條件，有效降低了任務調度的成本。

通過上面兩個實驗，可以得出在相同的截止時間和預算的約束下，使用相同的定價模型，在降低執(zhí)行成本和完成時間上，本算法比其他兩個算法優(yōu)越。

4.3 加速比對比

算法執(zhí)行加速比Speedup[15]表示所有任務的最小順序執(zhí)行時間之和與實際完工時間的比值，Speedup計算如下：

它是衡量算法性能的一個指標，值越大，表示算法性能越好。本算法與BHEFT算法和HEFT算法在加速比方面的性能對比結果如圖3所示。

由圖可知，在不同的任務數(shù)量下，本算法比其他兩個算法具有更好的加速性能，運行執(zhí)行效率更快。因為本算法采用全局策略一次性求解方法，并且本算法構建的策略求解模型計算簡單。

圖3 不同的任務數(shù)量下算法的Speedup性能

5 結 束 語

本文分析了現(xiàn)有云工作流調度模型存在的搜索資源占用時間長，造成算法執(zhí)行時間與執(zhí)行成本增加的問題。提出了基于資源分組的多約束云任務調度算法，該算法將調度過程分解為資源劃分和任務調度策略求解兩方面，首先提出基于模糊聚類的資源分組處理方法；然后考慮到任務的成本和執(zhí)行時間約束，提出了有約束條件的極小極大策略求解算法，并根據(jù)資源分配規(guī)則對任務進行調度。未來研究中，將考慮加入可靠性約束條件，并以運營的云平臺為對象進行驗證。

[1] FANG Y, WANG F, GE J. A task scheduling algorithm based on load balancing in cloud computing[C]//Web Information Systems and Mining. Sanya, China: Springer, 2010: 271-277.

[2] VILALTA R, MAYORAL A, MU?OZ R, et al. The SDN/NFV cloud computing platform and transport network of the ADRENALINE testbed[C]//2015 1st IEEE Conference on Network Softwarization (NetSoft). [S.l.]: IEEE, 2015: 1-5.

[3] 陳超. 改進CS算法結合決策樹的云工作流調度[J]. 電子科技大學學報, 2016, 45(6): 974-980.

CHEN Chao. Workflow task scheduling in cloud computing based on hybrid improved CS algorithm and decision tree[J]. Journal of University of Electronic Science and Technology of China, 2016, 45(6): 974-980.

[4] MATHEW T, SEKARAN K C, JOSE J. Study and analysis of various task scheduling algorithms in the cloud computing environment[C]//2014 International Conference on Advances in Computing, Communications and Informatics. [S.l.]: IEEE, 2014: 658-664.

[5] GUO L, ZHAO S, SHEN S, et al. Task scheduling optimization in cloud computing based on heuristic algorithm[J]. Journal of Networks, 2012, 7(3): 547-553.

[6] VARALAKSHMI P, RAMASWAMY A, BALASUBRAMANIAN A, et al. An optimal workflow based scheduling and resource allocation in cloud[C]// Advances in Computing and Communications. [S.l.]: Springer, 2011: 411-420.

[7] TOPCUOGLU H, HARIRI S, WU M. Performanceeffective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

[8] ARABNEJAD H, BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 682-694.

[9] MALAWSKI M, JUVE G, DEELMAN E, et al. Cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[C]//Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. [S.l.]: IEEE Computer Society, 2012.

[10] ABRISHAMI S, NAGHIBZADEH M, EPEMA D H J. Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[J]. Future Generation Computer Systems, 2013, 29(1): 158-169.

[11] VAN D B R, VANMECHELEN K, BROECKHOVE J. Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds[J]. Future Generation Computer Systems, 2013, 29(4): 973-985.

[12] ZHENG W, SAKELLARIOU R. Budget-deadline constrained workflow planning for admission control[J]. Journal of Grid Computing, 2013, 11(4): 633-651.

[13] SHIN K S, CHA M J, JANG M S, et al. Task scheduling algorithm using minimized duplications in homogeneous systems[J]. Journal of Parallel and Distributed Computing, 2008, 68(8): 1146-1156.

[14] VERMA A, KAUSHAL S. Cost minimized pso based workflow scheduling plan for cloud computing[J]. International Journal of Information Technology and Computer Science (IJITCS), 2015, 7(8): 37.

[15] CAO H, JIN H, WU X, et al. DAGMap: Efficient and dependable scheduling of DAG workflow job in Grid[J]. The Journal of Supercomputing, 2010, 51(2): 201-223.

編 輯 葉 芳

Multi-Constrained Scheduling Algorithm of Cloud Workflow Based on Resource Grouping

CHEN Ai-guo, WANG Ling, REN Jin-sheng, and LUO Guang-chun

(School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731)

The existing cloud workflow scheduling algorithms, using the global search for resource selection, exist a high computational cost and poor adaptability for large-scale cloud systems. Aimed at solving these problem, a multi-constrained cloud workflow scheduling algorithm based on resource grouping is proposed in this paper. It uses the direct acyclic graph to model the multi-task in cloud workflow and characterize the execution sequences and data transfer requirement between tasks with the DAG’s node and edge’s attributes. Then, fuzzy clustering method is employed to classify resources based on multidimensional features and reduce the computational load from workflow tasks to resource selection. By introducing execution time and cost budget constraints, the proposed algorithm transforms the scheduling problem into a minimax problem. Simulation results show that our algorithm significantly reduces the task execution time and cost.

cloud computing; cloud workflow; scheduling algorithms; resource allocation; fuzzy clustering

TP311

A

10.3969/j.issn.1001-0548.2017.03.014

2016 ? 12 ? 26；

2017 ? 03 ? 21

四川省科技支撐計劃(2016GZ0075, 2016GZ0077)；四川省技技廳國際合作項目(2017HH0075)

陳愛國(1981 ? )，男，博士，副教授，主要從事云計算、信息物理融合系統(tǒng)方面的研究.