一種基于任務(wù)執(zhí)行時間的啟發(fā)式獨立任務(wù)調(diào)度算法

喬保軍,張稼祥,左憲禹

(河南大學(xué) 河南省大數(shù)據(jù)分析與處理重點實驗室;計算機(jī)與信息工程學(xué)院,河南 開封 475004)

隨著技術(shù)的發(fā)展，互聯(lián)網(wǎng)中的數(shù)據(jù)激增，大量的數(shù)據(jù)將人們帶入了大數(shù)據(jù)時代[1].大數(shù)據(jù)時代的數(shù)據(jù)不僅數(shù)據(jù)量大，而且流動性強(qiáng).為了獲取數(shù)據(jù)中的價值所在，早期的單機(jī)計算已無法有效地進(jìn)行處理.目前為了處理大量的數(shù)據(jù)獲取其內(nèi)在的價值，無論是在研究領(lǐng)域還是商業(yè)領(lǐng)域，云計算、網(wǎng)格計算等分布式技術(shù)已經(jīng)成為人們的重點研究對象.通過這些分布式技術(shù)可以將大量的計算任務(wù)分配至多個資源上面同時計算，從而快速獲取所需的結(jié)果.保證數(shù)據(jù)的時效性，提高人們對數(shù)據(jù)的利用率.在分布式計算中，任務(wù)調(diào)度問題始終是一個重難點問題.任務(wù)調(diào)度通常指的是在分布式、云計算環(huán)境中，根據(jù)用戶的需求，合理地將N個任務(wù)分配至M個資源，實現(xiàn)整個計算系統(tǒng)的負(fù)載均衡,提高整體的資源利用率.從而提高任務(wù)的處理速度.在以往的研究中已經(jīng)證明任務(wù)調(diào)度是一個NP難問題[2].通常任務(wù)調(diào)度的目標(biāo)是提高系統(tǒng)資源的使用率，縮短任務(wù)完成時間.在目前大多數(shù)的研究中，都是對整體的任務(wù)完成時間進(jìn)行優(yōu)化，而對算法時間復(fù)雜度的研究偏少.本文提出一個基于任務(wù)執(zhí)行時間的啟發(fā)式獨立任務(wù)調(diào)度算法，降低算法時間復(fù)雜度的同時，優(yōu)化整體任務(wù)完成時間.

1 相關(guān)研究工作

任務(wù)調(diào)度作為分布式計算中一直存在的一個研究熱點，目前已有大量的學(xué)者、專家對其做了大量的工作[3].根據(jù)任務(wù)之間依賴性，可以將任務(wù)調(diào)度分為獨立任務(wù)調(diào)度與工作流調(diào)度[4-5].本文主要針對獨立任務(wù)調(diào)度進(jìn)行研究.有關(guān)任務(wù)調(diào)度的算法可以分為3類算法：啟發(fā)式算法、元啟發(fā)式算法[6-10]與混合式算法[11-13].相較于元啟發(fā)式算法與混合式算法，啟發(fā)式算法具有實現(xiàn)簡單、冪等性、算法執(zhí)行較快等優(yōu)點.故本文提出一種新的啟發(fā)式算法.

