張?zhí)眨诰?，楊興耀，廖彬

新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊 830046

基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度算法

張?zhí)?，于炯，楊興耀，廖彬

新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊 830046

1 引言

IBM公司于2007年底宣布了云計(jì)算計(jì)劃[1-2]后，云計(jì)算吸引了眾多人的關(guān)注，并迅速成為產(chǎn)業(yè)界和學(xué)術(shù)界研究的熱點(diǎn)。眾多云計(jì)算供應(yīng)商都根據(jù)自己企業(yè)業(yè)務(wù)推出相關(guān)的云計(jì)算戰(zhàn)略，投入巨資部署各自的云計(jì)算基礎(chǔ)架構(gòu)。研究機(jī)構(gòu)也提出各種原型系統(tǒng)[3-4]，并提出了超過(guò)20種以上的“云”的定義[5]。當(dāng)前，云計(jì)算服務(wù)可分為3個(gè)層次：（1）基礎(chǔ)設(shè)施即服務(wù)（IaaS）。如IBM的“藍(lán)云”計(jì)算平臺(tái)，Amazon的彈性云計(jì)算（EC2）服務(wù)、存儲(chǔ)服務(wù)（S3）和SimpleDB[6]，以及Sun的云基礎(chǔ)設(shè)施平臺(tái)（IAAS）。（2）平臺(tái)即服務(wù)（PaaS）。如Google AppEngine[7]、Apache Hadoop、Microsoft Azure等。（3）軟件即服務(wù)（SaaS）。如Salesforce公司的客戶關(guān)系管理服務(wù)。

云計(jì)算是網(wǎng)格計(jì)算、分布式計(jì)算、并行計(jì)算、效用計(jì)算、網(wǎng)絡(luò)存儲(chǔ)、虛擬化等先進(jìn)計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)發(fā)展融合的產(chǎn)物，具有普遍適用性。云計(jì)算技術(shù)的發(fā)展，一直與大規(guī)模任務(wù)調(diào)度密切相關(guān)。因此，依靠云計(jì)算環(huán)境如何對(duì)大規(guī)模任務(wù)進(jìn)行高效調(diào)度，是一個(gè)非常重要的研究方向。本文提出了一種基于雙適應(yīng)度粒子群算法（Double Fitness Particle Swarm Optimization，DFPSO）的云計(jì)算任務(wù)調(diào)度算法，并設(shè)計(jì)了適用于云環(huán)境下任務(wù)調(diào)度問(wèn)題的編碼、適應(yīng)度函數(shù)、位置速度更新策略。仿真實(shí)驗(yàn)取得了理想的調(diào)度結(jié)果，表明了本文算法在該問(wèn)題中具有較好的應(yīng)用前景。

在云計(jì)算環(huán)境中，一個(gè)大規(guī)模的計(jì)算任務(wù)的處理必須進(jìn)行分布式并行處理。首先要將一個(gè)邏輯上完整的大任務(wù)分解成若干個(gè)子任務(wù)，系統(tǒng)根據(jù)任務(wù)的信息采用適當(dāng)?shù)牟呗园巡煌娜蝿?wù)分配到不同資源節(jié)點(diǎn)上去運(yùn)行。當(dāng)所有子任務(wù)處理結(jié)束，則完成整個(gè)大任務(wù)的一次處理，最后將處理結(jié)果傳給用戶。目前的云計(jì)算環(huán)境中大部分采用Google提出的MapReduce[8-10]編程模型。如圖1，一個(gè)并行處理任務(wù)由多個(gè)Map任務(wù)和多個(gè)Reduce任務(wù)組成，任務(wù)的執(zhí)行分為Map階段和Reduce階段。在Map階段，每個(gè)Map任務(wù)對(duì)分配給它的數(shù)據(jù)進(jìn)行計(jì)算，然后按照Map的輸出key值將結(jié)果數(shù)據(jù)映射到對(duì)應(yīng)的Reduce任務(wù)中；在Reduce階段，每個(gè)Reduce任務(wù)對(duì)接收到的數(shù)據(jù)做進(jìn)一步聚集處理，得到輸出結(jié)果。

