王旖旎 李 明

1(重慶商務(wù)職業(yè)學(xué)院 重慶 401331)2(重慶大學(xué)計(jì)算機(jī)學(xué)院 重慶 400044)

0 引 言

云環(huán)境中的工作流調(diào)度廣泛應(yīng)用于科學(xué)研究與商業(yè)領(lǐng)域，如天文學(xué)、天氣預(yù)測(cè)、醫(yī)療和生物信息學(xué)等。工作流規(guī)模較大，包括大量獨(dú)立和依賴型任務(wù)，需要規(guī)模較大的計(jì)算、通信和存儲(chǔ)環(huán)境實(shí)現(xiàn)其調(diào)度與執(zhí)行。工作流調(diào)度的實(shí)質(zhì)是具有偏序關(guān)系的任務(wù)至云資源間的映射問題，通常以滿足用戶定義的相關(guān)QoS約束為目標(biāo)完成工作流任務(wù)的執(zhí)行[1]。傳統(tǒng)的網(wǎng)格工作流調(diào)度問題更加注重調(diào)度效率，即優(yōu)化調(diào)度時(shí)間，沒有考慮資源使用帶來的調(diào)度代價(jià)[2]。云計(jì)算環(huán)境中，資源的處理能力和處理租用價(jià)格不一，資源能力越高，價(jià)格也越高。此時(shí)，具體應(yīng)用的調(diào)度策略所帶來的調(diào)度時(shí)間和調(diào)度代價(jià)也不相同。因此，同步考慮工作流執(zhí)行的時(shí)間和代價(jià)，這將更加符合云環(huán)境下工作流調(diào)度的場(chǎng)景。

然而，現(xiàn)實(shí)的情況是，優(yōu)化工作流的調(diào)度時(shí)間和調(diào)度代價(jià)本身是兩個(gè)相互沖突的目標(biāo)。若要降低調(diào)度時(shí)間，則工作流任務(wù)將偏好在性能更高的資源上執(zhí)行，而資源性能越高，其利用代價(jià)也將越高；反之，若要降低調(diào)度代價(jià)，則工作流任務(wù)將偏好在價(jià)格更低的資源上執(zhí)行，而資源價(jià)格越低，其性能也將越低，此時(shí)調(diào)度時(shí)間也將延長(zhǎng)。為了解決這一問題，提出一種基于引力搜索算法的工作流調(diào)度算法，利用引力搜索的進(jìn)化機(jī)制，通過代理適應(yīng)度的評(píng)估，得到最終在調(diào)度時(shí)間和調(diào)度代價(jià)上綜合性能最優(yōu)化的任務(wù)映射方案。

1 相關(guān)研究

為了解決工作流調(diào)度問題，啟發(fā)式調(diào)度算法是常規(guī)方法。文獻(xiàn)[3]提出LOSS和GAIN兩種算法分別用來優(yōu)化預(yù)算約束下的時(shí)間和代價(jià)，但僅涉及單目標(biāo)優(yōu)化。文獻(xiàn)[4]討論了IaaS云環(huán)境中的代價(jià)和截止時(shí)間約束工作流調(diào)度，但所考慮的資源僅為同質(zhì)資源模型。文獻(xiàn)[5]提出兩種云工作流調(diào)度算法：一階段算法IC-PCP和兩階段算法IC-PCPD2。兩種算法可以在多項(xiàng)式時(shí)間內(nèi)得到載止時(shí)間約束下的代價(jià)最小調(diào)度方案。文獻(xiàn)[6]提出了在混合云中截止時(shí)間約束的代價(jià)最小化調(diào)度算法HEFT，利用子截止時(shí)間的概念進(jìn)行資源的重調(diào)度，并實(shí)現(xiàn)了代價(jià)最小化。文獻(xiàn)[7]則實(shí)現(xiàn)了包任務(wù)在截止時(shí)間約束下的代價(jià)最小化調(diào)度，但僅適用于獨(dú)立任務(wù)調(diào)度。文獻(xiàn)[8]利用粒子群搜索方法求解了用戶截止時(shí)間約束下費(fèi)用最小化的工作流調(diào)度方案。文獻(xiàn)[9-11]提出了一種截止時(shí)間與預(yù)算約束時(shí)工作流調(diào)度遺傳算法，但也僅是實(shí)現(xiàn)執(zhí)行代價(jià)或執(zhí)行時(shí)間的單一優(yōu)化?？梢钥闯?，以上啟發(fā)式或元啟式算法多數(shù)僅進(jìn)行了壟斷和單一目標(biāo)優(yōu)化。針對(duì)以上問題，本文將從優(yōu)化調(diào)度長(zhǎng)度和調(diào)度代價(jià)兩個(gè)方面入手，提出新的云工作流任務(wù)調(diào)度算法，提升在兩個(gè)指標(biāo)上的綜合性能。

