薛亞非，馮 鈞

(1.南京師范大學(xué) 中北學(xué)院，江蘇 南京 210046；2.河海大學(xué) 計算機與信息學(xué)院，江蘇 南京 210098)

0 引 言

對于有向無環(huán)圖應(yīng)用，任務(wù)調(diào)度問題是并行計算和分布式計算的基本問題之一，該問題一般是NP難的，最優(yōu)解僅限于該問題限制情形，該領(lǐng)域中啟發(fā)式任務(wù)調(diào)度算法已得到廣泛研究[1,2]。

組合優(yōu)化問題有許多技術(shù)，已被應(yīng)用到任務(wù)調(diào)度制導(dǎo)搜索算法中，可分為兩類[3,4]：①隨機制導(dǎo)搜索，其中使用隨機過程，借助于候選解表示方法和隨機候選解攝動過程。例如，文獻[5]提出基于模擬退火算法的任務(wù)調(diào)度策略，通過涉及重復(fù)加熱和冷卻的退火過程使晶體結(jié)構(gòu)處于更有序狀態(tài)的概念。文獻[6]提出基于禁忌搜索算法(Tabu)的任務(wù)調(diào)度策略，可避免在區(qū)域附近重復(fù)搜索。文獻[7]提出基于模擬進化算法(simulated evolution，SE)的任務(wù)調(diào)度策略，通過使用選擇和生成步驟從當前解決方案生成新的任務(wù)調(diào)度解決方案。②確定性制導(dǎo)搜索，使用確定性策略，對要解決問題的密切知識搜索候選解。例如，文獻[8]提出基于TASK算法(TASK algorithm)的任務(wù)調(diào)度策略，算法缺點是重復(fù)執(zhí)行步驟過多，計算復(fù)雜度過大。同時，當任務(wù)調(diào)度問題采用隨機制導(dǎo)搜索策略時，存在問題[9,10]：①隨機性可防止搜索在適當?shù)乃阉鞣较蛏峡焖龠M行。根據(jù)沿途發(fā)現(xiàn)的隨機解，對于中型或大型網(wǎng)絡(luò)搜索時間變化很長。②通常需要大量控制參數(shù)，這些參數(shù)通常由實驗確定。這是嚴重的限制，因為反映實際執(zhí)行環(huán)境的良好實驗對于獲得良好解決方案至關(guān)重要。

本文提出了基于時隙堆棧策略的確定性引導(dǎo)搜索算法，該算法對于異構(gòu)集群系統(tǒng)的DAG調(diào)度特別有效，通過使用消除由慢速網(wǎng)絡(luò)鏈路互連的節(jié)點之間的通信需求的“填充”操作來解決上述問題，實現(xiàn)算法性能提升。

1 問題模型

1.1 模型定義

應(yīng)用程序可利用DAG模型G=T,E表示[11]，其中T是一組NT任務(wù)集合，E是一組NE邊集。每個邊eij=ti,tj∈E表示優(yōu)先約束關(guān)系，指示任務(wù)ti應(yīng)該在任務(wù)tj開始之前完成執(zhí)行。任務(wù)ti具有與基線處理器平臺上任務(wù)ti的執(zhí)行時間相對應(yīng)的權(quán)重τi1≤i≤NT，邊緣eij1≤i,j≤NT具有與從pi到pj要傳輸?shù)臄?shù)據(jù)量對應(yīng)的權(quán)重εij。

目標異構(gòu)集群系統(tǒng)可以由無向圖HC=C,LW分層表示，其中C=Ck1≤k≤NC對應(yīng)于一組NC集群，而LW=lCiCjCi,Cj∈C對應(yīng)于一組集群之間的WAN鏈路。每個集群Ck=P(k),L(k)包含一組處理器P(k)和用于在P(k)中的處理器之間進行通信的一組局域網(wǎng)(LAN)鏈路L(k)。

為了進行任務(wù)調(diào)度，異構(gòu)集群系統(tǒng)可由非層次圖模型NHC=P,L表示，其中[12,13]

(1)

