云計算任務調度算法研究

黃 少 榮

(廣東司法警官職業(yè)學院 信息管理系, 廣州 510520)

?

云計算任務調度算法研究

黃 少 榮

(廣東司法警官職業(yè)學院 信息管理系, 廣州 510520)

云計算是一種新型的商業(yè)計算模式,應用大規(guī)模的虛擬化資源通過計算機網(wǎng)絡向用戶提供不同服務。云計算面對的用戶眾多,系統(tǒng)要處理的任務量與數(shù)據(jù)量十分巨大,并且云計算系統(tǒng)結構復雜,對大量任務進行高效調度是云計算中一個必須解決的難題。云計算任務調度算法決定了用戶任務的執(zhí)行效率和系統(tǒng)資源的使用效率,直接關系到云計算系統(tǒng)的整體穩(wěn)定性和整體效果。在對云計算任務調度算法的相關研究現(xiàn)狀進行深入分析和研究的基礎上,從模型高效和算法高效2個層面上指出未來云計算任務調度算法的發(fā)展趨勢,提出構建基于多目標優(yōu)化的云計算任務調度模型。

云計算; 任務調度; 啟發(fā)式算法; 多目標優(yōu)化; 群智能

0 引 言

云計算是下一代計算機網(wǎng)絡與應用的新技術,是網(wǎng)絡計算、分布式計算、并行計算、效用計算、網(wǎng)絡存儲、虛擬化和負載均衡等傳統(tǒng)計算機技術和網(wǎng)絡技術的發(fā)展和延伸。云計算的核心思想是把計算任務分配給一個由大量計算機器組成的資源池,使用戶能夠按需獲得云中的計算能力、存儲空間以及信息服務[1]。云計算包含了基礎設施即服務(IaaS)、平臺即服務(PaaS)以及軟件即服務(SaaS)這3個層次的服務,這些服務都存在任務與資源之間的調度問題,即云計算需要同時處理大量的計算任務,對用戶提交的各種任務快速分配所需的計算資源。高效的任務調度策略決定了云計算的工作效率,是保證云計算服務質量的關鍵[2]。

1 云計算任務調度模型

云計算任務調度主要研究如何為用戶提交的任務分配資源,也就是將多個相互獨立的多樣化任務分配到云中規(guī)模寵大的虛擬資源上,滿足用戶QoS要求、總任務的完成時間最小,負載均衡最高等目標,其調度模型如圖1所示[3]。

云計算任務調度工作于云任務和虛擬機之間,即圖1中左邊虛線圈所示的眾多箭頭所在之處。任務執(zhí)行所需要的成本、耗費的時間、負載均衡、系統(tǒng)穩(wěn)定性、用戶需求以及對系統(tǒng)的滿意度等都是由任務調度策略決定的。因此,云計算任務調度算法決定了用戶任務的執(zhí)行效率和系統(tǒng)資源的使用效率,影響了整個云計算系統(tǒng)的工作性能。

2 云計算任務調度算法

目前的云計算任務調度機制還未形成統(tǒng)一的標準和規(guī)范,各大云計算服務供應商都是自己搭建云平臺,并根據(jù)云平臺的特點采用不同的任務調度策略,所用算法大致分為以下幾種:

圖1 云計算任務調度模型

2.1 傳統(tǒng)任務調度算法

分布式計算是云計算技術的一種,分布式任務調度與云計算任務調度具有一定的相似性,一些用于分布式環(huán)境下的傳統(tǒng)調度算法經(jīng)過適當改進也可用于云計算任務調度問題。典型的有:

1) Min-min算法[4]。Min-min算法的設計思想是盡可能將任務指派給最早可用并且執(zhí)行速度最快的計算資源,通過獲取任務執(zhí)行的2個最小值(最早執(zhí)行開始時間和最快執(zhí)行速度)完成選擇。該算法屬于貪婪算法的一種,通過先易后難的策略,任務集中在計算能力較強的節(jié)點上,而性能較低節(jié)點沒有充分利用,容易造成負載不均衡。