在啟發(fā)式算法中，比較著名的兩個算法是MIN-MIN算法[14]與MAX-MIN算法[15].在MIN-MIN算法中，第一步需要找到每一個任務(wù)的最小完成時間，然后再在這些具有最小完成時間的任務(wù)中找到具有最小最小完成時間的任務(wù)，將其分配至對應(yīng)資源中.循環(huán)上述過程，直至所有的任務(wù)分配完成.在MIN-MIN算法的每次分配任務(wù)中，所有的資源的可用時間是一樣的，任務(wù)越小，則完成時間越小.故MIN-MIN算法優(yōu)先調(diào)度小任務(wù).MAX-MIN算法與MIN-MIN算法極其相似，不同之處在于，MAX-MIN算法是從具有最小完成時間的任務(wù)中找到具有最大最小完成時間的任務(wù)，并將其分配至相應(yīng)的資源.上述MIN-MIN算法優(yōu)先小任務(wù)調(diào)度，MAX-MIN算法優(yōu)先大任務(wù)調(diào)度.這就導(dǎo)致針對不同的任務(wù)類型，上述算法可能出現(xiàn)調(diào)度效果不理想的情況.為了解決上述問題，文獻(xiàn)[16]提出了MIN-MAX算法.MIN-MAX算法類似MIN-MIN算法與MAX-MIN算法的結(jié)合體.在MIN-MAX算法中，第一步與上述兩種算法相同.在第二步中，結(jié)合這兩種算法，分別找到最小最小完成時間與最大最小完成時間.將兩個任務(wù)進(jìn)行捆綁分配.Sufferage算法[17]是對MIN-MIN算法的改進(jìn).在Sufferage算法中，不僅需要計算出每個任務(wù)的最小完成時間，還需計算出每個任務(wù)的次小完成時間，然后計算每個任務(wù)最小與次小完成時間的差值.選擇具有差值最大的任務(wù)，將此任務(wù)分配到使其具有最小完成時間的資源上.ETSA算法[18]屬于對Sufferage算法的進(jìn)一步改進(jìn).不同之處在于，ETSA算法中，還需計算最小執(zhí)行時間與第二小執(zhí)行時間的差值.然后對完成時間的差值進(jìn)行排序，根據(jù)完成時間的順序相應(yīng)對執(zhí)行時間差值進(jìn)行排序.如果完成時間的差值大于執(zhí)行時間的差值則將任務(wù)進(jìn)行分配.文獻(xiàn)[19]提出了二階段的MIN-MIN算法，此算法主要根據(jù)MIN-MIN算法的調(diào)度結(jié)果，進(jìn)行二次分配，轉(zhuǎn)移負(fù)載較高的資源中的任務(wù)至負(fù)載較低的資源，以此來達(dá)到負(fù)載均衡的目的.

上述算法在針對各自的問題上都取得了良好的效果,然而未能很好地平衡算法時間復(fù)雜度與調(diào)度結(jié)果，同時在面對某些類型的任務(wù)時調(diào)度效果不理想.本文提出的一種基于任務(wù)執(zhí)行時間的啟發(fā)式獨立任務(wù)調(diào)度算法可以較好地平衡時間復(fù)雜度與調(diào)度結(jié)果，同時兼顧各種類型任務(wù)調(diào)度.

2 任務(wù)調(diào)度算法模型

在介紹本文算法之前首先對相關(guān)符號、概念進(jìn)行說明.

ETC(n*m)：任務(wù)執(zhí)行時間矩陣，二維矩陣，n個任務(wù)m個資源，每個任務(wù)在每個資源上面的執(zhí)行時間矩陣，在任務(wù)調(diào)度前已知.

ETC1：ETC矩陣分解的第一個矩陣，此矩陣行列有序，由ETC中的部分行組成.ETC1[i,j]表示任務(wù)i在資源j上面的完成時間.

ETC2：ETC矩陣分解的第二個矩陣，此矩陣中的元素?zé)o固定規(guī)律，由ETC矩陣中的部分行組成.ETC2[i,j]表示任務(wù)i在資源j上面的執(zhí)行時間.

CON：主要用于記錄某個任務(wù)對應(yīng)的行是否有序.CON[i]=true表示任務(wù)i在ETC矩陣中對應(yīng)的行為有序.

CON_NUM：ETC1矩陣中包含的任務(wù)數(shù).

TR：任務(wù)分配矩陣，二維矩陣.如果TR[i,j]=true，表明任務(wù)i分配至資源j上面.

CT：資源可用時間矩陣，表示當(dāng)前資源在分配下一個任務(wù)時，需多長時間可執(zhí)行到要分配的任務(wù).為了簡化模型，在本文中，每個資源的可用時間簡化為分配在資源上面的任務(wù)的執(zhí)行時間之和.CT[i]代表資源i的資源可用時間.

Rfrom,Rto：泛指需要進(jìn)行任務(wù)調(diào)整的兩個資源，擬將Rfrom中的任務(wù)調(diào)整至Rto中.

MAKESPAN:表示通過算法調(diào)度之后完成所有任務(wù)的時間,為所有資源完成時間的最大值.

Ti：表示任務(wù)i.

Rj：表示資源j.

任務(wù)完成時間：某個任務(wù)的完成時間為某個資源的可用時間與此任務(wù)的執(zhí)行時間之和.某個資源的任務(wù)完成時間為分配至該資源所有的任務(wù)執(zhí)行時間之和.

