姚英彪，王 璇

（杭州電子科技大學通信工程學院，浙江杭州310018）

面向多核任務調度的混合遺傳算法

姚英彪，王 璇

（杭州電子科技大學通信工程學院，浙江杭州310018）

多核處理器的并行任務調度一直是研究的熱點話題，屬于NP-hard問題。針對此問題，本文提出了一種集啟發(fā)式算法、禁忌搜索算法、模擬退火算法于一體的改進混合遺傳算法（modified hybrid genetic algorithm，MHGA）。MHGA改進如下：首先，采用啟發(fā)式的分層調度來初始化種群，提高初始種群質量；其次，提出基于禁忌搜索（tabu search，TS）的隨機編號交叉算子，提高種群的多樣性；最后，采用基于模擬退火（simulated annealing，SA）的變異，提高個體質量。實驗結果表明，與其他遺傳算法（genetic algorithm，GA）相比，MHGA可以得到更小的任務調度時間和更快的最優(yōu)解搜索能力。

遺傳算法；禁忌搜索；模擬退火；并行調度；多核處理器

0 引 言

在多核系統(tǒng)芯片（multi-processor system-on-chip，MPSoC）設計中，如何進行任務分配和調度是一個非常關鍵的問題，這個問題可以簡單描述為：N個有前后依賴關系的任務如何分配到P個處理器上執(zhí)行，在保證任務依賴關系的條件下使得任務總完工時間最小。任務分配解決在哪個處理器核上執(zhí)行任務，即匹配任務到處理器核上；任務調度解決何時執(zhí)行任務，即給出任務在具體處理器核上的起止時間。影響任務分配和調度的因素主要有：任務計算時間、任務之間的依賴關系和處理器核之間的數(shù)據傳輸延遲等。國內外學者對這個問題進行了深入的研究，研究結果表明多核任務分配和調度問題是一種組合優(yōu)化問題，不能在多項式時間復雜度內找到最優(yōu)解，已被證明是NP-hard問題［1－4］。

目前解決這個問題的方法大致可以劃分為啟發(fā)式算法和智能搜索算法兩類。啟發(fā)式算法一般采用某種啟發(fā)規(guī)則進行任務的分配和調度，它一般只能找到問題的次優(yōu)解，且在求解大規(guī)模任務分配和調度問題時，得到的解往往與最優(yōu)解相差甚遠。它的優(yōu)點在于復雜度低，可以快速給出某種次優(yōu)結果。啟發(fā)式算法的代表有修改關鍵路徑算法［5］（modified critical path，MCP）、異構最早完成時間算法［6］（heterogeneous earliest finish time，HEFT）等。智能搜索算法是一種利用自然現(xiàn)象與優(yōu)化過程的某些相似性而逐步發(fā)展起來的搜索方法，其算法思想簡單，同時還具備搜索全局最優(yōu)解的能力。遺傳算法（genetic algorithm，GA）［7－9］、模擬退火（simulated annealing，SA）［10］、粒子群算法（particle swarm optimization，PSO）［11］、禁忌搜索（tabu search，TS）［12］等都屬于智能搜索算法。

本文計劃采用遺傳算法框架解決MPSoC的任務分配和調度問題。文獻［13］率先將GA應用到并行任務調度中，奠定了用GA解決此類問題的基礎。但是，傳統(tǒng)GA也碰到了下面3個主要難題：①問題描述困難，②初始化種群質量難以保證，③容易早熟，造成進化后期搜索效率較低。因此，GA的改進可以從優(yōu)化初始種群［14］、改進編碼機制［15］、改進遺傳算子［16］、防止種群早熟［17］等方面進行。

針對傳統(tǒng)GA碰到的問題，本文提出一種集啟發(fā)式調度、TS、SA于一體的改進混合遺傳調度算法（modified hybrid genetic algorithm，MHGA）：①采用啟發(fā)式的分層調度來初始化種群，提高初始種群質量；②提出基于TS的隨機編號交叉算子，使用禁忌表來封鎖剛搜索過的區(qū)域從而避免迂回搜索，同時赦免禁忌區(qū)域中的一些優(yōu)良狀態(tài)，保證搜索的多樣性，從而提高種群的多樣性；③在對個體進行變異時，采用SA對個體進行變異，提高種群中每個個體的質量。本文實驗結果表明，與其他GA相比，MHGA可以得到更小的任務調度時間和更快的最優(yōu)解搜索能力。