在這一特定鏈接表示，給定鏈接lpipj，如果pi,pj都屬于第k個簇C(k)，則該鏈接對應(yīng)于L(k)中的LAN鏈接。否則，該鏈接對應(yīng)于LW中的WAN鏈接。每個處理器pq都有一個(相對)計算功率因數(shù)wq；在處理器pq上執(zhí)行任務(wù)ti需要τi·wq時間單位。同樣地，令λpq,pr表示pq和pr之間鏈路的帶寬的倒數(shù)，以便在εij·λpq,pr時間單元將εij從pq發(fā)送到pr。給定一個DAG模型G和一個異構(gòu)集群模型NHC，本文解決的問題是找到一個高質(zhì)量的調(diào)度，定義為從G到NHC的映射。解決方案的質(zhì)量由最大完工時間、所產(chǎn)生的計劃的總長度決定。

1.2 調(diào)度方案求解

可使用諸如圖1所示的圖形結(jié)構(gòu)來表示調(diào)度表。在這個圖中，虛線箭頭表示存在分配給同一處理器的兩個任務(wù)之間的執(zhí)行順序。

圖1 關(guān)鍵路徑(厚實線)和時隙模型

定義1[14]給定分配在同一處理器上的兩個任務(wù)，tjl和tjm，對于tjl優(yōu)先于tjm，表示為tjltjm，當且僅當l小于m時。符號“”用于表示執(zhí)行順序。當秩不同時，可用代替“”。

定義2[15]在同一處理器上連續(xù)分配的一組任務(wù)由tjl::tjm表示，其中tjl和tjm是分別具有最小和最大秩的兩個任務(wù)。這個集合可被認為是一個時隙堆棧。時隙堆棧的頂部和底部元素分別是tjl和tjm。

1.3 調(diào)度計劃評估

調(diào)度質(zhì)量可用列表啟發(fā)式方法評估。令A(yù)ST(ti)和AFT(ti)表示任務(wù)ti的指定開始時間和分配完成時間。Tdata(ti)是從處理器φ(ti)執(zhí)行任務(wù)ti的接收所有數(shù)據(jù)所需時間，Tavailφ(ti)是處理器φ(ti)可用時間。則可得

(2)

式中：compti,φ(ti)任務(wù)ti在處理器φ(ti)上的計算時間。下面列出其它有關(guān)定義。

定義4 計劃調(diào)度的關(guān)鍵路徑CP是任務(wù)和邊緣的路徑，從而導(dǎo)致該調(diào)度具有最小完成時間。CP中任務(wù)被稱為關(guān)鍵任務(wù)。CP長度是進度的最大化。

定義5 給定任務(wù)ti，ti的關(guān)鍵前置任務(wù)(cpt(ti))是ti的前置任務(wù)，它最遲在ti的所有前置任務(wù)中完成數(shù)據(jù)傳輸。Tdata(ti)由ti的關(guān)鍵前置任務(wù)決定。

1.4 調(diào)度過程改進

在基于搜索的調(diào)度算法中，常用技術(shù)包括試圖通過修改當前最佳任務(wù)調(diào)度來找到改進的任務(wù)調(diào)度，然后測試新調(diào)度是否優(yōu)于當前最佳調(diào)度。如果新的調(diào)度計劃更好(或者至少不是更壞)，那么在下一次迭代中，它被認為是當前最佳計劃。新的調(diào)度表被認為是可接受的。如果新的調(diào)度表是可接受的，它將在下一次搜索迭代期間替換當前最佳調(diào)度。

該“修改和測試”方案導(dǎo)致在每次迭代中找到連續(xù)更好的任務(wù)調(diào)度的可能性。但是必須有一種方法生成新的調(diào)度計劃，以有效方式搜索可能的解決方案空間。此外，生成的新調(diào)度必須具有有效的表示形式。下面給出如下兩個表示函數(shù)：

函數(shù)1：ψ′1=ReassignR→pjψ。此函數(shù)通過使用以下步驟將集合R中的所有任務(wù)重新分配給處理器pj來更改調(diào)度方案ψ。

步驟1 每當調(diào)度ψ下任務(wù)tjk,tjk+1不是E∈G的元素時，將該對作為零加權(quán)偽邊添加到DAG模型G中。

步驟2 按照拓撲順序?qū)Φ玫降腄AG模型進行排序，并構(gòu)造包含一系列匹配對ti,pj的字符串。該匹配意味著任務(wù)ti被映射到處理器pj。

步驟3 替換pj匹配的處理器部分；亦即，對于tk∈N利用tk,φtk替換tk,pj。

步驟4 基于拓撲排序和在修改后的字符串中使用的匹配來構(gòu)造新的調(diào)度。