圖1 MapReduce運(yùn)行機(jī)制

由于云計(jì)算可擴(kuò)展性和動(dòng)態(tài)性的特點(diǎn)，任務(wù)量和資源的數(shù)量是相當(dāng)龐大的，系統(tǒng)每時(shí)每刻都要處理海量的任務(wù)。因此在MapReduce編程模型下，如何對(duì)眾多的子任務(wù)進(jìn)行調(diào)度是個(gè)復(fù)雜的問(wèn)題。不好的任務(wù)分配策略勢(shì)必會(huì)增加任務(wù)的執(zhí)行時(shí)間，降低整個(gè)云的性能以及用戶的使用滿意度。目前的一些較為典型的任務(wù)調(diào)度算法多是以總?cè)蝿?wù)完成時(shí)間作為調(diào)度目標(biāo)（makespan），沒(méi)有太多地考慮任務(wù)的平均完成時(shí)間，這樣勢(shì)必會(huì)造成許多潛在的優(yōu)良粒子的丟失。因?yàn)楫?dāng)任務(wù)平均完成時(shí)間較小時(shí)，使找到更小的任務(wù)總完成時(shí)間成為了可能。因此，本文提出了DFPSO，對(duì)云計(jì)算中的任務(wù)調(diào)度策略進(jìn)行了改進(jìn)，較大限度地提高了云計(jì)算任務(wù)調(diào)度的效率和用戶滿意度。

本文主要討論當(dāng)子任務(wù)數(shù)量遠(yuǎn)大于資源數(shù)量時(shí)的調(diào)度策略，如何獲取資源信息、子任務(wù)的分解方法不在討論范圍內(nèi)，不做詳細(xì)論述。在同一個(gè)資源上執(zhí)行的子任務(wù)遵循FCFS原則。

2 采用雙適應(yīng)度粒子群算法的任務(wù)調(diào)度

和遺傳算法（Genetic Algorithm）、蟻群（Ant Colony Algorithm）一樣，作為一種群智能算法[11]的粒子群優(yōu)化PSO算法[12]，是1995年由美國(guó)社會(huì)心理學(xué)家Kennedy和電氣工程師Eberhart提出來(lái)的仿生優(yōu)化算法，來(lái)源于對(duì)鳥(niǎo)類和魚類覓食過(guò)程的模擬。傳統(tǒng)PSO算法在求解云計(jì)算任務(wù)調(diào)度這個(gè)大規(guī)模的、實(shí)時(shí)的問(wèn)題上有著天然的優(yōu)勢(shì)。參照MapReduce編程模型，為得到任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間都較短的調(diào)度結(jié)果，本文在傳統(tǒng)粒子群優(yōu)化算法基礎(chǔ)上做了一些改進(jìn)，增加了一個(gè)適應(yīng)度，用兩個(gè)適應(yīng)度來(lái)選擇種群，即雙適應(yīng)度粒子群算法——DFPSO。

2.1 問(wèn)題編碼

目前粒子的編碼方式可以分為直接編碼（基于問(wèn)題直接對(duì)粒子的位置速度進(jìn)行編碼，一個(gè)粒子對(duì)應(yīng)問(wèn)題的一個(gè)可行解）和間接編碼兩類。本文采用間接編碼方式，對(duì)每個(gè)子任務(wù)占用的資源進(jìn)行編碼，編碼長(zhǎng)度取決于子任務(wù)數(shù)量，這樣一個(gè)粒子實(shí)際上對(duì)應(yīng)著一個(gè)任務(wù)分配策略。

設(shè)有Task個(gè)任務(wù)，Resource個(gè)資源，每個(gè)任務(wù)又分為若干個(gè)子任務(wù)（SubTask），且任務(wù)劃分的子任務(wù)總數(shù)SubTask大于資源數(shù)Resource，即SubTask＞Resource。