1 任務模型及算法框架

1.1 任務模型

任務模型用有向無環(huán)圖（directed acyclic graph，DAG）來表示，即G＝〈T，E〉。其中，T為任務節(jié)點的集合，T＝｛i｜1≤i≤N｝表示N個任務的集合；E＝｛eij｝為任務之間有向邊的集合，邊eij表示任務i執(zhí)行后才可以執(zhí)行j。同時假設t＝｛t1，t2，…，tN｝表示任務的執(zhí)行時間；c＝｛cij｝為任務之間有向邊eij的權重，cij表示任務i和j分配到不同處理器時的通信時間；當任務i和j分配到同一處理器時，通信時間為0。一個簡單的11個任務的DAG圖如圖1所示（圖1中，每個任務的執(zhí)行時間為2，任務間的通信時間為1）。

圖1 任務DAG圖

1.2 算法框架

對于已知的DAG圖，可以根據任務之間的依賴關系定義任務層級值h，表示任務節(jié)點的層數(shù)，定義如下：

本文提出的MHGA算法由節(jié)點層級值計算、初始種群生成、輪盤賭選擇、禁忌搜索交叉、模擬退火變異組成。算法的框架圖如圖2所示。

圖2 算法框架圖

2 MHGA算法設計

2.1 初始種群生成

為提高初始種群質量，本文采用基于層級值h的分層調度啟發(fā)式算法來生成初始種群，替代傳統(tǒng)的完全隨機的初始種群。

2.1.1 任務的初始處理器分配

對于一個特定的DAG圖，根據式（1）可以算出每個任務的層級值h。圖1中，任務的層級值依次為｛1；2，2；3，3；4，4，4；5，5；6｝，不同層級值的任務用分號隔開。將所有任務按照層級值進行分層，層級值相同的任務放在同一層，第j層的任務集合為Tj＝T｛h＝j｝。因此，圖1可以分為6層，分別為T1＝｛1｝，T2＝｛2，3｝，T3＝｛4，5｝，T4＝｛6，7，8｝，T5＝｛9，10｝，T6＝｛11｝。

從圖1可以看出，具有相同層級值的任務可以并行執(zhí)行。因此，為降低任務的完工時間，應該盡量將每層的任務均衡地分配到處理器上。假設處理器總數(shù)為P，每層的任務總數(shù)為n，則n／P＝a…b（其中b為余數(shù)）。在總任務中隨機選取b個任務（b＜P）隨機分配到不同的處理器；對于剩下的a×P個任務，每個處理器從中隨機選擇a個任務。這樣可以確保將每層任務均衡的分配到處理器上，避免同一層任務過多集中在一個處理器上造成完工時間的延遲。

圖1的DAG圖，設其處理器總數(shù)P＝2。對于T4＝｛6，7，8｝，n／P＝3／2＝1…1，先任選1個任務分配給任一個處理器，例如把任務8分配給處理器P1；剩下的任務均衡分配給P1和P2；這樣T4可能的一個處理器分配為｛p1，p2，p1｝。根據以上處理器分配原則，圖1所示的11個任務的一個可能的處理器初始分配p＝｛p1；p1，p2；p1，p2；p1，p2，p1；p2，p1；p1｝。

2.1.2 任務的編碼

本文采用符號編碼方案，符號由任務的基因值組成，所有任務的基因序列構成一個染色體（或個體）。任務基因值產生包括兩個階段：

步驟1 基因值初始化階段，即由初始處理器分配序列得到初始基因值序列。這一階段采用固定映射方式，映射規(guī)則如下：

式中，vi為任務i的基因值；pi為任務i初始分配處理器號；P為處理器總數(shù)。上述規(guī)則能夠保證個體中的每個基因值都唯一，即每個任務的基因值都不相同。這樣可以保證后面（2.1.3節(jié)）根據基因值進行任務調度時，能夠得到唯一的調度方案。

步驟2 基因值隨機交換階段，即對每個處理器上的任務的基因值進行隨機交換。交換規(guī)則如下：假設某個處理器上共分配m個任務，隨機選取該處理器上兩個任務，將其基因值進行交換，重復進行 m／2 次交換；對每個處理器都執(zhí)行上述操作，最終得到新的染色體。

進行此階段的原因在于，依據式（2）得到的任務的基因值跟任務序號成正比，是逐漸遞增的，不具有隨機性，減小了初始種群的空間的大小。隨機交換后，任務的基因值與其序號不在具有對應關系，具有更好的隨機性。