2) Max-min算法。Max-min算法與Min-min算法類似,也是貪婪算法的一種,但采用的是先難后易的策略,分配任務時,按任務執(zhí)行的難度考慮,選擇最大最早完成時間的任務映射到具有最早執(zhí)行時間的資源上執(zhí)行。Min-min算法是先完成執(zhí)行時間短的任務,而Max-min算法則先完成執(zhí)行時間長的任務。在異構計算環(huán)境中,當短的任務數(shù)量遠遠多于長任務數(shù)量時,該算法具有一定的優(yōu)勢。

3) Sufferage算法[5]。Sufferage算法也是貪婪算法的一種,任務的Shfferage值就是該任務的最早完成時間與次早完成時間之間的差,該值代表某個任務如果不分配到完成時間最早的資源上將造成的損失。在任務間發(fā)生競爭時,比較各任務的執(zhí)行損失,將損失最大的任務優(yōu)先分配給計算資源。

這些算法都是為了提高用戶任務的執(zhí)行效率而設計的,但由于云計算中的任務資源的動態(tài)性、異構性和差異性,因此云計算的計算模式比傳統(tǒng)的計算模式更加復雜,這些傳統(tǒng)算法必須經(jīng)過適當改進才能用于云計算任務調度問題。

2.2 Hadoop中的任務調度算法

大多的云計算環(huán)境是基于開源云計算框架----Hadoop架構的,針對云系統(tǒng)用戶任務調度中不同的QoS目標約束要求,Hadoop實現(xiàn)了3種不同的調度算法:

1) 先進先出調度算法。FIFO算法(First In First Out,FIFO)根據(jù)用戶提交任務的時間先后和優(yōu)先級的高低來進行調度執(zhí)行,當系統(tǒng)中有空閑的Worker請求任務時,Master會選擇一個最早提交并且優(yōu)先級最高的任務分配給該Worker節(jié)點。該算法簡單,容易實現(xiàn),但由于不對用戶任務進行區(qū)分,并且云中用戶任務調度的優(yōu)先級和QoS要求各不相同,很難同時滿足不同用戶的QoS要求。

2) 公平調度算法[6]。公平調度算法(Fair Scheduling, FS)保證任務一個提交作業(yè)的用戶在一定時間內得到響應,有很好的公平性和效率。按照該算法,當只有一個作業(yè)提交到系統(tǒng)后,整個系統(tǒng)的所有計算資源都會被這個作業(yè)獨占。當有新作業(yè)提交時,原作業(yè)所占資源中已經(jīng)完成任務的Worker會被釋放,供那些新提交的作業(yè)使用。

3) 計算能力調度算法[7]。計算能力調度算法(Capacity Scheduling, CS)通過建立作業(yè)隊列來管理和維護作業(yè)。該算法的核心思想是按照各個隊列不同的需求將相應的資源分配出去,保證各個作業(yè)都能占用各自需要的資源。

這3種算法較為簡單,但性能不佳,存在QoS(Quality of Service)差、頻繁調度、資源碎片多、不夠靈活等弊端,而且任務隊伍和資源池配額受人為設置影響。

2.3 啟發(fā)式任務調度算法

云計算任務調度本質上是一種組合優(yōu)化類的NP-Hard問題,很難在多項式時間復雜度內求得全局最優(yōu)解。隨著資源和任務的急劇增加,傳統(tǒng)的任務調度算法已經(jīng)難以很好地滿足實際應用的需求。針對此問題,很多研究者提出了不同的改進算法,這些算法中除了改進一些經(jīng)典調度算法外,也逐漸被引入啟發(fā)式優(yōu)化算法。啟發(fā)式算法能在一個較短的時間內得到一個滿意的調度方案,在短時間內將大量用戶任務分別映射到合適的計算資源上,其中表現(xiàn)比較優(yōu)異的是遺傳算法和群智能算法中的蟻群算法和粒子群算法,這3種算法的工作原理以及在云計算任務調度中的應用如下:

1) 遺傳算法[8]

遺傳算法(Genetic Algorithm, GA)是一種借鑒生物進化過程中的優(yōu)勝劣汰機制而提出的一種隨機搜索算法。GA隨機生成一個固定數(shù)目的初始群體,群體中每個個體代表問題的一個解,該群體通過選擇、交叉和變異等操作,根據(jù)適者生存的原則不斷迭代進化,進化到一定代數(shù)的末代群體中的最優(yōu)個體即代表問題的近似最優(yōu)解。

GA的并行計算方式適合大規(guī)模運算和對復雜系統(tǒng)進行優(yōu)化,算法具有全局收斂性,能較快地收斂到全局近似最優(yōu)解,已經(jīng)在云計算任務調度問題中展現(xiàn)出優(yōu)越性能。Joanna等[9]在充分考慮云環(huán)境中的資源安全和信任機制問題等要素的基礎上,利用遺傳算法對云環(huán)境下的的資源進行調度。張水平等[10]對遺傳算法進行改進,避免算法陷入局部最優(yōu),并利用改進的元胞自動機遺傳算法對云環(huán)境下的資源進行合理調度。Sean Marston等[11]提出一種簡單高效的遺傳算法,對云環(huán)境下的資源進行分層排序,并根據(jù)資源利用屬性提供訪問順序。該算法在資源離散分布時容易出現(xiàn)資源搜索困難。劉愉等[12]在充分考慮云計算環(huán)境的動態(tài)異構性和大規(guī)模任務處理特性的基礎上,提出了一種基于染色體編碼方式和適應度函數(shù)的改進遺傳算法(IGA)對任務進行調度。

2) 蟻群算法[13]

蟻群算法(Ant Colony Algorithm, ACA)是模擬自然界中螞蟻的群體協(xié)作覓食過程而提出的一種基于群智能的啟發(fā)式仿生算法。該算法最早被應用于解決TSP問題,充分利用蟻群之間的信息傳遞,采用分布式正反饋機制在解路徑圖中搜索從蟻穴到食物間的最短路徑。

ACA具有全局搜索和快速收斂等優(yōu)點,并且容易與其他方法結合,魯棒性強,已經(jīng)在云計算任務調度問題上取得一定成績。劉永等[14]在Google公司的Map/Reduce框架上提出了2個基于蟻群優(yōu)化的資源調度策略,并在這兩個資源調度策略中引入雙向螞蟻機制。張春艷等[15]將蟻群分為搜索蟻、偵察蟻和工蟻,提出一種多態(tài)蟻群算法對云環(huán)境下的任務進行調度,優(yōu)化目標是最小化任務的平均完成時間。李坤[16]在考慮節(jié)點計算能力、網(wǎng)絡帶寬和任務難度等因素的基礎上,利用改進蟻群算法對云環(huán)境下的任務進行調度,以任務執(zhí)行時間和負載均衡為優(yōu)化目標。查英華等[17]提出了一種增強蟻群算法對云環(huán)境下的任務進行調度,在優(yōu)化任務完成時間同時兼顧了負載均衡。

3) 粒子群算法[18]

粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)是模擬鳥群覓食過程而提出的一種基于群智能的隨機優(yōu)化算法。PSO是一種基于迭代的優(yōu)化工具,系統(tǒng)初始化為一組隨機解,通過更新速度和位置來不斷進化到全局最優(yōu)解。