式（1）是子任務(wù)的總數(shù)量，其中TaskNum(t)為第t個(gè)任務(wù)所含子任務(wù)的個(gè)數(shù)。

式（2）是對(duì)子任務(wù)的編碼，此時(shí)采用順序法，即按任務(wù)順序進(jìn)行編碼。第i個(gè)Task中的第j個(gè)SubTask的序號(hào)是m[i，j]。

當(dāng)Task=3，Resource=3，SubTask=10時(shí)，粒子（3，2，2，1，3，2，3，1，1，2）即為一個(gè)可行的調(diào)度策略。如表1的粒子編碼所示，其中任務(wù)、子任務(wù)對(duì)（2，5）表示第2個(gè)任務(wù)中的第3個(gè)子任務(wù)序號(hào)是5；子任務(wù)、資源對(duì)（1，3）表示把子任務(wù)1分配到資源3上執(zhí)行。

表1 粒子編碼示例

表2 粒子解碼示例

之后是對(duì)粒子的解碼，得到資源上的SubTask分布情況。如表2所示，其中資源1上執(zhí)行的子任務(wù)是{4，8，9}，資源2上執(zhí)行的子任務(wù)是{2，3，6，10}，資源3上執(zhí)行的子任務(wù)是{1，5，7}。

本文使用ETC[13]矩陣記錄任務(wù)的執(zhí)行時(shí)間，ETC[i，j]表示子任務(wù)i在第j個(gè)資源上執(zhí)行的時(shí)間。

式（3）是完成所有任務(wù)的總時(shí)間，其中，Resource(r，i)是第r個(gè)資源執(zhí)行該資源上第i個(gè)子任務(wù)所用的時(shí)間，n為分配到此資源上的子任務(wù)個(gè)數(shù)。

式（4）是第t個(gè)任務(wù)完成的時(shí)間。其中，res(j，i)是子任務(wù)i分配的資源上執(zhí)行該資源第j個(gè)子任務(wù)所用的時(shí)間，k為第t個(gè)任務(wù)的第i個(gè)子任務(wù)在被分到的資源中的位置。

式（5）是每個(gè)任務(wù)平均完成時(shí)間。

2.2 粒子群體初始化

2.3 適應(yīng)度函數(shù)

對(duì)應(yīng)每個(gè)粒子的分配方案，都有一個(gè)用于衡量粒子優(yōu)劣的適應(yīng)度。代表任務(wù)分配最優(yōu)解的粒子具有最優(yōu)的適應(yīng)度，而適應(yīng)度函數(shù)作為相應(yīng)的評(píng)價(jià)函數(shù)要能有效地反映出每一個(gè)粒子與問(wèn)題最優(yōu)解粒子之間的差距。

任務(wù)調(diào)度較為典型的多是以任務(wù)總完成時(shí)間作為調(diào)度目標(biāo)，傳統(tǒng)的PSO算法用任務(wù)總完成時(shí)間來(lái)定義適應(yīng)度函數(shù)。為了提高算法的收斂精度，也是找到實(shí)際最優(yōu)解所必需的，DFPSO算法考慮任務(wù)總完成時(shí)間的同時(shí)也考慮到了任務(wù)的平均所用時(shí)間。即定義兩個(gè)適應(yīng)度函數(shù)：

TaskTime(t，i)為在第i個(gè)粒子中完成第t個(gè)任務(wù)所用的時(shí)間。

本文采用類似遺傳算法中選擇（Selection）的思想，優(yōu)選適應(yīng)度高的粒子。任務(wù)總完成時(shí)間和任務(wù)平均所用時(shí)間越短的粒子，適應(yīng)度值越大，越容易被選擇。通過(guò)這樣的選擇，種群中即有總?cè)蝿?wù)完成時(shí)間較短的粒子，又有任務(wù)平均所用時(shí)間較短的粒子，為進(jìn)化出下一代較優(yōu)秀的粒子提供了優(yōu)良的基礎(chǔ)。

