李學(xué)俊　徐　佳　朱二周　張以文

(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　合肥　230601)

?

任務(wù)調(diào)度算法中新的自適應(yīng)慣性權(quán)重計(jì)算方法

李學(xué)俊徐佳朱二周張以文

(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院合肥230601)

(xjli@ahu.edu.cn)

粒子群算法(particle swarm optimization, PSO)是解決云計(jì)算環(huán)境中工作流系統(tǒng)的任務(wù)調(diào)度優(yōu)化問(wèn)題的主流智能算法.然而基于傳統(tǒng)自適應(yīng)慣性權(quán)重的粒子群任務(wù)調(diào)度算法易陷入局部最優(yōu)，導(dǎo)致調(diào)度方案的執(zhí)行時(shí)間與費(fèi)用較高.因此，通過(guò)改進(jìn)單個(gè)粒子的成功值計(jì)算方法，提出了一種新的自適應(yīng)慣性權(quán)重計(jì)算方法NAIWPSO(new adaptive inertia weight based particle swarm optimization).該方法通過(guò)比較每個(gè)粒子的適應(yīng)度與全局最優(yōu)值，可以更加精確描述粒子狀態(tài)，進(jìn)而提高了權(quán)重的自適應(yīng)性.在新慣性權(quán)重基礎(chǔ)上，提出了一種解決云工作流系統(tǒng)中任務(wù)調(diào)度優(yōu)化問(wèn)題的改進(jìn)粒子群算法.新權(quán)重可以更準(zhǔn)確的調(diào)整粒子速度，使算法更好地平衡粒子全局與局部搜索，避免陷入局部最優(yōu)，獲得執(zhí)行費(fèi)用更優(yōu)的調(diào)度方案.實(shí)驗(yàn)表明，與5種已有慣性權(quán)重算法比較，新算法收斂穩(wěn)定、適應(yīng)度最低、執(zhí)行費(fèi)用平均減少18%.

云計(jì)算；工作流；任務(wù)調(diào)度；粒子群算法；慣性權(quán)重

工作流系統(tǒng)能夠根據(jù)用戶的需求管理與優(yōu)化工作流的任務(wù)調(diào)度[1].云計(jì)算是一種高效、可伸縮、高可靠性的網(wǎng)絡(luò)資源模型[2]，為用戶快速分配與回收各種資源(包括網(wǎng)絡(luò)、服務(wù)、存儲(chǔ)、應(yīng)用資源等)[3-4].隨著云環(huán)境中科學(xué)計(jì)算、大規(guī)模電子商務(wù)等應(yīng)用的發(fā)展，用戶的服務(wù)質(zhì)量(quality of service, QoS)要求不斷提高，系統(tǒng)應(yīng)用的運(yùn)行費(fèi)用急速上漲[5].因此，如何在滿足QoS約束的前提下降低云環(huán)境中工作流運(yùn)行費(fèi)用是一個(gè)值得研究的問(wèn)題[6].在文獻(xiàn)[7]中，Yu等人提出了一種在網(wǎng)格計(jì)算環(huán)境中最小化任務(wù)執(zhí)行費(fèi)用的工作流調(diào)度算法.Wieczorek等人[8]使用HEFT任務(wù)調(diào)度算法較好地解決了網(wǎng)格計(jì)算環(huán)境中科學(xué)工作流調(diào)度問(wèn)題.Xu等人[9]提出了一種在大量任務(wù)情況下的資源分配模型，有效降低了資源使用費(fèi)用.云工作流管理系統(tǒng)可以根據(jù)用戶的需求為每個(gè)任務(wù)分配合適的資源，有效降低云計(jì)算環(huán)境中工作流的運(yùn)行費(fèi)用[10-15].

目前云工作流管理系統(tǒng)中最常使用的任務(wù)調(diào)度算法為Eberhart和Shi[16]于1998年提出的粒子群算法(particle swarm optimization, PSO).該算法最初是受到鳥(niǎo)群、魚(yú)群等群體動(dòng)物的合作性行為啟發(fā)，進(jìn)而利用群體智能建立的一個(gè)隨機(jī)優(yōu)化啟發(fā)式算法[17].PSO算法具有參數(shù)少、易實(shí)現(xiàn)、收斂速度快等特性，已被廣泛地應(yīng)用于各種優(yōu)化領(lǐng)域.然而PSO算法沒(méi)有有效地控制粒子的速度，因此無(wú)法很好地平衡粒子全局與局部搜索能力，具有局部收斂的缺陷，導(dǎo)致無(wú)法在有限的迭代次數(shù)中找到最優(yōu)解.

