異構(gòu)云系統(tǒng)中基于智能優(yōu)化算法的多維資源公平分配

劉曦　張瀟璐　張學(xué)杰

摘要：資源分配策略的研究一直是云計(jì)算領(lǐng)域研究的熱點(diǎn)和難點(diǎn)，針對(duì)異構(gòu)云計(jì)算環(huán)境下多維資源的公平分配問題，結(jié)合基因算法（GA）和差分進(jìn)化算法（DE），分別給出了兩種兼顧分配公平性和效率的資源分配策略，改進(jìn)了解矩陣表達(dá)式使異構(gòu)云系統(tǒng)中的主資源公平分配（DRFH）模型轉(zhuǎn)化成為整數(shù)線性規(guī)劃（ILP）模型，并提出了基于最大任務(wù)數(shù)匹配值（MTM）的初始解產(chǎn)生機(jī)制和使不可行解轉(zhuǎn)化為可行解的修正操作，以此提高算法的收斂速度，使其能夠快速有效地得到最優(yōu)分配方案。實(shí)驗(yàn)結(jié)果表明，基于GA和DE算法的多維資源公平分配策略可以得到近似最優(yōu)解，在最大化最小主資源份額目標(biāo)值和資源利用率方面明顯優(yōu)于Best-Fit DRFH和Distributed-DRFH，而且針對(duì)不同任務(wù)類型的資源需求，具有較強(qiáng)的自適應(yīng)能力。

關(guān)鍵詞：主資源公平； 基因算法； 差分進(jìn)化算法； 異構(gòu)云

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A

0引言

在云計(jì)算環(huán)境中，如何有效地對(duì)資源進(jìn)行分配調(diào)度，保證資源分配的公平性，最大可能地滿足服務(wù)的資源需求，同時(shí)，確保資源能夠最大限度被利用，是云計(jì)算平臺(tái)分配系統(tǒng)需要解決的重要問題。而目前面臨的是云計(jì)算環(huán)境由大量異構(gòu)服務(wù)器組成，每個(gè)服務(wù)器的配置不同，而且由于資源供給的多樣性，更增加了資源公平分配的難度。因此，設(shè)計(jì)針對(duì)異構(gòu)云計(jì)算環(huán)境下兼顧多維資源的分配公平性和效率，并使其分配到的資源盡可能達(dá)到最大值的公平分配方法是目前云計(jì)算平臺(tái)急需解決的一個(gè)關(guān)鍵問題。

2011年，美國加州大學(xué)伯克分校的Ghodsi等[1]首次提出了占優(yōu)資源公平分配（Dominant Resource Fairness， DRF）。該機(jī)制是在最大最小公平模型的基礎(chǔ)上，擴(kuò)展使其能夠?qū)Χ喾N類型的資源進(jìn)行分配并能保證分配的公平性?；舅枷胧亲畲蠡杏脩糁械恼純?yōu)資源份額的最小值，從而將多資源分配問題轉(zhuǎn)化為單資源分配問題。DRF與傳統(tǒng)的基于單資源的分配機(jī)制相比，其資源利用率有了明顯的提升。雖然DRF分配機(jī)制考慮到了多維資源的情形，但卻將所有待分配的資源全部集中在一個(gè)資源池中進(jìn)行考慮。

針對(duì)上述問題，文獻(xiàn)[2]提出了在異構(gòu)服務(wù)器組成的云計(jì)算環(huán)境下的主資源公平分配機(jī)制（Dominant Resource Fairness allocation in Heterogeneous system， DRFH），其分配機(jī)制是實(shí)現(xiàn)最大化用戶的最小主資源份額。DRFH分配機(jī)制很好地解決了異構(gòu)服務(wù)器之間的資源差異化問題和用戶任務(wù)不可分割問題。但DRFH求解是一個(gè)NP難問題，目前很難找到一個(gè)快速有效的方法來求最優(yōu)解。文獻(xiàn)[2]中設(shè)計(jì)了一個(gè)啟發(fā)式算法（Best-Fit DRFH）來求解DRFH。該算法優(yōu)先給最小主資源份額的用戶分配資源，在最佳適應(yīng)值的服務(wù)器上進(jìn)行資源分配，以提高資源利用率。文獻(xiàn)[3]將DRFH分配機(jī)制擴(kuò)展到了分布式環(huán)境中，提出 Distributed-DRFH算法。雖然Best-Fit DRFH和Distributed-DRFH算法與傳統(tǒng)的方法相比，在目標(biāo)函數(shù)值和資源利用率方面都有所提升，但我們認(rèn)為還有提升的空間。首先，Best-Fit DRFH和Distributed-DRFH算法采用簡單的啟發(fā)式算法，能達(dá)到快速求解目的，但求出來的解與最優(yōu)解有明顯差距；其次，在異構(gòu)云計(jì)算環(huán)境下，需要考慮異構(gòu)服務(wù)器資源類型和用戶資源需求的多樣性帶來的資源分配公平和效率問題。由以上分析可以看出，采用簡單的啟發(fā)式算法來解決DRFH問題無法得到以資源公平分配最大化為目標(biāo)的最優(yōu)分配方案。