上節(jié)所示的處理器初始分配序列p＝｛p1；p1，p2；p1，p2；p1，p2，p1；p2，p1；p1｝，根據式（2）初始化后得到的個體為V＝｛3；5，8；9，12；13，16，17；20，21；23｝；隨機交換后，可能的一個個體為V＝｛23；5，20；13，16；9，12，21；8，3；17｝。此時，任務1到11對應的基因值分別為23，5，20，13，16，9，12，21，8，3，17。

2.1.3 任務調度與分配

得到個體V后，采用基于任務的層級值和基因值的任務調度、基于任務基因值的處理器分配。

任務調度規(guī)則：首先，對于不同層級值的任務，按照任務的層級值從小到大進行調度，也就是說，層級值較小的所有任務都調度完成才能調度層級值較大的任務；其次，對于相同層級值的任務，按照任務的基因值從大到小進行調度。

根據以上規(guī)則，個體V＝｛23；5，20；13，16；9，12，21；8，3；17｝的調度順序TS為：1→3→2→5→4→8→7→6→9→10→11。

處理器分配規(guī)則：任務的基因值和處理器總數(shù)取余即為任務分配的處理器，如式（3）所示，其中mod代表取余。

上述個體進行處理器分配后，可得到任務1，2，4，6，8，10和11在p1上執(zhí)行，任務3，5，7和9在p2上執(zhí)行?？梢园l(fā)現(xiàn)，由式（3）得到的處理器分配序列和該個體對應的初始處理器分配序列p＝｛p1；p1，p2；p1，p2；p1，p2，p1；p2，p1；p1｝仍然一致，這是因為：式（3）是式（2）的反變換，同時，上一節(jié)基因值隨機交換只針對同一個處理器上的任務進行，它不改變任務分配的處理器結果。

對該個體，在兩個處理器上的任務調度順序可以表示成：

2.1.4 任務開始時間和完工時間

按照任務在調度序列TS的順序，依次計算每個任務開始執(zhí)行時間和完工時間，可得到每個處理器的完工時間和任務的總完工時間。假設TS序列中第q個執(zhí)行的任務為i，其分配到的處理器為pi，任務i能夠開始執(zhí)行的先決條件是其資源約束和依賴約束同時被滿足，具體如下：

（1）資源約束規(guī)則。由于每個處理器一個時刻只能執(zhí)行一個任務，即分配到pi上的任務調度序列必須順序執(zhí)行，因此i在pi上的開始時間必須不小于i前一個任務k的完工時間。假設k的開始時間為sk，執(zhí)行時間為tk，則該約束確定的i的開始時間應該滿足：

（2）依賴約束規(guī)則。任務i能在pi開始執(zhí)行的另一個約束為其前繼任務集合pre（i）中的每一個任務j都完成，且當i與j不在同一個處理器時，i與j之間的通信任務也必須完成，即要滿足任務之間的前后依賴關系。根據該約束確定的i的開始時間應該滿足：

最后，根據上述兩個規(guī)則確定的任務i的最早開始執(zhí)行時間為

在得到每個任務的開始執(zhí)行時間和完工時間后，就可以給出任務的分配和調度圖。圖3給出圖1所示11個任務的一個可能分配和調度圖。

圖3 任務分配和調度圖

2.1.5 初始種群優(yōu)化

為更好地生成高質量的初始種群，本文還進行了初始種群優(yōu)化，其思想是在完工時間最長的處理器plong上選取一個任務分配到完工時間最短的處理器pshort上，重復進行若干次。具體步驟如下：

步驟1 若plong上存在一個任務i，使得i與在i后執(zhí)行且分配到plong的所有任務都沒有前后繼依賴關系，那么將i分配到pshort上，這樣明顯可以縮短完工時間；若不存在這樣的i，則在plong上隨機選取一個任務分配到pshort上。

需要注意的是，由于任務i的處理器分配發(fā)生了改變，必須修改任務i的基因值。假設任務i原基因值為vi，原分配的處理器號為pi，新分配的處理器號為p′i，則新基因值v′i如式（7）所示。

這樣，不僅任務的新基因值和分配到的處理器符合式（3），同時保證了新基因值不會與其他任務的基因值重復，確保了基因值的唯一性。同時可以證明，該層的任務調度序列不會發(fā)生改變，因此總的任務調度序列不變。