為了解決局部收斂的缺陷，粒子群算法的速度更新公式增加了慣性權(quán)重這一參數(shù)，以增強(qiáng)平衡粒子全局與局部搜索的能力[16].目前，慣性權(quán)重大體上分為3類：常數(shù)或隨機(jī)型慣性權(quán)重[16-18]、線性或指數(shù)變化慣性權(quán)重[19-21]、自適應(yīng)性慣性權(quán)重[22].固定常數(shù)值慣性權(quán)重[16]實(shí)現(xiàn)簡(jiǎn)單，在算法執(zhí)行過(guò)程中，慣性權(quán)重固定為一個(gè)常數(shù)，導(dǎo)致算法容易陷入局部最優(yōu).因此Eberhart和Shi[18]提出了隨機(jī)慣性權(quán)重，以優(yōu)化目標(biāo)動(dòng)態(tài)變化的問(wèn)題.Shi和Eberhart[19-20]又提出線性減少慣性權(quán)重，以提高粒子群算法的求精能力，該算法如果在初期粒子搜索不到較好的位置點(diǎn)，易陷入局部最優(yōu).在線性減少慣性權(quán)重的基礎(chǔ)上，Chatterjee和Siarry[21]提出了指數(shù)減少慣性權(quán)重，在一定程度上避免了算法陷入局部最優(yōu).然而，指數(shù)值的確定是一個(gè)難點(diǎn)，而且算法的計(jì)算量較大，不適合復(fù)雜優(yōu)化問(wèn)題求解.

綜合上述非自適應(yīng)慣性權(quán)重，Nickabadi等人[22]提出了基于自適應(yīng)慣性權(quán)重(adaptive inertia weight, AIW)的粒子群算法(adaptive inertia weight based particle swarm optimization, AIWPSO).該算法可以在算法迭代過(guò)程中根據(jù)整個(gè)粒子群中粒子的位置狀態(tài)信息對(duì)慣性權(quán)重進(jìn)行動(dòng)態(tài)地調(diào)整，提高PSO算法的尋優(yōu)能力.然而，該參數(shù)中的成功值計(jì)算方法只考慮了單個(gè)粒子在不同迭代次數(shù)中位置的優(yōu)劣，造成了自適應(yīng)機(jī)制無(wú)法精確地調(diào)整慣性權(quán)重，導(dǎo)致PSO算法速度調(diào)節(jié)不夠精確，易陷入局部最優(yōu).因此，本文通過(guò)改進(jìn)傳統(tǒng)權(quán)重中的成功值計(jì)算方法，提出了一種新的自適應(yīng)慣性權(quán)重(new adaptive inertia weight, NAIW)；并將基于新自適應(yīng)慣性權(quán)重的粒子群算法(new adaptive inertia weight based particle swarm optimization, NAIWPSO)運(yùn)用到解決云工作流任務(wù)調(diào)度優(yōu)化問(wèn)題.實(shí)驗(yàn)結(jié)果表明，NAIWPSO任務(wù)調(diào)度算法在算法收斂速度、適應(yīng)度和執(zhí)行費(fèi)用3方面均優(yōu)于其余5種(固定、線性、指數(shù)、隨機(jī)、傳統(tǒng)自適應(yīng))慣性權(quán)重的粒子群算法.

1　自適應(yīng)慣性權(quán)重

本節(jié)首先介紹了表示粒子位置狀態(tài)優(yōu)劣的適應(yīng)度計(jì)算方法；然后分析了傳統(tǒng)自適應(yīng)慣性權(quán)重在成功值計(jì)算方面存在粒子位置狀態(tài)表示不全面的不足；最后，提出了一種新的自適應(yīng)慣性權(quán)重，改進(jìn)了成功值計(jì)算公式.該權(quán)重可以更加精確地調(diào)整粒子速度，使算法更好地平衡粒子全局與局部搜索，達(dá)到避免算法局部收斂、搜索到最優(yōu)值的目的.

1.1適應(yīng)度

適應(yīng)度是評(píng)價(jià)任務(wù)調(diào)度方案執(zhí)行時(shí)間和費(fèi)用的一項(xiàng)綜合指標(biāo)[2]，表示粒子群算法中粒子位置狀態(tài)的優(yōu)劣，如式(1)所示.適應(yīng)度可以全面衡量該調(diào)度方案所需的時(shí)間與費(fèi)用.適應(yīng)度越高的調(diào)度方案，所需時(shí)間與費(fèi)用的開(kāi)銷也就越大，粒子位置狀態(tài)就越不好；相反，開(kāi)銷越小，粒子位置狀態(tài)就越好.

