不確定性云環境工作流調度多目標優化

張曉東

(內蒙古師范大學青年政治學院 信息工程系，內蒙古 呼和浩特 010051)

0 引 言

云計算通過按需方式解決了私有集群的諸多限制，可有效應用于復雜科學計算問題。科學計算常用模型為工作流模型，工作流通過控制流和數據流依賴將任務連接為有向無環圖。云計算的工作流調度是NP問題，大量啟發式方法被用于求解該問題。然而，云計算獨有特點使工作流調度更具難度，如：即付即用定價模式、動態按需資源提供及虛擬機性能不穩定、動態變化特征。已有工作流調度模型通常假設任務處理時間和資源性能可準確預測。然而，虛擬機和主機資源故障、虛擬機不可預知的性能變化都具有不確定性。實驗研究結果表明[1,2]，即使在不同次重復實驗中相同虛擬機的性能變化也很難預測。由于云資源性能的不確定性，工作流任務執行時間也無法準確估算。

考慮這種不確定性，提出一種云計算中滿足健壯性的工作流調度模型。模型假設任務執行時間未知，并局限于不確定區間。不確定區間中的任務執行時間分布概率函數也為未知，唯一確定信息是區間上下限，利用該模型，設計了一種多目標優化調度算法，可以求解工作流調度在執行跨度、代價及健壯性三目標同步優化的Pareto最優解集合。算法改善了傳統工作流調度僅考慮執行時間和代價的優化，而忽略資源性能不確定性對同步優化目標的影響，將健壯性也考慮到同步優化目標中。結果表明，所提算法可以更好適應于任務執行時間的波動，而僅生成較少最優解的Pareto邊界值。

1 相關工作

基于任務執行時間確定性，將調度算法劃為4類討論：①執行時間精確可知。一些啟發式方法可以求解工作流調度的近似最優解，給定準確估算的任務執行時間下，前向在線調度算法是最佳方法，如文獻[3,4]。這類方法僅考慮的不確定性是任務開始時間，而它取決于工作流有向圖中的任務關鍵路徑。②擁有已知概率分布函數的隨機執行時間。概率論和統計法是處理不確定性的常用方法，該方法將調度考慮為隨機問題，將任務處理時間、到達時間建模為擁有已知概率分布函數的隨機變化模型。如文獻[5]提出模糊調度實現了不確定帶寬的應用執行時間最小化。文獻[6]提出在考慮歷史執行數據情況下度量工作流執行的健壯性，在考慮時間和代價約束的同時，設計了健壯工作流調度和資源分配算法。文獻[7]也同時考慮兩種約束討論了不確定云環境中的調度問題。③完全未知執行時間。當任務執行時間無任何先驗信息時，在線調度算法是實現有效調度的方法。在線調度對于未來任務到達是無法預知的，僅在任務到達時再實時作出調度決策。但該方法根據資源占用狀況及資源最優分配作出決策，無法保證最優調度。④不確定任務執行時間。當擁有概率分布的隨機變量為可用信息時，隨機化方法是常用調度方法。然而，很多現實條件并沒有給予概率分布函數中每個隨機參數較多的信息。考慮到穩定性和健壯性，文獻[8]實現了一種由在線計劃和在線調度兩階段的多階段決策框架，可以得到任務調度的最小占優集合解。文獻[9]討論了資源提供不確定性的影響，以及可解決該問題的主動式、隨機式、模糊式和健壯式求解方法，但并沒有給出任何有效模型。文獻[10]基于HEFT設計的算法克服了對于處理時間和通信時間的錯誤估算的不足。文獻[11]為了同步最小化執行跨度和最大化穩定性，設計了進化調度算法，但并沒有優化執行代價。文獻[12]在異構對等網格中解決了非搶占調度問題，利用任務復制機制克服了不確定環境中資源分配的不當。然而，任務復制可能導致調度代價激增。文獻[13]通過聯立在線和隨機調度討論了不確定性調度模型。在任務到達時即使用在線調度，但僅以概率分布得到處理時間進行調度，并不是準確值。文獻[14]提出不確定性多階段調度算法，已知任務時間上下限。第一階段離線調度中，考慮輸入數據不確定性構造潛在調度方案集，第二階段通過穩定性和敏感性分析尋找最優解。文獻[15]針對執行時不確定性設計了基于模糊規劃理論的云資源調度模型，根據三角模糊數來確定任務執行時間。綜合現有工作流調度算法中對于不確定性的不同定義，本文假設在云實例類型上已知任務處理時間的區間，該區間是可以根據工作流任務的結構和工作流類型進行估算的。同時，不存在已知的執行時間的概率分布函數，也無模糊模型可用，這表明無法通過針對隨機問題的概率統計方法確定執行時間。以上所討論的不確定性是調度問題中最為實際的模型，還未應用在云工作流調度的建模中。