PSO具有簡單通用、可調參數(shù)少、優(yōu)化性能高等優(yōu)點,是目前計算智能領域的一個研究熱點,并且已經(jīng)被應用于很多領域的優(yōu)化問題中,也成功應用于云計算任務調度問題。Suraj等[19]在考慮任務之間的依賴關系的基礎上,利用粒子群算法對云計算環(huán)境中的資源進行調度。劉萬軍等[20]在粒子群優(yōu)化算法中引入變異粒子逆向飛行思想和動態(tài)多群體協(xié)作以提高全局搜索能力,提出一種改進粒子群算法對云計算資源進行調度。王登科等[21]提出一種基于粒子群優(yōu)化和蟻群優(yōu)化的任務調度算法,以總任務完成時間最小為優(yōu)化目標。李依桐等[22]提出一種混合粒子群優(yōu)化算法用于云任務調度,以最小化工作流費用為優(yōu)化目標。算法中引入遺傳算法的交叉和變異思想,并結合隨迭代次數(shù)變化的變異指數(shù),保證種群進化初期具有較高的全局搜索能力,避免陷入局部最優(yōu)。

4) 其他智能算法

差分演化算法(Differential Evolution, DE)是一種新興的基于群體進化的計算技術,通過模擬生物進化過程中個體間的合作與競爭來實現(xiàn)對復雜優(yōu)化問題的求解,是一種具有保優(yōu)思想的貪婪遺傳算法。該算法實現(xiàn)簡單、全局優(yōu)化能力強,但不能直接用于離散問題[23]。朱宇航根據(jù)云計算任務調度問題的特點,對基本差分演化算法進行離散化改進,并將改進的離散差分演化算法(TC-MDDE)應用于滿足用戶QoS需求的云計算任務調度問題[3]。

人工峰群算法(Artificial Bee Colony, ABC)是一種模仿蜜蜂行為的群智能優(yōu)化算法,通過蜂群覓食過程中不同分工的蜜蜂之間的信息共享和交流而實現(xiàn)問題空間的尋優(yōu)[24]。ABC具有計算簡單、參數(shù)少、容易實現(xiàn)等優(yōu)點,成為云計算任務調度問題的一種新工具。卓濤等提出一種基于改進人工蜂群算法(IABC)對云計算資源調度模型進行求解,將個體當前最優(yōu)值及隨機向量引入到蜂群搜索過程中以加快搜索速度。該算法提高了云計算資源利用率,并且減少了任務的執(zhí)行時間[25]。

人工魚群算法(Artificial Fish-warm Algorithm, AFA)是一種基于動物自治體的優(yōu)化方法,根據(jù)水域中魚生存數(shù)目最多的地方就是本水域中富含營養(yǎng)物質最多的地方這一特點來模擬魚群的覓食行為而實現(xiàn)尋優(yōu)。AFA不需要了解問題的特殊信息,只需要對問題進行優(yōu)劣的人工魚個體的局部尋優(yōu)行為,達到全局最優(yōu)值在群體中突現(xiàn)出來的目的,收斂速度快[26]。孫文等提出了一種基于郭濤思想的AFA對云計算環(huán)境下的任務實現(xiàn)調度,該算法主要優(yōu)化總任務的完成時間,同時也把任務平均完成時間作為一個必要的參考量[27]。

蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是一種通過啟發(fā)性搜索來尋找全局最優(yōu)解的新型群體智能優(yōu)化算法[28],該算法結合了基于個體所帶模因(meme)進化的模因演化算法和粒子群優(yōu)化算法的優(yōu)點,先通過子群內部尋優(yōu),再通過子群間的混合來交換全局信息實現(xiàn)全局尋優(yōu)。該算法具有高效的計算性能和優(yōu)良的全局搜索能力,主要應用于解決多目標優(yōu)化問題。駱劍平等改進SFLA對云計算資源進行調度,提出了2種不同的編碼結構以及相應的更新方程,并根據(jù)調度方案的QoS值進行個體間的優(yōu)勝劣汰,最后得到最佳調度。該調度方案只考慮任務完成時間和帶寬資源,沒有考慮其他參數(shù)[29]。