(1)

適應(yīng)度的計(jì)算分為3個(gè)部分：1)完工時(shí)間未超出截止期限時(shí)(f1=1，f2=0)的虛擬機(jī)運(yùn)行費(fèi)用；2)完工時(shí)間超出截止期限時(shí)(f1=0，f2=1)的虛擬機(jī)運(yùn)行費(fèi)用；3)各虛擬機(jī)的空閑時(shí)間wastetime之和.其中，makespanSk表示調(diào)度方案Sk中所有任務(wù)的最大完工時(shí)間；deadline表示整個(gè)工作流的截止期限，可以在deadlinemin～deadlinemax之間變化.deadlinemin與deadlinemax的計(jì)算方法如式(2)、式(3)：

deadlinemin=min{makespanSk}；

(2)

deadlinemax=max{makespanSk}.

(3)

在適應(yīng)度計(jì)算式(1)中，costSk為某一調(diào)度方案Sk的費(fèi)用值，其計(jì)算方法如式(4)所示：

(4)

1.2傳統(tǒng)的自適應(yīng)慣性權(quán)重

在文獻(xiàn)[22]中，Nickabadi等人提出了一種自適應(yīng)性慣性權(quán)重AIW，該權(quán)重首先計(jì)算單個(gè)粒子的成功值(如式(5)所示)，之后計(jì)算整個(gè)粒子群的成功率(如式(6)所示)，最后更新慣性權(quán)重(如式(7)所示).

(5)

(6)

(7)

(8)

算法AIWPSO產(chǎn)生的調(diào)度方案執(zhí)行時(shí)間和費(fèi)用比普通PSO算法高.原因在于權(quán)重AIW中成功值計(jì)算公式S(i,t)只考慮了2種情況，即當(dāng)前粒子的適應(yīng)度優(yōu)于上次，成功值則為1，反之則為0.由于該方法沒(méi)有全面分析粒子的位置狀態(tài)信息，即沒(méi)有考慮全局最優(yōu)位置，導(dǎo)致了成功率(式(6))以及慣性權(quán)重值(式(7))的計(jì)算不夠準(zhǔn)確.因此，該方法無(wú)法在每次迭代時(shí)精確地調(diào)整慣性權(quán)重值，造成算法在迭代過(guò)程中不能有效平衡粒子的全局與局部搜索，使算法易陷入局部最優(yōu)，無(wú)法找到最優(yōu)解.

1.3新的自適應(yīng)慣性權(quán)重

針對(duì)傳統(tǒng)慣性權(quán)重中單個(gè)粒子位置狀態(tài)描述不全面的問(wèn)題，本文在成功值計(jì)算方法中增加每個(gè)粒子的適應(yīng)度與全局最優(yōu)值比較，以更加精確地描述粒子所處的位置狀態(tài).權(quán)重NAIW中改進(jìn)后的成功值如式(9)所示.在式(5)中每個(gè)粒子的當(dāng)前適應(yīng)度與上次迭代比較的基礎(chǔ)上，式(9)中S(i,t)加入了全局最優(yōu)值globalbestt.新的S(i,t)計(jì)算方法的取值擴(kuò)充為3種情況：1，0.5，0.該方案基于對(duì)粒子位置狀態(tài)更加細(xì)化的評(píng)價(jià)使得在粒子將要陷入局部最優(yōu)解時(shí)，通過(guò)與全局最優(yōu)適應(yīng)度的比較來(lái)更加準(zhǔn)確地得出S(i,t).精確的S(i,t)可以提高粒子群的成功率(式(6))的準(zhǔn)確性和慣性權(quán)重(式(7))的自適應(yīng)性.因此，算法可以更準(zhǔn)確地調(diào)整粒子速度，以平衡粒子的全局與局部搜索能力，避免算法陷入局部最優(yōu).

(9)

算法NAIWPSO中的權(quán)重NAIW會(huì)隨著粒子群的不同搜索狀態(tài)而改變，可以動(dòng)態(tài)改變粒子的速度.當(dāng)粒子群的成功率PS(t)較大時(shí)，說(shuō)明整個(gè)粒子群離最優(yōu)值較遠(yuǎn)，此時(shí)需要粒子以較大的初速度進(jìn)行全局搜索，通過(guò)式(7)和式(9)會(huì)提高速度更新式(8)中的w(t)的值，進(jìn)而可以使粒子能夠以較大的初速度接近最優(yōu)值.當(dāng)粒子群的成功率PS(t)較小時(shí)，說(shuō)明整個(gè)粒子群已經(jīng)接近最優(yōu)值，通過(guò)式(7)和式(9)使w(t)值相應(yīng)地減小，這樣可以使粒子搜索時(shí)的速度下降，進(jìn)而可以逐步精化最優(yōu)解，保證了算法的精確度.綜上，通過(guò)新的成功值計(jì)算公式，結(jié)合成功率與慣性權(quán)重更新公式，可以根據(jù)當(dāng)前粒子群的位置狀態(tài)不斷改變粒子的速度，進(jìn)而動(dòng)態(tài)平衡算法的全局搜索與局部搜索能力.