本文提出的獨立任務(wù)調(diào)度算法主要由4個階段組成.分別為預(yù)處理階段、分解階段、預(yù)調(diào)度階段、調(diào)整階段.算法的輸入即為ETC矩陣，輸出的結(jié)果為每個資源上面的任務(wù)完成時間矩陣以及任務(wù)分配矩陣.為了便于理解，本文將整個算法按照上述4個階段分別進(jìn)行介紹.第一個階段的輸入為整個算法的輸入為ETC矩陣，接下來的每個階段的輸入分別為上一個階段的輸出.接下來分別介紹上述4個階段.

2.1 預(yù)處理階段

在預(yù)處理階段，主要是對原始的ETC進(jìn)行調(diào)整.調(diào)整的目的在于給下一階段矩陣分解做準(zhǔn)備.給定一個ETC矩陣，ETC矩陣中的每一行代表一個任務(wù)在每個資源上面的執(zhí)行時間.每一列代表所有任務(wù)在某一個資源上面的執(zhí)行時間.針對ETC矩陣中的第一行元素，從小到大對第一行元素進(jìn)行排序處理，整個ETC矩陣的每一行排列的順序與第一行元素的順序相同.即根據(jù)ETC矩陣的首行元素的大小，從小到大對每一行進(jìn)行排序處理.之后，根據(jù)首列元素的大小再次進(jìn)行ETC矩陣的重組.經(jīng)過兩次重組后的矩陣即為分解階段的輸入，進(jìn)行算法的下一步處理.預(yù)處理階段偽代碼如算法1所示.

算法1 預(yù)處理階段算法

輸入：(ETC,n,m)

輸出：(ETC)/*預(yù)處理后的ETC*/

1.fori←1 tondo

2. forj←1 ton-i-1 do

3. ifETC[0,j]>ETC[0,j+1]

4. swap(j,j+1)/*交換ETC矩陣兩列*/

5.fori←1 tomdo

6. forj←1 tom-i-1 do

7. ifETC[j,0]>ETC[j+1,0]

8. swap(j,j+1)/*交換ETC矩陣兩行*/

2.2 分解階段

在分解階段主要的功能是將經(jīng)過預(yù)處理階段的ETC矩陣分解為ETC1和ETC2兩個矩陣.在預(yù)調(diào)度階段會對分解后的矩陣采取不同的調(diào)度策略.ETC1矩陣中，任意一行、一列都滿足從小到大的排列順序，即整個矩陣行列有序.而ETC2矩陣則沒有限制.在分解階段首先是將ETC矩陣中滿足從小到大順序的行標(biāo)記出來，若此行有序則CON[i]=true，若無序則CON[i]=false.標(biāo)記完成后，遍歷整個CON矩陣，找到第一個標(biāo)記為true的行.然后從標(biāo)記的第二行開始與標(biāo)記的第一行進(jìn)行比較，如果在所有資源上，第二行的執(zhí)行時間都大于第一行，接下來的比較行，則會變成標(biāo)記的第三行與第二行進(jìn)行比較，依次類推.如果第二行中有元素小于第一行中的元素，則將CON[i]設(shè)置為false.接下來的比較則會變成標(biāo)記的第三行與第一行進(jìn)行比較.按照上述規(guī)則，直至比較完成.接下來再一次遍歷CON矩陣，如果CON[i]為true，則將任務(wù)Ti對應(yīng)的行添加至ETC1中，否則添加至ETC2中.分解階段偽代碼如算法2所示.

算法2 分解階段算法

輸入：(ETC,n,m)

輸出：(ETC1,ETC2)

1./*判斷ETC的每一行是否有序*/

2.fori←1 tondo

3. ifi行有序

4.CON[i]=true

5.CON_NUM=CON_NUM+1

6. ifCON_NUM==1

7.TASKID=i/*記錄第一個行有序的任務(wù)ID*/

8.fori←1 tondo

9. ifCON[i]

10. if 任務(wù)i在所有的資源上面的執(zhí)行時間都大于TASKID的執(zhí)行時間

11.TASKID=i

12. else if

13.CON_NUM=CON_NUM-1

14.CON[i]=false

15.fori←1 tondo

16. ifCON[i]

17. 將ETC[i]添加至ETC1中

18. else if