人工螢火蟲算法(Artificial Firefly Algorithm,AFA)是受自然界中的螢火蟲通過螢光進行信息交流這種群體行為的啟發(fā)演變而來的一種新型仿生優(yōu)化算法,該算法將搜索和優(yōu)化過程模擬成螢火蟲個體的吸引和移動過程,通過求解問題的目標函數(shù)量化各個個體位置的優(yōu)劣。該算法具有參數(shù)少、實現(xiàn)簡單、計算速度快等優(yōu)點,在生產調度和路徑規(guī)劃等方面具有廣闊的應用前景[30]。劉運等[31]在人工螢火蟲算法的基礎上,引入高斯變異的概念以提高算法的搜索精度和收斂速度,并將改進后的算法運用到云計算環(huán)境下的資源進行調度問題中,解決云計算中資源分配不均的問題。實驗證明該算法能有效縮短云計算任務的完成時間。

啟發(fā)式任務調度算法雖然可以較好地對云環(huán)境下的任務進行調度,但優(yōu)化目標大多是單一地降低任務執(zhí)行時間、降低成本或改善負載平衡等,沒有綜合考慮實際應用中更多的復雜因素,比如計算成本、用戶多樣化需求、網(wǎng)絡延遲、故障處理、節(jié)能環(huán)保等,并且通常存在著收斂性能或全局最優(yōu)解搜索能力較低的缺點,算法的收斂速度和計算精度有待進一步提高。此外,在啟發(fā)式任務調度算法中,如果僅僅采用一種優(yōu)化算法,得到的結果往往不是很理想,因此需要在啟發(fā)式算法中結合其他優(yōu)化技術,形成混合算法,以使其對云計算環(huán)境下的任務調度在綜合性能上達到最優(yōu)。

3 云計算調度算法的研究展望

目前的云計算任務調度主要存在著優(yōu)化目標單一和算法性能不高這2方面問題,可以從模型高效和算法高效2個層面出發(fā),綜合考慮云計算的時間、成本、成功率、網(wǎng)絡故障等約束條件,兼顧云計算用戶和運營商雙方的利益,構建多目標優(yōu)化模型,并利用改進的算法對模型進行求解。

3.1 構建適合云環(huán)境下的任務調度模型,提出多個目標的優(yōu)化

云計算任務調度主要采用的性能指標有:最優(yōu)時間跨度(optimal makespan)、服務質量(quality of service)、負載均衡(load balancing)和經(jīng)濟原則(economic principles)等。從用戶角度上考慮的是任務執(zhí)行時間、可靠性、經(jīng)濟成本等約束條件,并且用戶偏好多樣,目標約束條件通常會包含多個指標的要求;從服務提供商角度考慮的是降低能耗、減少開銷、提高資源利用率等。

針對傳統(tǒng)云計算任務調度算法優(yōu)化目標單一的問題,提出同時將任務執(zhí)行時間、執(zhí)行費用以及資源負載均衡等多個因素同時作為調度的優(yōu)化目標,建立有效靈活的多目標優(yōu)化模型,保障系統(tǒng)選擇最佳的任務調度,最大化地滿足用戶多樣化需求并最大化地提高云服務提供者的資源利用率和經(jīng)濟效益,達到互利共贏。

3.2 改進任務調度策略,提高算法性能

目前對云計算任務調度算法的研究仍處于探索階段,每一種調度算法都有其應用領域和局限性,還沒有一種能適用于所有領域,同時獲得最佳調度效果的任務調度算法。