步驟2 計算新個體的任務完工時間并與原來的完工時間進行對比，如果新完工時間更短，則用新個體代替原個體；反之，保持原個體不變。

圖3所示調度中，p1上不存在任務i，使得i與在i后執(zhí)行且分配到p1的所有任務都沒有前后繼依賴關系。所以只能在p1上隨機選取一個任務（假設選擇了任務6），重新分配到p2上。任務6的原基因值為9，因此新基因值為9＋2－1＝10。同h值有6，7，8三個任務，該層的基因序列由｛9，12，21｝變?yōu)椋?0，12，21｝，依據第2.1.3節(jié)得到該層的調度順序仍為：8→7→6，沒有發(fā)生改變，因此總的任務調度序列TS保持不變。由此可以得到新的調度圖，如圖4所示，任務的完工時間由18變?yōu)?6，得到了優(yōu)化，因此用該新個體代替原個體。

圖4 重新調度的任務圖

步驟3 重復前兩步，進行足夠多次后（本文取10次）就可以得到較優(yōu)個體。

以上3步，可以有效地減少個體的總完工時間，提高個體質量。對種群中所有個體進行相同的操作，這樣就可以得到高質量的初始種群。圖5為初始種群的流程圖。

圖5 初始種群流程圖

2.2 適應度函數(shù)

適應度函數(shù)表示個體對生存環(huán)境的適應能力，個體的適應度越大，則該個體被遺傳到下一代的概率就越大。對于多核處理器的任務調度，可以用總任務的完工時間（也就是最后一個執(zhí)行的任務的完成時間）來評價其適應能力，個體Vi適應度函數(shù)如下：

式中，span（Vi）表示個體Vi的完工時間，圖4中任務的完工時間為16。

2.3 遺傳搜索過程

2.3.1 輪盤賭選擇

選擇是從當前種群中選取適應值高的個體進行交叉、變異，將優(yōu)良基因遺傳給后代。本文用輪盤賭旋轉法進行選擇，如圖6所示，方法如下：

（1）在［0，1］區(qū)間內產生一個均勻分布的隨機數(shù)r；（2）若r≤q（1），則個體V1被選中；

（3）若q（k－1）＜r≤q（k）（2≤k≤SN，SN為種群規(guī)模），則個體Vk被選中。

其中，q（i）為染色體的累計概率，計算公式為

P（Vi）為個體Vi被挑選的概率，其公式為

圖6 輪盤賭選擇

2.3.2 基于TS的隨機編號交叉

交叉可以增加種群多樣性，提高種群搜索能力。鑒于GA的廣域搜索能力較強，TS的局部搜索能力較強，可以將兩者混合對交叉操作進行改進，也就是把TS的“禁忌”和“特赦”思想引入到GA的交叉步驟中。

基于TS的隨機編號交叉步驟如下：

步驟1 初始化。規(guī)定種群中所有個體的最大適應度值為初始渴望水平；個體的適應度值為禁忌表中的元素；禁忌表長度為l。

步驟2 根據交叉率選擇相鄰兩個父代進行基于隨機編號交叉操作，產生兩個子代。對于進行交叉的兩個個體V1，V2，在V1中隨機選擇一個初始交叉點和截止交叉點，交叉總任務數(shù)為l，該初始交叉點和截止交叉點也是V2的初始交叉點和截止交叉點。將V1截取的一小段個體的l個任務隨機編號1～l；V2同理。然后，將這兩小段編號一樣的任務的基因值進行交換，最后再將這兩小段整體互換，這樣就可以得到新的個體S1，S2，如圖7所示。

圖7 基于隨機編號的交叉

步驟3 如果子代個體適應度值大于渴望水平，則破禁，該個體進入下一代；同時，更新禁忌表和渴望水平，將該個體的適應度值設為新的渴望水平。

步驟4 如果沒有破禁，檢測子代個體適應度值是否在禁忌表中。如果不在，該個體進入下一代，同時更新禁忌表；反之，舍棄該個體，選擇相應的父本進入下一代。

步驟5 返回步驟2，直至種群中所有個體完成交叉。

2.3.3 基于SA的變異

變異提供給種群新的基因，提高了種群的多樣性。GA的局部搜索能力差，變異后個體的質量不高；將SA算法添加到遺傳算法中，利用SA算法局部搜索能力強的優(yōu)點，優(yōu)化每個個體的質量。

基于SA的變異步驟如下：