2 問題模型

2.1 工作流模型

工作流應(yīng)用可表示為有向無循環(huán)圖DAG，G=(T,E)，如圖1所示，其中：T={t1,t2,…,tn}表示任務(wù)集合；E表示有向邊集合；一條邊ti→tj表明前驅(qū)ti與后繼tj間的執(zhí)行次序約束。因此，任務(wù)tj在ti完成前無法開始執(zhí)行。每個(gè)任務(wù)ti擁有以MI表示的計(jì)算負(fù)載屬性。而每條邊ti→tj擁有的屬性為任務(wù)ti生成的輸出數(shù)據(jù)量，該數(shù)據(jù)即執(zhí)行tj需要的數(shù)據(jù)。若任務(wù)不存前驅(qū)，則可視為入口任務(wù)tentry；若任務(wù)不存在后繼，則可視為出口任務(wù)texit。若工作流擁有多個(gè)入口任務(wù)，可添加零計(jì)算負(fù)載無數(shù)據(jù)輸出的傀儡任務(wù)至工作流結(jié)構(gòu)中。擁有多個(gè)出口任務(wù)的工作流也可作類似操作，不影響計(jì)算工作流調(diào)度時(shí)間和代價(jià)。

注：節(jié)點(diǎn)代表任務(wù)，有向邊代表順序關(guān)系，節(jié)點(diǎn)t1中任務(wù)標(biāo)識(shí)下的數(shù)字13代表任務(wù)的計(jì)算負(fù)載量，有向邊上的數(shù)字代表有向邊對(duì)應(yīng)的出發(fā)任務(wù)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)量

圖1 工作流示例

2.2 云服務(wù)模型

假設(shè)云服務(wù)包含m個(gè)虛擬機(jī)，表示為V={v1,v2,…,vm}。每個(gè)虛擬機(jī)擁有自身的計(jì)算能力，以MIPS衡量。所有虛擬機(jī)之間是全連通結(jié)構(gòu)，可寄宿于一個(gè)或多個(gè)物理云服務(wù)器上。傳輸任務(wù)ti至tj的輸出數(shù)據(jù)的時(shí)間可考慮為通信開銷時(shí)間。若任務(wù)ti與tj執(zhí)行于同一虛擬機(jī)上，則通信開銷為零。

3 問題定義

3.1 相關(guān)參數(shù)定義

文中相關(guān)參數(shù)含義說明如下：

N：種群大?。?/p>

n：工作流中任務(wù)數(shù)量；

ti：任務(wù)i；

m：可用虛擬機(jī)量；

vj：虛擬機(jī)j；

Xi：代理i；

Xbest：至目前為止的最優(yōu)代理；

α：計(jì)算適應(yīng)度時(shí)調(diào)度長(zhǎng)度和調(diào)度代價(jià)的權(quán)重；

fiti：代理i的適應(yīng)度；

Mi：代理i的質(zhì)量；

σ：價(jià)格模型中的隨機(jī)變量；

Vcbase：最慢虛擬機(jī)的基準(zhǔn)價(jià)格；

digvj：虛擬機(jī)vj的性能下降；

γ：控制引力常量偏差的常量；

δ：質(zhì)量門限值。

相關(guān)約束和假設(shè)如下：

1) 考慮虛擬機(jī)的性能變化來計(jì)算執(zhí)行任務(wù)時(shí)的有效CPU周期，對(duì)于虛擬機(jī)vj，性能變化表示為degvj，利用degvj，任務(wù)ti在虛擬機(jī)vj上的執(zhí)行時(shí)間可重寫為：

(1)

式中：Load(ti)表示任務(wù)ti的計(jì)算負(fù)載；Capacity(vj)表示虛擬機(jī)vj的計(jì)算能力。

2) 計(jì)算執(zhí)行代價(jià)時(shí)考慮單位支付時(shí)間τ。若租用虛擬機(jī)的時(shí)間小于τ，則按照全部時(shí)間單位τ支付費(fèi)用。