在云計(jì)算環(huán)境中，多維資源公平分配是一個(gè)NP難問題，其主要目的是最大化最小主資源分配份額。目前求解NP難問題的主要智能優(yōu)化算法有基因算法（Genetic Algorithm， GA）[4]、差分進(jìn)化（Different Evolution， DE）算法[5]、模擬退火（Simulated Annealing， SA）算法、神經(jīng)網(wǎng)絡(luò)等，每種算法都有自己的求解方式與優(yōu)點(diǎn)，并且已有很多研究人員針對(duì)不同的應(yīng)用場(chǎng)景對(duì)它們進(jìn)行了相應(yīng)的優(yōu)化或者有效的結(jié)合，但這些算法較少涉及到異構(gòu)環(huán)境下資源分配調(diào)度問題。將這些算法合理地引用到異構(gòu)云計(jì)算環(huán)境下多維資源的公平分配問題的研究上，可以快速得到最優(yōu)解分配方案，保證資源的公平性分配，提高整個(gè)系統(tǒng)的資源利用率。在智能優(yōu)化算法中， GA 和DE算法都是基于種群的啟發(fā)式全局搜索算法，能夠掌握并動(dòng)態(tài)跟蹤目前的全局搜索情況，并根據(jù)當(dāng)前的搜索情況自適應(yīng)調(diào)整其搜索策略，因此能很好適用于異構(gòu)云計(jì)算環(huán)境下復(fù)雜的資源分配情況，并且它們擁有較強(qiáng)的魯棒性和全局收斂能力，算法能在很短的時(shí)間內(nèi)找到近似最優(yōu)解，提高分配的效率。因此，本文提出在異構(gòu)云計(jì)算環(huán)境下基于GA和DE算法來求解DRFH最優(yōu)分配方案的策略，并針對(duì)傳統(tǒng)GA和DE算法在求解最優(yōu)解過程中易早熟收斂等缺點(diǎn)，改進(jìn)解矩陣表達(dá)式，使其更適用于離散解空間域內(nèi)搜索全局最優(yōu)解，并且使DRFH模型轉(zhuǎn)化成為整數(shù)線性規(guī)劃（Integer Linear Programming， ILP）模型；解的初始值生成采用采用基于最大任務(wù)數(shù)匹配值（Max Task Match，MTM）的啟發(fā)式算法，以加快解空間的探測(cè)；設(shè)計(jì)修正操作算法，使不可行解在每次迭代過程中保留優(yōu)秀特征的情況下變?yōu)榭尚薪?。模擬實(shí)驗(yàn)對(duì)比了基于GA和DE算法的多維資源公平分配策略與Best-Fit DRFH和Distributed-DRFH在真實(shí)實(shí)例和不同資源請(qǐng)求類型實(shí)例下的性能表現(xiàn)，其目標(biāo)函數(shù)值和資源利用率均顯著地優(yōu)于Best-Fit DRFH和Distributed-DRFH，且近似最優(yōu)解。實(shí)驗(yàn)結(jié)果表明基于GA和DE算法的分配策略能很好地適應(yīng)用戶資源請(qǐng)求類型的變化，有效地利用服務(wù)器資源，提高了服務(wù)質(zhì)量。

1相關(guān)工作