這4個步驟通過在DAG中維護任務(wù)之間的優(yōu)先約束來保證生成有效的調(diào)度。該函數(shù)的時間復(fù)雜度為O(TlogT)，其中T是任務(wù)的總數(shù)。這源于在步驟2中在DAG拓撲模型中對所有T任務(wù)排序所需的時間。

2 基于時隙堆棧的任務(wù)調(diào)度算法

2.1 算法描述

在所提基于時隙堆棧的任務(wù)調(diào)度算法中，可利用兩個步驟獲得高質(zhì)量的解決方案：①使用基線算法生成基線調(diào)度。最近開發(fā)的算法，例如HEFT或HCPT算法[13,14]，可以快速地為大多數(shù)類型的目標計算環(huán)境生成良好的任務(wù)調(diào)度，可以用作基線算法。②使用確定性搜索過程改進基線調(diào)度。其實質(zhì)為協(xié)調(diào)搜索過程，試圖通過利用任務(wù)調(diào)度問題和目標計算環(huán)境先驗知識來迭代地改進當前最佳解決方案。

所提算法采用兩種技術(shù)以提高基線調(diào)度：①涉及找到當前調(diào)度的關(guān)鍵路徑，并試圖通過將任務(wù)移動到其它處理器來縮短完工時間，從而減少關(guān)鍵任務(wù)分配開始時間。②包括找到給定時間表中的所有可行時隙(在兩個指定任務(wù)之間的處理器時間中的空閑間隙)，并檢查是否有可能將一組任務(wù)插入到這些時隙中。如果成功地將任務(wù)插入時隙可顯著縮短完成時間(執(zhí)行DAG應(yīng)用程序中的所有任務(wù)所需的時間)。這兩種技術(shù)，分別稱為推送和填充過程，以迭代方式執(zhí)行，直到在搜索解決方案中沒有進一步改進為止。算法1給出了任務(wù)調(diào)度的時隙堆棧過程形式化描述。

算法1：時隙堆棧過程形式化描述

(1) 利用現(xiàn)有算法(基于列表的啟發(fā)式算法)生成調(diào)度計劃ψ。

(2) Repeat

(3)利用推送過程獲得新調(diào)度方案ψ′；

(4)利用填充過程獲得新調(diào)度方案ψ″；

(5)在ψ,ψ′,ψ″中選取最佳調(diào)度→ψ；

(6) UntilK步迭代后→ψ不發(fā)生變化；

(7) Returnψ(當前最佳調(diào)度方案)

最初，該算法使用基線算法(例如，基于列表的啟發(fā)式算法)獲得基線調(diào)度。接下來，它重復(fù)時隙堆棧過程，直到K步迭代過程中解的質(zhì)量沒有改善為止。K是該算法中唯一的控制參數(shù)(通常設(shè)置為一個小值，如K=4或5)。當算法終止時，它返回迄今為止找到的最佳調(diào)度。算法中ψ′即為函數(shù)1～函數(shù)2中所定義的ψ′1和ψ′2。

觸發(fā)任務(wù)與目標任務(wù)集定義方面，時隙堆棧操作試圖通過重新分配任務(wù)來減少調(diào)度長度。在這些操作中，激勵這種重新分配任務(wù)ti被稱為觸發(fā)任務(wù)，且由觸發(fā)任務(wù)重新分配的相同處理器上連續(xù)分配一組任務(wù)，例如R=[tjl::tjm]，被稱為目標任務(wù)集。對于所有推拉操作，都需觸發(fā)任務(wù)ti和目標任務(wù)集R。

2.2 推送操作

給定觸發(fā)任務(wù)ti和R中的目標任務(wù)，涉及觸發(fā)任務(wù)ti目標任務(wù)到另一處理器上的操作稱為推送操作。因此，推送操作可表述如下

(3)

圖2 推送操作

示例中，假設(shè)觸發(fā)任務(wù)是t5，目標任務(wù)集R具有t3和t4。由于t5推送t3和t4，兩個目標任務(wù)被重新分配到產(chǎn)生最佳結(jié)果調(diào)度的任何處理器(在p1、p2和p3之間)。圖2給出推送結(jié)果。任務(wù)t3和t4分別被移動到p1和p3，這導(dǎo)致了最大完工時間減少。

