林兵，郭文忠，陳國龍

?

多云環(huán)境下帶截止日期約束的科學工作流調度策略

林兵1,2,3，郭文忠2,3,4，陳國龍2,3

（1. 福建師范大學物理與能源學院，福建 福州 350117；2. 福建省網(wǎng)絡計算與智能信息處理重點實驗室（福州大學），福建 福州 350116；3. 空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室，福建 福州 350003；4. 福州大學數(shù)學與計算機科學學院，福建 福州 350116）

針對多云環(huán)境下帶截止日期約束的科學工作流調度問題，提出一種基于遺傳算法操作的自適應離散粒子群優(yōu)化算法（ADPSOGA），目的是在盡可能滿足工作流截止日期前提下，減少其執(zhí)行代價。該方法考慮多云之間的通信代價、虛擬機的啟動和關閉時間以及多云之間不同的帶寬通信波動；為了避免傳統(tǒng)粒子群優(yōu)化算法（PSO, particle swarm optimization）存在的過早收斂問題，引入遺傳算法的隨機兩點交叉操作和隨機單點變異操作，有效提高種群進化過程中的多樣性；在充分考慮數(shù)據(jù)通信代價和任務計算代價的情況下，設計一種基于工作流截止日期約束的代價驅動調度策略。實驗結果表明，ADPSOGA在波動因素存在情況下，對工作流截止日期滿足和執(zhí)行代價控制方面具有良好的性能表現(xiàn)。

云計算；截止日期約束；工作流調度；波動性

1 引言

隨著云計算技術[1]的不斷發(fā)展，當前云市場上出現(xiàn)多個云服務提供商共存的“多云”局面[2]。云計算彈性供應虛擬資源并按需付費的性質，為處理大規(guī)?？茖W工作流（以下簡稱工作流）提供便利[3]。然而，云異構環(huán)境下的任務調度是一個NP-hard問題[4]，工作流自身的子任務之間存在復雜的時間依賴和數(shù)據(jù)依賴關系，且多個云服務提供商之間存在諸多差異（如要價機制、實例類型、通信帶寬等），因此，需要一種合適的調度策略在盡可能滿足工作流服務質量（QoS, quality of service）前提下，減少其執(zhí)行代價。當前云環(huán)境下的工作流調度策略大多是在傳統(tǒng)分布式計算環(huán)境（如網(wǎng)格）的工作流調度算法基礎上做一些改進，未考慮云環(huán)境自身特性[3,5,6]，或一些調度策略僅考慮在靜態(tài)單一云環(huán)境中，單純追求執(zhí)行時間最小化目標，未對帶約束的工作流（如截止日期）的代價優(yōu)化調度問題展開研究[7,8]。

關于多云環(huán)境存在波動因素的帶截止日期約束工作流的代價驅動調度問題，目前國內外還未有相關研究工作。而其中最具相關性的研究工作是關于單云環(huán)境存在波動因素的基于截止日期約束的工作流調度研究[1]，該工作利用傳統(tǒng)粒子群優(yōu)化（PSO, particle swarm optimization）調度策略來處理全局的工作流子任務調度方案。受到文獻[1]的啟發(fā)，提出一種基于遺傳算法操作的自適應離散粒子群優(yōu)化算法（ADPSOGA, adaptive discrete particle swarm optimization with genetic algorithm），主要研究的問題及思路包括3個部分：首先，該方法考慮多云環(huán)境下更多的基本要素，如多云之間的數(shù)據(jù)通信代價、虛擬機的啟停時間以及多云之間的差異化帶寬通信速率，同時還考慮虛擬機的性能波動和帶寬通信波動；其次，為了避免傳統(tǒng)PSO存在的過早收斂問題，引入遺傳算法的隨機兩點交叉操作和隨機單點變異操作，有效提高種群進化過程中的多樣性；最后，在充分考慮數(shù)據(jù)通信代價和工作流子任務計算代價的前提下，設計一種基于工作流截止日期約束的代價驅動調度策略。

2 相關工作

近年來，傳統(tǒng)分布式環(huán)境下的工作流調度已得到廣泛研究。網(wǎng)格環(huán)境下調度工作流的目標通常是最小化工作流執(zhí)行時間。Chen等[9]設計一種網(wǎng)格環(huán)境下基于蟻群優(yōu)化（ACO, ant colony optimization）的工作流調度方法，其目的是優(yōu)化工作流執(zhí)行時間，同時滿足其QoS需求。Cao等[10]提出基于鏈表調度和組調度的工作流調度算法，該方法可以有效降低工作流執(zhí)行時間，并提高網(wǎng)格環(huán)境下的資源利用率。Higashino等[11]提出基于PSO和遺傳算法（GA, genetic algorithm）的混合工作流調度策略，實驗表明該方法在執(zhí)行時間優(yōu)化方面效果明顯。另外，部分研究工作在調度策略中考慮工作流執(zhí)行代價因素。苑迎春等[12]基于逆向分層思想，將截止日期約束轉化為層截止約束，在滿足約束前提下大幅度降低工作流執(zhí)行代價。Abrishami等[13]提出網(wǎng)格環(huán)境下基于局部關鍵路徑（PCP, partial critical path）的代價驅動工作流調度策略，實驗表明該方法能夠在滿足截止日期約束前提下降低工作流執(zhí)行代價。Khajemohammadi等[14]設計一種基于遺傳算法的多目標工作流調度策略，通過分層工作流模型達到同時優(yōu)化執(zhí)行時間和執(zhí)行代價的目標。

上述方法為網(wǎng)格環(huán)境下工作流調度的機遇和挑戰(zhàn)提供寶貴經(jīng)驗。然而，云計算環(huán)境和網(wǎng)格環(huán)境在資源供應和資源要價機制上存在巨大差異[1]。沈虹等[15]提出云環(huán)境下帶準備時間和截止日期約束的代價驅動工作流調度算法，實驗表明該算法可以在合理的CPU時間內減少工作流執(zhí)行代價。Malawski等[3]提出調度工作流組的動態(tài)和靜態(tài)算法，其目的是在滿足預算和截止日期雙約束的前提下提高工作流組的完成率。該工作提到虛擬機需要一定時間來啟動工作，然而其僅考慮一種虛擬機類型，不符合現(xiàn)實云環(huán)境。肖鵬等[16]在經(jīng)典的CPOP算法和HEFT算法基礎上，引入啟發(fā)式策略并設計2種工作流能耗感知調度算法CPOP-MECP和HEFT-MECP，目的是降低工作流子任務之間的數(shù)據(jù)訪問能耗開銷。Mao等[17]提出一種動態(tài)的工作流組調度方案，基于按需付費模式優(yōu)化工作流組的總執(zhí)行代價，該工作考慮多種虛擬機類型，然而該方案對于代價優(yōu)化的單一工作流調度并不適用。部分研究工作引入PSO指導云環(huán)境下的工作流調度問題，并取得良好效果。Wu等[5]提出基于PSO的單一工作流調度方案，他們分別針對截止日期約束的代價優(yōu)化問題和預算約束的執(zhí)行時間優(yōu)化問題展開研究，該工作的虛擬機類型和數(shù)量是固定的，不符合云環(huán)境彈性供應性質。Pandey等[18]設計一種基于離散PSO的優(yōu)化求解單一工作流調度執(zhí)行代價問題，該工作同樣忽略云環(huán)境資源彈性提供的性質。以上云環(huán)境下的工作流調度工作均考慮單個云服務提供商，未對多云環(huán)境展開研究。