在資源分配公平性方面的研究中，文獻(xiàn)[6]提出了基于單資源的最大最小公平（Max-min Fairness）模型，其基本思想是使得資源分配的最小分配量盡可能最大化；文獻(xiàn)[1]提出了針對(duì)多維資源的DRF機(jī)制；文獻(xiàn)[7]將DRF機(jī)制推廣到零需求和任務(wù)不可分等情形，并討論了DRF機(jī)制的局限性；文獻(xiàn)[8]考慮用戶任務(wù)總數(shù)有限的情況， 提出了Lexicographically Max-Min Dominant Share （LMMDS）機(jī)制，推廣了DRF機(jī)制，并分析了DRF機(jī)制的近似比。針對(duì)用戶動(dòng)態(tài)加入系統(tǒng)的情形，文獻(xiàn)[9]提出了一種動(dòng)態(tài)情形下多資源公平分配機(jī)制DDRF；筆者之前的研究工作也將動(dòng)態(tài)DDRF機(jī)制推廣到任務(wù)數(shù)受限的情形[10]。

以上成果是基于將資源全部集中在一個(gè)資源池中且用戶任務(wù)可以分割的情況下研究的，與云計(jì)算真實(shí)環(huán)境下的資源分配情況不相符。由于服務(wù)器的異構(gòu)性，如分給用戶i在服務(wù)器1上能完成1/2任務(wù)的資源，在服務(wù)器2能完成1/2任務(wù)的資源，但用戶任務(wù)不可分割執(zhí)行，使得服務(wù)器1和2上的資源閑置，造成了資源的浪費(fèi)。針對(duì)上述問題，文獻(xiàn)[11]提出了多個(gè)異構(gòu)系統(tǒng)下多維資源公平分配算法；文獻(xiàn)[12]對(duì)異構(gòu)系統(tǒng)中任務(wù)不可分割情形下的公平分配機(jī)制進(jìn)行了深入的理論分析；文獻(xiàn)[13]在異構(gòu)云計(jì)算體系結(jié)構(gòu)下提出了基于占優(yōu)資源的多資源聯(lián)合公平分配機(jī)制，該機(jī)制定義了占優(yōu)資源熵及占優(yōu)資源權(quán)重，提高了系統(tǒng)的自適應(yīng)能力；文獻(xiàn)[2]提出了異構(gòu)系統(tǒng)中資源公平分配機(jī)制DRFH，其分配機(jī)制是實(shí)現(xiàn)最大化用戶的最小主資源份額；文獻(xiàn)[3]在DRFH[2]的基礎(chǔ)上，針對(duì)分布式環(huán)境中有多個(gè)資源管理者的情況，提出了Distributed-DRFH算法。Distributed-DRFH算法是將用戶資源請(qǐng)求分到與其最適應(yīng)的資源管理者的服務(wù)器上，并提出了本地資源管理算法。實(shí)驗(yàn)表明在多個(gè)資源管理者的情況下，Distributed-DRFH能有效提高資源利用率。但是求解DRFH問題是一個(gè)NP難問題，若采用傳統(tǒng)搜索方法，可能無法在合理的時(shí)間內(nèi)找到問題的最優(yōu)解，因此需要尋求一種能夠快速求出最優(yōu)解或者近似最優(yōu)解的方法。

近年來已有研究者將GA、蟻群算法（Ant Colony Optimization， ACO）、粒子群優(yōu)化（Particle Swarm optimization， PSO）算法、人工神經(jīng)網(wǎng)絡(luò)等引入到云計(jì)算任務(wù)調(diào)度問題中，取得了不錯(cuò)的應(yīng)用效果。文獻(xiàn)[14]為提高云計(jì)算任務(wù)調(diào)度的服務(wù)質(zhì)量，提出基于GA和ACO算法的多群智能算法。首先利用GA在全局搜索較優(yōu)解，然后利用ACO算法來尋找全局最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，智能優(yōu)化算法提高了云計(jì)算任務(wù)調(diào)度的效率，縮短了任務(wù)完成時(shí)間。文獻(xiàn)[15]針對(duì)云計(jì)算MapReduce框架下軟件即服務(wù)（Software-as-a-Service， SaaS）多租戶情況，提出了一種基于ACO的多租戶服務(wù)定制算法；文獻(xiàn)[16]針對(duì)云計(jì)算基礎(chǔ)設(shè)施即服務(wù)（Infrastructure as a Service， IaaS）中虛擬機(jī)部署問題，提出了一種基于PSO算法的負(fù)載平衡虛擬機(jī)部署策略。但以上研究均未考慮異構(gòu)云計(jì)算環(huán)境下資源的多樣性和用戶需求的差異性；而且，多維資源公平分配是一個(gè)復(fù)雜問題，傳統(tǒng)GA、DE算法、ACO算法等均存在不足，因此考慮到異構(gòu)云計(jì)算環(huán)境下多維資源分配的公平性和效率問題，需要對(duì)其算法進(jìn)行改進(jìn)，從而找到問題的最優(yōu)解。