2　基于新自適應(yīng)慣性權(quán)重的粒子群任務(wù)調(diào)度算法

算法1. 基于新自適應(yīng)慣性權(quán)重的粒子群任務(wù)調(diào)度算法.

輸入：算法迭代次數(shù)Iteration、任務(wù)Tasks、虛擬機(jī)VMs、截止期限D(zhuǎn)eadline；

輸出：最優(yōu)調(diào)度方案Sbest.

① fori=1 tokdo

② 隨機(jī)初始化任務(wù)調(diào)度方案Si及其搜索速度vi;

③ end for

④ fori=1 tokdo

⑤ 計(jì)算任務(wù)調(diào)度方案Si的適應(yīng)度;

⑥ end for

⑦ 從k個(gè)任務(wù)調(diào)度方案中選出適應(yīng)度最小的全局最優(yōu)調(diào)度方案;

⑧ fori=1 toIterationdo

⑨ 根據(jù)搜索速度更新所有任務(wù)調(diào)度方案;

⑩ 為任務(wù)調(diào)度方案中的每一個(gè)任務(wù)重新分配虛擬機(jī);

3　算法示例分析

首先給出了一個(gè)云工作流示例，然后比較分析傳統(tǒng)自適應(yīng)慣性權(quán)重的粒子群任務(wù)調(diào)度算法AIWPSO以及本文所提出的任務(wù)調(diào)度算法NAIWPSO，所生成調(diào)度方案的執(zhí)行時(shí)間與費(fèi)用.

工作流由若干個(gè)相互依賴的任務(wù)組成[1].工作流通常使用有向無(wú)環(huán)圖(directed acyclic graph, DAG)來(lái)表示任務(wù)的執(zhí)行先后順序以及任務(wù)之間的相互依賴關(guān)系[2, 25].在DAG圖中每一個(gè)節(jié)點(diǎn)都代表工作流中的1個(gè)任務(wù)，節(jié)點(diǎn)之間的連線代表任務(wù)之間的依賴關(guān)系.圖1反映了1個(gè)工作流中5個(gè)任務(wù)的執(zhí)行先后順序：任務(wù)B和C必須在任務(wù)A執(zhí)行完成后才能開(kāi)始執(zhí)行；而任務(wù)D必須在任務(wù)C執(zhí)行完成后才能開(kāi)始執(zhí)行；當(dāng)最后1個(gè)任務(wù)E執(zhí)行完成后，代表該工作流全部完成.假定各任務(wù)在小型機(jī)上的執(zhí)行時(shí)間是中型機(jī)的1.3倍，是大型機(jī)的1.6倍.同時(shí)，小型機(jī)、中型機(jī)和大型機(jī)的每單位時(shí)間價(jià)格(USD)分別為：0.12, 0.24, 0.48.圖1中各任務(wù)在3種虛擬機(jī)上的執(zhí)行時(shí)間如表1所示.下面將分別使用傳統(tǒng)自適應(yīng)慣性權(quán)重的粒子群任務(wù)調(diào)度算法AIWPSO以及本文所提出的任務(wù)調(diào)度算法NAIWPSO對(duì)圖1表示的工作流進(jìn)行任務(wù)調(diào)度.

Fig. 1　Example of workflow.圖1　工作流示例

VirtualMachineTaskTypeSpeedABCDESmall1.03.28.04.81.64.8Middle1.32.66.53.91.33.9Large1.62.05.03.01.03.0

假設(shè)云環(huán)境中3臺(tái)虛擬機(jī)(小型、中型、大型各1臺(tái))執(zhí)行圖1中的工作流.圖2(a)為使用任務(wù)調(diào)度算法AIWPSO產(chǎn)生的調(diào)度方案，執(zhí)行時(shí)間為16.7單位時(shí)間，費(fèi)用為4.3USD;圖2(b)展示了本文所使用的算法NAIWPSO所得到的調(diào)度方案，執(zhí)行時(shí)間為14.6單位時(shí)間，費(fèi)用為3.98USD.從圖2可以看出，算法NAIWPSO所得到的調(diào)度方案相比算法AIWPSO，執(zhí)行時(shí)間減少了2.1單位時(shí)間，費(fèi)用減少了0.32USD.因此，新算法NAIWPSO相比AIWPSO能夠有效降低云環(huán)境下任務(wù)調(diào)度的執(zhí)行時(shí)間與費(fèi)用.