2.4 粒子位置與速度的更新

粒子群算法中，只有當(dāng)粒子的當(dāng)前位置與所經(jīng)歷的最好位置相比具有更好的適應(yīng)值時(shí)，其粒子所經(jīng)歷的最好位置才會(huì)唯一地被該粒子當(dāng)前的位置所替代[14-15]。第i個(gè)粒子經(jīng)歷過(guò)的最好位置（有最好適應(yīng)度）記為pbi=(pbi1，pbi2，…，pbin)，在整個(gè)群體中，所有粒子經(jīng)歷過(guò)的最好位置記為gb=(gb1，gb2，…，gbn)。s代表群體的大小。分別用式（6）、（8）得出的兩個(gè)適應(yīng)度計(jì)算pb、gb：

每一代粒子根據(jù)下面公式更新自己的速度和位置，首先利用粒子自身的最佳飛行位置pb[16]作用于當(dāng)前位置，然后根據(jù)群體最佳位置gb對(duì)當(dāng)前粒子位置進(jìn)行調(diào)整。

其中，t表示迭代次數(shù)；ω為慣性權(quán)重，使粒子保持運(yùn)動(dòng)慣性，防止算法的早熟收斂；c1和c2是學(xué)習(xí)因子[17]；Rand為[0，1]之間的隨機(jī)數(shù)。迭代過(guò)程中，粒子的速度和位置都限制在特定的范圍內(nèi)[18-19]，同時(shí)pb和gb不斷更新，最后輸出的gb就是全局最優(yōu)解。

3 仿真實(shí)驗(yàn)與分析

3.1 仿真實(shí)驗(yàn)環(huán)境及算法設(shè)置

為了評(píng)價(jià)和分析本文算法的性能，實(shí)驗(yàn)是采用Matlab產(chǎn)生ETC[13]矩陣，首先用CloudSim[20]對(duì)傳統(tǒng)PSO算法和具有雙適應(yīng)度的PSO算法進(jìn)行了云環(huán)境下的仿真實(shí)驗(yàn)，繼而在相同的仿真平臺(tái)下對(duì)此兩種算法進(jìn)行橫向?qū)Ρ?。?shí)驗(yàn)測(cè)試各運(yùn)行100次，取100次實(shí)驗(yàn)的平均結(jié)果作為作圖的數(shù)據(jù)。

表3 算法主要參數(shù)

通過(guò)多次實(shí)驗(yàn)并參考文獻(xiàn)[21-22]的參數(shù)調(diào)整策略，兩種算法參數(shù)按表3設(shè)置，可以在較短的時(shí)間內(nèi)取得優(yōu)質(zhì)解。

其中，每個(gè)任務(wù)劃分成的子任務(wù)個(gè)數(shù)范圍為[30，70]，各個(gè)子任務(wù)的預(yù)計(jì)完成時(shí)間在[1，60]區(qū)間上隨機(jī)產(chǎn)生，單位為s。算法終止條件為：（1）達(dá)到最大迭代次數(shù)tmax；（2）連續(xù)60次總?cè)蝿?wù)完成時(shí)間與任務(wù)平均完成時(shí)間都沒(méi)有變化。

3.2 實(shí)驗(yàn)結(jié)果和性能分析

圖2～圖7為云計(jì)算環(huán)境下，基于傳統(tǒng)PSO的任務(wù)調(diào)度算法和本文提出的基于DFPSO的任務(wù)調(diào)度算法在任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間兩個(gè)方面的對(duì)比。

圖2和圖3中任務(wù)數(shù)Task=50，其迭代過(guò)程可看出PSO算法和DFPSO算法的前期迭代過(guò)程基本一致，得出的任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間相差不大。隨著粒子迭代更新次數(shù)的增大，兩種算法所得到的任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間都在不斷地減小，且DFPSO算法所得調(diào)度結(jié)果在任務(wù)總時(shí)間和任務(wù)平均完成時(shí)間上要小于傳統(tǒng)PSO算法。