2.3修正操作

智能優(yōu)化算法在每一次迭代完成后，都會(huì)產(chǎn)生不可行解，如超過資源總量限制等，這時(shí)需要一種操作去檢測(cè)解是否可行，若不可行則修正成可行解。本文采用貪心策略來修正不可行解，具體包含兩個(gè)階段：第一個(gè)階段是遍歷所有服務(wù)器，檢查其資源分配情況。如果分給用戶的資源超過服務(wù)器資源總量，則選擇最大主資源份額的用戶，減少它的任務(wù)數(shù)。第二個(gè)階段是選擇MTMkl最大的用戶，在不超過資源總量的前提下，增加它的任務(wù)數(shù)，提高最小主資源份額值。算法描述為算法2。

4基于DE算法的多維資源公平分配策略

DE算法是一種在連續(xù)空間中進(jìn)行隨機(jī)搜索的全局優(yōu)化算法[5]，其基本思想是：從種群中隨機(jī)選擇幾個(gè)不相同的個(gè)體（解），以其中一個(gè)個(gè)體作為基礎(chǔ)，剩余的個(gè)體為參照作一個(gè)隨機(jī)的擾動(dòng)，將擾動(dòng)得到的新個(gè)體（新解）與目標(biāo)個(gè)體進(jìn)行交叉操作后產(chǎn)生實(shí)驗(yàn)個(gè)體（新解），將實(shí)驗(yàn)個(gè)體與目標(biāo)個(gè)體進(jìn)行自然選擇，優(yōu)勝劣汰，從而實(shí)現(xiàn)在全局空間內(nèi)搜索最優(yōu)個(gè)體（最優(yōu)解，記為OPT）[19]。DE算法相比于其他進(jìn)化算法，其在較強(qiáng)的種群全局搜索策略的基礎(chǔ)上，通過變異操作中采用的特殊且容易實(shí)現(xiàn)的差分策略，降低了進(jìn)化操作的復(fù)雜度。DE算法與GA相似，也分為三個(gè)步驟：變異操作、交叉操作和選擇操作。

4.1變異操作

DE算法通過差分策略實(shí)現(xiàn)個(gè)體的變異，有效利用群體的分布特性，提高算法的搜索能力。算法首先通過差分策略對(duì)種群中的每一個(gè)個(gè)體Xk進(jìn)行變異操作，得到變異個(gè)體V。本文隨機(jī)使用表1中列舉的5種差分策略。其中：x表示種群中的隨機(jī)個(gè)體、最優(yōu)個(gè)體或當(dāng)前個(gè)體，y表示進(jìn)行差分的個(gè)體個(gè)數(shù)，z表示差分的模式。如算法中的Rand1bin操作是隨機(jī)在種群中選擇兩個(gè)不同的個(gè)體相減生成差分個(gè)體，將差分個(gè)體賦予權(quán)值之后加到第三個(gè)隨機(jī)選擇的不同個(gè)體上，生成變異個(gè)體。數(shù)學(xué)表達(dá)式為：

5實(shí)驗(yàn)評(píng)估