Fig. 2　Scheduling plan of two algorithms.圖2　2個(gè)算法的調(diào)度方案

4　實(shí)驗(yàn)分析

本節(jié)首先詳細(xì)給出了實(shí)驗(yàn)環(huán)境及算法參數(shù)設(shè)置；然后從算法收斂、適應(yīng)度、執(zhí)行費(fèi)用3個(gè)方面將本文算法NAIWPSO與其他5種已有算法進(jìn)行了對(duì)比分析；最后，為了對(duì)不同規(guī)模工作流的截止期限約束設(shè)置提供依據(jù)，給出了算法NAIWPSO生成調(diào)度方案的執(zhí)行費(fèi)用隨截止期限的變化情況.

4.1實(shí)驗(yàn)環(huán)境與算法參數(shù)

本文實(shí)驗(yàn)采用Matlab 2010編寫，運(yùn)行在環(huán)境為Intel core i3 3.0 GHz CPU、2 GB內(nèi)存的PC機(jī)上.為了評(píng)價(jià)和分析文中算法的性能，將常數(shù)值(constant)、指數(shù)減小(index-decreasing)、線性(linear decreasing)、 隨機(jī)(random)、傳統(tǒng)自適應(yīng)(AIW)、新自適應(yīng)(NAIW)這6種慣性權(quán)重應(yīng)用到PSO任務(wù)調(diào)度算法中，對(duì)應(yīng)的PSO算法分別表示為CPSO，IPSO，LPSO，RPSO，AIWPSO，NAIWPSO.實(shí)驗(yàn)所使用的亞馬遜EC2(Amazon EC2①http:aws.amazon.comcnec2pricing)計(jì)價(jià)模型與虛擬機(jī)運(yùn)行速度[2]如表2所示：

Table 2　Pricing Model of Amazon

實(shí)驗(yàn)對(duì)象工作流采用DAG圖方式隨機(jī)生成，每個(gè)工作流總?cè)蝿?wù)數(shù)為50～300，單個(gè)任務(wù)的負(fù)載量是30～3 000范圍內(nèi)的隨機(jī)值[26].PSO算法中粒子數(shù)量為30，虛擬機(jī)數(shù)量為4，學(xué)習(xí)因子c1與c2均為2[2]，慣性權(quán)重的最小值與最大值分別為0，1[22].各算法均取不同任務(wù)值情況下運(yùn)行100次的平均值.

4.2實(shí)驗(yàn)結(jié)果與分析

本節(jié)從算法收斂、適應(yīng)度、執(zhí)行費(fèi)用3個(gè)方面比較本文算法NAIWPSO 與其他5種算法.算法收斂表示算法找到最終解的速度，適應(yīng)度是調(diào)度方案在時(shí)間、執(zhí)行費(fèi)用、虛擬機(jī)使用效率3個(gè)方面的綜合評(píng)

價(jià)標(biāo)準(zhǔn)，執(zhí)行費(fèi)用為調(diào)度方案執(zhí)行所需費(fèi)用的虛擬機(jī)計(jì)算費(fèi)用.

4.2.1算法收斂

6種算法生成調(diào)度方案的收斂情況表3所示.任務(wù)數(shù)為50和300時(shí)，生成調(diào)度方案適應(yīng)度的6種算法收斂情況如圖3～4所示.從表4可以看出，本文算法NAIWPSO在不同任務(wù)數(shù)情況下得出最優(yōu)調(diào)度方案的迭代次數(shù)較為穩(wěn)定，整體上優(yōu)于傳統(tǒng)的自適應(yīng)算法AIWPSO.從圖3和圖4可以看出，算法NAIWPSO生成調(diào)度方案的適應(yīng)度均優(yōu)于其他5種算法，而且任務(wù)規(guī)模越大，優(yōu)化效果越顯著.

Table 3　Convergence for Six Algorithms in Different Tasks

Fig. 3　Convergence of six algorithms for 50 tasks.圖3　任務(wù)數(shù)為50時(shí)算法收斂情況

Fig. 4　Convergence of six algorithms for 300 tasks.圖4　任務(wù)數(shù)為300時(shí)算法收斂情況

4.2.2適應(yīng)度