19. 將ETC[i]添加至ETC2中

2.3 預(yù)調(diào)度階段

在預(yù)調(diào)度階段，主要的任務(wù)就將按照不同的調(diào)度策略，分別將ETC1,ETC2矩陣進(jìn)行調(diào)度.首先在對ETC1矩陣進(jìn)行調(diào)度的時候，從ETC1最后一行開始，依次進(jìn)行直至整個ETC1矩陣調(diào)度完成.找到最后一行任務(wù)的最早完成時間，然后將此任務(wù)分配至相應(yīng)的具有最小完成時間的資源，更新資源可用時間，更新任務(wù)分配矩陣.根據(jù)更新的資源可用時間矩陣，繼續(xù)計算尋找下一行的最小完成時間，直至ETC1矩陣中的任務(wù)全部分配完成.此時，資源可用時間與任務(wù)分配矩陣已得到更新.其次開始對ETC2進(jìn)行任務(wù)調(diào)度.對ETC2矩陣進(jìn)行調(diào)度時，直接按照每個任務(wù)的最小執(zhí)行時間進(jìn)行調(diào)度.即，遍歷ETC2矩陣中的每一行，然后找到當(dāng)前任務(wù)在所有資源中具有最小執(zhí)行時間的資源，直接將當(dāng)前任務(wù)分配至對應(yīng)的資源，更新資源可用時間矩陣與資源分配矩陣.預(yù)調(diào)度階段偽代碼如算法3所示.

算法3 預(yù)調(diào)度階段算法

輸入：(ETC1,ETC2,CON_NUM,nm)

輸出：(CT,TR)

1./*首先對ETC1矩陣進(jìn)行調(diào)度*/

2.fori←CON_NUM-1 to 1 do

3. forj←1 tomdo

4.Ti在Rj上面具有最小完成時間

5. 更新CT矩陣CT[j]=CT[j]+ETC[i,j]

6. 更新TR矩陣TR[i,j]=true

7./*對ETC2矩陣進(jìn)行調(diào)度*/

8.fori←1 ton-CON_NUMdo

9. forj←1 tomdo

10.Ti在Rj上具有最小執(zhí)行時間

11. 更新CT矩陣CT[j]=CT[j]+ETC[i,j]

12. 更新TR矩陣TR[i,j]=true

2.4 調(diào)整階段

調(diào)整階段主要是根據(jù)預(yù)調(diào)度的結(jié)果對任務(wù)分配重新進(jìn)行調(diào)整.在調(diào)整階段可以分為如下3個階段.

1)首先尋找兩個需要調(diào)整任務(wù)的資源Rfrom與Rto，擬將資源Rfrom上面的任務(wù)重新調(diào)整至Rto中.在尋找這兩個資源Rfrom與Rto時，最開始所找的是具有最大資源完成時間的資源為Rfrom，具有最小資源完成時間的資源為Rto，如果資源Rfrom中的任務(wù)可以分配至資源Rto中，那么下次進(jìn)行尋找兩個資源時依舊是以最大資源完成時間的資源為Rfrom，以最小資源完成時間的資源為Rto.如果Rfrom上面的任務(wù)無法分配至Rto，那么下一次尋找時Rfrom依舊為最大資源完成時間的資源，而Rto則變?yōu)榫哂械诙〉馁Y源完成時間，后續(xù)依次類推.如果在Rfrom為最大完成時間時，遍歷了除Rto之外的所有資源依舊無法分配任務(wù)，再進(jìn)行下一次尋找兩個資源時，則Rfrom變?yōu)榈诙筚Y源完成時間，而Rto依舊從最小資源完成時間開始.只要發(fā)生一次Rfrom上面的任務(wù)可以調(diào)整至Rto，那么尋找這兩個資源時，則Rfrom重新為最大完成時間資源，Rto為最小完成時間資源.

2)找到資源Rfrom中分配的任務(wù)在Rto中具有最小執(zhí)行時間的任務(wù)T.

3)如果將任務(wù)T調(diào)度至Rto中，Rto的資源完成時間小于之前Rfrom中的完成時間，則將任務(wù)T分配至Rto中.更新對應(yīng)資源的任務(wù)完成時間以及任務(wù)分配矩陣.如果無法進(jìn)行重新調(diào)度，則回到1)繼續(xù)尋找Rfrom與Rto.共進(jìn)行n次循環(huán)即可結(jié)束.