相對于傳統(tǒng)任務調度算法,啟發(fā)式算法具有更高的優(yōu)化效率,特別是群智能算法,其潛在的并行性和分布式的特點為處理海量數(shù)據(jù)提供了技術保證[32]。在對云計算環(huán)境下的多目標任務調度問題的特點進行詳細分析的基礎上,應該進一步對群智能算法(ACA、PSO、DE、ABC、AFA和SFLA等)進行改進,充分調查群算能算法的參數(shù),對參數(shù)做出合理設置,根據(jù)群智能算法的優(yōu)缺點,在群智能中加入其他優(yōu)化技術,采用相應的混合策略使各算法有效結合,取長補短,不斷提高算法的優(yōu)化性能,并將這些改進后高效的混合群智能算法運用到云環(huán)境下多目標優(yōu)化的任務調度模型中,為用戶任務做出合理調度,使任務執(zhí)行時間短,費用低,能夠有效應對資源進入退出、節(jié)點失效、資源故障這些突發(fā)事件,滿足用戶多樣化需求,提高任務執(zhí)行成功率。并且能夠平衡系統(tǒng)負載,提高資源利用率,節(jié)約成本,進而提高云服務提供商的效益,同時滿足多個目標的優(yōu)化。

4 結 語

云計算任務調度算法決定了整個云計算系統(tǒng)的運行效率和工作性能,對云計算任務調度算法進行研究對于提高云計算系統(tǒng)的服務能力具有重要的理論價值和現(xiàn)實意義。本文對云計算環(huán)境下的任務調度算法做了分析和比較,重點闡述了啟發(fā)式算法在云計算任務調度中的應用現(xiàn)狀。結合云技術的發(fā)展趨勢,指出構建多目標優(yōu)化的云任務調度模型的必要性,針對目前使用的任務調度算法的不足,提出利用改進的混合群智能算法對云環(huán)境下的多目標任務調度模型進行優(yōu)化的思路,使云計算中的任務調度更科學,保證云平臺高效率運行。

[ 1 ]劉鵬. 云計算[M]. 2版. 北京:電子工業(yè)出版社, 2011:1-15.

[ 2 ]MICHAEL A, ARMANDO F, REAN G, et al. Above the clouds: a Berkeley view of cloud computing[M]. Berkeley: University of California, 2009:1-23.

[ 3 ]朱宇航. 差分進化算法及其在云計算任務調度中的應用研究[D]. 蘭州:蘭州交通大學, 2013.

[ 4 ]BRAUN T D, SIEGEL H J, BECK N. A comparsion of eleven static heristics for mapping a class of independent tasks onto heterogonous distributed computing systems[J]. Parallel and Distributed Computing, 2001,61(1):810-837.

[ 5 ]鄭愛卿. 基于執(zhí)行時間方差的元任務網(wǎng)格調度算法研究[D]. 北京:北京交通大學, 2008.

[ 6 ]ISARD M, PRABHAKARAN V, CURREY J, et al. Fair scheduling for distributed computing clusters[C]∥Proceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles, New York:ACM, 2009:261-276.

[ 7 ]遆鳴. 云計算下計算能力調度算法的研究和改進[D]. 太原:太原理工大學, 2012.

[ 8 ]HOLLAND J H. Adaptation in Nature and Artificial Systems[M]. Boston: MIT Press, 1992.

[ 9 ]JOANNA K, FATOS X, MARCIN B. Secure and task abortion aware GA-based hybridmetaheuristics for grid scheduling[J]. Computer Science, 2010,1:526-535.

[10]張水平,鄔海艷. 基于元胞自動機遺傳算法的云資源調度[J]. 計算機工程, 2012,38(11):11-13.

[11]SEAN M, ZHI L, SUBBAJYOTI B. Cloud computing-the business perspective[J]. Decision Support Systems, 2011,51(1):176-189.

[12]劉愉,趙志文,李小蘭,等. 云計算環(huán)境中優(yōu)化遺傳算法的資源調度策略[J]. 北京師范大學學報:自然科學版, 2012,48(4):378-384.

[13]DORIGO M, MANIEZZO V, COLOMI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on System, Man and Cybernetics, 1996,26(1):29-41.

[14]劉永,王新華,邢長明,等. 云計算環(huán)境下基于蟻群優(yōu)化算法的資源調度策略[J]. 計算機技術與發(fā)展, 2011,21(9):19-27.

[15]張春艷,劉清林,孟珂. 基于蟻群算法的云計算任務分配[J]. 計算機應用, 2012,32(5):1418-1420.