在傳統(tǒng)自適應(yīng)慣性重的成功值計(jì)算方法的基礎(chǔ)上,擴(kuò)充了適應(yīng)度優(yōu)于上次且不優(yōu)于全局最優(yōu)值時(shí)取值0.5的情況，該值是根據(jù)經(jīng)驗(yàn)設(shè)定的.為了說(shuō)明取值的合理性，任務(wù)數(shù)取50～300，成功值取0.1～1.0，算法NAIWPSO的調(diào)度方案適應(yīng)度變化如圖5所示.本文算法NAIWPSO中成功值計(jì)算方法(式(9))第2種情況取值為0.5，與其他5種算法生成調(diào)度方案的適應(yīng)度如圖6所示.

從圖5可以看出，對(duì)于不同任務(wù)規(guī)模的工作流，成功值取值為0.5時(shí)，算法NAIWPSO所得任務(wù)調(diào)度方案的適應(yīng)度均最低.因此本文算法NAIWPSO中改進(jìn)的成功值計(jì)算方法(式(9))第2種情況取值為0.5是合理的.圖6中算法NAIWPSO生成調(diào)度方案的適應(yīng)度均優(yōu)于其他5種算法.任務(wù)數(shù)為50時(shí)，AIWPSO與NAIWPSO算法的適應(yīng)度十分接近；但隨著任務(wù)數(shù)量的增長(zhǎng)，2種算法所得調(diào)度方案的適應(yīng)度差距不斷增大.因此，本文算法更適合于大規(guī)模任務(wù)調(diào)度優(yōu)化.

4.2.3執(zhí)行費(fèi)用與截止期限

6種算法產(chǎn)生的調(diào)度方案的執(zhí)行費(fèi)用如圖7所示.為了給不同任務(wù)數(shù)情況下截止期限的最大值和最小值確定提供依據(jù)，任務(wù)數(shù)為50～300時(shí)，通過(guò)式(2)、式(3)計(jì)算截止期限的最小值與最大值如表4所示，任務(wù)調(diào)度算法NAIWPSO的調(diào)度方案費(fèi)用隨截止期限的變化情況如圖8所示.圖7中，隨著任務(wù)量在50～300范圍內(nèi)變化，本文算法NAIWPSO所生成的調(diào)度方案費(fèi)用值均最低，并且NAIWPSO算法的調(diào)度方案費(fèi)用值與其他5種算法的差值越來(lái)越大.這說(shuō)明NAIWPSO算法更加適用于任務(wù)數(shù)較多的情況.這是因?yàn)樵谌蝿?wù)數(shù)較小的情況下，各算法均進(jìn)行小范圍的局部搜索，使得權(quán)重NAIW對(duì)粒子全局與局部搜索能力的平衡優(yōu)勢(shì)無(wú)法體現(xiàn)；然而隨著問(wèn)題規(guī)模的增大和任務(wù)數(shù)的增加，更能體現(xiàn)NAIW權(quán)重的自適應(yīng)性，更好地平衡全局與局部搜索.

Fig. 5　Fitness of success value from 0.1 to 1.0.圖5　不同成功值的適應(yīng)度

Fig. 6　Fitness of six algorithms.圖6　6種算法的適應(yīng)度

Fig. 7　Execution cost of six algorithms.圖7　6種算法的執(zhí)行費(fèi)用

Table 4　The Minimum and Maximum Value of Deadline

Fig. 8　Execution cost with deadline constraint for different tasks.圖8　不同任務(wù)規(guī)模中執(zhí)行費(fèi)用隨截止期限的變化

從圖8可以看出，當(dāng)截止期限接近最小值時(shí)，算法可能沒(méi)有合適的最優(yōu)調(diào)度方案，這是因?yàn)楫?dāng)截止期限過(guò)小時(shí)，算法無(wú)法找到最優(yōu)調(diào)度方案；當(dāng)截止期限在最小與最大之間時(shí)，調(diào)度方案的費(fèi)用值逐漸下降;當(dāng)截止期限增長(zhǎng)到一定范圍時(shí)，調(diào)度方案費(fèi)用值的執(zhí)行費(fèi)用都趨于穩(wěn)定，這是由于在截止期限的值增長(zhǎng)到某一時(shí)刻時(shí)所有任務(wù)都已被分配到費(fèi)用最優(yōu)的虛擬機(jī)上.本實(shí)驗(yàn)為云計(jì)算用戶設(shè)置截止期限提供參考，例如任務(wù)數(shù)為300時(shí)，實(shí)驗(yàn)所得截止期限的最小值和最大值分別是31和45.