調(diào)整階段偽代碼如算法4所示.

算法4 調(diào)整階段算法

輸入：(ETC,TR,CT,n,m)

輸出：(CT,TR)

1.fori←1 tondo

2. forj←1 tomdo

3. 找到需要重新調(diào)度的資源Rfrom,Rto

4. fori←1 tondo

5. 找到資源Rfrom中任務(wù)在Rto中具有最小執(zhí)行時間的任務(wù)Ti

6. if 任務(wù)Ti調(diào)整至資源Rto中,Rto的資源完成時間<資源Rfrom之前的資源完成時間

7. 更新資源可用時間CT

8. 更新任務(wù)分配矩陣TR

3 算法調(diào)度實例

現(xiàn)有3個資源R1，R2，R3，6個任務(wù)T1，T2，T3，T4，T5，T6.每個任務(wù)在每個資源上面的執(zhí)行時間已知.首先開始進(jìn)行第一階段進(jìn)行ETC矩陣的預(yù)處理.ETC矩陣如表1所示.

表1 ETC矩陣

按照ETC矩陣的第一列進(jìn)行排序，排序后的矩陣如表2所示.按照ETC矩陣第一行進(jìn)行排序，排序后的矩陣如表3所示.

表2 按照第一列排序后的ETC矩陣

表3 按照第一行排序后的ETC矩陣

第二階段將ETC矩陣分解為兩個矩陣.由表3可知，T1,T4,T6滿足從小到大排列.T2,T3,T5不滿足.故所對應(yīng)的CON矩陣如表4所示.

表4 CON矩陣

遍歷CON矩陣，第一個為true的任務(wù)為T1，第二個為true的任務(wù)為T4.任務(wù)T4對應(yīng)的行與任務(wù)T1對應(yīng)的進(jìn)行比較.經(jīng)過比較可知，在每一個資源上面，任務(wù)T4的執(zhí)行時間都要大于任務(wù)T1的執(zhí)行時間.故，將任務(wù)T1，T4添加至ETC1中.第三個標(biāo)記為true的任務(wù)為T6.T6與任務(wù)T4進(jìn)行比較.經(jīng)過比較可知，任務(wù)T6在每個資源上面的執(zhí)行時間都要大于T4.故將T6加入ETC1中.遍歷完成后，原始的ETC矩陣即可分解為ETC1，ETC2分解后的矩陣如表5、表6所示.

表5 ETC1矩陣

表6 ETC2矩陣

第三階段首先將ETC1矩陣進(jìn)行調(diào)度，對ETC1矩陣進(jìn)行調(diào)度的時，從T6任務(wù)開始調(diào)度.T6任務(wù)具有最小的完成時間為100，對應(yīng)的資源為R1，故將T6分配至資源R1中.T6任務(wù)分配完成后，任務(wù)T4開始分配，T4在R3具有最小完成時間45 ms，將T4分配至R3.T1在R2中具有最小完成時間6 ms，故將任務(wù)T1分配至R2.ETC1矩陣調(diào)度完成后.開始對ETC2矩陣進(jìn)行調(diào)度.ETC2中的矩陣，按照任務(wù)執(zhí)行時間的大小進(jìn)行分配，任務(wù)T2，T3，T5都在R1中具有最小執(zhí)行時間.故將任務(wù)T2，T3，T5都分配至R1.第三階段分配完成后，任務(wù)分配結(jié)果圖如圖1所示.

第四階段為調(diào)整階段.第一輪的調(diào)整，具有最大完成時間的資源為R1，具有最小完成時間的資源為R2，現(xiàn)在將分配至R1中的任務(wù)調(diào)整至R2中.R1中的任務(wù)在R2中具有最小執(zhí)行時間的任務(wù)為T2，T2在R2上的執(zhí)行時間為2.若將T2分配至R2，則R2中的完成時間為8，而R1之前的完成時間為166.8 ms(小于166)，故將任務(wù)T2調(diào)整至R2.第一輪調(diào)整后的任務(wù)分配圖如圖2所示.在本次實例中共進(jìn)行6輪調(diào)整，最終R1任務(wù)完成時間為100 ms，R2完成時間為100 ms，R3完成時間為97 ms.最終任務(wù)分配圖如圖3所示.

