云工作流中基于分時虛擬機的任務(wù)層調(diào)度算法

王建　李龍澍

摘要：云計算是新的一種面向市場的商業(yè)計算模式，向用戶按需提供服務(wù)，云計算的商業(yè)特性使其關(guān)注向用戶提供服務(wù)的服務(wù)質(zhì)量。任務(wù)調(diào)度和資源分配是云計算中兩個關(guān)鍵的技術(shù)，所使用的虛擬化技術(shù)使得其資源分配和任務(wù)調(diào)度有別于以往的并行分布式計算。目前主要的調(diào)度算法是借鑒網(wǎng)格環(huán)境下的調(diào)度策略，研究基于 QoS 的調(diào)度算法，存在執(zhí)行效率較低的問題。我們對云工作流任務(wù)層調(diào)度進行深入研究，分析由底層資源虛擬化形成的虛擬機的特性，結(jié)合工作流任務(wù)的各類QoS約束，提出了基于虛擬機分時特性的任務(wù)層ACS調(diào)度算法。經(jīng)過試驗，我們提出的算法相比于文獻[1]中的算法在對于較多并行任務(wù)的執(zhí)行上存在較大的優(yōu)勢，能夠很好的利用虛擬的分時特性，優(yōu)化任務(wù)到虛擬機的調(diào)度。

關(guān)鍵詞：云計算；工作流系統(tǒng)；云工作流；工作流調(diào)度；蟻群算法

中圖分類號：TP18 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）10-2431-05

Abstract：Cloud computing is a new market-oriented business model， providing the users the services they need， so that the commercial characteristics of cloud computing makes service providers pay more attention to the quality of service users need.Task scheduling and resource allocation are two key cloud technologies， and virtualization technology makes its resource allocation and task scheduling is different from the previous Parallel distributed computing.Currently，The scheduling algorithm in Cloud Workflow references to the scheduling strategy in grid environment.Based QoS scheduling algorithm in some papers are Inefficient in Cloud Environment.In this paper， they focus on Task-level scheduling in Cloud Workflow and analysis the features of virtual machines which is from the underlying resource by virtualization ，.considering all kinds of QoS constraints of workflow tasks， they propose ACS scheduling algorithm based on virtual machine sharing features .By the simulation experiment， the proposed algorithm，compared to the algorithm in the literature[1]，shows the better performance in the situation where there are many parallel tasks ， and can make good use of virtual resource and optimize the Task-to-VM assignment in the cloud data centers.

Key words： cloud computing；workflow system；cloud workflow；workflow scheduling；ant colony algorithm

云工作流系統(tǒng)區(qū)別于其他的工作流系統(tǒng)就是它的面向市場商業(yè)模型[2-3]，成本節(jié)約是它最大的特點，用戶使用云端的資源就像是使用水電一樣，用多少付多少錢，所以用戶通常使用云工作流系統(tǒng)會對應(yīng)用服務(wù)進行執(zhí)行時間和成本上的約束。云服務(wù)供應(yīng)商和用戶通過協(xié)商簽訂服務(wù)級協(xié)議，云服務(wù)供應(yīng)商根據(jù)服務(wù)級協(xié)議執(zhí)行用戶的云工作流實例，云中有很多滿足各種條件的云服務(wù)，能夠滿足各種服務(wù)質(zhì)量要求，所以要為工作流實例中的任務(wù)選擇合適的云軟件服務(wù)，符合服務(wù)級協(xié)議。同時作為一個服務(wù)供應(yīng)商，也要盡可能為自身獲得一定的利潤，那么，對云工作流的資源管理提出了一個很高的要求，而云工作流調(diào)度是云工作流資源管理的核心問題，因此，研究云工作流調(diào)度是非常有意義的。云工作流調(diào)度就是將云工作流實例中的任務(wù)映射到合適的執(zhí)行資源上并管理其運行。