多云協(xié)同計算的定義由Keahey等[19]提出。而Fard等[2]提出一種同時優(yōu)化執(zhí)行時間和執(zhí)行代價的多云環(huán)境下工作流調度策略，他們雖然考慮虛擬資源的彈性供應，但忽略虛擬資源的異質性，僅考慮一種虛擬機類型。之前研究工作中[20]提出多云環(huán)境下帶截止日期約束的代價驅動工作流調度策略，該策略引入局部關鍵路徑理論，對工作流的子任務進行局部整體分配，達到壓縮數(shù)據(jù)通信、減少執(zhí)行代價的目的，然而該策略并未考慮波動因素對調度結果帶來的干擾，同時該工作忽略云間的數(shù)據(jù)通信代價和實例啟停時間等因素。

云環(huán)境下關于科學工作流調度的相關工作分析如表1所示。其主要分成6類：設施環(huán)境、應用類型、環(huán)境波動性、目標、限制條件和方法。其中，設施環(huán)境包括單云和多云環(huán)境，應用類型包括作業(yè)、單工作流和工作流組，環(huán)境波動性包括靜態(tài)和動態(tài)，目標分為代價和時間要求，限制條件包括截止日期和預算約束，方法主要包括數(shù)學規(guī)劃、啟發(fā)式和元啟發(fā)式。表1中的“+”代表存在該性質，“?”代表不存在該性質。

3 問題定義

工作流調度模型框架如圖1所示，它主要包括工作流、多云環(huán)境以及代價驅動調度器。

工作流是用有向無環(huán)圖(,)來表示，其中，表示包含個任務的頂點集合{1,2,…,t}，而則表示任務之間數(shù)據(jù)依賴關系{12,13,…,e}。每條數(shù)據(jù)依賴邊e=(t,t)代表任務t和任務t之間存在數(shù)據(jù)依賴關系，其中，任務t是任務t的直接先驅（父）節(jié)點，而任務t則是任務t的直接后繼（子）節(jié)點。在工作流調度過程中，一個任務必須在其所有先驅節(jié)點都已被執(zhí)行完畢后，才能開始執(zhí)行。在某個給定的代表工作流的有向無環(huán)圖中，把沒有先驅節(jié)點的任務稱為“入任務”，同理，把沒有后繼節(jié)點的任務稱為“出任務”。每個工作流都有一個對應的截止日期()，當某個調度策略能夠在對應截止日期前執(zhí)行完成該工作流，則稱其為一種可行解。

表1 云環(huán)境下關于科學工作流調度的相關工作分析

圖1 工作流調度模型

多云環(huán)境中存在多個云服務提供商={,,…,}，服務提供商提供多種虛擬機實例類型S={s1,s2,…,s}。每種類型的虛擬機實例都有其特定的計算能力和存儲能力，假設虛擬機在執(zhí)行子任務過程中有足夠的存儲空間來存儲傳輸數(shù)據(jù)[17]，因此，本文主要關注虛擬機計算能力（即CPU數(shù)量）。子任務t在虛擬機vm上的估計執(zhí)行時間為(t,vm)，給定任務在不同類型虛擬機上的執(zhí)行性價比不同。

同一個云服務提供商的基礎設施通常都集中在較小區(qū)域內，而不同云服務提供商的基礎設施則相距較遠[2]，因此，假設單云的云內帶寬要快于不同云之間的云間帶寬。云服務提供商內，數(shù)據(jù)從子任務t傳輸?shù)阶尤蝿?i>t的云內通信時間為intra(e,)，而數(shù)據(jù)在云服務提供商和之間的通信時間為，如式(1)和式(2)所示。

其中，(e)是子任務t傳輸?shù)阶尤蝿?i>t的數(shù)據(jù)量大小，intra()是云的云內帶寬，而inter(,)則是云和云之間的云間帶寬。假設單個虛擬機上的帶寬無窮大[8]，因此，當2個子任務被分配到同一臺虛擬機上執(zhí)行時，intra(e,)的值為0。

不同云之間的數(shù)據(jù)通信代價將會影響到最終的調度決策[16]，c,q表示從云通信1 GB的數(shù)據(jù)量到云所需的單價。不考慮資源監(jiān)控、數(shù)據(jù)存儲和負載均衡等業(yè)務產(chǎn)生的代價，因為這些代價與計算代價或數(shù)據(jù)通信代價相比可以忽略不計[3]。

代價調度器的目的是在滿足截止日期約束的前提下，最小化工作流執(zhí)行代價。調度器的輸入包括工作流信息（結構、數(shù)據(jù)、依賴等）和多云環(huán)境信息（虛擬機、帶寬、要價等），其輸出是對應的調度方案。整個調度方案的定義為=(,,total,total)，其中，表示一組需要啟用的虛擬機資源，={1,2,…,vm}，={(t,vm)|t∈,vm∈}表示工作流中子任務對應虛擬機資源的映射關系，total表示工作流的執(zhí)行完成時間，而total則表示工作流總執(zhí)行代價。每臺虛擬機都有對應的虛擬機類型s以及對應的開啟時刻(vm)和關閉時刻(vm)。當子任務被調度完成后，都有一組對應的實際執(zhí)行開始時間(t)和實際執(zhí)行完成時間(t)，且“出任務”不會再產(chǎn)生并通信數(shù)據(jù)。因此，工作流執(zhí)行完成時間total和對應的總執(zhí)行代價total分別如式(3)和式(4)所示。