基于Google數(shù)據(jù)集來評(píng)估基于GA和DE算法的多維資源公平分配策略的性能（以下簡稱為GA和DE算法），同時(shí)與Best-Fit DRFH、Distributed-DRFH和最優(yōu)解OPT進(jìn)行比較。Distribute-DRF資源分配方式設(shè)置1個(gè)資源提供者（p=1）。服務(wù)器資源配置和用戶的任務(wù)需求均是從Google的集群數(shù)據(jù)集[20]中隨機(jī)選擇。該數(shù)據(jù)集是Google 7個(gè)小時(shí)的真實(shí)數(shù)據(jù)，其中包含了服務(wù)器的配置情況，如CPU、內(nèi)存和硬盤，以及用戶的資源需求等。表2為Google的異構(gòu)服務(wù)器集群資源配置及數(shù)量情況，CPU和內(nèi)存都是基于最大處理能力的服務(wù)器容量正則化處理后的值。GA和DE算法的種群大小設(shè)置為SN=30，迭代次數(shù)不超過2000。由于智能優(yōu)化算法具有隨機(jī)性，因此針對(duì)每個(gè)實(shí)例，運(yùn)行50次后取平均值進(jìn)行性能評(píng)估。

參照文獻(xiàn)[3]中的設(shè)置，從Google數(shù)據(jù)集中隨機(jī)選取20個(gè)用戶，且每個(gè)用戶不少于20個(gè)任務(wù)需求，然后在一個(gè)由100個(gè)服務(wù)器節(jié)點(diǎn)組成的異構(gòu)云計(jì)算系統(tǒng)上進(jìn)行資源分配，服務(wù)器的CPU和內(nèi)存配置從表2中的Google數(shù)據(jù)集中隨機(jī)選擇。由于該實(shí)驗(yàn)利用Lingo程序在24h內(nèi)未找到整數(shù)最優(yōu)解，因此沒有進(jìn)行與最優(yōu)解的比較。表3比較了GA、DE算法、Best-Fit DRFH和Distributed-DRFH的主資源份額，可以看出，GA和DE算法相比Best-Fit和Distributed-DRFH的主資源份額有明顯的提高，其中GA和DE算法的結(jié)果非常接近。這主要是因?yàn)镚A和DE算法是在全局空間域內(nèi)搜索最優(yōu)解，并通過多次迭代，不斷地改善當(dāng)前最優(yōu)解。從表3中還能夠看出，Best-Fit DRFH的CPU和內(nèi)存利用率均高于Distributed-DRFH，但GA和DE算法的CPU和內(nèi)存使用率均顯著地高于Best-Fit DRFH和Distributed-DRFH，說明基于GA和DE算法的多資源公平分配策略能夠有效提高服務(wù)器的資源利用率，避免服務(wù)器資源的閑置浪費(fèi)。

在實(shí)際異構(gòu)云計(jì)算資源分配情況下，用戶任務(wù)的資源請(qǐng)求類型呈現(xiàn)多樣化，如在資源類型為CPU和內(nèi)存的情況下，可能會(huì)出現(xiàn)計(jì)算資源密集型任務(wù)或內(nèi)存資源密集型任務(wù)。針對(duì)這兩種情況，設(shè)計(jì)了兩個(gè)實(shí)例來評(píng)估GA和DE算法的性能表現(xiàn)。對(duì)于計(jì)算資源密集型任務(wù)，從表2中隨機(jī)選取5臺(tái)服務(wù)器和3個(gè)用戶，滿足用戶任務(wù)資源需求類型為計(jì)算資源密集型（Di1>Di2）；對(duì)于內(nèi)存資源密集型任務(wù)，從表2中隨機(jī)選取5臺(tái)服務(wù)器和3個(gè)用戶，滿足用戶任務(wù)資源需求類型為內(nèi)存資源密集型（Di1

1）當(dāng)資源需求是內(nèi)存資源密集型時(shí)，Distributed-DRFH的主資源份額優(yōu)于Best-Fit DRFH，而當(dāng)資源需求是計(jì)算資源密集型時(shí)，Best-Fit DRFH卻優(yōu)于Distributed-DRFH；但GA和DE算法均明顯地優(yōu)于Best-Fit DRFH和Distributed-DRFH，且主資源份額接近最優(yōu)解。該實(shí)驗(yàn)結(jié)果表明GA和DE算法均能很好地適應(yīng)用戶任務(wù)需求類型的變化并能得到近似最優(yōu)解。

2）雖然啟發(fā)式算法和兩種智能優(yōu)化算法的解均低于最優(yōu)解，但GA和DE算法均顯著地高于Best-Fit DRFH和Distributed-DRFH算法。實(shí)驗(yàn)結(jié)果也表明在啟發(fā)式算法下的CPU利用率較低，運(yùn)用智能優(yōu)化算法可以提高資源利用率，有效地避免CPU資源的浪費(fèi)。GA和DE算法最多迭代2000次，如果增加迭代次數(shù)，得到的主資源份額和資源利用率會(huì)更加接近最優(yōu)解。