3) 利用虛擬機(jī)時(shí)需要考慮虛擬機(jī)的初始啟動(dòng)時(shí)間，即在計(jì)算調(diào)度長(zhǎng)度時(shí)需要加入虛擬機(jī)啟動(dòng)時(shí)間，同時(shí)將虛擬機(jī)的關(guān)機(jī)時(shí)間也考慮至調(diào)度長(zhǎng)度中。

4) 虛擬機(jī)之間以相同帶寬進(jìn)行全連通。

3.2 優(yōu)化問題描述

1) 調(diào)度長(zhǎng)度Makesapn計(jì)算。調(diào)度長(zhǎng)度即為整個(gè)工作流的總體執(zhí)行時(shí)間，包括租用虛擬機(jī)的啟動(dòng)時(shí)間、執(zhí)行時(shí)間、虛擬機(jī)間的數(shù)據(jù)傳輸時(shí)間和虛擬機(jī)的關(guān)機(jī)時(shí)間。假設(shè)數(shù)據(jù)正在傳輸過程中虛擬機(jī)無法執(zhí)行任務(wù)，則調(diào)度長(zhǎng)度等于虛擬機(jī)啟動(dòng)時(shí)間、所有虛擬機(jī)中虛擬機(jī)時(shí)間VM-time的最大值及虛擬機(jī)關(guān)機(jī)時(shí)間之和。VM-time[i]表示最后一個(gè)時(shí)間戳至虛擬機(jī)vi執(zhí)行其指定任務(wù)的時(shí)間間隔。啟動(dòng)時(shí)間和關(guān)機(jī)時(shí)間僅需計(jì)算一次的原因在于虛擬機(jī)僅需在首次啟動(dòng)并在最后一次關(guān)機(jī)。因此，調(diào)度長(zhǎng)度為：

VM-shutdown-time

(2)

2) 調(diào)度代價(jià)cost計(jì)算。調(diào)度模型中，云服務(wù)器由擁有針對(duì)不同負(fù)載類型的不同計(jì)算能力的虛擬機(jī)組成，式(1)表示任務(wù)ti在虛擬機(jī)vj上的執(zhí)行時(shí)間，令τ表示任務(wù)的單位支付時(shí)間，Vcbase表示最慢虛擬機(jī)的基準(zhǔn)價(jià)格，cost(ti,vj)定義為任務(wù)ti在虛擬機(jī)vj上的執(zhí)行代價(jià)：

(3)

式中：σ表示隨機(jī)變量，以產(chǎn)生不同的虛擬機(jī)價(jià)格組合和能力,CCvj表示虛擬機(jī)vj的CPU周期數(shù)，CCslowest表示虛擬機(jī)中最慢CPU周期數(shù)。令Bi,j表示布爾變量，定義為：

(4)

因此，工作流的調(diào)度代價(jià)為：

(5)

3) 最優(yōu)化問題。云工作流的調(diào)度目標(biāo)即是最小化調(diào)度長(zhǎng)度和調(diào)度代價(jià)，可表示為最小化兩個(gè)目標(biāo)的線性組合，將其形式化為：

Minz=α×Makespan+(1-α)×Costtotal

(6)

(2) 0≤α≤1

其中：約束條件(1)表明工作流中的任一任務(wù)僅能分配至一個(gè)虛擬機(jī)上；約束條件(2)表明權(quán)重因子，表示算法對(duì)于調(diào)度長(zhǎng)度和調(diào)度代價(jià)優(yōu)化的偏好。

4 算法設(shè)計(jì)

本文設(shè)計(jì)的算法稱為混合引力搜索算法，簡(jiǎn)稱HGSA。

4.1 初始種群生成方式

以HEFT算法[13]的輸出結(jié)果作為初始種群的生成方式，即以最小化最早完成時(shí)間為目標(biāo)進(jìn)行任務(wù)調(diào)度，具體包括兩個(gè)步驟：

步驟1計(jì)算任務(wù)優(yōu)先級(jí)。該階段中，每個(gè)任務(wù)的優(yōu)先級(jí)利用平均執(zhí)行時(shí)間和平均通信時(shí)間計(jì)算。優(yōu)先級(jí)定義為升秩值表達(dá)。根據(jù)由高到低的優(yōu)先級(jí)排序得到任務(wù)調(diào)度次序，從而滿足給定工作流的任務(wù)執(zhí)行順序約束。任務(wù)ti的優(yōu)先級(jí)定義為：