5　結(jié)束語(yǔ)

本文針對(duì)PSO算法中自適應(yīng)慣性權(quán)重的成功值計(jì)算方法進(jìn)行了改進(jìn)，提出了新的自適應(yīng)慣性權(quán)重，并設(shè)計(jì)了基于新慣性權(quán)重的任務(wù)調(diào)度算法NAIWPSO.新自適應(yīng)慣性權(quán)重中的成功值計(jì)算方法比較了單粒子與全局最優(yōu)粒子，可以更加精確地描述粒子所處的位置狀態(tài)，從而提高權(quán)重的自適應(yīng)性.因此，新自適應(yīng)慣性權(quán)重可以更準(zhǔn)確地調(diào)整粒子速度以平衡粒子的全局與局部搜索，使算法避免陷入局部最優(yōu)，獲得時(shí)間與費(fèi)用更優(yōu)的調(diào)度方案.實(shí)驗(yàn)結(jié)果表明，新的任務(wù)調(diào)度算法NAIWPSO算法收斂穩(wěn)定、適應(yīng)度和執(zhí)行費(fèi)用均優(yōu)于其他5種算法.然而，本文DAG圖表示的工作流模型中僅考慮了順序、選擇和循環(huán)3種任務(wù)關(guān)系，后續(xù)工作需要研究并發(fā)、互斥等不同任務(wù)關(guān)系對(duì)調(diào)度算法的影響.

[1]Dellman E, Gannon D, Shields M, et al. Workflows and e-science: An overview of workflow system features and capabilities[J]. Future Generation Computer Systems, 2008, 25(5): 528-540[2]Netjinda N, Sirinaovakul B, Achalakul T. Cost optimal scheduling in IaaS for dependent workload with particle swarm optimization[J]. The Journal of Supercomputing, 2014, 68(3): 1579-1603[3]Shi Xuelin, Xu Ke. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2): 252-262 (in Chinese)(師雪霖, 徐恪. 云虛擬機(jī)資源分配的效用最大化模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 252-262)[4]Wang Peng, Huang Yan, Li Kun, et al. Load balancing degree first algorithm on phase space for cloud computing cluster[J]. Journal of Computer Research and Development, 2014, 51(5): 1095-1107(in Chinese)(王鵬, 黃焱, 李坤, 等. 云計(jì)算集群相空間負(fù)載均衡度優(yōu)先調(diào)度算法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(5): 1095-1107)[5]Wang Qiang, Li Xiongfei, Wang Jing. A data placement and task scheduling algorithm in cloud computing[J]. Journal of Computer Research and Development, 2014, 51(11): 2416-2426(in Chinese)(王強(qiáng), 李雄飛, 王婧. 云計(jì)算中的數(shù)據(jù)放置與任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(11): 2416-2426)[6]Lee Y, Han H, Zomaya A, et al. Resource-efficient workflow scheduling in clouds[J]. Knowledge-Based Systems, 2015, 80(5): 153-162[7]Yu J, Buyya R, Tham C. Cost-based scheduling of scientific workflow applications on utility grids[C]Proc of the 1st IEEE Int Conf on e-Science and Grid Computing. Piscataway, NJ: IEEE, 2005: 1-8[8]Wieczorek M, Prodan R, Fahringer T. Scheduling of scientific workflows in the ASKALON grid environment[J]. ACM SIGMOD Record, 2005, 34(3): 56-62[9]Xu J, Liu C, Zhao X. Resource planning for massive number of process instances[C]Proc of the Move to Meaningful Internet Systems: OTM 2009. Berlin: Springer, 2009: 219-236[10]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[11]Hoffa C, Mehta G, Freeman T, et al. On the use of cloud computing for scientific workflows[C]Proc of the 4th IEEE Int Conf on eScience. Piscataway, NJ: IEEE, 2008: 640-645[12]Sheng J, Wu W. Scheduling workflow in cloud computing based on hybrid particle swarm algorithm[J]. Telkomnika Indonesian Journal of Electrical Engineering, 2012, 10(7): 1560-1566[13]Pandey S, Wu L, Guru S, et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]Proc of the 24th IEEE Int Conf on Advanced Information Networking and Applications. Piscataway, NJ: IEEE, 2010: 400-407[14]Tao Q, Chang H, Yi Y, et al. QoS constrained grid workflow scheduling optimization based on a novel PSO algorithm[C]Proc of the 8th Int Conf on Grid and Cooperative Computing. Piscataway, NJ: IEEE, 2009: 153-159[15]Wu Z, Ni Z, Gu L, et al. A revised discrete particle swarm optimization for cloud workflow scheduling[C]Proc of 2010 Int Conf on Computational Intelligence and Security. Piscataway, NJ: IEEE, 2010: 184-188[16]Shi Y, Eberhart R. A modified particle swarm optimizer[C]Proc of 1998 IEEE Int Conf on Evolutionary Computation. Piscataway, NJ: IEEE, 1998: 760-766[17]Eberhart R, Shi Y. Particle swarm optimization: Developments, applications and resources[C]Proc of 2001 IEEE Int Conf on Evolutionary Computation. Piscataway, NJ: IEEE, 2001: 81-86[18]Eberhart R, Shi Y. Tracking and optimizing dynamic systems with particle swarms[C]Proc of 2001 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2001: 94-100[19]Shi Y, Eberhart R. Empirical study of particle swarm optimization[C]Proc of 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 1999: 1945-1950[20]Eberhart R, Shi Y. Comparing inertia weights and constriction factors in particle swarm optimization[C]Proc of 2000 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2000: 84-88[21]Chatterjee A, Siarry P. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J]. Computers & Operations Research, 2006, 33(3): 859-871[22]Nickabadi A, Ebadzadeh M, Safabakhsh R. A novel particle swarm optimization algorithm with adaptive inertia weight[J]. Applied Soft Computing, 2011, 11(4): 3658-3670[23]Ho S, Lin H, Liauh W, et al. OPSO: Orthogonal particle swarm optimization and its application to task assignment problems[J]. IEEE Trans on Systems, Man and Cybernetics, Part A: Systems and Humans, 2008, 38(2): 288-298[24]Gong M, Wu Y, Cai Q, et al. Discrete particle swarm optimization for high-order graph matching[J]. Information Sciences, 2016, 328(1): 158-171[25]Rimal B, Jukan A, Katsaros D, et al. Architectural requirements for cloud computing systems: An enterprise cloud approach[J]. Journal of Grid Computing, 2011, 9(1): 3-26[26]Fard H, Prodan R, Fahringer T. A truthful dynamic workflow scheduling mechanism for commercial multicloud environments[J]. IEEE Trans on Parallel and Distributed Systems, 2013, 24(6): 1203-1212