3）當(dāng)資源需求是內(nèi)存資源密集型時(shí)，DE算法的CPU和內(nèi)存的利用率均優(yōu)于GA；當(dāng)資源需求是計(jì)算資源密集型時(shí)，GA的CPU利用率優(yōu)于DE算法，而DE算法的內(nèi)存利用率優(yōu)于GA，可以看出GA和DE算法均顯著地高于Best-Fit DRFH和Distributed-DRFH的內(nèi)存利用率，且接近最優(yōu)解。值得注意的是，Best-Fit DRFH和Distributed-DRFH啟發(fā)式算法在兩種資源請(qǐng)求類型下，出現(xiàn)了明顯的波動(dòng)（內(nèi)存資源密集型時(shí)Distributed-DRFH較優(yōu)，計(jì)算資源密集型時(shí)Best-Fit DRFH較優(yōu)），而GA和DE算法并沒有出現(xiàn)較大的波動(dòng)，均接近最優(yōu)解。這表明GA和DE算法能很好地適應(yīng)用戶任務(wù)資源請(qǐng)求類型的變化，可以有效地利用服務(wù)器資源，有較強(qiáng)的環(huán)境適應(yīng)能力。

6結(jié)語

本文針對(duì)異構(gòu)服務(wù)器組成的云計(jì)算系統(tǒng)下多樣化的用戶資源類型請(qǐng)求和用戶任務(wù)不可分割等需求，運(yùn)用GA和DE算法求解DRFH最優(yōu)資源分配問題，改進(jìn)適合于兩種智能優(yōu)化算法的解矩陣表達(dá)式使求解DRFH模型轉(zhuǎn)化成為求解整數(shù)線性規(guī)劃模型，設(shè)計(jì)基于MTM啟發(fā)式算法的初始解產(chǎn)生機(jī)制和使不可行解轉(zhuǎn)化為可行解的修正操作。實(shí)驗(yàn)結(jié)果表明，基于GA和DE算法的多維資源公平分配策略分配到的主資源份額和資源利用率方面均優(yōu)于Best-Fit DRFH和Distributed-DRFH算法，且近似最優(yōu)解，有效提升了資源利用率，使供給和需求更加匹配，而且兩種算法能夠很好地適應(yīng)于用戶資源請(qǐng)求類型的變化。接下來的研究工作將會(huì)在大規(guī)模的集群中對(duì)算法性能進(jìn)行驗(yàn)證，并優(yōu)化算法參數(shù)使其更適用于異構(gòu)云計(jì)算環(huán)境下的多維資源分配情況。

參考文獻(xiàn)：

[1]GHODSI A， ZAHARIA M， HINDMAN B， et al. Dominant resource fairness： Fair allocation of multiple resource types [C]//NSDI 2011： Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2011： 323-336.