國內(nèi)外有較多的研究機構(gòu)和研究團隊在研究關(guān)于云工作流調(diào)度。Gurmeet Singh等[4]提出了在網(wǎng)格環(huán)境中通過任務(wù)聚類來優(yōu)化工作流運行，使用提前預(yù)留和動態(tài)提供等資源配置方法，來降低科學(xué)工作流的完成時間。同時還研究了資源配置的成本問題，提出了基于資源利用率的評價矩陣，用于決策配置方式。Eun-Kyu Byuna[5]提出了平衡時間調(diào)度（BTS）近似算法，該算法通過計算出執(zhí)行在用戶指定結(jié)束時間內(nèi)的工作流任務(wù)所需的計算資源的最小數(shù)量，來確保執(zhí)行工作流執(zhí)行所需的最優(yōu)資源數(shù)量。Buyya 等[6]提出采用基于粒子群算法（PSO）的啟發(fā)式算法調(diào)度云工作流任務(wù)，該算法不僅考慮計算成本，還考慮數(shù)據(jù)的傳輸成本，滿足用戶的最小化時間、最小化運行成本以及均衡資源負載的 QoS 約束。MohsenAmini Salehi等[7]提出了兩個以市場為導(dǎo)向的調(diào)度策略，分別用來優(yōu)化執(zhí)行時間和執(zhí)行成本。通過向服務(wù)提供者租用資源來擴展本地資源的計算能力，來滿足用戶截止時間的服務(wù)質(zhì)量需求。該策略無需應(yīng)用程序執(zhí)行時間的相關(guān)歷史數(shù)據(jù)，并以用戶層代理的方式集成在 Gridbus 系統(tǒng)中。國內(nèi)也有較多的團隊在研究云工作流，在活動調(diào)度方面，謝海軍等[8]為提出了一種新穎的基于Skyline點和局部選擇的啟發(fā)式服務(wù)組合方法SLOMIP。該方法首先從候選服務(wù)集合中選出 Skyline服務(wù)，再從Skyline服務(wù)集中選取最優(yōu)的k個服務(wù)進行最終服務(wù)組合方案的優(yōu)化求解。該方法求得的解必然是最優(yōu)解。

群集智能作為一種新興的求解問題的方案，在工程優(yōu)化領(lǐng)域具有不可替代的作用，它對提高大規(guī)模優(yōu)化問題的求解速度及優(yōu)化精度具有非常重要的實際意義。蟻群算法作為群集智能的一種，在工作流調(diào)度上也有很好的應(yīng)用。Ruay-Shiung Chang[9]等就提出了在網(wǎng)格中的平衡工作流調(diào)度的蟻群算法。Wei-Neng Chen[10]等提出了網(wǎng)格中工作流調(diào)度算法——蟻群優(yōu)化算法，文中提出兩種啟發(fā)式信息——成本和執(zhí)行時間。之后，又提出基于多種服務(wù)質(zhì)量的要求的蟻群優(yōu)化算法優(yōu)化網(wǎng)格工作流任務(wù)調(diào)度[11]，將蟻群優(yōu)化算法應(yīng)用于優(yōu)化云工作流的任務(wù)調(diào)度，結(jié)合云工作流的特點設(shè)置改進蟻群算法的各個參數(shù)模型。Zhangjun Wu[1]等提出面向市場云工作流的兩層調(diào)度算法。在任務(wù)層就提出采用蟻群優(yōu)化算法來生成任務(wù)層的調(diào)度策略。在任務(wù)層中的調(diào)度，由于分配到數(shù)據(jù)中心局部調(diào)度器的任務(wù)可能有上千個，那么匹配局部調(diào)度器管理的虛擬機上采用蟻群算法進行調(diào)度，結(jié)合云工作流的特點，設(shè)置合適的蟻群算法的參數(shù)算子，提高算法解決問題的整體能力。