圖2 Task=50時(shí)的任務(wù)總完成時(shí)間

圖3 Task=50時(shí)的任務(wù)平均完成時(shí)間

圖4 Task=100時(shí)的任務(wù)總完成時(shí)間

圖5 Task=100時(shí)的任務(wù)平均完成時(shí)間

圖6 Task=500時(shí)的任務(wù)總完成時(shí)間

圖7 Task=500時(shí)的任務(wù)平均完成時(shí)間

圖8 優(yōu)化效果總體對(duì)比圖

當(dāng)任務(wù)數(shù)Task增加到100時(shí)，通過(guò)比較圖4與圖5，可以看出兩種算法所得到的任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間的差距拉大。

其中傳統(tǒng)PSO算法收斂速度很快，迭代到40次后，由于任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間都沒(méi)有任何變化，傳統(tǒng)PSO算法收斂于自己的最優(yōu)調(diào)度結(jié)果，但所得任務(wù)調(diào)度結(jié)果的任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間都較大。DFPSO算法所得任務(wù)調(diào)度結(jié)果的任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間，分別比傳統(tǒng)PSO算法所得調(diào)度結(jié)果優(yōu)化了14 s和11 s，從而驗(yàn)證了在傳統(tǒng)PSO算法中多加入一個(gè)適應(yīng)度的有效性。

計(jì)算資源數(shù)量Resource不變，任務(wù)數(shù)Task繼續(xù)增加到500，從圖6和圖7可以看出，兩種算法所得調(diào)度結(jié)果的任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間的差距隨之達(dá)到30 s和28 s。隨著任務(wù)數(shù)量加大，通過(guò)DFPSO算法進(jìn)行任務(wù)調(diào)度，得到了任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間都更小的調(diào)度結(jié)果，充分地利用了現(xiàn)有云資源，提高了任務(wù)調(diào)度的效率。

通過(guò)圖8可以得出結(jié)論，采用DFPSO算法對(duì)云中任務(wù)進(jìn)行調(diào)度，有效地減少了任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間，提高了用戶的滿意度。在云中資源不增加的情況下，隨著用戶任務(wù)數(shù)量不斷的增加，DFPSO算法的綜合調(diào)度性能也呈現(xiàn)上升趨勢(shì)，進(jìn)一步驗(yàn)證了DFPSO算法的有效性。

從以上實(shí)驗(yàn)結(jié)果反映出，傳統(tǒng)PSO算法因?yàn)橹恢匾暱側(cè)蝿?wù)的完成時(shí)間，造成了一些潛在優(yōu)良的粒子丟失。雖然提高了自己的收斂速度，但該算法在運(yùn)行過(guò)程中由于無(wú)法有效跳出局部最優(yōu)的搜索狀態(tài)而過(guò)早地收斂到局部最優(yōu)的任務(wù)調(diào)度結(jié)果上，得到的任務(wù)調(diào)度結(jié)果不論是任務(wù)總完成時(shí)間還是任務(wù)平均完成時(shí)間都較大。本文在傳統(tǒng)的PSO算法的基礎(chǔ)上增加一個(gè)適應(yīng)度，最終形成了DFPSO算法。該算法由于同時(shí)考慮任務(wù)總完成時(shí)間和任務(wù)平均完成時(shí)間，需對(duì)每個(gè)任務(wù)進(jìn)行計(jì)算，盡管在收斂速度上比PSO算法有所下降，但該算法的調(diào)度結(jié)果不但任務(wù)總完成時(shí)間短，任務(wù)的平均所用時(shí)間也短。因此，對(duì)于DFPSO算法和傳統(tǒng)PSO算法的比較，從以一定收斂速度的損失來(lái)?yè)Q取能夠得到明顯更優(yōu)的調(diào)度結(jié)果的能力方面來(lái)說(shuō)，DFPSO算法優(yōu)于傳統(tǒng)PSO算法。通過(guò)DFPSO算法進(jìn)行任務(wù)調(diào)度可以找到明顯更小的任務(wù)總完成時(shí)間，是一種云計(jì)算環(huán)境下的有效任務(wù)調(diào)度算法。