2 背景知識

2.1 多目標優化問題

多目標優化問題考慮的是在兩個空間內兩個以上目標的優化問題，且滿足：①解空間X包含所有可行解，如工作流調度的可能解的完全集合；②目標空間O包括X的每個元素的一個鏡像可映射至目標值上。

當o在所有目標上不差于o’且o至少在一個目標上優于o’時，稱點o∈O占優o’∈O。 若沒有o∈O能夠占優o’，則稱點o’∈O為非占優。當一個解x的目標空間內的鏡像為非占優時，則解x∈X為Pareto最優解。所有Paerto最優解的集合稱為Pareto最優解。目標空間內一個Pareto最優解集合的所有成員的鏡像稱為Pareto邊界。由所有目標的最優可行值構成的矢量稱為理想點，該矢量占優所有Pareto邊界。由所有目標的最差可行值構成的一個矢量稱為最低點，完全Pareto邊界占優該點。

高質量Pareto邊界需要通過覆蓋最優解的所有可能范圍并滿足兩個屬性：準確性和多樣性。一種度量均衡解集合X質量(均衡解的接近程度)的指標為超體積hypervo-lumeHV(X)，它代表X內的點與參考點W(通常選擇為最低點)間的封閉區域，如圖1所示。給定均衡解X的集合，hypervolumeHV(X)測量的是X中的點與參考點W間的封閑區域，如圖1所示，通常選擇為最大目標值(即最高的makespan和cost)。因此，在X中的點越多不同越好，且HV(X)也越高。圖1中，包含實線圖周圍點的解集合優于包含正方形中點集合的解，因此，包含所有實線圖周圍點的集合的hypervolume高于包含正方形中點集合的hypervolume。

圖1 Pareto邊界、Hypervolume和擁擠距離

對于調度解的均衡度，可由超體積hypervolumeHV(X)度量，測量的是目標空間X中的點與參考點W間的封閑區域，在X中的點越多不同越好，這時HV(X)也越高，相應調度解的均衡度也就越好。

2.2 工作流雙目標調度問題

工作流多目標調度的目標是同步考慮工作流任務執行的執行效率和執行費用(雙目標優化)，在執行時間和執行代價雙目標上達到最小化，得到工作流調度解的Pareto最優解集合。該算法的實現思路如算法1所示。對于給定的工作流應用W和云資源集合，多目標調度算法的目標是計算大小為np的Pareto最優解集合，以此作為算法的輸出。算法中，步驟(3)根據任務的降秩值B-rank對工作流任務進行降序排列，圖論中工作流任務Ai的降秩值定義為至出口任務Aexit的最長路徑，包括任務Ai本身[16]。步驟(4)～步驟(16)的外層循環在所有排序的工作流任務上進行迭代。對于每一個任務，算法通過分別將任務映射至每個可用資源并將其插入至所有局部Pareto最優解的方式生成所有可能的子調度方案，即步驟(9)～步驟(12)。從局部解集合中，算法基于擁擠距離計算選擇最優的np個調度方案，即步驟(14)～步驟(15)。擁有更高擁擠距離的解將被優先選擇，由于Pareto集合代表著不同均衡解的較大區域。算法每次迭代的結果是至目前得到的子調度中最優的np個Pareto最優解。遍歷所有任務之后，算法在步驟(17)中返回計算得到的調度方案的Pareto最優解集合。