4 仿真與結(jié)果分析

在文獻(xiàn)[20]中，根據(jù)資源與任務(wù)的異構(gòu)性，將模擬仿真的ETC矩陣分為低任務(wù)異構(gòu)-低資源異構(gòu)、低任務(wù)異構(gòu)-高資源異構(gòu)、高任務(wù)異構(gòu)-低資源異構(gòu)、高任務(wù)異構(gòu)-高資源異構(gòu)4種.同時，根據(jù)整個ETC矩陣的一致性，將ETC矩陣分為非一致性、半一致性、一致性矩陣.共計12種ETC矩陣.在本文中的仿真實驗中，除了應(yīng)用上述12種ETC矩陣外，還增加了另外八種不同的ETC矩陣.這8種ETC矩陣中，每個任務(wù)的執(zhí)行時間主要由任務(wù)大小除以資源處理能力得到.低異構(gòu)資源處理能力的大小在[1,100]均勻分布隨機(jī)產(chǎn)生，高異構(gòu)資源處理能力的大小在[1,1 000]均勻分布隨機(jī)產(chǎn)生.低異構(gòu)任務(wù)大小在[1 000,10 000]均勻分布隨機(jī)產(chǎn)生，高異構(gòu)任務(wù)大小在[1 000,300 000]均勻分布隨機(jī)產(chǎn)生.在這8種ETC矩陣中根據(jù)ETC矩陣的一致性分為，特殊一致性矩陣與特殊半一致性.特殊一致性主要是與一致性矩陣進(jìn)行區(qū)分.特殊半一致性矩陣主要與半一致性矩陣進(jìn)行區(qū)分.一致性矩陣主要指的是，如果任務(wù)Ti在資源Rn中的執(zhí)行時間小于Rm中的執(zhí)行時間，那么所有的任務(wù)在Rn中的執(zhí)行時間要小于Rm的執(zhí)行時間.在模擬的ETC矩陣中表現(xiàn)為行有序.本文中所提的特殊一致性，指的是不僅滿足一致性的條件，還要滿足，如果任務(wù)Ti在某一資源上的執(zhí)行時間小于任務(wù)Tj執(zhí)行時間，那么在所有的資源上面任務(wù)Ti執(zhí)行時間小于Tj執(zhí)行時間.在ETC矩陣中，特殊一致性矩陣表現(xiàn)為行列有序.特殊半一致性矩陣，指的是，ETC矩陣中，一半任務(wù)滿足本文所提的特殊一致性，一半不滿足特殊一致性.在構(gòu)造特殊半一致性矩陣時，通過隨機(jī)打亂特殊一致性矩陣中一半的行來實現(xiàn).

4.1 實驗環(huán)境

實驗環(huán)境：CPU主頻3.40 GHz，硬盤：1 T，內(nèi)存：16 GB，操作系統(tǒng)：Windows10 64位.

開發(fā)環(huán)境：開發(fā)平臺為Eclipse，開發(fā)語言為Java.

4.2 結(jié)果分析

本文實驗是在上述模型與實驗環(huán)境下進(jìn)行的，選擇16個資源，256個任務(wù)產(chǎn)生的ETC矩陣.在上述基礎(chǔ)上比較MIN-MIN算法、MAX-MIN算法、本文算法.比較的結(jié)果為完成所有任務(wù)的時間MAKESPAN.每一種ETC矩陣產(chǎn)生4種最后求得4種調(diào)度結(jié)果的平均值為算法在某一ETC矩陣下的調(diào)度結(jié)果.圖4至圖7為根據(jù)文獻(xiàn)[20]提出的模擬數(shù)據(jù)實驗的結(jié)果.圖8至圖11為本文添加的8種ETC矩陣的調(diào)度結(jié)果.

與MIN-MIN算法進(jìn)行比較.觀察圖5與圖7，由一致性矩陣、半一致性矩陣與高任務(wù)異構(gòu)-高資源異構(gòu)、低任務(wù)異構(gòu)-高資源異構(gòu)所組合成的4種條件下，本文算法MAKESPAN明顯高于MIN-MIN算法的MAKESPAN，由此可以得出結(jié)果，在上述條件下MIN-MIN算法明顯優(yōu)于本文所提出的算法.觀察圖4與圖6，由半一致性矩陣與低任務(wù)異構(gòu)-低資源異構(gòu)、高任務(wù)異構(gòu)-低資源異構(gòu)組合的兩種條件下，本文算法與MIN-MIN算法相差無幾.觀察圖4至圖11，除上述6種情況外，在余下的14種情況下，本文MAKESPAN均低于MIN-MIN算法的MAKESPAN.