4 總結(jié)

在粒子群優(yōu)化算法的基礎(chǔ)上，針對(duì)云計(jì)算的編程模型，提出了一種具有雙適應(yīng)度的粒子群（DFPSO）算法的任務(wù)調(diào)度算法。本文算法在進(jìn)行任務(wù)調(diào)度時(shí)不僅考慮總?cè)蝿?wù)完成時(shí)間，同時(shí)也考慮到了任務(wù)的平均完成時(shí)間。仿真實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)云計(jì)算環(huán)境下這種編程模式可以實(shí)現(xiàn)較為理想的任務(wù)調(diào)度結(jié)果。下一步工作，是如何在保證任務(wù)調(diào)度效率的同時(shí)提高此算法的收斂速度。

[1]Sims K.IBM introduces ready-to-use cloud computing collaboration services get clients started with cloud computing[EB/OL].（2007）[2011-12].http：//www.ibm.com/press/us/en/pressrelease/ 22613.wss.

[2]Boss G，Malladi P，Quan D，et al.Cloud computing.IBM White Paper[EB/OL].（2007）[2011-12].http：//download.boulder.ibm.com/ ibmdl/pub/software/dw/wes/hipods/Cloud_computing_wp_final_ 8Oct.pdf.

[3]Rochwerger B，Breitgand D，Levy E，et al.The reservoir model and architecture for open federated cloud computing[J].IBM Journal of Research and Development，2009，53（4）：1-17.

[4]Nurmi D，Wolski R，Grzegorczyk C，et al.The eucalyptus opensource cloud-computing system[C]//Proceeding of the Crid，2009：124-131.

[5]Armbrust M，F(xiàn)ox A，Griffith R，et al.Above the clouds：a berkeley view of cloud computing，Technical Report No.UCB/EECS-2009-28[R].USA：UC Berkley，2009：1-25.

[6]Amazon SimpleDB[EB/OL].（2011-08-10）[2011-12].http：//aws. smazon.com/simpledb/.

[7]Barroso L A，Dean J，Holzle U.Web search for a planet：The Google cluster architecture[J].IEEE Micro，2003，23（2）：22-28.

[8]Jeffrey D，Sanjay G.MapReduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

[9]Dean J，Ghemawat S.Distributed programming with MapReduce[M]//Oram A，Wilson G.Beautiful Code.Sebastopol：O’Reilly Media，Inc，2007：371-384.

[10]Jeffrey D，Sanjay G.MapReduce：simplifed data processing on large clusters[C]//Proceedings of the Conference on Operating System Design and Implementation（OSDI），San Francisco，USA，2004：137-150.

[11]Eberhart R C，Kennedy J.A new optimizer using particles swarm theory[C]//Proc of the 6th Int’1 Symp on Micro Machine and Human Science.Nagoya：IEEE Inc，1995：39-43.

[12]Bratton D，Kennedy J.Defining a standard for particle swarm optimization[C]//ProceedingsoftheIEEESwarmIntelligence Symposium，Honolulu，HI，2007：120-127.

[13]Ali S，Siegel H J，Maheswaran M，et al.Representing task and machine heterogeneities for heterogeneous computing systems[J].Journal of Science and Engineering，2000，3（3）：195-207.

[14]Clerc M，Kennedy J.The particle swarm-explosion，stability，and convergence in a multidimensional complex space[J].IEEE Trans on Evolutionary Computation，2002，6（1）：58-73.

[15]Li N，Sun D B，Zou T，et al.An analysis for a particle’s trajectory of PSO based on difference equation[J].Chinese Journal of Computers，2006，29（11）：2052-2061.