其中，式(4)的前半部分表示虛擬機的執(zhí)行代價，后半部分表示數(shù)據(jù)通信代價。子任務t是子任務t的后繼節(jié)點，(t)和(t)分別表示執(zhí)行t和t的服務提供商。當t和t由同一個云服務提供商執(zhí)行時，s為0（即不產(chǎn)生云間數(shù)據(jù)通信），否則，s為1。

基于以上相關定義，多云環(huán)境下帶截止日期約束的工作流調度問題，可形式化表示為式(5)，其核心思想是在追求執(zhí)行代價total最低的同時，使執(zhí)行時間total小于或等于工作流截止日期()。

4 ADPSOGA調度策略

本節(jié)首先介紹基礎PSO，然后具體介紹ADPSOGA調度策略。

4.1 PSO

PSO是一種基于鳥群社會行為的動物進化計算技術，它是在1995年由Kennedy等[22]提出的。粒子在PSO中尤為重要，每個粒子代表優(yōu)化問題的候選解，它們可以在整個問題空間范圍內移動。每個粒子以某種速度移動更新自己的移動方向，該速度受粒子自身情況、粒子自身最佳歷史位置以及整個種群的歷史最佳位置這3個方面影響。為了判斷每個粒子在問題空間中的不同位置所產(chǎn)生解的優(yōu)劣性，引入適應度函數(shù)來評估每個粒子的解質量。每個粒子是由它自身的位置和速度決定，它們根據(jù)周圍粒子和自身的經(jīng)驗在問題搜索空間中不斷迭代更新調整自己的位置和速度。其中，速度根據(jù)式(6)進行更新，位置根據(jù)式(7)進行更新。

4.2 ADPSOGA

從以下7個部分具體闡述ADPSOGA。

4.2.1 問題編碼

提高算法搜索效率和性能，需要一種好的編碼方式。編碼策略的評價標準主要考慮其健全性、完備性和非冗余性3個基本原則[23]。

定義1 健全性。編碼空間中的某個編碼粒子，必須對應問題空間中的某個潛在問題優(yōu)化解。

定義2 完備性。問題空間中的全部可行解，都能在編碼空間中被相應的粒子表現(xiàn)出來。

定義3 非冗余性。問題空間中的潛在解，只能和編碼空間中的相關粒子一一對應。

其中，(,s,vm)表示該子任務被分配到云中實例類型是s的第個具體實例上。粒子上的每一個節(jié)點位被嵌套劃分成3個小分位，分別表示云服務提供商、實例類型和具體實例，因此，編碼空間大小是子任務數(shù)量的3倍。初始化種群時，粒子的節(jié)點小分位各自隨機初始化為0到其對應最大值之間的整數(shù)值。圖2展示調度包含8個子任務工作流的粒子編碼策略，其中假設多云環(huán)境包含3個云服務提供商，且每個云服務提供商均提供8種實例類型。因此，坐標值是從0~2，s坐標值是從0~7。由圖2可知，子任務1被分配給云第0個云中類型是00的虛擬機000。

圖2 粒子編碼

性質1 云提供商—實例類型—具體實例的嵌套離散編碼方式滿足編碼完備性和非冗余性基本原則，但不滿足編碼的健全性基本原則。

粒子的每個編碼分位代表對應子任務的分配位置，滿足完備性原則。不同編碼粒子分別代表不同調度方案，問題空間的某個可行解只與編碼空間的一個編碼粒子對應，因此，滿足非冗余性原則。部分粒子存在對應問題空間中不可行解情況，例如，調度方案超過工作流截止日期，因此，不滿足健全性原則。

4.2.2 初始化資源池

多云環(huán)境資源的彈性供應模式，導致算法無法得到初始資源集合。對于PSO而言，初始化資源池的大小將決定搜索空間的范圍，對算法復雜度以及工作流執(zhí)行性能起著關鍵作用。當初始化資源池太小時，會出現(xiàn)本可以在截止日期前完成的工作流，由于資源的缺乏而無法及時完成。當初始化資源池太大時，PSO編碼的潛在解過于龐大，使算法無法及時收斂。一種簡單可行的初始化資源分配方案，是為每個子任務分配多云環(huán)境中所有類別的虛擬機各一臺，這樣可以保證搜索空間的多樣性和完整性。然而，這種方案的初始化資源池intial的大小為·Num(vm)，搜索空間比較大，增加算法復雜度。其中，為工作流中的子任務數(shù)量，Num(vm)為所有云服務提供商的實例類型數(shù)量總和，其定義為

其中，Num(p)為云服務提供商所提供的實例類型數(shù)量。

為進一步壓縮搜索空間，同時保持原有潛在解的多樣性，設計初始化資源池intial的大小是|S(w)|Num(vm)，其中，S(w)是工作流中的最大可并行子任務集合。由于除了S(w)中的子任務外，其他子任務都會和S(w)中的子任務存在直接和間接的依賴關系，所以該初始化資源策略可以保證每個子任務都有選擇一種類型實例的機會，從而保證潛在解的多樣性，同時降低搜索空間。

4.2.3 適應度函數(shù)

粒子的適應度函數(shù)是用來評價2個相比較粒子的優(yōu)劣性，通常較小的適應度函數(shù)值對應的粒子較優(yōu)。由于前期的粒子編碼策略不滿足健全性原則，即會出現(xiàn)工作流的執(zhí)行時間超過對應截止日期，所以需要對可行解和超過截止日期的不可行解的適應度函數(shù)區(qū)分定義。判斷2個粒子優(yōu)劣的適應度函數(shù)分3種不同情況定義。

情況1一個粒子是可行解，另一個粒子是不可行解。毫無爭議地選擇可行解，其適應度值定義為

情況2 2個粒子都是可行解。選擇執(zhí)行代價較低的粒子，其適應度值定義為

情況3 2個粒子都是不可行解。選擇執(zhí)行時間較小的粒子，因為該粒子進化后更有可能變?yōu)榭尚薪狻Ｆ溥m應度值定義為

4.2.4 粒子的更新策略

如式(6)所示，PSO包括3個核心部分：慣性部分、個體認知部分和社會認知部分。為克服傳統(tǒng)PSO存在的過早收斂缺陷，ADPSOGA引入遺傳算法的變異和交叉操作，對式(6)中相應部分進行更新操作。粒子在時刻的更新方式為

其中，M()表示變異操作，C()和C()表示交叉操作。

式(6)中的慣性部分結合遺傳算法中變異操作思想，慣性部分的更新方式為

其中，1為0~1的隨機數(shù)。M()隨機選取粒子中的一個分位，不規(guī)律改變其分位值，且新值必須都在對應的閾值內。