本文提出在數(shù)據(jù)中心內(nèi)，采用虛擬機分時的特性，進行工作流實例的任務(wù)和非工作流任務(wù)的調(diào)度，優(yōu)化數(shù)據(jù)中心內(nèi)系統(tǒng)的執(zhí)行效率。

1 問題分析

在任務(wù)層調(diào)度中，我們所要調(diào)度的工作流任務(wù)可能來自不同的工作流實例。對其進行邏輯處理，根據(jù)其任務(wù)間相互依賴關(guān)系，并添加一個虛擬的開始任務(wù)節(jié)點和結(jié)束任務(wù)節(jié)點，構(gòu)成一個集成工作流實例。采用一個集成的DAG圖表示一個工作流實例。一個集成的工作流實例為[G=N，E]。n表示集成工作流實例的任務(wù)個數(shù)。其中[N=T1，T2，…，Tn]表示流任務(wù)集合，集合[E=Ti，TjTi，Tj∈N]表示任務(wù)間的依賴關(guān)系，每個任務(wù)[Ti（1≤i≤n）]將調(diào)度到虛擬機集合[V=V1，V2，…，Vm]中的某個虛擬機上，因此，任意的工作流任務(wù)[Ti]可用兩個元素[]表示，其中[timei=time1i，time2i，…timemi]表示[Ti]在虛擬機集合[V]中每個虛擬機上的執(zhí)行時間，[co st]表示[Ti]的成本約束。

現(xiàn)有的任務(wù)層調(diào)度算法未考慮虛擬機的分時特性，并發(fā)任務(wù)串行執(zhí)行，執(zhí)行效率低。在公有云計算環(huán)境中，虛擬機是多用戶共享的，任務(wù)在各個虛擬機上要形成一個隊列任務(wù)。因此，任務(wù)層在虛擬機上執(zhí)行有先后關(guān)系。如果兩個任務(wù)是并行的， 要么分配到不同的虛擬機，或者形成串行化的任務(wù)。但是，一個虛擬機同時只做一個任務(wù)是不現(xiàn)實的，虛擬機應(yīng)當(dāng)是分時的。在考慮分時的情況下，并行任務(wù)可以并發(fā)執(zhí)行，也就縮短了執(zhí)行時間，減少了時序異常的出現(xiàn)。因此，對于虛擬機集合中的任意虛擬機[Vi]可以用兩個元素[]表示，其中[price]表示虛擬機的價格，[ma xpra]表示保證任務(wù)執(zhí)行效率時并行執(zhí)行任務(wù)的最大個數(shù)。兩者均為常數(shù)。

任務(wù)層調(diào)度形成一個調(diào)度方案表示為一個二元組集[Ki=Ti1，Vi1，Ti2，Vi2，…Tin，Vin]，二元組中的任務(wù)集[Ti1，Ti2，…Tin]任務(wù)具有一定的先后關(guān)系。則在調(diào)度方案[Kj]下的該數(shù)據(jù)中心內(nèi)部局部調(diào)度的最大完工時間為：

[MakespanKj=m ax1≤i≤nTKji.makespan]

其中，[TKji.makespan]表示任務(wù)[Ti]在調(diào)度方案[Kj]下的完成時間，包含等待時間。

那么，調(diào)度的優(yōu)化目標(biāo)是局部調(diào)度器內(nèi)所有任務(wù)的最大完工時間的最小即：

對于集成的工作流任務(wù)執(zhí)行要滿足用戶定義的QoS約束，該文主要考慮以下兩個約束：

1）集成的工作流實例必須滿足一定的成本上限。即所有任務(wù)在調(diào)度方案[Kj]下的成本：

[CostKj=i=1nVKiji.c ost≤Budget]

其中，[Budget]表示為用戶的容忍成本上，其上限為所有任務(wù)成本約束之和。

2）對于每一個虛擬機都有自己相應(yīng)的最大并行上限，在調(diào)度方案[Kj]下滿足

[ViKj.prataskNum≤Vi.ma xpra ?i∈1，2，3，…，m]