為執(zhí)行推送操作，需一個目標任務(wù)集，可通過觸發(fā)任務(wù)ti和目標任務(wù)tk之間的下列先決條件完成的，須滿足：①tk和ti彼此獨立；②φtk=φ(ti)；③tkti。推送操作目的是通過將目標任務(wù)推離當前處理器來更早地執(zhí)行觸發(fā)任務(wù)ti。為此，增加第3個條件。上述3個條件均滿足ti和Bitsk(ti)位之間的任務(wù)tk。因此，Bitsk(ti)用作推送操作中給定任務(wù)ti的匹配目標集R。該算法過程見算法2所示。

算法2：推送操作

ProcedurePush_optc,Bitsktc→P

(1)R←Bitsktc；

(2) whileR≠? do

(3)在R中選取任務(wù)tr；

(4)P′←P中候選處理器；

(5)repeat do

(6) 在P′中選取處理器pj；

(7)ψ′←Reassigntr→pjψ；

(8) ifψ′可接受 then

(9)ψ←ψ′；

(10)P′←P′-pj；

(11)untilψ′可接受；

(12)R←R-tr；

(13) endwhile

在最壞的情況下，所有新生成調(diào)度都是不可接受的，該算法的時間復(fù)雜度是ORPTlogT。然而，由于新生成的調(diào)度可以在內(nèi)環(huán)內(nèi)被接受，所以平均時間復(fù)雜度會更小。

必須將Bitsktc的所有任務(wù)重新分配到P中處理器中。由于在典型的異構(gòu)集群環(huán)境中存在大量的處理器，因此希望限制要考慮的處理器集。因此，對于給定目標任務(wù)，只有以下處理器被視為候選處理器，表示為P′：①分配至少一個任務(wù)的處理器；②在每個集群中沒有任務(wù)分配的處理器中最快的處理器(具有最低的wq)。

以這種方式選擇候選處理器原因如下：①如果在給定處理器上分配任務(wù)，則在該處理器上執(zhí)行其它任務(wù)可以消除通信延遲。②可能還有其它有用的處理器，在這些處理器上還沒有分配任務(wù)。當計算和通信成本都被考慮時，在可用處理器集合中每個集群中最快處理器也可能對某些任務(wù)有益。利用該操作，推送操作時間復(fù)雜度變?yōu)镺RP′TlogT。

2.3 填充操作

給定分配給處理器pi的觸發(fā)任務(wù)ti和分配給處理器pk≠pi的目標任務(wù)集R=tjl::tjm，涉及觸發(fā)任務(wù)填充設(shè)置到處理器pi的目標任務(wù)的動作被稱為填充操作。因此，該操作可以表述如下

Pull_opti,R≡ReassignR→φ(ti)

(4)

當填充目標任務(wù)時，將被重新分配給觸發(fā)器任務(wù)處理器。這使得觸發(fā)器任務(wù)和目標任務(wù)在同一處理器上執(zhí)行，從而消除了它們之間的通信成本。填充運算的時間復(fù)雜度為OTlogT。

圖3給出了填充操作的一個例子。在這個例子中，假設(shè)觸發(fā)任務(wù)是t7，目標任務(wù)集R包括t3、t4和t5。因為t7填充R=t3,t4,t5，將3個目標任務(wù)重新分配給p7，從而減少最大完工時間。

圖3 填充操作

要執(zhí)行填充操作，填充操作需要一個目標任務(wù)集。這是通過在R=tjl::tjm中的觸發(fā)任務(wù)ti和目標任務(wù)tk之間滿足以下前提條件來實現(xiàn)的，必須滿足以下條件：①必須存在一個邊緣ejmi；②φ(ti)≠φtk。這兩個條件稱為填充條件。

給定目標任務(wù)ti，使用以下方法來確定目標任務(wù)集。首先，選擇一個具有φ(ti)≠φcpt(ti)的任務(wù)cpt(ti)作為第一目標任務(wù)，這對應(yīng)于R中的tjm。這種選擇的原因是ti的指定起始時間嚴重依賴于cpt(ti)。如果通過填充操作消除了這兩個任務(wù)之間的通信成本，則預(yù)期會有益處，因為任務(wù)ti可以更早地執(zhí)行。

如果只填補目標任務(wù)cpt(ti)，就會出現(xiàn)問題。假設(shè)cptcpt(ti)、cpt(ti)最初運行在同一處理器上。如果ti填充cpt(ti)，則不會消除cpt(ti)和cptcpt(ti)之間的通信成本，即使它消除了ti和cpt(ti)之間的通信成本。cptcptcpt(ti)與運行在相同處理器的cptcpt(ti)存在相同的情況。