步驟1 初始化。在種群中隨機選取個體Vi為初始解。給定初始溫度T0，終止溫度Tf，降溫值ΔT，內循環(huán)次數(shù)n（Tk）。令Tk＝T0，最優(yōu)解Vbest初始化為Vbest＝Vi。

步驟2 對個體Vi進行變異，變異后的個體為Vj，則完工時間增量Δf＝span（Vj）－span（Vi）。

變異步驟：在個體V中，隨機選擇兩個不同的變異點，然后交換其基因值，就可以得到一個新的個體S，如圖8所示。

圖8 變異

步驟3 如果Vj的完工時間小于Vbest的完工時間，更新Vbest＝Vj。

步驟4 若Δf＜0，則無條件轉移：Vi＝Vj；若Δf＞0，則進行有條件轉移：隨機產生一個隨機數(shù)ξ＝U（0，1），如果則Vi＝Vj，反之Vi保持不變。

步驟5 若達到熱平衡狀態(tài)（內循環(huán)次數(shù)大于n（Tk）），進行步驟6，否則轉步驟2。

步驟6 降低Tk，降溫函數(shù)為：Tk＝Tk－ΔT。若Tk＜Tf，則算法停止，輸出Vbest；否則轉步驟2。

對交叉后的種群中的每個個體都進行上述操作，最終可以得到變異后新的種群。通過SA，新種群中每個個體的適應度值均得到有效的提高，避免了常規(guī)變異造成個體變差的可能性，提高了GA的性能。

2.3.4 變異后調度圖

需要注意的是，變異使得某些任務的基因值發(fā)生了改變，這些任務分配到的處理器也就相應地發(fā)生變化，由式（3）可得到這些任務分配到的新處理器。根據第2.1.3節(jié)，可得到任務調度序列TS；根據第2.1.4節(jié)可得到新一代種群中所有個體的任務調度圖，也就知道了其最優(yōu)個體完工時間。

2.3.5 算法結束

重復進行上述步驟到規(guī)定的代數(shù)，就可以得到最優(yōu)任務調度圖及最短完工時間。圖1的DAG圖，根據上述算法，得到的最優(yōu)調度圖如圖9所示，其完工時間為14。

圖9 最優(yōu)調度圖

本文所述的遺傳算法流程圖如圖10所示。

圖10 遺傳算法流程圖

3 仿真實驗

3.1 實驗參數(shù)

在進行仿真實驗時，可以隨機生成DAG圖，規(guī)定所有任務的計算時間總和與通信開銷的總和的比值為0.5，且每個任務的計算時間和任務間通信時間的取值范圍為［2，20］，其他仿真實驗參數(shù)如表1所示。用MATLAB 2012b進行仿真，并將本文的MHGA算法和標準HGA算法［13］、Hwang的PGA算法［15］進行比較。為了消除數(shù)據隨機性對結果的影響，將實驗數(shù)據取30次平均，可以得到最終的對比結果。

表1 實驗參數(shù)設定

3.2 仿真結果

本文提出的MHGA算法使用了初始化種群和混合遺傳算法兩部分操作，為了更好地研究MHGA的性能，這里將該算法拆分成兩部分。MHGA-1只進行初始化種群，沒有采用改進混合遺傳算法；MHGA-2只進行改進混合遺傳算法，沒有初始化種群。

圖11是不同任務數(shù)完工時間的比較。從圖11中可以看到，本文提出的MHGA算法得到的完工時間是最優(yōu)的，即MHGA尋找最優(yōu)解的能力最強。PGA次之，HGA搜索最優(yōu)解的能力最差。MHGA相比于MHGA-1，性能得到較大提高；相比于MHGA-2相差不多，但也得到了改善。

圖11 不同任務數(shù)的完工時間比較

圖12為3種算法在100代的完工時間收斂過程。從圖12可以看出，在收斂值方面，本文提出的MHGA算法的收斂值明顯優(yōu)于HGA和PGA；在收斂速度方面，HGA最快，MHGA次之，PGA最慢。HGA算法因為其過早收斂，造成其收斂值最大，即搜索最優(yōu)解能力最差。PGA算法不僅收斂較慢，其收斂值也高于MHGA算法。由于MHGA優(yōu)化了初始種群，使用了混合遺傳算法，導致此算法整體上每代結果均優(yōu)于其他兩種算法。

圖12 最小完工時間的收斂過程