算法1： 執行時間和執行代價的雙目標優化工作流調度MOHEFT

Input: workflowW=(A,D), Resource set: resourcePool, Number of Pareto optimal solutions:np//輸入工作流結構、 資源池以及Pareto最優解集合中的解數量

Output: Pareto optimal set of workflow schedules: ParetoSet //輸出雙目標優化Pareto解集

(1)Begin

(2) ParetoSet[0∶np-1]←null//建立大小為np的工作流調度方案的空集

(3) rankedTasks←sortBrank(A)//基于降秩值對工作流任務進行排序

(4)foreachAi∈rankedTasks//在所有排序后的任務上進行迭代

(5)do

(6) solutions←null//存儲每次迭代中的所有子調度方案

(7)foreachRj∈resourcePool//在所有資源上迭代

(8)do

(9)foreach ParetoSolution∈ParetoSet//在當前Pareto解上進行迭代

(10)do

(11) solutions←solutions∪{ParetoSolution∪ (Ai,Rj)}//存儲新的子調度方案

(12)end

(13)end

(14) solutions←sortCrowdingDistance(solutions)//基于擁擠距離對調度解進行排序

(15) ParetoSet←tail(solutions,np)//基于擁擠距離選擇最優的np個調度解

(16)end

(17)returnParetoSet//返回最終得到的雙目標優化Pareto解集

(18)end

3 調度模型

3.1 工作流模型

定義函數pred∶A→P(A)，P代表冪集合，返回每個任務Ai∈A的直接前驅任務集合，即Aj∈pred(Ai)?(Aj,Ai,Dji)∈D。 定義函數succ∶A→P(A) 返回每個任務Ai∈A的直接后繼任務集合，即Aj∈succ(Ai)?(Ai,Aj,Dij)∈D。 每個工作流擁有一個入口任務Aentry，該任務沒有前驅，即Aentry∈A∶pred(Aentry)=null； 并擁有一個出口任務Aexit，該任務沒有后繼，即Aexit∈A∶succ(Aexit)=null。

每個工作流任務Ai擁有一個資源需求矢量Ri，用于定義該任務的軟硬件需求。每個任務Ai的計算量wi以百萬指令數MI表達。

3.2 云資源模型

定義任務Ai的期望處理(執行)時間ti,j為其計算量wi與執行它的虛擬機實例Ij的計算速率的比例，若在虛擬機不可用時再加上其啟動延時bj，則可表示為

(1)

由于虛擬機資源實例的性能(sk)和啟動延時(bk)是無法精確預測的，假設僅已知期望處理時間ti,j的上下限值在一個不確定區間內，即ti,j∈[lower(ti,j),upper(ti,j)]， 且時間概率分布函數也未知。因此，對該區間進行縮放將降低執行時間ti,j的不確定性。

3.3 融入不確定性的三目標優化調度模型

定義工作流調度解為函數S∶A→I， 函數的功能是將每個任務Ai∈A映射至一個云資源實例Ij∈I上，基于目標函數的同步優化，完成所有工作流任務的執行。工作流調度問題中考慮的同步優化目標為：工作流執行跨度makespan、工作流執行代價cost以及資源實例性能和啟動延時等因素波動變化帶來的調度健壯性。算法的目標是同步最小化3個優化目標的度量公式值。

(1)執行跨度makespan

一個任務Ai在實例Ij上的完成時間為其所有前驅任務的最遲完成時間與其期望執行時間之和，表示為

(2)

式(2)表明，若任務為入口任務，則該任務的完成時間可以直接通過調度該任務的實例確定；若為非入口任務，則其完成時間由該任務本身的完成時間與其前驅任務中完成時間最大值之和組成。那么，工作流的執行跨度M即為工作流的出口任務的完成時間，定義為

M=end(Aexit)

(3)

(2)執行代價cost

任務Ai在實例Ij上的執行代價ci,j定義為

(4)