圖3為對圖2編碼粒子的變異操作，隨機選擇粒子的一個分位mp1，mp1位置上的值由(0,1,2)更新為(1,2,0)，該變異符合調度準則。

圖3 慣性部分的變異操作

式(6)中的個體認知和社會認知部分結合遺傳算法交叉操作思想，其更新結果分別如式(16)和式(17)所示。

其中，2和3為0~1的隨機數(shù)，C()（或C()）隨機選擇粒子的2個分位，將分位之間的數(shù)值與對應（或）分位之間的數(shù)值進行交叉。

圖4為個人（或社會）認知部分的交叉操作，隨機產(chǎn)生2個交叉位置（即cp1和cp2），將粒子cp1和cp2位置之間的值替換為（或）在該區(qū)間的值。

圖4 個人（或社會）認知部分的交叉操作

4.2.5 粒子到調度結果的映射

編碼粒子到調度結果的映射如算法1所示。

算法1 編碼粒子到調度結果的映射

procedure Schedule_Generation(,intial,)

1) 初始化:←,←,total← 0,total← 0

2) 計算[||×|intial|]

3) 計算intra[||×||],inter[||×||, ||×||]

4) for= 0 to= ||?1

5)t=[],r(i)=R[()]

6) ift為真實入任務then

7) ifr(i)未啟動then

8) 啟動r(i),r(i)=boot(r(i)),(r(i)) = LETr(i)?boot(r(i))

9) end if

10)STt=r(i)

11) else

12) 調用max(t)過程, max= max(t)

13) ifr(i)未啟動then

14) 啟動r(i),r(i)=max(max,boot(r(i))),

(r(i)) = LETr(i)?boot(r(i))

15) end if

16)STt=max(max, r(i))

17) end if

18)=[][()]

19) for each childtoftdo

20) ift被調度到與t同一個云中，但不同的虛擬機上then

21)+=intra[][]

22) else ift被調度到與t不同的云中 then

23)+=inter[i][c]

24) end if

25) end for

26)ETt= STt + exe

27)=∪(t,r(i),STt,ETt)

28) ifr(i)?then

29)=∪{ r(i)}

30) end if

31)r(i)=r(i)

32) end for

33)根據(jù)式(3)和式(4)分別計算total和total

34)輸出調度方案及其對應結果= (,,total,total)

算法1的輸入包括工作流、初始化資源池intial和編碼粒子。首先，對調度方案=(,,total,total)的四元素初始化（第1)行）。初始化后，計算每個子任務對應不同類型實例的估計執(zhí)行時間矩陣[||×|intial|]，矩陣中的元素[][]表示子任務t在虛擬機mv上的估計執(zhí)行時間（第2) 行）。計算子任務之間的數(shù)據(jù)量在單云和多云之間的估計通信時間，intra[][]表示單云中子任務t產(chǎn)生的數(shù)據(jù)量通信到子任務t所需的估計時間，inter[][][][]表示子任務t產(chǎn)生的數(shù)據(jù)量從云通信到云的子任務t所需的估計時間（第3)行）。

經(jīng)過以上操作，目前已得到從編碼粒子得到候選解的全部信息。逐步掃描粒子的各個分位，生成對應的和集合?；凇皢栴}編碼”，粒子的編碼分位對應子任務，分位的值對應實例資源，因此，確定子任務t被分配到實例r(i)上（第5)行）。第6)~17)行是計算子任務t的估計開始時間STt，這里有2種情況。

1) 子任務t是真實入任務，即其沒有直接先驅子任務。當虛擬機r(i)可用時，子任務t立刻開始執(zhí)行，其估計開始時間STt為虛擬機r(i)的已租賃時間LETr(i)。另外，需要判斷虛擬機r(i)是否已開啟，如果未開啟，則需要啟動虛擬機，虛擬機的已租賃時間LETr(i)即虛擬機的初始化時間boot(r(i))。

2) 子任務t不是入任務，即其有一個或多個父任務。子任務t不但需要等待資源空閑時才可執(zhí)行，還得等待其所有父任務執(zhí)行完成，并將產(chǎn)生數(shù)據(jù)通信到虛擬機r(i)上才可執(zhí)行。調用max_(t)過程計算子任務t等待時間和數(shù)據(jù)通信代價，同時考慮虛擬機r(i)是否已被啟動。

計算完子任務t的估計開始時間STt，需要根據(jù)其在虛擬機上的估計執(zhí)行時間和數(shù)據(jù)通信時間，來計算子任務t的估計結束時間ETt（第18)~26)行）。對于數(shù)據(jù)通信時間的計算，需要根據(jù)其后輩子任務t是否與子任務t分配在同一個云中來確定，這里有3種情況。

1)t與t在同一臺虛擬機上執(zhí)行，則通信時間為0。

2)t與t在同一個云中但不同虛擬機上執(zhí)行，則通信時間為intra[][]。

3)t與t分別在不同云（如云和云）上執(zhí)行，則通信時間為inter[i][c]。

子任務t調度到虛擬機r(i)，其開始時間STt和結束時間ETt等四元素的映射關系添加到集合中（第27)行）。隨后判斷虛擬機r(i)是否已被添加到租賃資源中，如果未被添加，則進行添加（第28)~30)行）。虛擬機r(i)的最新已租賃時間，等于子任務t的估計完成時間（第31)行）。最后，根據(jù)式(3)和式(4)分別計算工作流的總執(zhí)行時間和總執(zhí)行代價。輸出編碼粒子對應的調度方案。子任務的等待時間和通信代價如算法2所示。

算法2 子任務的等待時間和通信代價

procedure max_(t)

1) 初始化：wait← 0,tranfer← 0

2) for each parenttoftdo

3) ift被調度到與t同一個云中，但不同的虛擬機上then

4)wait=max(wait,intra[][])

5) else ift被調度到與t不同的云中 then

6)wait=max(wait,inter[p][i] )

7)tranfer+=(e)c,p

8) end if

9) end for

10) 輸出最長等待時間wait, 通信代價tranfer

首先，初始化等待時間wait和數(shù)據(jù)通信代價tranfer（第1)行）。子任務t等待時間等于其所有父任務中最大的數(shù)據(jù)通信時間（第3)~6)行）。當子任務t和其父任務t分配到不同云中時，才考慮數(shù)據(jù)通信代價（第7)行）。

4.2.6 參數(shù)設置