MHGA-1只初始化了種群，盡管在第一代的結果較優(yōu)，但隨著代數(shù)的增加，其搜索能力變差且收斂速度較慢。MHGA-2采用了混合遺傳算法，使得種群多樣性增加，個體的適應度值也得到提高。隨著代數(shù)的增加，其最優(yōu)解的搜索能力逐漸變好。由于沒有初始化種群，使得收斂值大于MHGA，且收斂速度較慢，搜索時間更長。而本文的MHGA綜合了MHGA-1和MHGA-2兩者優(yōu)點，不僅收斂值更優(yōu)，其收斂速度也得到了提高，提升了遺傳算法的性能。

以上是取30次實驗求平均得到的結果，為了更好地分析每次遺傳的情況，隨機選取1次實驗來進行分析（N＝35），由此可以得到每代的任務完工時間，如圖13所示（圖13中，MHGA算法輸出的每代完工時間是圖10中種群S3的最優(yōu)個體的完工時間）。

圖13 每代的完工時間（N＝35）

由圖13可以看出，HGA算法每代結果的動態(tài)范圍最小，其算法達到較優(yōu)結果后，很難再跳出去，從而使得算法早熟，其結果易于陷入局部最優(yōu)。PGA算法采用了基于優(yōu)先級的編碼（priority-based multi-chromosome，PMC）、權重交叉（weight mapping crossover，WMX）等操作，使得算法每代結果的動態(tài)范圍最大，可以避免算法早熟，但其收斂速度較慢，且得到的最優(yōu)解較差。MHGA-1初始化了種群，盡管第一代的結果較優(yōu)，但最優(yōu)解的搜索能力較差。MHGA-2采用混合遺傳算法，但由于沒有初始化種群，其搜索時間更長，收斂速度較慢，最優(yōu)解也差于MHGA。MHGA綜合了MHGA-1和MHGA-2的優(yōu)點，不僅收斂值更優(yōu)，其收斂速度也得到了提高。

4 結束語

本文提出的MHGA在解決并行多核任務的分配和調度時，其性能優(yōu)于其他算法的原因在于：首先利用啟發(fā)式方法對初始種群進行分層分配和調度，產生質量較高的初始種群；其次，使用基于TS的隨機編號交叉，提高了種群的多樣性；最后，采用基于SA的變異，提高個體的質量，所有個體的適應度值得到了提高。仿真結果表明，MHGA能夠得到更短的任務完工時間，具有較強的最優(yōu)解搜索能力，可用于實際應用。當然，MHGA也有不足，主要表現(xiàn)在：①僅適用于同構MPSoC系統(tǒng)；②算法參數(shù)不能夠自適應調整。因此，未來希望將本文算法擴展到異構多核系統(tǒng)中，同時一些關鍵參數(shù)能夠自適應調整，從而增強MHGA的適用范圍和性能。

［1］Lee J，Chung M K，Cho Y G，et al.Mapping and scheduling of tasks and communica-tions on many-core soc under local memory constraint［J］.IEEE Trans.on Computer-aided Design of integrated circuits and System，2013，32（11）：1748－1761.

［2］Venugopalan S，Sinnen O.ILP formulations for optimal task scheduling with communi-cation delays on parallel systems［J］.IEEE Trans.on Parallel and Distributed Systems，2014，（99）：1－10.

［3］Topcuoglu H，Hariri S，Wu M Y.Performance-effective and low-complexity task scheduling for heterogeneous compu-ting［J］.IEEE Trans.on Parallel and Distributed Systems，2002，13（3）：260－274.

［4］Fan M，Quan G.Harmonic-aware multi-core scheduling for fixedpriority real-time systems［J］.IEEE Trans.on Parallel and Distributed Systems，2014，25（6）：1476－1488.

［5］Lan Z，Sun S X.Task scheduling genetic algorithm based on the knowledge of critical path［J］.Computer Applications，2008，28（2）：272－274.（蘭舟，孫世新.基于關鍵路徑知識的任務調度遺傳算法［J］.計算機應用，2008，28（2）：272－274.）

［6］Chopra N，Singh S.HEFT based workflow scheduling algorithm for cost optimization within deadline in hybrid clouds［C］∥Proc.of the 4th International Conference on Computing，Communications and Networking Technologies，2013：1－6.

［7］TabakE K，Cambazoglu B B，Aykanat C.Improving the performance of independent task assignment heuristics minmin，maxmin and sufferage［J］.IEEE Trans.on Parallel and Distributed Systems，2014，25（5）：1244－1256.