解決這個問題的方案是將整個關(guān)鍵前端任務(wù)鏈(在單個處理器上分配)視為一組目標任務(wù)。設(shè)R為目標任務(wù)集，tr為cpt(ti)。目標任務(wù)tr擴展為一組目標任務(wù)R，包括cpttr、cptcpttr等。在填充操作中，R中所有任務(wù)都被認為是填充候選。因此，填充操作中任務(wù)ti的目標任務(wù)集為R=tjl::tjm，其中對于l≤r≤m-1，存在tjm=cpt(ti)，φcpt(ti)≠φ(ti)，tjr=cpttjr+1，φtjr≠φtjr+1。

在填充過程中，只有在通過可行性檢查和新的時間表是可接受的情況下才執(zhí)行填充操作。如果當前堆棧R的可行性和可接受性檢查失敗，則移除堆棧R的頂部并重復(fù)該過程，直到通過檢查或堆棧變空。整個過程如算法3所示。

算法3： 填充操作

(1)N←T中任務(wù)的拓撲排序列表；

(2) whileN≠? do

(3) 選取N中的第一個任務(wù)tk；

(4) 尋找滿足填充條件的tk,R對；

(5) whileR≠? do

(6) if 插入R可行 then

(7)ψ′←Pull_optk,Rψ；

(8) ifψ′可接受 then

(9)ψ←ψ′， 跳轉(zhuǎn)步驟(2)；

(10) 移除R的最頂端；

(11) endwhile

(12)R←R-tk；

(13) endwhile

3 實驗分析

3.1 實驗設(shè)置

所使用的調(diào)度算法在公共計算平臺上進行了仿真：CPU雙核英特爾Xeon(3.0 GHz)服務(wù)器PC，內(nèi)存為6 GB ddr4-2400k，系統(tǒng)為win7旗艦。兩個基于列表的啟發(fā)式算法，異質(zhì)性最早完成時間算法(HEFT)和異質(zhì)性關(guān)鍵父樹算法(HCPT)，被用作基線算法，因為它們是迄今為止針對異構(gòu)系統(tǒng)提出的性能最好的算法之一。兩種算法實現(xiàn)過程如圖4所示。

圖4 HEFT和HCPT實現(xiàn)過程

考慮圖4所示示例，為一個簡單的DAG和一個由兩個處理器組成的計算系統(tǒng)，兩個處理器通過一個鏈路相連。當使用HEFT算法時，生成的調(diào)度如圖4(a)所示。該算法根據(jù)任務(wù)優(yōu)先級形成一個任務(wù)序列，然后按順序逐個分配給處理器。當使用HEFT算法時，生成的調(diào)度如圖4(b)所示。該算法根據(jù)任務(wù)優(yōu)先級形成一個關(guān)鍵父樹任務(wù)序列，然后按照父樹子樹模式逐個分配給處理器。

表1 參數(shù)值集

使用參數(shù)值集的所有組合(總共11 520個測試用例)來創(chuàng)建應(yīng)用程序DAG模型G和異構(gòu)集群圖模型HC。相對于最小關(guān)鍵路徑SLR的調(diào)度長度是用于評估DAG調(diào)度算法的常用性能度量。然而，由于推送-填充算法被設(shè)計用于提高由基線算法生成的調(diào)度完整性，所以另一個性能度量，改進SLR，也用于評估考慮的調(diào)度算法[15,16]

(5)

式中：SLRBA是基線算法產(chǎn)生調(diào)度方案的關(guān)鍵路徑SLR，SLRGSA是使用引導(dǎo)搜索算法產(chǎn)生的調(diào)度方案的關(guān)鍵路徑SLR。

3.2 結(jié)果分析

對比算法選取模擬退火(SA)[17]，禁忌搜索(Tabu)[18]，TASK算法[19]，模擬進化(SE)[20]。在SA算法中，初始溫度被設(shè)定為初始計劃的完工時間。下一代的解決方案是概率接受的。在Tabu算法中，試圖找到更好的解決方案的跳數(shù)決定了調(diào)度開銷。在SE中，控制解的搜索時間的選擇偏差B設(shè)置為0。參數(shù)Y是根據(jù)特定任務(wù)在所有處理器上的執(zhí)行時間分配給它的處理器數(shù)量。在設(shè)置中，Y是20，這表示只有在異構(gòu)集群系統(tǒng)中考慮的最好的20個處理器。