其中，uj表示實例Ij未使用的時間，即實例上被上一任務利用完的時槽，在已有實例上的未利用時間內執行任務不產生執行代價，若任務完成時間小于或等于該時槽長度，則執行代價為0，即第一種情況；h表示云資源提供方收費的時間單元，即以每小時為一個時間單元。第二種情況表示若任務完成時間大于該時槽長度，則超過該時槽部分按需付費。第三部分表示現有實例若無已付費空閑時槽可用，則依據調度該任務的實例所需代價進行付費。

那么，算法第二優化目標即為工作流執行代價C，表示為

(5)

(3)執行健壯性robustness

工作流調度模型中，由于工作流任務執行時間的不確定性，離線式調度方案通常無法得到最優解。因此，需要利用啟發式方法處理這種不確定性。

由于任務執行時間的可變性，每個調度解S可能映射在目標空間內的不同點上，即擁有不同的執行跨度和執行代價。令目標空間中的點Slower代表以較低的任務執行時間lower(ti,j) 對應的執行跨度Mlower，對應執行代價為Clower。類似地，令點Supper代表以較高的任務執行時間upper(ti,j) 對應的執行跨度Mupper，對應的執行代價為Cupper。

為了考慮任務執行時間的不確定性，以目標空間中點Slower和點Supper間的歐氏距離D(Slower,Supper) 定義一個調度解S的健壯性R(robustness)，其依據是：執行時間的不確定性使得任務的準確執行時間只能以一個區間段的上下限為前提，而可變的任務執行時間使得任務調度解可能映射在目標空間中的不同點上，這些點所反映的執行跨度與執行代價目前點間的歐氏距離即可較好地反映調度解能否在相應不確定性下得到穩定的調度結果。因此，綜合考慮這些因素可將健壯性定義為

(6)

圖2表示一個調度解S映射至目標空間中點Slower和點Supper上的情況，圖中還包括以歐氏距離度量的解的健壯性情況。

圖2 調度解S與目標空間的映射關系

算法選擇三目標優化的主要動機是需要通過利用任務執行時間的上下限值尋找一種使得執行跨度Mlower和執行代價Clower達到最小化的調度解，并同時得到由Supper與Slower間的歐氏距離度量的調度健壯性的最優值(即上式的最小值)。執行跨度優化與執行代價優化之間的關系是：性能越強的資源得到的任務執行跨度越短，但其執行代價也越高，所以執行跨度越小，執行代價相對越高。健壯性優化則同時與執行跨度與執行代價相關，代價與跨度的上下限值決定了目標空間中兩個點的歐氏距離，上下限值區間跨度越大，會導致其歐氏距離越大，相應的健壯性表現也越差。健壯性與執行時間不確定性之間的關系在于：執行時間的上下限分別對應于執行代價的下和上限，而執行時間與執行代價在二維目標空間中的歐氏距離直接決定了健壯性。

4 調度算法設計

本節描述同步考慮調度健壯性的三目標優化工作流調度算法。由于云計算環境中，用戶可訪問大量的資源類型，此時的資源數量并不像集群系統是穩定不變的，調度模塊需要有效處理隨機動態變化的資源池。因此，調度算法也需要隨著資源規模的縮放做出相應調整，而這對工作流調度問題的時間復雜度也將產生影響。

定理1 在具有r個資源實例類型的云計算環境中調度n個工作流任務的時間復雜度為O((r+n-1)!/(r-1)!)。

為了求解工作流調度的三目標優化問題，需要融入健壯性指標改進算法1的雙目標優化調度。算法2是考慮了健壯性的三目標工作流調度優化算法。算法的輸入與算法1類似，僅將靜態的資源池修改為資源實例類型的集合。由于云計算環境的動態特征，將每個調度解表示為一個由于工作流調度與相應資源實例的元組形式。進行初始化后，步驟(3)基于降秩值標準對所有工作流任務進行排序。三目標優化算法包含三層嵌套循環，分別將每個工作流任務映射至每個資源實例上，以形成所有可能的子調度方案。此外，算法在步驟(9)中從每個子調度方案中提取了Pareto最優調度解，在步驟(10)中添加了所有云資源實例類型至潛在的資源池中，步驟(11)～步驟(16)將已調度任務所利用的每個實例插入至已使用資源池中。每個外層迭代的結果(步驟(4)～步驟(20))是遍歷至目前為止得到的np個Pareto最優解。最后，算法將返回調度解的Pareto集合paretoSet，即步驟(21)。