［8］Omara F A，Arafa M M.Genetic algorithms for task scheduling problem［J］.Journal of Parallel and Distributed Computing，2010，70（1）：13－22.

［9］Wen Y，Xu H，Yang J D.A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks［J］.Journal of Parallel and Distributed Computing，2011，71（11）：1518－1531.

［10］Zhou S E，Lei H.Based on the improved genetic-simulated annealing algorithm for task scheduling orderly［J］.Micro-electronics and Computer，2006，23（10）：62－64.（周雙娥，雷輝.基于改進的遺傳－模擬退火的有序任務調度算法［J］.微電子學與計算機，2006，23（10）：62－64.）

［11］Li J M，Zhang B，Wang X.Heterogeneous multiprocessor task scheduling based on particle swarm optimization algorithm［J］.Application Research of Computers，2012，29（10）：3621－3624.（李靜梅，張博，王雪.基于粒子群優(yōu)化的異構多處理器任務調度算法［J］.計算機應用研究，2012，29（10）：3621－3624.）

［12］Faragardi H R，Shojaee R，Yazdani N.Reliability-aware task allocation in distributed computing systems using hybrid simu-lated annealing and tabu search［C］∥Proc.of the 14th IEEE International Conference on High Performance Computing and Communication ＆IEEE9th International Conference on Embedded Software and Systems，2012：1088－1095.

［13］Hou E，Ansari N，Ren H.A genetic algorithm for multiprocessor scheduling［J］.IEEE Trans.on Parallel and Distributed Systems，1994，5（2）：113－120.

［14］Peng M M，Huang L.Task scheduling and load balancing for multi-processors［J］.Microelectronics and Computer，2011，28（11）：35－39.（彭蔓蔓，黃亮.多核處理器中任務調度與負載均衡的研究［J］.微電子學與計算機，2011，28（11）：35－39.）

［15］Hwang R，Gen M，Katayama H.A comparison of multiprocessor task schedu-ling algorithms with communication costs［J］.Computers and Operations Research，2008，35（3）：976－993.

［16］Zhong Q X，Xie T，Chen H W.Task matching and scheduling by genetic algorithm［J］.Journal of Computer Rese-arch and Development，2000，37（10）：1197－1203.（鐘求喜，謝濤，陳火旺.基于遺傳算法的任務分配與調度［J］.計算機研究與發(fā)展，2000，37（10）：1197－1203.）

［17］Yuan X L，Zhong M Y.Improved genetic algorithms for parallel task scheduling［J］.Computer Engineering and Applications，2011，47（10）：56－59.（袁雪莉，鐘明洋.改進遺傳算法的并行任務調度［J］.計算機工程與應用，2011，47（10）：56－59.）

Modified hybrid genetic algorithm for parallel task scheduling of multiprocessors

YAO Ying-biao，WANG Xuan
（College of Communication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

Parallel task scheduling of multiprocessors is a hot research topic，and also is a well known NP-hard problem.Focusing on this problem，a modified hybrid genetic algorithm（MHGA）is proposed，in which the heuristic algorithm，tabu search（TS）algorithm and simulated annealing（SA）algorithm are integrated.The modifications of the MHGA include：using the hierarchical scheduling based heuristic method to initialize the population so as to improve the quality of initial population；employing the TS based random number crossover to enhance the diversity of the population；adopting the SA based mutation to improve the quality of the individual.Experimental results show that the MHGA can obtain smaller task scheduling time and have ability to fast search better solution in comparison with other GAs.

genetic algorithm（GA）；tabu search（TS）；simulated annealing（SA）；parallel scheduling；multiprocessor

TP 332

A

10.3969／j.issn.1001-506X.2015.08.32

姚英彪（1976－），男，副教授，博士，主要研究方向為計算機體系結構、嵌入式系統(tǒng)設計。

E-mail：yaoyb＠hdu.edu.cn

王 璇（1991－），女，碩士研究生，主要研究方向為多核處理器任務調度。

E-mail：15158116166＠163.com

1001－506X201508－1928－08

網址：www.sys－ele.com

2014－09－11；

2014－10－30；網絡優(yōu)先出版日期：2015－01－20。

網絡優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150120.1050.006.html

國家自然科學基金（61100044），中國浙江省科技廳科技計劃項目（2013C31100）資助課題