[16]Ratnaweera A，Halgamuge S K，Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Trans on Evolutionary Computation，2004，8（3）：240-255.

[17]Parsopoulos K E，Vrahatis M N.Recent approaches to global optimization problems through particle swarm optimization[J]. Natural Computing，2002，1（2/3）：235-306.

[18]Eberhart R，Shi Y.Particle swarm optimization：developments，applications，and resource[C]//Proceedings of the IEEE International Conference on Evolutionary Computation，Piscataway，NJ，2001：81-86.

[19]Said M，Ahamed A.Hybrid periodic boundary condition for particle swarm optimization[J].IEEE Transactions on Antennas and Propagation，2007，55（11）：3251-3256.

[20]Calheiros R N，Ranjan R，Beloglazov A，et al.CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software：Practice and Experience，2010，41（1）：23-50.

[21]Chen G L，Guo W Z，Chen Y Z.A PSO-based intelligent decision algorithm for VLSI floor planning[J].Soft Computing，2010，14（12）：1329-1337.

[22]李曉東，張慶紅，葉瑾琳.基于仿真的優(yōu)化的粒子群算法參數(shù)選取研究[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（33）：30-35.

ZHANG Tao,YU Jiong,YANG Xingyao,LIAO Bin

School of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

How to schedule tasks efficiently is one of the key issues to be resolved in cloud computing environment.A Double Fitness Particle Swarm Optimization algorithm（DFPSO）based on conventional Particle Swarm Optimization（PSO）is brought up for the programming framework of cloud computing.Through this algorithm,the better task scheduling not only shortens total task completion time and also has shorter average task completion time.Simulation results show that DFPSO is better than PSO, and the integrated scheduling performance is excellent,especially when the number of tasks increases.

task scheduling;cloud computing;Particle Swarm Optimization（PSO）algorithm;double-fitness

如何對(duì)任務(wù)進(jìn)行高效合理的調(diào)度是云計(jì)算需要解決的關(guān)鍵問(wèn)題之一，針對(duì)云計(jì)算的編程模型框架，在傳統(tǒng)粒子群優(yōu)化算法（PSO）的基礎(chǔ)上，提出了一種具有雙適應(yīng)度的粒子群算法（DFPSO）。通過(guò)該算法不但能找到任務(wù)總完成時(shí)間較短的調(diào)度結(jié)果，而且此調(diào)度結(jié)果的任務(wù)平均完成時(shí)間也較短。仿真分析結(jié)果表明，在相同的條件設(shè)置下，該算法優(yōu)于傳統(tǒng)的粒子群優(yōu)化算法，當(dāng)任務(wù)數(shù)量增多時(shí)，其綜合調(diào)度性能優(yōu)點(diǎn)明顯。

任務(wù)調(diào)度；云計(jì)算；粒子群算法；雙適應(yīng)度

A

TP311

10.3778/j.issn.1002-8331.1201-0022

ZHANG Tao,YU Jiong,YANG Xingyao,et al.Improved Particle Swarm Optimization algorithm for cloud computing task scheduling.Computer Engineering and Applications,2013,49（19）：68-72.

國(guó)家自然科學(xué)基金（No.60863003，No.61063042）；新疆大學(xué)博士科研啟動(dòng)基金（No.BS090153）。

張?zhí)眨?988—），女，碩士研究生，主要研究領(lǐng)域?yàn)樵朴?jì)算，網(wǎng)格與分布式計(jì)算；于炯（1964—），男，教授，博士，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全，網(wǎng)格與分布式計(jì)算；楊興耀（1984—），男，博士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)，網(wǎng)格與分布式計(jì)算；廖彬（1986—），男，博士研究生，主要研究領(lǐng)域?yàn)榫W(wǎng)格與分布式計(jì)算。E-mail：zt59921661@126.com

2012-01-09

2012-03-21

1002-8331（2013）19-0068-05