步驟(4)～步驟(20)的外層循環需要迭代n次，步驟(7)～步驟(17)的循環執行np次，而步驟(11)～步驟(16)的內層循環需要迭代 (n-1+r) 次，因此，算法的時間復雜度為O(n×np×(n-1+r))， 與算法1的時間復雜度相似，且并不高于定理1中給出的理論時間復雜度。

算法2: 考慮健壯性的三目標工作流調度優化算法R-MOHEFT

Input: workflow application:W=(A,D), Cloud instance type set:T, Number of Pareto optimal solutions:np//輸入工作流結構、 云資源實例類型數量以及Pareto最優解集合中的解數量

Output:Pareto optimal set of scheduling solutions: ParetoSet//輸出三目標優化的Pareto解集

(1)begin

(2) ParetoSet[0∶np-1]←null//初始化每次迭代得到的Pareto集合， 即ParetoSet={ParetoSolutions}

(3) rankedTasks←sortBrank(A)//基于任務降秩值對任務進行排序

(4)foreachAi∈rankedTasks//在所有排序后的任務上迭代

(5)do

(6) solutions←null

(7)foreach ParetoSolution∈ParetoSet

(8)do

(9) (schedule,resourcePool)←ParetoSolution//提取Pareto解的元素

(10) tempPool←resourcePool∪T//增加所有的云資源實例類型為潛在可用的新資源

(11)foreachIj∈tempPool//在所有可能的資源上迭代

(12)do

(13) schedule←schedule∪(Ai,Ij)//將已調度任務插入調度解中

(14) resourcePool←resourcePool∪Ij//將資源插入至新的資源池中

(15) solutions←solutions∪(schedule,resourcePool)//保存新的調度解

(16)end

(17)end

(18) solutions←sortCrowdingDistance(solutions)//基于擁擠距離對調度解進行排序

(19) ParetoSet←tail(solutions,np)//基于擁擠距離選擇最優的np個調度解

(20)end

(21)returnParetoSet//返回最終得到的Pareto最優解集

(22)end

5 實驗仿真

5.1 仿真環境搭建

利用工作流仿真平臺WorkFlowSim[17]實現工作流調度算法的仿真，觀察工作流任務執行時間的不確定性對算法性能的影響。仿真環境構建具有5種資源實例類型的云計算環境，配置見表1。假設工作流任務在資源實例上執行具有非搶占性，即某一資源實例分配至一個任務，將直到其完成為止。以區間[30,60]sec的均勻分布方式生成每個資源實例的啟動時間。

表1 虛擬機資源實例類型

利用PovRay和WIEN2k這兩種現實工作流應用進行仿真實驗測試，其中，PovRay是創建三維圖形的工作流應用，是生物醫學和建筑學的常用應用，結構如圖3所示，該工作流由并行任務集合構成，以PNG格式對圖像幀數渲染，緊接著是少量串行任務對所有幀進行合并，生成最終mpeg影映。WIEN2k是利用密集泛函理論計算固體電子結構的一種材料科學工作流應用，工作流包含兩個并行部分，分別由連續同步任務構成，結構如圖4所示。

圖3 PovRay工作流結構

圖4 WIEN2k工作流結構

以[100,10000]sec的時間區間作為可變的工作流任務執行時間，執行50個WIEN2k工作流應用和50個PovRay工作流應用。不確定間隔變化在[0,10000] sec，使得lower(ti,j)≤upper(ti,j)≤2×lower(ti,j)。 任務間的通信時間服從[10,1000] sec的均勻分布，每個循環中并行任務數量pt的變化范圍為[1,100]，這表明對于WIEN2k工作流總任務數量為n=3+2×pt， 即變化范圍為[5,203]，對于PovRay工作流總任務數量為n=4+pt， 即變化范圍為[5,104]。

