任務調度算法中新的自適應慣性權重計算方法

李學俊　徐　佳　朱二周　張以文

(安徽大學計算機科學與技術學院　合肥　230601)

?

任務調度算法中新的自適應慣性權重計算方法

李學俊徐佳朱二周張以文

(安徽大學計算機科學與技術學院合肥230601)

(xjli@ahu.edu.cn)

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

云計算；工作流；任務調度；粒子群算法；慣性權重

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

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

為了解決局部收斂的缺陷，粒子群算法的速度更新公式增加了慣性權重這一參數，以增強平衡粒子全局與局部搜索的能力[16].目前，慣性權重大體上分為3類：常數或隨機型慣性權重[16-18]、線性或指數變化慣性權重[19-21]、自適應性慣性權重[22].固定常數值慣性權重[16]實現簡單，在算法執行過程中，慣性權重固定為一個常數，導致算法容易陷入局部最優.因此Eberhart和Shi[18]提出了隨機慣性權重，以優化目標動態變化的問題.Shi和Eberhart[19-20]又提出線性減少慣性權重，以提高粒子群算法的求精能力，該算法如果在初期粒子搜索不到較好的位置點，易陷入局部最優.在線性減少慣性權重的基礎上，Chatterjee和Siarry[21]提出了指數減少慣性權重，在一定程度上避免了算法陷入局部最優.然而，指數值的確定是一個難點，而且算法的計算量較大，不適合復雜優化問題求解.

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

1　自適應慣性權重

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

1.1適應度

適應度是評價任務調度方案執行時間和費用的一項綜合指標[2]，表示粒子群算法中粒子位置狀態的優劣，如式(1)所示.適應度可以全面衡量該調度方案所需的時間與費用.適應度越高的調度方案，所需時間與費用的開銷也就越大，粒子位置狀態就越不好；相反，開銷越小，粒子位置狀態就越好.

(1)

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

deadlinemin=min{makespanSk}；

(2)

deadlinemax=max{makespanSk}.

(3)

在適應度計算式(1)中，costSk為某一調度方案Sk的費用值，其計算方法如式(4)所示：

(4)

1.2傳統的自適應慣性權重

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

(5)

(6)

(7)

(8)

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

1.3新的自適應慣性權重

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

(9)

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

2　基于新自適應慣性權重的粒子群任務調度算法

算法1. 基于新自適應慣性權重的粒子群任務調度算法.

輸入：算法迭代次數Iteration、任務Tasks、虛擬機VMs、截止期限Deadline；

輸出：最優調度方案Sbest.

① fori=1 tokdo

② 隨機初始化任務調度方案Si及其搜索速度vi;

③ end for

④ fori=1 tokdo

⑤ 計算任務調度方案Si的適應度;

⑥ end for

⑦ 從k個任務調度方案中選出適應度最小的全局最優調度方案;

⑧ fori=1 toIterationdo

⑨ 根據搜索速度更新所有任務調度方案;

⑩ 為任務調度方案中的每一個任務重新分配虛擬機;

3　算法示例分析

首先給出了一個云工作流示例，然后比較分析傳統自適應慣性權重的粒子群任務調度算法AIWPSO以及本文所提出的任務調度算法NAIWPSO，所生成調度方案的執行時間與費用.

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

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

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

Fig. 2　Scheduling plan of two algorithms.圖2　2個算法的調度方案

4　實驗分析

本節首先詳細給出了實驗環境及算法參數設置；然后從算法收斂、適應度、執行費用3個方面將本文算法NAIWPSO與其他5種已有算法進行了對比分析；最后，為了對不同規模工作流的截止期限約束設置提供依據，給出了算法NAIWPSO生成調度方案的執行費用隨截止期限的變化情況.

4.1實驗環境與算法參數

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

Table 2　Pricing Model of Amazon

實驗對象工作流采用DAG圖方式隨機生成，每個工作流總任務數為50～300，單個任務的負載量是30～3 000范圍內的隨機值[26].PSO算法中粒子數量為30，虛擬機數量為4，學習因子c1與c2均為2[2]，慣性權重的最小值與最大值分別為0，1[22].各算法均取不同任務值情況下運行100次的平均值.

4.2實驗結果與分析

本節從算法收斂、適應度、執行費用3個方面比較本文算法NAIWPSO 與其他5種算法.算法收斂表示算法找到最終解的速度，適應度是調度方案在時間、執行費用、虛擬機使用效率3個方面的綜合評

價標準，執行費用為調度方案執行所需費用的虛擬機計算費用.

4.2.1算法收斂

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

Table 3　Convergence for Six Algorithms in Different Tasks

Fig. 3　Convergence of six algorithms for 50 tasks.圖3　任務數為50時算法收斂情況

Fig. 4　Convergence of six algorithms for 300 tasks.圖4　任務數為300時算法收斂情況

4.2.2適應度

在傳統自適應慣性重的成功值計算方法的基礎上,擴充了適應度優于上次且不優于全局最優值時取值0.5的情況，該值是根據經驗設定的.為了說明取值的合理性，任務數取50～300，成功值取0.1～1.0，算法NAIWPSO的調度方案適應度變化如圖5所示.本文算法NAIWPSO中成功值計算方法(式(9))第2種情況取值為0.5，與其他5種算法生成調度方案的適應度如圖6所示.

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

4.2.3執行費用與截止期限

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

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

Fig. 6　Fitness of six algorithms.圖6　6種算法的適應度

Fig. 7　Execution cost of six algorithms.圖7　6種算法的執行費用

Table 4　The Minimum and Maximum Value of Deadline

Fig. 8　Execution cost with deadline constraint for different tasks.圖8　不同任務規模中執行費用隨截止期限的變化

從圖8可以看出，當截止期限接近最小值時，算法可能沒有合適的最優調度方案，這是因為當截止期限過小時，算法無法找到最優調度方案；當截止期限在最小與最大之間時，調度方案的費用值逐漸下降;當截止期限增長到一定范圍時，調度方案費用值的執行費用都趨于穩定，這是由于在截止期限的值增長到某一時刻時所有任務都已被分配到費用最優的虛擬機上.本實驗為云計算用戶設置截止期限提供參考，例如任務數為300時，實驗所得截止期限的最小值和最大值分別是31和45.

5　結束語

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

[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]. 計算機學報, 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]. 計算機研究與發展, 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)(王強, 李雄飛, 王婧. 云計算中的數據放置與任務調度算法[J]. 計算機研究與發展, 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

國家自然科學基金項目(61300169)；安徽省教育廳自然科學研究重點項目(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).