與MAX-MIN算法進(jìn)行比較，觀察圖8至圖11.矩陣為特殊一致性矩陣條件下，無論異構(gòu)性大小，本文算法的MAKESPAN與MAX-MIN算法的MAKESPAN相同.由此可以得出結(jié)論，在特殊一致性矩陣的4種條件下本文算法與MAX-MIN算法調(diào)度結(jié)果相同.觀察圖10，在特殊半一致性-高任務(wù)異構(gòu)-低資源異構(gòu)條件下，本文算法的MAKESPAN高于MAX-MIN算法的MAKESPAN，說明在此條件下，MAX-MIN算法要優(yōu)于本文算法.觀察圖4至圖11，除上述5種情況，其余15種條件下，本文算法調(diào)度結(jié)果都要優(yōu)于MAX-MIN算法調(diào)度結(jié)果.

除上述之外，觀察圖4至圖11可以發(fā)現(xiàn)，本文提出的算法無論在那種情況下都不會出現(xiàn)極差的結(jié)果，相比MIN-MIN,MAX-MIN調(diào)度結(jié)果更加平穩(wěn)，表明本文算法的適應(yīng)性也要優(yōu)于上述算法.

4.3 時間復(fù)雜度分析

在本文算法中，預(yù)處理階段需要對行與列進(jìn)行排序，預(yù)處理階段的時間復(fù)雜度為O(n2).分解階段包含雙重迭代，時間復(fù)雜度為O(n*m).預(yù)調(diào)度階段包含雙重迭代時間復(fù)雜度為O(n*m).調(diào)整階段包含雙重迭代，時間復(fù)雜度為O(n2).因此本文算法時間復(fù)雜度為MAX(O(n2),O(n*m)).在MIN-MIN,MAX-MIN算法中包含三重迭代，他們的時間復(fù)雜度都為O(n2m).本文算法時間復(fù)雜度要優(yōu)于上述兩個算法.

圖12展示了模擬10 000個任務(wù)分別在16,32,64,128,256節(jié)點下的算法執(zhí)行時間.MIN-MIN,MAX-MIN的計算時間幾乎相當(dāng)，這是因為其時間復(fù)雜度均為O(n2m).在本節(jié)的實驗中本文算法的計算時間分別是MIN-MIN或者M(jìn)AX-MIN的計算時間的50.4%，32.0%，25.7%，18.0%，15.0%，與算法復(fù)雜度的理論結(jié)果MAX(O(n2),O(n*m))/O(n2m)并不一致.因為時間復(fù)雜度主要反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級.但從圖12中可以發(fā)現(xiàn)，本文算法隨著節(jié)點個數(shù)的增加，算法執(zhí)行時間的增長幅度明顯弱于MIN-MIN與MAX-MIN算法. 圖13展示了模擬128個節(jié)點分別在2 000,4 000,6 000,8 000,10 000任務(wù)下的算法執(zhí)行時間.從圖13中也可發(fā)現(xiàn)，本文算法隨著任務(wù)個數(shù)的增加，算法執(zhí)行時間的增長幅度也要明顯弱于MIN-MIN與MAX-MIN算法.

5 結(jié)束語

MIN-MIN,MAX-MIN算法是獨立任務(wù)調(diào)度中常見的算法.針對上述算法時間復(fù)雜度高以及調(diào)度結(jié)果不理想的等問題,本文提出了一種基于任務(wù)執(zhí)行時間的啟發(fā)式獨立任務(wù)調(diào)度算法.在降低分配算法時間復(fù)雜度的前提下，改善任務(wù)調(diào)度結(jié)果，縮短整體的任務(wù)完成時間.在本文提出的20種任務(wù)類型下，大多數(shù)條件下本文算法調(diào)度結(jié)果要優(yōu)于上述兩種算法.此外,優(yōu)化分解階段和調(diào)整階段，解決個別條件下本文算法劣于上述兩種算法的情況，將是下一步工作的重點.