為了計算每個Pareto最優集合的超體積hypervolume，將最低點考慮為參考點。一個間隔長度并不能清晰反映內部值的變化程度。例如：兩個工作流任務的執行時間區間分別是為[10,20]和[1000,1010]，擁有相同的區間長度為10，但是前者的變化明顯高于后者很多。因此，需要將區間以相對時間變化的標準化方法來表示，即δ=[upper(ti,j)-lower(ti,j)]/lower(ti,j)。 由于upper(ti,j)∈[lower(ti,j),2×lower(ti,j)]， 那么δ∈[0,1]。 實驗中將以步長0.125得到不同的δ值，并忽略upper(ti,j)=lower(ti,j) 的特殊情況進行實驗(由于此時不存在不確定性，算法1和算法2的結果將是相同的)。

5.2 原始雙目標調度的健壯性研究

本節研究忽略任務執行時間的不確定性區間 [lower(ti,j),upper(ti,j)]， 根據固定的執行時間調度工作流時算法1得到的子最優解的情況。將算法1命名為MOHEFT算法，以MOHEFT(lower)、MOHEFT(average)和MOHEFT(upper)這3個算法對應以3個執行時間為常量的算法進行實驗，常量時間分別為lower(ti,j)、lower(ti,j)+upper(ti,j)/2和upper(ti,j)。 算法MOHEFT(lower-upper)則是利用不確定性區間的上限值(即圖2中的點Supper)對MOHEFT(lower)的解進行映射。

為了更好理解目標空間，對于PovRay工作流應用所得到的Pareto邊界如圖5所示。可以觀察到，MOHEFT(lower-upper)的解無法占優MOHEFT(upper)的解，這表明僅考慮不確定性區間的上限值的MOHEFT(lower)解并不是最優的。換言之，盡管MOHEFT(lower)的解是Pareto最優，但在相同解上以利用上限值upper(ti,j) 替換下限值lower(ti,j) 計算Supper時將變成子最優。進一步觀察，有兩個MOHEFT(lower-upper)的解被其它8個解所占優，這表明它們均不是Pareto最優解。

圖5 不同執行時間常量的Pareto邊界

圖6表示4種算法得到的超體積hypervolumes指標值的情況，其中忽略了MOHEFT(lower-upper)的占優解。為了更好地進行性能比較，通過對參考點與(0,0)點間的標準化計算將hypervolume值映射至區間[0,1]上。可以觀察到，利用不同的常量化任務執行時間對MOHEFT算法得到的Pareto邊界將具有較大影響，隨著相對時間變化因子δ漸增至1，MOHEFT(lower)與MOHEFT(lower-upper)得到的超體積hypervolume的差值將增加。當MOHEFT利用更高的執行時間時，所得到的超體積hypervolume值將越小。該結果表明在不確定性條件下基于固定任務執行時間的調度決策的假設在可變的執行時間背景下并不具有調度求解的健壯性和穩定性。

圖6 相對時間變化因子對hypervolume的影響

5.3 融入不確定性的調度算法健壯性研究

本節研究對于一個調度解(Slower,Supper)的完整不確定性區間的健壯性與調度解(Srandom,Supper)間的關系，后者表示的是在不確定區間中考慮任務具有隨機執行時間替換下限值的方式。圖7顯示了Slower與Srandom間健壯性的正值相關性。可以看到，縮短健壯性將減少在不確定區間內執行時間在目標空間中得到的調度解的波動，該結果表明健壯性是處理云資源性能變化導致任務執行時間不確定性的有效手段。換言之，擁有越小不確定性的調度解將得到更高的健壯性，反之亦然。

圖7 (Srandom,Supper)與(Slower,Supper)健壯性的相互關系

5.4 兩者比較研究