在圖5中，在平均和最大SLR改進方面比較幾種引導(dǎo)搜索算法的性能。

圖5 作為任務(wù)數(shù)量函數(shù)的SLR改進

根據(jù)圖5實驗結(jié)果可知，在與選取的SA算法，Tabu算法，TASK算法以及SE算法對比實驗過程中，結(jié)合異質(zhì)性最早完成時間算法(HEFT)和異質(zhì)性關(guān)鍵父樹算法(HCPT)的實驗對比結(jié)果分別如圖5(a)～圖5(b)所示。從圖5(a)可以看出，在HEFT框架下，本文算法的SLR指標提升幅度顯著的高于選取的SA，Tabu，TASK算法以及SE幾種對比算法，這表明本文算法的最小關(guān)鍵路徑SLR的調(diào)度長度提升幅度最高，體現(xiàn)了所提時隙堆棧算法在任務(wù)調(diào)度算法上的有效性。以上分析結(jié)果同樣適用于HCPT框架下的實驗對比分析結(jié)果，上述結(jié)果驗證了所提算法的有效性。

選取HEFT作為基線算法，利用其它參數(shù)值獲得的性能結(jié)果趨勢如圖6所示。

圖6 度量指標SLR改進效果對比

根據(jù)圖6結(jié)果可知，SA算法、Tabu算法、TASK算法、SE算法以及本文算法的SLR指標提升幅度均隨著簇大小參數(shù)的增加，這表明增加簇大小參數(shù)有助于SLR改進得到提升，因為存在更多的處理器導(dǎo)致更多的機會增加并行性。在圖6(b)中，隨著出度outdegree參數(shù)增加，所提算法SLR指標提升幅度增加，大大優(yōu)于其它算法，而選取的對比算法在出度outdegree參數(shù)增加后均出現(xiàn)下降趨勢，這是因為對比算法并未考慮出度outdegree參數(shù)的優(yōu)化問題，而本文算法在設(shè)計過程中考慮到了出度outdegree參數(shù)問題。這個結(jié)果暗示了所提算法在改善外延DAG的調(diào)度長度方面優(yōu)于其它引導(dǎo)搜索算法。圖6(c)中，隨著異構(gòu)性參數(shù)的增加，幾種對比算法的SLR指標提升幅度均出現(xiàn)下降趨勢，但是本文算法相對于選取的對比算法具有更佳的性能表現(xiàn)，上述實驗結(jié)果驗證了所提算法的有效性。

同時，為驗證所提算法的計算性能優(yōu)勢，這里選取上述幾種算法在HCPT和HEFT框架下的計算時間進行實驗對比分析，結(jié)果見表2。

根據(jù)表2所示算法計算效率實驗對比結(jié)果可知，在HCPT和HEFT框架下，本文算法的計算時間分別為2.13 s和3.17 s，均不高于10 s，而選取的幾種對比算法在上述算法框架下的計算時間均高于10 s，相對于本文算法的計算時間均高出近4倍以上，這表明本文算法在上述算法框架下的計算效率要顯著優(yōu)于所選取的對比算法，主要原因是本文采用的是列表式計算方法，繼承了該類算法的計算效率優(yōu)勢，而選取的對比計算方法采用的均是進化計算方法，具有較高的計算復(fù)雜度，上述實驗結(jié)果體現(xiàn)了算法的計算效率優(yōu)勢。

表2 計算效率對比

4 結(jié)束語

針對異構(gòu)集群系統(tǒng)，提出了一種基于引導(dǎo)搜索策略的靜態(tài)調(diào)度算法，稱為時隙堆棧算法。該算法從基線算法生成的初始解中搜索改進的解。通過在一個給定的調(diào)度計劃中迭代地推送和填充任務(wù)，實現(xiàn)試圖改進初始解的效果。該算法在改善諸如HEFT或HCPT等列表調(diào)度算法生成的初始解方面特別好，因為時隙堆棧操作修復(fù)了列表調(diào)度算法的主要缺點。最后通過實驗仿真過程，對所提算法的有效性進行了驗證。下一步研究，主要集中在應(yīng)用系統(tǒng)開發(fā)以及算法理論分析兩個角度，對所提算法進行深入拓展。