式(6)的慣性權重因子能夠決定PSO的收斂性和搜索能力[4]。當較小時，算法具有較強的局部搜索能力；否則，算法具有較強的全局搜索能力。在算法執(zhí)行初期，更注重問題空間搜索的多樣性和粒子全局搜索能力，隨著搜索深入，后期則更加注重局部搜索方面的能力。因此，慣性權重因子的權值應隨著算法迭代次數(shù)的增多而逐漸減少。式(18)是經(jīng)典的慣性權重因子調整策略。

其中，max和min分別是初始化時設定的最大值和最小值，cur和max分別表示當前算法迭代次數(shù)和初始化設定的最大迭代次數(shù)。

以上的經(jīng)典慣性權重因子調整策略，的變化僅和迭代次數(shù)有關，不能很好地滿足實際問題的非線性和復雜多變特性。慣性權重因子的權值大小應該隨著種群粒子的進化而不斷演變，因此，構建一種根據(jù)當前種群粒子的優(yōu)劣而自適應調整的慣性權重因子調整策略。如式(19)所示，該策略基于當前粒子與全局歷史最優(yōu)粒子之間的差異程度來調整慣性權重因子大小。

其中，(X?1,gBest?1)表示粒子X?1和全局歷史最優(yōu)粒子gBest?1之間的不同分位的位數(shù)大小，是工作流中子任務的個數(shù)大小。當(X?1)值較小時，表示粒子X?1和gBest?1之間差異程度較小，所以應該減小的權值，以保證粒子可在小范圍內更好搜索，找到優(yōu)化解；否則，應該增加的權值，使粒子的搜索空間變大，以便更快找到優(yōu)化解空間。因此，慣性權重因子的權值計算式更新為

另外，算法的2個認知因子1和2采用線性增減策略進行設置[24]。其更新方式如式(21)和式(22)所示。

其中，1_start和2_start分別表示參數(shù)1和2迭代的初始值，1_end和2_end分別表示參數(shù)1和2迭代的最終值。

4.2.7 算法流程

ADPSOGA流程如圖5所示，具體步驟如下。

步驟1 初始化ADPSOGA中種群大小、最大迭代次數(shù)、慣性權重因子和認知因子等參數(shù)的數(shù)值，隨機生成初始種群。

步驟2 根據(jù)第4.2.5節(jié)的粒子映射策略以及式(11)~式(13)計算各個粒子不同情況下的適應度值，從中選擇適應度值最小的粒子作為種群全局最優(yōu)粒子，將第一代中每個粒子設置為其自身歷史最優(yōu)粒子。

步驟3 根據(jù)粒子更新式(14)~式(17)更新粒子。

步驟4 重新計算每個粒子的適應度值，若當前粒子的適應度值小于其自身歷史最優(yōu)值，則將新粒子更新為其自身歷史最優(yōu)粒子。

圖5 ADPSOGA流程

步驟5 若當前粒子的適應度值小于種群全局最優(yōu)粒子的適應度值，則將該粒子更新為種群全局最優(yōu)粒子。

步驟6 檢查是否滿足算法終止條件，如果滿足，則算法終止；反之，轉到步驟3。

5 實驗仿真與結果

本文的模擬實驗是在64位Windows 7系統(tǒng)環(huán)境下，其配置是8 GB內存和2.30 GHz的i7 Intel處理器?；谖墨I[24]，ADPSOGA的參數(shù)設置如下。種群大小為100，最大迭代次數(shù)為1 000，1_start= 0.9，1_end= 0.2，2_start =0.4，2_end =0.9。

5.1 實驗設置

工作流測試樣例采用Bharathi等[25]研究的來自5個不同科學領域的工作流：天文學（Montage）、地震科學（CyberShake）、生物基因學（Epigenomics）、重力物理學（LIGO）以及生物信息學（SIPHT）。這些工作流具有不同結構，它們的信息（如子任務大小、數(shù)據(jù)通信量和依賴關系等）被存儲在xml格式的文件中。對于每種工作流，選取其中3個數(shù)量級：小型（約30個任務），偏小型（約50個任務）和中型（約100個任務）。由于子任務在具體實例上的執(zhí)行時間存在波動，因此，假設工作流子任務的大小呈正態(tài)分布，其變化率區(qū)間為(?10%,10%)[1]。

基于Amazon服務帶寬[20]，假設單云的云內帶寬為20 Mbit/s。不同云之間的通信代價如表2所示，這些數(shù)值是通過帶寬測試工具iperf測試得到，主要針對Amazon EC2的悉尼區(qū)域(C1)、Rackspace(C2)和GoGrid(C3)。

表2 不同云之間的通信代價

假設帶寬大小變化率滿足最大減少19%、均值減少9.5%、標準差為5%的正態(tài)分布[1]。另外，假設虛擬機的初始化時間是97 s，要價區(qū)間是1 h[21]。表3是不同云之間的數(shù)據(jù)通信價格，該表數(shù)值來自各自云服務提供商的官方網(wǎng)站。

表3 不同云之間的數(shù)據(jù)通信價格（美元·GB?1）

每個工作流都有一個對應的截止日期，以此來測試調度策略性能。選擇5個不同的截止日期D()來測試本文涉及的調度方法。

其中，()是用HEFT算法[26]調度工作流的執(zhí)行時間，r則是從集合{1.5, 2, 5, 8, 15}中依次取值。

5.2 對比算法

為了驗證ADPSOGA調度策略的有效性，通過改寫文獻[20]的靜態(tài)MCPCPP調度策略和文獻[1]的WPSO調度策略，使它們適應多云環(huán)境，并作為本文的對比算法。

MCPCPP調度策略是在靜態(tài)多云環(huán)境下，在滿足工作流截止日期前提下，追求執(zhí)行代價最低。該方法通過合并包含共同“割邊”的相鄰子任務，降低算法復雜度并減少數(shù)據(jù)通信時間；分配子截止日期到局部關鍵路徑上，并對局部關鍵路徑進行整體調度，壓縮數(shù)據(jù)通信時間和代價；通過調度局部關鍵路徑到“最適合”實例上，進一步減少工作流執(zhí)行代價。然而，該策略未考慮多云之間的數(shù)據(jù)通信代價，也忽視了實例啟停時間對調度結果的影響。因此，在對比試驗中，MCPCPP調度策略同時考慮云間的數(shù)據(jù)通信代價和實例啟停時間。