[16]李坤. 云環(huán)境下的任務調度算法研究與實現(xiàn)[D]. 長春:吉林大學, 2012.

[17]查英華,楊靜麗. 改進蟻群算法在云計算任務調度中的應用[J]. 計算機工程與設計, 2013,34(5):1716-1719.

[18]KENNEDY J, EBERHART R. C. Particle Swarm Optimization [C]∥Proceedings of the IEEE International Conference on Neural Networks, Piscataway: IEEE,1995:1942-1948.

[19]PANDEY S, WU L, GURU M, et al. A particle swarm optimization-based heuristic for scheduling workflow application in cloud computing environments[C]∥24th IEEE International Conference on Advanced Information Networking and Applications, Piscataway: IEEE, 2010:1109-1119.

[20]劉萬軍,張孟華,郭文越. 基于MPSO算法的云計算資源調度策略[J]. 計算機工程, 2011,37(11):43-44.

[21]王登科,李忠. 基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務調度算法[J]. 計算機應用與軟件, 2013,30(1):290-293.

[22]李依桐,林燕. 基于混合粒子群算法的云計算任務調度研究[J]. 計算技術與自動化, 2014,33(1):73-77.

[23]STORN R, PRICE K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces[J]. J Global Optimization, 1997,11(4):341-359.

[24]KARABOGA N. A new design method based on artificial bee colony algorithm for digital IIR Filters [J]. J Franklin Institute, 2009,346(4):328-348.

[25]卓濤,詹穎. 改進人工蜂群算法的云計算資源調度模型[J]. 微電子學與計算機, 2014,31(7):147-150.

[26]李曉磊,邵之江,錢積新. 一種基于動物自治體的尋優(yōu)模式:魚群算法[J]. 系統(tǒng)工程理論與實踐, 2002,22(11):32-38.

[27]孫文新. 人工魚群優(yōu)化在云計算環(huán)境中任務調度算法[J]. 安徽農業(yè)科學, 2012,40(11):6923-6929.

[28]EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Water Resources Planning and Management, 2003,129(3):210-225.

[29]駱劍平,李霞,陳泯融. 云計算環(huán)境中基于混合蛙跳算法的資源調度[J]. 計算機工程與應用, 2012,48(29):67-72.

[30]GROSSMAN R L. The case of cloud computing[J]. IT Professional, 2009,11(2):23-27.

[31]劉運,程家興,林京. 基于高斯變異的人工螢火蟲算法在云計算資源調度中的研究[J]. 計算機應用研究, 2015,32(3):834-837.

[32]CHRISTIAN B, DANIEL M. 群智[M]. 龍飛,譯. 北京:國防工業(yè)出版社, 2010.

Study of task scheduling algorithm on cloud computing

HUANGShaorong

(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Cloud computing is a new business computing model which uses large-scale virtualized resources to provide services through the computer network. In the cloud computing environment, the users are multitudinous, and the number of tasks and the amounts of data are huge, and the structure of cloud computing system is very complex, and it is a difficult problem to be resolved to schedule tasks efficiently. Task scheduling algorithm determines the execution efficiency of user tasks and use efficiency of system resources, and is directly related to the integral stability and overall effect. After the analysis and comparison of the cloud computing scheduling strategies, based on two aspects of model efficiency and algorithm efficiency, this paper points out the development trend of cloud computing task scheduling algorithm, and proposes cloud computing task scheduling model based on multi-objective optimization.

cloud computing; task scheduling; heuristic algorithm; multi-objective optimization; swarm intelligence

2014-10-10。

廣東省科技廳自然科學基金資助項目(101754539192000000)。

黃少榮(1976-),女,廣東饒平人,廣東司法警官職業(yè)學院副教授,碩士。

1673-5862(2015)03-0417-06

TP306.1

A

10.3969/ j.issn.1673-5862.2015.03.022