其中，[Vi.ma xpra]表示虛擬機[i]的允許最大并行數(shù)。

由于在任務(wù)層的調(diào)度中針對的是來自至少一個工作流實例的任務(wù)，是一個集成的工作流。那么對于集成DAG，并行任務(wù)的開始執(zhí)行時間不僅受到集成的DAG中的相互依賴關(guān)系，還要滿足該任務(wù)所在的工作流實例中的依賴關(guān)系。如圖1所示，工作流調(diào)度分為兩層，即服務(wù)層調(diào)度和任務(wù)層調(diào)度。在服務(wù)層調(diào)度中，用戶通過web端口的建模工具，構(gòu)建一定規(guī)格的工作流實例，并將其提交給全局調(diào)度器，進行工作流的管理和評估，將工作流的任務(wù)分配給相應(yīng)的服務(wù)。任務(wù)層調(diào)度的任務(wù)數(shù)量并不多，但是由于虛擬機是共享的，在分配任務(wù)的時刻虛擬機上正運行著其他任務(wù)，所以涉及到的任務(wù)數(shù)量會很大.

在服務(wù)層調(diào)度之后，全局調(diào)度器將工作流實例中的任務(wù)段分配給相應(yīng)的局部調(diào)度器，為了優(yōu)化任務(wù)所在數(shù)據(jù)中心的系統(tǒng)運行時間，局部調(diào)度器將分配的任務(wù)形成集成的DAG圖，進行優(yōu)化分配任務(wù)到虛擬機。圖1中，工作流實例2中的[T1，T5，T7]分配給了同一個服務(wù)，在集成的DAG圖中，[T5，T7]都是[T1]的后繼任務(wù)，一般，在任務(wù)[T1]執(zhí)行完后，就可執(zhí)行[T5，T7]，但是，[T5，T7]在其原本的工作流實例不是并行執(zhí)行的，它們的開始執(zhí)行時間分別是由[T3，T6]任務(wù)的結(jié)束時間決定的。另外，在一個數(shù)據(jù)中心中，虛擬機都是建立在不同的規(guī)格的商業(yè)機或者是高性能的超級計算機上的，虛擬機的執(zhí)行速度和價格是不一樣的。

針對上述問題，如何構(gòu)建基于虛擬機分時特性的任務(wù)層調(diào)度模型，使得在滿足成本約束的情況下，優(yōu)化數(shù)據(jù)中心局部調(diào)度器內(nèi)的執(zhí)行時間是關(guān)鍵所在。該文就針對這一問題進行詳細的研究提出合理的算法。

2 基于分時虛擬機的任務(wù)層ACS調(diào)度算法

針對上述的問題分析，該文對于不同的虛擬機設(shè)置在不影響其他任務(wù)運行的情況下，允許最大并行任務(wù)數(shù)。該文根據(jù)任務(wù)所在的工作流實例的時間約束，結(jié)合集成工作流的時間約束，設(shè)置任務(wù)預(yù)計開始時間，然后根據(jù)任務(wù)的預(yù)計開始時間，對蟻群算法進行改進設(shè)置新的啟發(fā)式信息并將其用于任務(wù)層調(diào)度。

2.1 信息素設(shè)置

在算法中，所有的信息素值都設(shè)置為[τ0]，該文中對于[τ0]初始化為：

其中，[Min_makespan]表示為在資源不受限制的情況下，集成工作流實例的最小執(zhí)行時間。[Max_makespan]表示在資源不受限制的情況下，集成工作流實例的最大執(zhí)行時間。

2.2 啟發(fā)式設(shè)置

在任務(wù)層調(diào)度中存在成本約束，以及對執(zhí)行時間的優(yōu)化，因此，在蟻群算法中對應(yīng)不同的啟發(fā)式信息。

1）執(zhí)行時間啟發(fā)式：該啟發(fā)式信息引導(dǎo)螞蟻為未分配的任務(wù)選擇執(zhí)行時間短的虛擬機。