WPSO調度策略是在單云環(huán)境下，在滿足工作流截止日期前提下，追求執(zhí)行代價最低。該方法利用傳統(tǒng)PSO的連續(xù)編碼方式，其子任務和實例的映射關系是通過選取編碼粒子的實數(shù)取整部分來實現(xiàn)，粒子更新方式是基于式(6)的傳統(tǒng)方式。為了和本文算法形成對比，WPSO經(jīng)過適當改寫就可以適合多云環(huán)境的工作流調度。WPSO的總體框架和文獻[1]相同，但在考慮初始資源池時，需要考慮多云環(huán)境下的所有實例類型，另外，還需要考慮多云之間數(shù)據(jù)傳輸?shù)耐ㄐ糯鷥r，其慣性權重因子和認知因子1、2的設置依然參照文獻[1]。

5.3 結果評價

為了測試ADPSOGA、MCPCPP和WPSO策略在多云環(huán)境存在波動因素的工作流調度性能，對各種波動因素的生成函數(shù)隨機取值，并對每種因素各進行100組實驗，綜合深入考察各個調度策略性能。

表4 ADPSOGA和WPSO在D1(w)達到gBest的迭代次數(shù)

表5 ADPSOGA和WPSO在D5(w)達到gBest的迭代次數(shù)

另外，由于測試的5個類型工作流的結構和子任務大小存在差異，因此，需要對工作流執(zhí)行代價的結果進行歸一化處理。引入工作流標準執(zhí)行代價()，如式(24)所示。

其中，()表示采用本文任何一種調度策略產(chǎn)生的工作流執(zhí)行代價，而()則表示利用不考慮截止日期約束的最廉價調度策略[6]所產(chǎn)生的工作流執(zhí)行代價。

表4和表5分別表示在100組重復測試中，ADPSOGA和WPSO這2種基于PSO的調度策略在1()和5()不同截止日期下，得到各自全局歷史最優(yōu)值的平均迭代次數(shù)。由表4和表5可知，隨著工作流子任務數(shù)量的增加，2種算法得到各自全局歷史最優(yōu)值的平均迭代次數(shù)均明顯增多。這主要是因為子任務數(shù)量的增加，使基于編碼策略的粒子維度增加，粒子更新過程中也產(chǎn)生更多的新粒子和更大種群規(guī)模，從而導致出現(xiàn)更多的候選解粒子，并擴大問題域的搜索空間，使搜索到最佳解的迭代次數(shù)增多。隨著截止日期約束的變化，2種不同算法達到的平均迭代次數(shù)并未發(fā)生明顯改變，反而是不同調度策略之間在同等環(huán)境下的迭代次數(shù)存在明顯區(qū)別，這說明截止日期約束對迭代次數(shù)的影響并不顯著。同等條件下，ADPSOGA調度策略的平均迭代次數(shù)明顯高于WPSO調度策略。ADPSOGA調度策略的自適應慣性權重因子和漸進式增減認知因子的設置，導致其編碼粒子更具有多樣性，在算法執(zhí)行初期更加注重問題空間的廣泛性搜索，而后期則傾向于對算法收斂性的關注，從而產(chǎn)生更佳的全局歷史最優(yōu)值。而WPSO調度策略主要采用連續(xù)的編碼和更新方式來解決工作流調度這個離散問題，這種編碼方式容易陷入局部最優(yōu)，從而過早收斂，導致產(chǎn)生的優(yōu)化結果并非最優(yōu)結果。

圖6是多云環(huán)境存在波動因素的5種中型工作流在3種不同調度策略（即MCPCPP、ADPSOGA和WPSO）中的完成率。該完成率是指在相應的100組測試中，工作流完成時間達到對應截止日期約束要求的比例大小。從圖6中的5個子圖可以發(fā)現(xiàn)，隨著截止日期的增大，基于PSO的ADPSOGA和WPSO這2種調度策略的完成率都呈上升趨勢。特別在5()階段，除了CyberShake工作流，2種調度策略的完成率都達到了100%。MCPCPP調度策略的完成率明顯低于其他2種調度策略，其完成率變化規(guī)律與截止日期之間不存在明顯的相關性，即其完成率不隨著截止日期約束的寬松而得到明顯提升。在Montage、Epigenomics和LIGO工作流的測試樣例中，MCPCPP調度策略在不同的截止日期約束下的完成率均為0，主要是因為MCPCPP調度策略過于強調壓縮子任務之間的數(shù)據(jù)通信代價，這種操作方式對動態(tài)因素的抗干擾能力較弱。

圖6 多云環(huán)境存在波動因素的5種中型工作流在不同調度策略的完成率

圖6(a)是3種調度策略在不同截止日期約束下的Montage工作流完成率。ADPSOGA調度策略在1()和2()階段的完成率明顯優(yōu)于WPSO調度策略。WPSO調度策略在1()階段的完成率還不到30%，但在3()階段就達到近80%，稍遜于ADPSOGA調度策略。在4()和5()階段，ADPSOGA和WPSO調度策略均達到100%的工作流完成率。圖6(b)則是3種調度策略的CyberShake工作流完成率。在1()階段，WPSO調度策略的完成率超過20%，排在3種策略之首，其次是MCPCPP調度策略，完成率最低的是ADPSOGA調度策略。但隨著截止日期約束不斷寬松，如在3()階段之后，ADPSOGA調度策略就處于優(yōu)勢地位，其完成率均超過另外2種調度策略。在5()階段，ADPSOGA和WPSO這2種調度策略的工作流完成率均接近100%，但MCPCPP調度策略卻只有不足10%的完成率。這主要還是歸因于MCPCPP過分壓縮子任務間的數(shù)據(jù)通信。圖6(c)是3種調度策略的Epigenomics工作流完成率。與圖6(a)和圖6(d)相似，MCPCPP調度策略在所有截止日期約束下的完成率均為0，除了過分壓縮數(shù)據(jù)的原因外，還主要跟這3種工作流的結構和對應子任務大小有關。這3種工作流均包含較多只占實例小部分單位執(zhí)行時間的子任務，通過MCPCPP調度策略的整合壓縮，在同一個路徑上的這些子任務被統(tǒng)一分配給特定執(zhí)行實例。當環(huán)境波動時，這些子任務路徑的實際執(zhí)行時間往往超過估計值，所以使工作流無法在截止日期前完成。另外，各階段的ADPSOGA和WPSO調度策略的完成率相當接近，均超過85%。圖6(d)是3種調度策略的LIGO工作流完成率。ADPSOGA在1()和2()階段的完成率明顯優(yōu)于WPSO。同時在3()之后，它們二者的完成率基本相同，均接近100%。圖6(e)是3種調度策略的SIPHT工作流完成率。在1()階段，ADPSOGA調度策略的完成率最高，達到85%。在2()階段，ADPSOGA完成率稍遜于WSPO。在后續(xù)階段，基于PSO的2種調度策略的完成率均達到100%。