將算法2考慮了不確定性的三目標優化調度算法命名為R-MOHEFT，進一步比較MOHEFT(lower)和R-MOHEFT(lower)得到的Pareto邊界情況，以及在應用不確定性區間的上限值時Pareto邊界的波動情況。圖8表示利用與圖5相同的PovRay工作流應用得到的Pareto最優解集合。可以看到，盡管對于Pareto邊界而言，MOHEFT(lower)得到了更好的hypervolume值，但R-MOHEFT(lower)所得到的一半左右的解仍然不被MOHEFT(lower)所占優。正如圖9所示，MOHEFT(lower-upper)與R-MOHEFT(lower-upper)以及文獻[15]算法間的結果對比表明所有R-MOHEFT(lower-upper)的調度解均具有比MOHEFT(lower-upper)和文獻[15]更好的健壯性(依據前文健壯性定義式(6)，公式值越小健壯性更好)。

圖8 MOHEFT與R-MOHEFT的Pareto最優集合比較

圖9 健壯性比較

繼續討論X坐標軸為執行跨度makespan時健壯性矢量的角度問題。可以觀察到，對于較小的執行跨度，角度越大，表明資源實例性能不確定性對調度解的目標影響越大。對比在較小的執行代價情況下MOHEFT和R-MOHEFT的調度解的角度，可以看到，MOHEFT調度解的角度要大于R-MOHEFT，這表明R-MOHEFT的調度方案在任務執行時間增加時偏好于執行跨度的增加，而不偏好于執行代價的增加。

圖10進一步比較了超體積指標情況(將超體積hypervo-lume作為相對時間變化因子的函數)，從遞增程度上可以看到，R-MOHEFT算法在相對時間變化因子下對于執行時間的不確定性具有很好的適應性和抵抗性。R-MOHEFT(lower-upper)的hypervolume值基本與R-MOHEFT(lower)是一致的，且平均是MOHEFT(lower-upper)的3倍左右。在處理不確定性的均衡性上R-MOHEFT(lower)的hypervolume值則減小了15%左右。

圖10 處理不確定性的量化分析

在δ=0.125即在執行時間具有12.5%的不確定性時，所對應的為Amazon EC2的實際情況。此時，MOHEFT算法的hypervolume值從0.77降低至0.48，下降幅度為37.7%，而R-MOHEFT僅從0.73下降至0.69，下降率僅為5.5%。R-MOHEFT在越大的不確實性區間和更高的相對時間變化因子下甚至可以增加其hypervolume值。對于δ=1的情況，MOHEFT的hypervolume值下降了87.3%，而R-MOHEFT則僅下降了16%。

5.5 競爭率對比研究

競爭率ρ可以度量在線調度算法比較離線調度算法的有效性。若其形成的調度方案的目標值高于最優離線調度算法得到的調度解的目標值最多ρ倍，則該在線調度算法視為具有ρ競爭性。這表明具有越小競爭率的在線調度解將獲得更好的對應目標值。

為了計算ρ值，將MOHEFT(lower)得到的調度解考慮為最優離線解。圖11和圖12代表MOHEFT、R-MOHEFT和文獻[15]總共3種算法在執行跨度和執行代價上的競爭率。比較MOHEFT和文獻[15]，R-MOHEFT在執行跨度和執行代價上得到了更低的競爭率，這表明該算法的在線調度解要優于兩種對比。另一個觀察結果是，δ值的增加直接導致兩種算法的競爭率的持續增加。同時，比較兩個競爭率ρ值，可以看出，相對時間變化因子δ的增加會更多的影響執行跨度，而不會影響執行代價，這是由于比較代價的區間長度，時間的區間長度的差值會更大所導致的。

圖11 執行跨度上的競爭率比較

圖12 執行代價上的競爭率比較

6 結束語

考慮工作流任務執行時間具有不確定性，基于執行時間和執行代價的同步優化，提出了同步滿足健壯性的三目標優化工作流調度算法。算法將三目標最優化問題以滿足Pareto最優的均衡最優解集合的形式進行建模，以啟發式方式對模型進行求解。為了衡量多目標均衡解的質量，設計了超體積評估機制，并比原始雙目標優化對任務執行時間的波動具有更小的敏感性。通過兩種現實工作流的實驗測試，結果表明，比較未考慮不確定性的雙目標優化，算法得到的調度解均衡度更好，更能適應于任務執行時間不確定性的云工作流調度環境。