2）成本啟發(fā)式：該啟發(fā)式信息引導(dǎo)螞蟻為未分配的任務(wù)選擇成本最少的虛擬機。

3）成本預(yù)算的啟發(fā)式：由于有多個QoS約束，各個約束之間會產(chǎn)生矛盾，執(zhí)行時間短的虛擬機的成本高，執(zhí)行成本低的虛擬機執(zhí)行時間長。所以，為了權(quán)衡各個約束條件之間的關(guān)系，在設(shè)置啟發(fā)式信息時會有一定的傾向性，該啟發(fā)式信息引導(dǎo)螞蟻為未分配的任務(wù)選擇滿足成本約束的虛擬機。

2.3 解的構(gòu)建

在螞蟻選擇某個具體的啟發(fā)式信息后，螞蟻開始構(gòu)造調(diào)度方案。每只螞蟻為未調(diào)度的任務(wù)選擇合適的虛擬機時，要考慮啟發(fā)式信息和信息素。其概率選擇方程為：

[Vji=arg max1≤j≤miτi，jβηi，j q≤q0 輪盤賭方式選擇 q>q0] [6]

其中，[τi，j]為活動[i]選擇資源[j]的信息素，[ηi，j]為活動[i]選擇資源[j]的啟發(fā)式信息。[β]為常系數(shù)。

2.4 解的優(yōu)化

在ACS算法中，螞蟻在為集成工作流任務(wù)分配到合適的虛擬機上，對于選擇的路徑進行信息素更新，包括局部更新和全局更新。

1）在螞蟻為未分配的任務(wù)選擇合適的虛擬機后，進行局部信息素更新，從而能夠減少其他螞蟻為相同任務(wù)選擇相同虛擬機的概率保證調(diào)度方案的多樣性。局部更新信息素規(guī)則如下：

2）在本算法中有多個啟發(fā)式信息，每只螞蟻只選擇某一種啟發(fā)式信息，進行啟發(fā)式選擇信息素局部更新，保證其他螞蟻能夠盡可能選擇其他的啟發(fā)式信息，從而使調(diào)度方案多樣。啟發(fā)式選擇信息素局部更新規(guī)則如下：

其中，[τA]為當(dāng)前最優(yōu)調(diào)度的選擇信息素，[ρlocal∈（0，1）]為揮發(fā)系數(shù)，[τ0]為信息素最小值。

在所有的螞蟻都構(gòu)造了調(diào)度方案之后，算法將評價各個螞蟻所構(gòu)造的調(diào)度方案。具體評價函數(shù)為：

其中，[K]為當(dāng)前最優(yōu)調(diào)度方案。

2.5 算法流程

基于分時虛擬機的任務(wù)層ACS調(diào)度算法的具體過程如下：

步驟1. 初始化蟻群系統(tǒng)的各類參數(shù)：信息素，螞蟻個數(shù)，選擇參數(shù)[q]，局部信息素揮發(fā)因子[ρlocal]，全局信息素揮發(fā)因子[ρglobal]，最大迭代次數(shù)，當(dāng)前迭代次數(shù)為1；

步驟2. 初始化所有螞蟻：為每只螞蟻構(gòu)建任務(wù)序列，選擇合適的啟發(fā)式方式（選擇采用輪盤賭的方式進行，同時進行類似信息素的更新的方式進行對每個啟發(fā)式方式的選擇概率進行調(diào)整。）

步驟3. 對每個任務(wù)，每只螞蟻根據(jù)其啟發(fā)式信息和信息素選擇相應(yīng)的資源。

步驟4. 對每只螞蟻構(gòu)建的調(diào)度方案進行評價，并進行全局更新。

步驟5. 計算迭代次數(shù)，如果小于最大迭代次數(shù)，轉(zhuǎn)step2，否則結(jié)束，輸出最優(yōu)方案。