(7)

式中：wi,avg表示任務(wù)ti的平均執(zhí)行時(shí)間；ci,j,avg表示任務(wù)ti與tj間的平均通信時(shí)間。

步驟2任務(wù)與虛擬機(jī)間的映射。通過在所有可用虛擬機(jī)上計(jì)算任務(wù)最早開始時(shí)間EST和最早完成時(shí)間EFT，根據(jù)任務(wù)的優(yōu)先級(jí)，得到任務(wù)的調(diào)度結(jié)果。

4.2 代理表示

算法中，工作流中任務(wù)與虛擬機(jī)間的映射可視為一個(gè)代理agent。對(duì)于擁有n個(gè)任務(wù)的工作流和m個(gè)虛擬機(jī)的云服務(wù)器的調(diào)度環(huán)境，代理i可表示為維度為1×n的矢量，即：

(8)

表1 代理示例

4.3 適應(yīng)度評(píng)估

(9)

4.4 調(diào)度方法

HGSA算法包括兩個(gè)階段。第一階段僅集中于調(diào)度長(zhǎng)度的優(yōu)化，第二階段優(yōu)化調(diào)度代價(jià)，同時(shí)最小化適應(yīng)度值，適應(yīng)度則同步考慮了調(diào)度長(zhǎng)度和調(diào)度代價(jià)。第一階段產(chǎn)生的結(jié)果可指導(dǎo)引力搜索算法GSA中粒子的運(yùn)動(dòng)，可以改進(jìn)傳統(tǒng)GSA的隨機(jī)初始化粒子運(yùn)行機(jī)制。算法具體步驟為：

步驟1以HEFT算法的輸出結(jié)果作為種子得到初始種群，以更少的迭代次數(shù)產(chǎn)生更優(yōu)的解。

步驟2根據(jù)適應(yīng)度函數(shù)保留當(dāng)前代中的最優(yōu)粒子，確保最優(yōu)代理在未來代中不被剔除。

步驟3質(zhì)量小于門限值δ的代理從當(dāng)前種群中剔除，由于該類代理在種群更新中貢獻(xiàn)較少。剔除以上代理后，添加以最優(yōu)代理為基礎(chǔ)的新的代理至種群中，改進(jìn)種群全局適應(yīng)度。

4.5 粒子位置更新

考慮系統(tǒng)包含N個(gè)代理，代理i的位置定義為：

(10)

(11)

式中：ε表示極小常量；Ri,j(k)表示第k次迭代時(shí)代理i與代理j間的歐氏距離，定義為：

(12)

若代理i在維度d上的總引力為其他代理在維度d上產(chǎn)生的引力的隨機(jī)權(quán)重和，則：

(13)

式中：randj表示[0,1]間的隨機(jī)數(shù)。可知，代理i在第k次迭代時(shí)在維度d上的加速度為：

(14)

由此可知，代理的位置和速率更新可計(jì)算為：

(15)

(16)

G(k)為引力常量G0和迭代次數(shù)k的函數(shù)，定義為：

(17)

式中：γ表示較小常量，用于控制引力常量的降低；G0在算法開始時(shí)初始化，并隨著算法的執(zhí)行而降低，以改進(jìn)搜索準(zhǔn)確性。

4.6 算法具體步驟

算法1是HGSA的具體執(zhí)行過程。步驟1為將任務(wù)在虛擬機(jī)間進(jìn)行隨機(jī)映射以產(chǎn)生初始種群，步驟2為將HEFT算法輸出的結(jié)果播種至種群中。初始種群準(zhǔn)備就緒后，種群中的代理需要迭代若干次數(shù)以產(chǎn)生最終結(jié)果，即步驟3-步驟16。迭代的第一步是計(jì)算引力常量，即步驟4。然后在步驟5中，根據(jù)式(9)計(jì)算每個(gè)代理的適應(yīng)度。根據(jù)適應(yīng)度值，步驟6為識(shí)別種群中的最優(yōu)代理和最差代理，步驟7為計(jì)算所有代理的質(zhì)量。步驟8為通過計(jì)算純引力、純加速度和速率，以更新每個(gè)代理的位置。剩余步驟中，算法用新的代理取代劣勢(shì)代理。新代理的生成方式為將任務(wù)映射至隨機(jī)選取的虛擬機(jī)上，剩余映射方案則仍然維持不變。