Li Xuejun, born in 1976. PhD, associate professor. Member of China Computer Federation. His main research interests include workflow systems, cloud computing and intelligent software.

Xu Jia, born in 1992. Master candidate. His current research interests include intelligent algorithm and workflow systems (xujia_ahu@foxmail.com).

Zhu Erzhou, born in 1981. PhD, associate professor. His current research interests include program analysis, binary translation, compiling technology, virtualization and cloud computing.

Zhang Yiwen, born in 1976. PhD, associate professor. His current research interests include service computing, cloud computing and evolutionary algorithm.

A Novel Computation Method for Adaptive Inertia Weight of Task Scheduling Algorithm

Li Xuejun, Xu Jia, Zhu Erzhou, and Zhang Yiwen

(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601)

Particle swarm optimization (PSO) is a primary intelligence algorithm to solve task scheduling problem for workflow systems in cloud computing. The inertia weight is one of the most important parameters to achieve a balance between the global and local search in PSO algorithm. However, traditional adaptive inertia weight-based PSO task scheduling algorithms usually get local optimal and cause longer execution time and higher cost for scheduling plan. The traditional adaptive inertia weight does not comprehensively represent the information of particle position, and then cannot make a suitable balance between global and local search. Hence, a novel computation method for adaptive inertia weight is proposed to improve the computation method of success value of each particle. This method shows the position state of each particle more accurately and then improves the adaptability of inertia weight by comparing the fitness of each particle with the global best particle. Then a new inertia weight-based PSO algorithm is presented to solve task scheduling problem for cloud workflow systems. The novel weight can adjust the particle velocity more correctly so that the algorithm avoids premature convergence by a proper balance between local and global search. Comparing our new adaptive inertia weight with other five traditional inertia weights (viz. constant, index decreasing, linear decreasing, random, and adaptive inertia weight), the results show that our new adaptive inertia weight-based scheduling algorithm can always achieve stable convergence speed, the optimal fitness and execution cost of the scheduling plan (i.e. roughly 18% reduction of execution cost).

cloud computing; workflow; task scheduling; particle swarm optimization (PSO); inertia weight

2015-12-22；

2016-04-19

國(guó)家自然科學(xué)基金項(xiàng)目(61300169)；安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2016A024)

TP391

This work was supported by the National Natural Science Foundation of China (61300169) and the Natural Science Foundation of Education Commission of Anhui Province (KJ2016A024).