3 實驗仿真

3.1 實驗數(shù)據(jù)描述

本文中的實驗數(shù)據(jù)均是隨機產(chǎn)生，根據(jù)應(yīng)用層的DAG圖隨機產(chǎn)生50到250個集成任務(wù)DAG圖。任務(wù)的平均執(zhí)行時間是隨機正態(tài)分布30到3000 之間的時間單位，為了能體現(xiàn)底層資源的高動態(tài)性，標(biāo)準(zhǔn)差定義為平均值的33%。

每個資源包含三個屬性，包括資源的ID，執(zhí)行速度，執(zhí)行成本和最大任務(wù)并行數(shù)。執(zhí)行速度被定義為一個在1到5之間隨機整數(shù)，任務(wù)的執(zhí)行時間等于任務(wù)的平均執(zhí)行時間除以各自虛擬機的執(zhí)行速度。每組有一半虛擬機的速度為1。為了實驗設(shè)置方便，實驗中每個資源價格定義為執(zhí)行速度加上一個1到3之間的隨機整數(shù)。隨機的云工作流總?cè)蝿?wù)數(shù)量從50個變化到 300 個，包含工作流任務(wù)和非工作流任務(wù)。子工作流的數(shù)量相應(yīng)地由5個增加至50個。由于是集成的工作流應(yīng)用，在DAG圖中表現(xiàn)的并行任務(wù)不一定是真正的并行。因此，每個任務(wù)都有一個絕對的開始時間，它是由它所在的工作流實例的時間約束推導(dǎo)得到的。在實驗中任務(wù)的預(yù)計開始時間也是隨機產(chǎn)生的，且每個任務(wù)的 QoS 約束定義為時間約束和成本約束：時間約束為平均執(zhí)行時間加上 1.28倍的標(biāo)準(zhǔn)差，成本約束為時間約束的三倍。云工作流的完工時間定義為所有虛擬機上的最后結(jié)束時間，工作流的總成本定義為任務(wù)執(zhí)行時間之和乘以分配給它們的虛擬機價格。

3.2 實驗分析

3.2.1 收斂性分析

每組實驗的螞蟻個數(shù)為10個，集成工作流任務(wù)約束取集成DAG中所有任務(wù)成本約束之和。設(shè)置概率選擇方程中的[β]為1.2和[q0]為0.9，，全局信息素更新和局部信息素更新的揮發(fā)系數(shù)[ρglobal]和[ρloacal]均為0.1。我們設(shè)計了5組實驗，集成工作流應(yīng)用的任務(wù)個數(shù)分別從50到250，對于每個工作流實例得到調(diào)度方案每次迭代的統(tǒng)計得出本算法的收斂情況。

從圖中，可以看出本算法收斂速度較快。由于在算法設(shè)計過程中考慮集成的工作流實例中，任務(wù)是來自各個實際工作流實例，都有各自的時間約束，任務(wù)的開始時間不僅是受集成的DAG中任務(wù)的影響，也受到各自的工作流實例的任務(wù)間的依賴關(guān)系的影響，基于上述的考慮，設(shè)置了任務(wù)的預(yù)計開始時間，從而造成算法的收斂速度較快。

3.2.2 算法比較

將本文提出的基于分時虛擬機的任務(wù)層ACS調(diào)度算法和在文獻[1]提出的蟻群算法進行比較。設(shè)置概率選擇方程中的[β]為1.2和[q0]為0.9，，全局信息素更新和局部信息素更新的揮發(fā)系數(shù)[ρglobal]和[ρloacal]均為0.1。我們設(shè)計了5組實驗，集成工作流應(yīng)用的任務(wù)個數(shù)分別從50到250，對于每個工作流實例運行10次，求平均值后得到實驗結(jié)果。