綜上，MCPCPP調度策略在多云環(huán)境存在波動因素的適應性最差。ADPSOGA和WPSO調度策略在截止日期約束寬松的情況下，均能獲得良好的完成率。在截止日期約束嚴格的情況下，ADPSOGA調度策略相比于其他2種策略，性能更加優(yōu)越。這主要是因為ADPSOGA的編碼策略和更新方式，使其獲取更加多樣的進化種群，適應動態(tài)變化環(huán)境。

圖7是3種不同調度策略（即MCPCPP、ADPSOGA和WPSO）在對應3種不同截止日期（即1()、3()和5()）約束下的工作流平均標準執(zhí)行代價和平均執(zhí)行時間（每個結果針對100組重復測試樣例）。每個子圖中的3條線，分別表示對應的3個截止日期參考線，目的是為了確定相關工作流平均執(zhí)行時間是否超過對應截止日期。同一圖中同時展示執(zhí)行代價和執(zhí)行時間的目的是為了尋找執(zhí)行時間滿足截止日期約束，同時其執(zhí)行代價最低的有效調度策略。

圖7(a)是Montage工作流的平均標準執(zhí)行代價和平均執(zhí)行時間。MCPCPP調度策略在3個截止日期約束下的平均標準執(zhí)行代價()都是最低的，但其對應的平均執(zhí)行時間均遠超過截止日期參考線，因此，該調度策略在3個截止日期約束下均不是有效調度方法。在1()、3()和5()階段，ADPSOGA和WPSO調度策略均滿足截止日期約束，且ADPSOGA調度策略的()最低。尤其在3()階段，ADPSOGA調度策略的優(yōu)勢顯得尤為明顯。相對于其他工作流而言，3種調度策略在執(zhí)行Montage工作流時，產(chǎn)生更大的平均標準執(zhí)行代價()，其大約是在同等條件下調度SIPHT工作流的20倍。造成巨大差距的原因主要是因為不同類型工作流的自身結構和子任務大小存在差異。對于Montage工作流而言，其第2層中含有許多子任務，該層子任務在最快虛擬機上的執(zhí)行時間都不超過15 s。在要價區(qū)間是1 h的實驗環(huán)境下，這些子任務都只占用虛擬機整個要價區(qū)間的很小一部分。為了滿足截止日期約束，需要啟動更多的高速虛擬機來處理Montage工作流相關子任務，造成資源浪費、對應標準執(zhí)行代價過高。MCPCPP調度策略往往將第2層子任務壓縮到少數(shù)幾臺高速虛擬機上執(zhí)行。當存在波動因素時，其結果往往是執(zhí)行時間超過對應截止日期約束。

對于CyberShake工作流，在1()階段，3種調度策略的平均執(zhí)行時間均超過對應截止日期參考線，說明它們均不滿足截止日期約束。雖然ADPSOGA調度策略的()最低，但無法判定其就是最優(yōu)調度策略，因為其不滿足截止日期約束條件。在3()和5()階段，其整體情況與Montage類似。MCPCPP調度策略雖然在5()階段()最低，但其不滿足相應截止日期約束條件。另外，2種基于PSO的調度策略均滿足對應截止日期約束，其中ADPSOGA調度策略的平均標準執(zhí)行代價()最低，其是相對MCPCPP和WPSO調度策略的最優(yōu)調度方法。

對于Epigenomics工作流，MCPCPP調度策略雖然在每個階段的平均標準執(zhí)行代價()都是最低的，但其對應的平均執(zhí)行時間均明顯高于截止日期參考線，因此，MCPCPP調度策略不是有效方法。在滿足約束條件的調度策略中，ADPSOGA調度策略在3個階段的優(yōu)勢較為明顯，其不僅在工作流平均執(zhí)行時間上處于最低值，而且相應的平均標準執(zhí)行代價()也是最低的。這主要是因為ADPSOGA調度策略的編碼技巧和更新方式，使其獲得更大的種群類別和問題搜索空間，能夠更好地適應動態(tài)多云環(huán)境。

圖7 不同調度策略在3種截止日期下的工作流標準執(zhí)行代價和執(zhí)行時間

相對于LIGO和SIPHT工作流，3種調度策略的表現(xiàn)情況與Epigenomics工作流類似，在此不再贅述。

綜上，MCPCPP調度策略雖然工作流平均標準執(zhí)行代價()通常較低，但其往往不滿足對應的截止日期約束，不能算是好的調度方法。WPSO調度策略雖然通常滿足截止日期約束，但其產(chǎn)生的平均標準執(zhí)行代價()一般不理想。ADPSOGA調度策略相對于所有測試樣例，在滿足截止日期約束下的平均標準執(zhí)行代價()表現(xiàn)是最優(yōu)的。

6 結束語

本文提出一種基于PSO和GA更新算子的多云環(huán)境下ADPSOGA工作流調度策略。該算法綜合考慮云間數(shù)據(jù)通信代價、虛擬機啟停時間和云環(huán)境下波動干擾因素等。其是以工作流截止日期為約束，優(yōu)化工作流總執(zhí)行代價的元啟發(fā)式算法。通過對5個類型的中型工作流的調度測試表明，ADPSOGA調度策略在多云環(huán)境存在波動因素干擾下，對帶截止日期約束的工作流調度具有更佳的有效性和適應性。

未來工作中，將進一步考慮壓縮初始資源池大小的方法，使算法的執(zhí)行效率進一步提升。另外，將對動態(tài)波動的影響因子逐一分析，找出干擾最大的若干影響因子，進一步提高算法的頑健性。

[1] RODRIGUEZ M A, BUYYA R. Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J]. IEEE Transactions on Cloud Computing, 2014, 2(2): 222-235.

[2] FARD H M, PRODAN R, FAHRINGER T. A truthful dynamic workflow scheduling mechanism for commercial multicloud environments[J]. IEEE Transactions on Parallel & Distributed Systems, 2013, 24(6): 1203-1212.

[3] MALAWSKI M, JUVE G, DEELMAN E, et al. Cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[C]//International Conference for High Performance Computing, Networking, Storage and Analysis. 2012: 1-11.

[4] MASDARI M, SALEHI F, JALALI M, et al. A survey of PSO-based scheduling algorithms in cloud computing[J]. Journal of Network & Systems Management, 2017, 25(1): 1-37.

[5] WU Z, NI Z, GU L, et al. A revised discrete particle swarm optimization for cloud workflow scheduling[C]//International Conference on Computational Intelligence and Security, 2010: 184-188.

[6] 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.