算法1HGSA算法過程

輸入：工作流應(yīng)用W，云服務(wù)資源CSS

輸出：任務(wù)映射結(jié)果M

1. 初始化擁有N個(gè)隨機(jī)代理的種群X

2. 利用HEFT生成的解代替種群中的一個(gè)代理

3. fork=1 toMAX_ITERATIONdo

4. 利用式(19)計(jì)算G(k)

5. 利用式(10)計(jì)算適應(yīng)度值fiti

6. 基于計(jì)算的適應(yīng)度值識(shí)別最優(yōu)和最差代理

7. 利用式(11)計(jì)算代理質(zhì)量Mi

8. 利用式(13)-式(18)計(jì)算每個(gè)代理的速率與位置

9. fori=1 toNdo

10. ifMi<δthen

11. 賦值Pos為區(qū)間[1,n]間的隨機(jī)整數(shù)值

13. 賦值xposi為區(qū)間[1,m]間的隨機(jī)整數(shù)值

14. end if

15. end for

16. end for

17. 基于適應(yīng)度fiti尋找M個(gè)對(duì)應(yīng)的最優(yōu)代理

18. returnM

HGSA算法根據(jù)原始引力搜索算法的空間搜索步驟進(jìn)行最優(yōu)解搜索，因此其時(shí)間復(fù)雜度與GSA算法相同，同為O(N)，N為初始化的粒子數(shù)量。

5 算例分析

考慮一個(gè)Montage工作流進(jìn)行算法算例分析，工作流包括16個(gè)任務(wù)，T={t1,t2,…,t16}，云環(huán)境包括4個(gè)虛擬機(jī)，V={v1,v2,v3,v4}，工作流的結(jié)構(gòu)和虛擬機(jī)結(jié)構(gòu)如圖2和圖3所示。4個(gè)虛擬機(jī)為全連通結(jié)構(gòu)，算法分析的目標(biāo)是以優(yōu)化調(diào)度長(zhǎng)度和調(diào)度代價(jià)為目標(biāo)，將任務(wù)調(diào)度至虛擬機(jī)上執(zhí)行。表2給出算例中的相關(guān)參數(shù)，表3給出算法步驟1描述的生成初始種群結(jié)構(gòu)。

圖2 算例應(yīng)用的工作流結(jié)構(gòu)

圖3 云資源環(huán)境

參數(shù)取值虛擬機(jī)數(shù)量4虛擬機(jī)計(jì)算能力2.0,3.5,4.5,5.5MIPS網(wǎng)絡(luò)帶寬1Mbit/s虛擬機(jī)啟動(dòng)時(shí)間和關(guān)機(jī)時(shí)間0.5s虛擬機(jī)性能變化24%最大迭代次數(shù)10種群大小N100引力常量G05權(quán)重系數(shù)α0.5較小常量γ0.3劣勢(shì)代理的質(zhì)量門限值δ0.1極小常量ε10

表3 代理初始種群

利用式(8)計(jì)算任務(wù)優(yōu)先級(jí)，根據(jù)優(yōu)先級(jí)的降序排列，任務(wù)被依次映射至一個(gè)虛擬機(jī)上，使得任務(wù)的最早完成時(shí)間達(dá)到最小化。表4為算法得到的任務(wù)優(yōu)先級(jí)與相應(yīng)任務(wù)映射情況。同時(shí)可以計(jì)算出HEFT算法得到的調(diào)度長(zhǎng)度和調(diào)度代價(jià)分別為36.57 s和＄50.31。

表4 任務(wù)優(yōu)先級(jí)及映射

續(xù)表4

圖4顯示了HEFT生成的映射方案加至初始種群以取代劣勢(shì)代理的示例，即算法步驟2。

圖4 HEFT解加至種群

至此，當(dāng)前種群包含HEFT生成的代理和隨機(jī)生成的代理，種群按照算法中步驟3-步驟16的迭代步驟進(jìn)行進(jìn)化。表5給出了每次迭代中最優(yōu)代理的相關(guān)值情況，表6則是相應(yīng)的調(diào)度結(jié)果，此時(shí)的調(diào)度長(zhǎng)度為32.64 s，調(diào)度代價(jià)為＄47.71。

表5 最優(yōu)代理結(jié)果

表6 調(diào)度結(jié)果