通過算法運行得到的結(jié)果顯示，采用基于分時虛擬機的任務(wù)層蟻群調(diào)度算法的優(yōu)化的整體執(zhí)行時間比采用隊列形式的算法得到的執(zhí)行時間要短。這是由于工作流實例中某些任務(wù)是可以并行的，采用隊列的形式只能將并行任務(wù)串行化，這增加了執(zhí)行的時間。在100和150的任務(wù)數(shù)的點上，由于任務(wù)是隨機生成的，預(yù)計開始時間也是隨機生成的，造成實際并行的任務(wù)數(shù)不多，造成兩個算法得出的實際的全局完工時間較為接近，但是總局也是由于對比的算法，由此得出，該文提出的算法在對于較多并行任務(wù)的執(zhí)行上存在較大的優(yōu)勢，能夠很好的利用虛擬的分時特性，優(yōu)化系統(tǒng)的執(zhí)行時間。

4 總結(jié)

云工作流調(diào)度是云工作流資源管理的核心問題。該文提出的于分時虛擬機的任務(wù)層ACS調(diào)度算法在滿足用戶定義的QoS約束，優(yōu)化系統(tǒng)執(zhí)行時間，讓相同時間內(nèi)在相同資源盡可能多的任務(wù)允許。通過實驗證明，該文提出的算法相比于其他算法在對于較多并行任務(wù)的執(zhí)行上存在較大的優(yōu)勢，能夠很好的利用虛擬的分時特性，優(yōu)化系統(tǒng)的執(zhí)行時間。

參考文獻：

[1] Wu Z， Liu X， Ni Z， et al. A market-oriented hierarchical scheduling strategy in cloud workflow systems[J]. The Journal of Supercomputing， 2013， 63（1）： 256-293.

[2] Foster I， Zhao Y， Raicu I， et al. Cloud computing and grid computing 360-degree compared[C]//Grid Computing Environments Workshop， 2008. GCE'08. IEEE， 2008： 1-10.

[3] Zhang X D， Li X P， Wang Q， et al. Hybrid particle swarm optimization algorithm for cost minimization in service-workflows with due dates[J]. Tongxin Xuebao/Commun， 2008， 29（8）.

[4] Buyya R， Yeo C S， Venugopal S， et al. Cloud computing and emerging IT platforms： Vision， hype， and reality for delivering computing as the 5th utility[J]. Future Generation computer systems， 2009， 25（6）： 599-616.

[5] Han J， Kamber M， Pei J. Data mining： concepts and techniques[M]. Morgan kaufmann， 2006.

[6] Pandey S， Wu L， Guru S M， et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//Advanced Information Networking and Applications （AINA）， 2010 24th IEEE International Conference on. IEEE， 2010： 400-407.

[7] Salehi M A， Buyya R. Adapting market-oriented scheduling policies for cloud computing[M]//Algorithms and Architectures for Parallel Processing. Springer Berlin Heidelberg， 2010： 351-362.

[8] 謝海軍， 齊連永， 竇萬春. 基于 Skyline 和局部選擇的啟發(fā)式服務(wù)組合方法[J]. 東南大學(xué)學(xué)報： 自然科學(xué)版， 2011， 41（3）： 449.

[9] Chang R S， Chang J S， Lin P S. An ant algorithm for balanced job scheduling in grids[J]. Future Generation Computer Systems， 2009， 25（1）： 20-27.

[10] Chen W N， Zhang J， Yu Y. Workflow scheduling in grids： an ant colony optimization approach[C]//Evolutionary Computation， 2007. CEC 2007. IEEE Congress on. IEEE， 2007： 3308-3315.

[11] Chen W N， Zhang J. An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements[J]. Systems， Man， and Cybernetics， Part C： Applications and Reviews， IEEE Transactions on， 2009， 39（1）： 29-43.

[12] Yang Y， Liu K， Chen J， et al. Peer-to-peer based grid workflow runtime environment of SwinDeW-G[C]//e-Science and Grid Computing， IEEE International Conference on. IEEE， 2007： 51-58.