[7] MATTOSO M, DIAS J, OCA?A K A C S, et al. Dynamic steering of HPC scientific workflows: a survey[J]. Future Generation Computer Systems, 2015, 46(C): 100-113.

[8] ZENG L, VEERAVALLI B, ZOMAYA A Y. An integrated task computation and data management scheduling strategy for workflow applications in cloud environments[J]. Journal of Network & Computer Applications, 2015, 50(C): 39-48.

[9] CHEN W N, ZHANG J. An ant colony optimization approach to a Grid workflow scheduling problem with various QoS requirements[J]. IEEE Transactions on Systems Man & Cybernetics Part C, 2008, 39(1): 29-43.

[10] 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.

[11] HIGASHINO W A, CAPRETZ M A M, TOLEDO M B F D, et al. A hybrid particle swarm optimization-genetic algorithm applied to grid scheduling[J]. International Journal of Grid & Utility Computing, 2016, 7(2): 113-129.

[12] 苑迎春, 李小平, 王茜, 等. 基于逆向分層的網(wǎng)格工作流調度算法[J].計算機學報, 2008, 31(2): 282-290.

YUAN Y C, LI X P, WANG Q, et al. Bottom level based heuristic for workflow scheduling in grids[J]. Chinese Journal of Computers, 2008, 31(2): 282-290.

[13] ABRISHAMI S, NAGHIBZADEH M, EPEMA D H J. Cost-driven scheduling of grid workflows using partial critical paths[J]. IEEE Transactions on Parallel & Distributed Systems, 2012, 23(8): 1400-1414.

[14] KHAJEMOHAMMADI H, FANIAN A, GULLIVER T A. Fast workflow scheduling for grid computing based on a multi-objective genetic algorithm[C]//Communications, Computers and Signal Processing. 2013: 96-101.

[15] 沈虹, 李小平. 帶準備時間和截止期約束的云服務工作流調度算法[J]. 通信學報, 2015, 36(6): 183-192.

SHEN H, LI X P. Algorithm for the cloud service workflow scheduling with setup time and deadline constraints[J]. Journal on Communications, 2015, 36(6): 183-192.

[16] 肖鵬, 胡志剛, 屈喜龍. 面向數(shù)據(jù)密集型工作流的能耗感知調度策略[J]. 通信學報, 2015, 36(1): 149-158.

XIAO P, HU Z G, QU X L. Energy-aware scheduling policy for data-intensive workflow[J]. Journal on Communications, 2015, 36(1): 149-158.

[17] MAO M, HUMPHREY M. Auto-scaling to minimize cost and meet application deadlines in cloud workflows[C]//High Performance Computing, Networking, Storage and Analysis. 2011: 1-12.

[18] PANDEY S, WU L, GURU S M, et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//IEEE International Conference on Advanced Information Networking and Applications. 2010: 400-407.

[19] KEAHEY K, TSUGAWA M, MATSUNAGA A, et al. Sky computing[J]. IEEE Internet Computing, 2009, 13(5): 43-51.

[20] LIN B, GUO W, XIONG N, et al. A pretreatment workflow scheduling approach for big data applications in multicloud environments[J]. IEEE Transactions on Network & Service Management, 2016, 13(3): 581-594.

[21] WOO S S, MIRKOVIC J. Optimal application allocation on multiple public clouds[J]. Computer Networks, 2014, 68(11): 138-148.

[22] KENNEDY J, EBERHART R. Particle swarm optimization[C]//IEEE International Conference on Neural Networks. 2002: 1942-1948.

[23] SU J S, GUO W Z, YU C L, et al. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network[J]. Chinese Journal of Computers, 2014, 37(2): 445-456.

[24] SHI Y, EBERHART R. A modified particle swarm optimizer[C]// IEEE World Congress on Computational Intelligence. 1998: 69-73.

[25] BHARATHI S, CHERVENAK A, DEELMAN E, et al. Characterization of scientific workflows[C]//Workflows in Support of Large-Scale Science. 2008: 1-10.

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

Scheduling strategy for science workflow with deadline constraint on multi-cloud

LIN Bing1,2,3, GUO Wenzhong2,3,4, CHEN Guolong2,3

1. College of Physics and Energy, Fujian Normal University, Fuzhou 350117, China 2. Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing (Fuzhou University), Fuzhou 350116, China 3. Key Laboratory of Spatial Data Mining & Information Sharing, Ministry of Education, Fuzhou 350003, China 4. College of Mathematics and Computer Science, FuzhouUniversity, Fuzhou 350116, China

In view of the deadline-constrained scientific workflow scheduling on multi-cloud, an adaptive discrete particle swarm optimization with genetic algorithm (ADPSOGA) was proposed, which aimed to minimize the execution cost of workflow while meeting its deadline constrains. Firstly, the data transfer cost, the shutdown and boot time of virtual machines, and the bandwidth fluctuations among different cloud providers were considered by this method. Secondly, in order to avoid the premature convergence of traditional particle swarm optimization (PSO), the randomly two-point crossover operator and randomly one-point mutation operator of the genetic algorithm (GA) was introduced. It could effectively improve the diversity of the population in the process of evolution. Finally, a cost-driven strategy for the deadline-constrained workflow was designed. It both considered the data transfer cost and the computing cost. Experimental results show that the ADPSOGA has better performance in terms of deadline and cost reducing in the fluctuant environment.

cloud computing, deadline constraint, workflow scheduling, fluctuation

TP338

A

10.11959/j.issn.1000-436x.2018006

林兵（1986-），男，福建福清人，博士，福建師范大學講師，主要研究方向為云計算技術、計算智能及其應用。

郭文忠（1979-），男，福建泉港人，博士，福州大學教授、博士生導師，主要研究方向為計算智能及其應用。

陳國龍（1965-），男，福建莆田人，博士，福州大學教授、博士生導師，主要研究方向為人工智能、網(wǎng)絡安全。

2017-05-24；

2018-01-01

郭文忠，fzugwz@163.com

國家重點研發(fā)計劃基金資助項目（No.2017YFB1002000）；國家自然科學基金資助項目（No.61672159）；福建省科技創(chuàng)新平臺計劃基金資助項目（No.2009J1007, No.2014H2005）；海峽政務大數(shù)據(jù)應用省級協(xié)同創(chuàng)新中心基金資助項目

: The National Key R&D Program of China (No.2017YFB1002000), The National Natural Science Foundation of China (No.61672159), The Technology Innovation Platform Project of Fujian Province (No.2009J1007, No.2014H2005), The Foundation of The Fujian Collaborative Innovation Center for Big Data Application in Governments