[2]WANG W， LIANG B， LI B. Multi-resource fair allocation in heterogeneous cloud computing systems [J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（10）： 2822-2835.

[3]ZHU Q， OH J C. An approach to dominant resource fairness in distributed environment [M]// IEA/AIE 2015： Proceedings of the 28th International Conference on Industrial， Engineering and Other Applications of Applied Intelligent Systems， LNCS 9101. Berlin： Springer-Verlag， 2015： 141-150.

[4]HOLLAND J H. Adaptation in Natural and Artificial Systems [M]. Cambridge， MA： MIT Press， 1992： 89-121.

[5]STORN R， PRICE K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization， 1997， 11（4）：341-359.

[6]Wikipedia. Max-min fairness[EB/OL]. [2015-06-10]. http：//en.wikipedia.org/wiki/Max-min_fairness.

[7]PARKES D C， PROCACCIA A D， SHAH N. Beyond dominant resource fairness： extensions， limitations， and indivisibilities [J]. ACM Transactions on Economics and Computation， 2015， 3（1）： 1-22.

[8]LI W， LIU X， ZHANG X， et al. Multi-resource fair allocation with bounded number of tasks in cloud computing systems [J/OL]. arXiv preprint arXiv： 1410.1255v2. （2015-02-03） [2015-12-01]. http：//arxiv.org/abs/1410.1255.[2015-02-03]. http：//xueshu.baidu.com/s？wd=paperuri%3A%28fb34151b4905f286d5f3c4d576091855 %29&filter=sc_long_sign&tn=SE_xueshusource_2kduw 22v&sc_vurl=http%3A%2F%2Farxiv.org%2Fabs%2F1410.1255&ie=utf-8&sc_us=15855640868426366128.

[9]KASH I， PROCACCIA A D， SHAH N. No Agent left behind： dynamic fair division of multiple resources [J]. AAMAS 13： Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems. Richland， SC： International Foundation for Autonomous Agents and Multiagent Systems， 2013： 351-358.

[10]LIU X， ZHANG X， ZHANG X. Dynamic fair division of multiple resources with satiable Agents in cloud computing systems [C]// BDCLOUD 15： Proceedings of the 2015 IEEE Fifth International Conference on Big Data and Cloud Computing. Washington， DC： IEEE Computer Society， 2015： 131-136.

[11]PSOMAS C-A， SCHWARTZ J. Beyond beyond dominant resource fairness： indivisible resource allocation in clusters [EB/OL]. [2015-12-03]. http：//people.eecs.berkeley.edu/～kubitron/courses/cs262a-F12/projects/reports/project13_report_ver2.pdf.

[12]FRIEDMAN E， GHODSI A， PSOMAS C-A. Strategyproof allocation of discrete jobs on multiple machines [C]// EC14： Proceedings of the fifteenth ACM Conference on Economics and Computation. New York： ACM， 2014： 529-546.

[13]王金海，黃傳河，王晶，等.異構(gòu)云計(jì)算體系結(jié)構(gòu)及其多資源聯(lián)合公平分配策略[J].計(jì)算機(jī)研究與發(fā)展，2015，52（6）：1288-1302. （WANG J H， HUANG C H， WANG J， et al. A heterogeneous cloud computing architecture and multi-resource-joint fairness allocation strategy [J]. Journal of Computer Research and Development， 2015， 52（6）： 1288-1302.）

[14]陳海燕.基于多群智能算法的云計(jì)算任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)科學(xué)，2014，41（S1）：83-86. （CHEN H Y. Task scheduling in cloud computing based on swarm intelligence algorithm[J]. Computer Science， 2014， 41（S1）： 83-86）

[15]王會(huì)穎， 倪志偉， 伍章俊. 基于MapReduce和多目標(biāo)蟻群算法的多租戶服務(wù)定制算法[J]. 模式識(shí)別與人工智能，2014，27（12）：1105-1116. （WANG H Y， NI Z W， WU Z J. Multi-tenant service customization algorithm based on MapReduce and multi-objective ant colony optimization[J]. Pattern Recognition and Artificial Intelligence， 2014， 27（12）： 1105-1116.）

[16]楊靖， 張宏軍，趙水寧，等.基于粒子群優(yōu)化算法的虛擬機(jī)部署策略[J]. 計(jì)算機(jī)應(yīng)用，2016，36（1）：117-121. （YANG J， ZHANG H J， ZHAO S N， et al. Virtual machine deployment strategy based on particle swarm optimization algorithm [J]. Journal of Computer Applications， 2016， 36（1）： 117-121.）

[17]XIONG A， XU C. Energy efficient multiresource allocation of virtual machine based on PSO in cloud data center [J]. Mathematical Problems in Engineering， 2014（6）：1-8.

[18]STADNYK I. Schema recombination in pattern recognition problems [C]// Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. Hillsdale， NJ： L. Erlbaum Associates Inc.， 1987： 27-35.

[19]LAMPINEN J， ZELINKA I. On stagnation of the differential evolution algorithm [C]// MENDEL 2000： Proceedings of the 6th International Conference on Soft Computing. Brno， Czech Republic： PC-DIR， 2000： 76-85.

https：//www.researchgate.net/publication/2645446_On_Stagnation_Of_The_Differential_Evolution_Algorithm

[20]WILKES J， REISSEISS C. Google cluster data 2011_2 [EB/OL]. [2015-06-15]. https：//code.google.com/p/googleclusterdata/.