6 仿真實(shí)驗(yàn)

6.1 實(shí)驗(yàn)配置與性能指標(biāo)

本節(jié)利用CloudSim平臺(tái)下的仿真實(shí)驗(yàn)的方法對(duì)工作流調(diào)度算法進(jìn)行性能分析，測(cè)試算法包括標(biāo)準(zhǔn)GSA算法[14]、HEFT算法[13]和HGA算法[15]。除種群模式設(shè)置為500，最大迭代次數(shù)設(shè)置為200之外，其他參數(shù)與表2相同。

通過標(biāo)準(zhǔn)化方法對(duì)調(diào)度長(zhǎng)度和調(diào)度代價(jià)作出處理，以調(diào)度長(zhǎng)度比率SLR和調(diào)度代價(jià)比率MCR作為性能評(píng)估指標(biāo)，分別定義為：

選取四種不同科學(xué)領(lǐng)域的工作流結(jié)構(gòu)作為數(shù)據(jù)測(cè)試源，包括：Epigenomic工作流(同時(shí)擁有計(jì)算密集型和網(wǎng)絡(luò)密集型任務(wù))、Montage工作流(網(wǎng)絡(luò)密集型任務(wù))、CyberShake工作流(同時(shí)擁有I/O密集型和網(wǎng)絡(luò)密集型任務(wù))以及Inspiral工作流(計(jì)算密集型任務(wù))。工作流的具體結(jié)構(gòu)可參見文獻(xiàn)[12]。

6.2 實(shí)驗(yàn)結(jié)果

圖5為四種工作流在不同任務(wù)規(guī)模下得到的SLR和MCR指標(biāo)情況?？梢钥吹?，在所有工作流類型中，HGSA算法的MCR指標(biāo)是優(yōu)于HEFT、HGA和GSA算法的，這說明初始種群的優(yōu)化配置和引力搜索機(jī)制可以得到代價(jià)更低的工作流調(diào)度解。比較標(biāo)準(zhǔn)的引力搜索GSA算法，該算法未優(yōu)化初始種群；而比較混合遺傳算法HGA，該算法則在種群位置更新上不如本文算法效率高。HEFT算法在進(jìn)行工作流調(diào)度時(shí)，僅考慮了任務(wù)的執(zhí)行時(shí)間優(yōu)化，因此其代價(jià)性能是最差的。此外，在SLR指標(biāo)上，HEFT是所有算法中性能最好的，因?yàn)樵撍惴ㄊ且哉{(diào)度長(zhǎng)度為單目標(biāo)進(jìn)行的工作流算法。HGSA在SLR指標(biāo)上優(yōu)于HGA和GSA算法，雖然同為雙目標(biāo)優(yōu)化算法，但本文在引力搜索機(jī)制上的改進(jìn)，以及初始種群融入HEFT調(diào)度方案的優(yōu)化方法，使得本文算法在搜索最優(yōu)解時(shí)效率更高，在調(diào)度代價(jià)最優(yōu)的同時(shí)僅僅犧牲了極小的調(diào)度長(zhǎng)度性能，其綜合性能是四種算法中最優(yōu)的。而在四種不同類型工作流結(jié)構(gòu)中得到的結(jié)果并沒有體現(xiàn)很大差異，這說明本文算法在適應(yīng)性上也是較優(yōu)的。

(a) Epigenomic工作流

(b) Montage工作流

(c) CyberShake工作流

(d) Inspiral工作流圖5 算法執(zhí)行結(jié)果

7 結(jié) 語

為了同步優(yōu)化云環(huán)境中工作流調(diào)度的長(zhǎng)度和代價(jià)，提出了一種基于引力搜索算法的工作流任務(wù)調(diào)度算法。首先以異構(gòu)最早完成時(shí)間機(jī)制生成引力搜索的部分初始代理，并結(jié)合隨機(jī)生成方式，得到初始種群。然后，利用引力搜索的進(jìn)化機(jī)制，通過代理適應(yīng)度的評(píng)估，得到最終在調(diào)度時(shí)間和調(diào)度代價(jià)上綜合性能最優(yōu)的任務(wù)映射方案。利用一個(gè)算例對(duì)算法的有效性進(jìn)行了論證與評(píng)估，結(jié)果表明，本文算法不僅可以得到最小的調(diào)度時(shí)間，調(diào)度代價(jià)也是對(duì)比算法中最小的。