資源約束條件下任務(wù)調(diào)度算法研究

路程昭, 龔建興, 朱 雷, 劉 權(quán)

(國防科技大學智能科學學院, 湖南 長沙 410073)

0 引 言

資源約束條件下的任務(wù)調(diào)度問題(resource-constrained task scheduling problem, RCTSP)是一個涉及眾多領(lǐng)域的關(guān)鍵問題,比如并行計算、軟件開發(fā)和工程建造等。特別在應(yīng)急管理領(lǐng)域(如地震救援和突發(fā)公共衛(wèi)生事件),該問題是影響應(yīng)急處置效果的核心問題。RCTSP通常存在任務(wù)之間關(guān)系復雜、資源緊缺或補充不及時的特點,被證明是NP完全問題[1],復雜度高,實現(xiàn)高效任務(wù)調(diào)度和資源分配難度大。

針對RCTSP,國內(nèi)外學者已經(jīng)進行了大量的研究,涉及云計算[2-5]、分布式系統(tǒng)[6-7]、流水線生產(chǎn)[8]等多個領(lǐng)域。研究內(nèi)容還包括問題的分析、建模、求解、應(yīng)用等多個方向,例如,Orr[9]基于分配排序模型,提出了一種狀態(tài)空間模型,用于解決存在重復任務(wù)的最優(yōu)調(diào)度問題,任務(wù)重復調(diào)度可以縮短時間表總長度,并且可以給出最佳的任務(wù)重復計劃;Krishnakumar[10]提出了一種基于模仿學習的方法,用于在處理無線通訊和雷達系統(tǒng)應(yīng)用程序的多核心平臺進行任務(wù)調(diào)度,通過提供一個分層學習框架,從已開發(fā)的任務(wù)調(diào)度策略學習,最大程度減少應(yīng)用程序執(zhí)行時間;田啟華[11]采用多目標理想法構(gòu)造評價函數(shù),選擇最優(yōu)任務(wù)調(diào)度方法;Wang[12]建立了一種新型的分布式成像衛(wèi)星緊急任務(wù)多目標動態(tài)調(diào)度模型,提出了一種綜合考慮任務(wù)合并、后移、復原的動態(tài)調(diào)度算法;Yuan[13]根據(jù)早期樹對所有任務(wù)進行分組,對于關(guān)鍵活動和非關(guān)鍵活動采用不同的優(yōu)化算法;Lin[14]針對多技能資源受限項目調(diào)度問題提出一種遺傳規(guī)劃超啟發(fā)算法,將遺傳程序作為管理低級啟發(fā)式的高級策略;Kosztyanzt[15]研究了靈活項目管理的調(diào)度方法,提出了一種基于矩陣的方法,包含靈活任務(wù)依賴性和未定補充任務(wù)完成情況,處理新的未調(diào)度任務(wù),討論了傳統(tǒng)的多模式資源受限項目調(diào)度問題;Ali[16]提出了一種過濾矩陣方法,將大規(guī)模工作流劃分為子工作流以提高調(diào)度的效率。

關(guān)鍵路徑技術(shù)同樣在任務(wù)調(diào)度相關(guān)領(lǐng)域得到廣泛應(yīng)用,Abrishami[17]提出了基于部分關(guān)鍵路徑的工作流調(diào)度算法,遞歸計算以當前節(jié)點為結(jié)束的關(guān)鍵路徑;張艷[18]提出了一種新的基于關(guān)鍵路徑的遞歸調(diào)度算法,對調(diào)度節(jié)點進行遞歸選擇,結(jié)合它的后繼任務(wù)確定最佳時間槽;Takakura[19]對經(jīng)典的關(guān)鍵路徑方法進行改進,在目標完成時間內(nèi)使過程完成概率最大化,并利用生產(chǎn)系統(tǒng)中的歷史數(shù)據(jù)來處理不確定的任務(wù)工期;柳玉[20]分析最長關(guān)鍵路徑算法,提出一種運用結(jié)點信息流量減少CPU空閑時間碎片的并行任務(wù)調(diào)度優(yōu)化算法;Wang[21]針對多模式資源受限的項目調(diào)度問題提出了7個離散時間模型,擴展了關(guān)鍵路徑方法,以解決替代性先決條件活動的情況;Ramezani[22]提出了一種基于啟發(fā)式的動態(tài)關(guān)鍵路徑感知調(diào)度技術(shù),用于在多現(xiàn)場可編程門陣列系統(tǒng)上調(diào)度任務(wù);Maurya[4]使用有效關(guān)鍵路徑,提出一種基于聚類的調(diào)度算法,用于最小化給定應(yīng)用程序的調(diào)度長度。上述文獻均在關(guān)鍵路徑技術(shù)的基礎(chǔ)上運用各自提出的方法解決實際問題。

在現(xiàn)有文獻中[15,23-24],RCTSP又被稱之為資源約束條件下項目調(diào)度問題(resource-constrained project scheduling problem, RCPSP)?？傮w來看,該問題已經(jīng)有了大量的研究。但是目前已有的算法在考慮資源約束時,通常將單個任務(wù)所需的資源考慮為固定量,沒有考慮在資源不足時執(zhí)行任務(wù)產(chǎn)生的效果和影響;RCTSP的研究多是從避免資源沖突角度出發(fā),對已產(chǎn)生資源沖突的消解研究相對較少;另外目前鮮有在地震救援情景問題上采用任務(wù)調(diào)度算法并驗證有效性的研究。

針對現(xiàn)有問題,本論文的工作如下。

(1) 本文基于工作流圖模型,完成了對資源約束條件下任務(wù)調(diào)度的建模,提出了任務(wù)調(diào)度與資源沖突消解的框架。

(2) 本文提出了兩種任務(wù)調(diào)度算法,實現(xiàn)對調(diào)度過程中資源沖突的消解:一種是通過任務(wù)關(guān)鍵度確定優(yōu)先級,并基于貪心策略和調(diào)整工作流圖拓撲結(jié)構(gòu)方法的算法;另一種是采用彈性資源調(diào)度的方法,為產(chǎn)生資源沖突的任務(wù)分配現(xiàn)有不充足資源的任務(wù)調(diào)度算法(task scheduling algorithm based on elastic resources, ER)。

(3) 本文通過一個地震救援的案例背景,驗證了本文提出的資源約束條件下任務(wù)調(diào)度算法的可行性,并通過隨機生成的算例,將本文提出的算法與兩類RCPSP典型求解方法中的代表性算法進行對比。

1 問題描述

RCPSP主要面對復雜的情景下,存在先后邏輯順序、可能產(chǎn)生資源沖突的一系列任務(wù)的調(diào)度。任務(wù)調(diào)度主要涉及任務(wù)優(yōu)先級確定、開始時刻安排、資源分配等問題,由于問題本身的復雜性或時間緊迫性,其求解存在一定的困難,因此需要建立模型對此類問題進行描述,設(shè)計符合相應(yīng)需求的算法。

定義 1前驅(qū)任務(wù)和后繼任務(wù)。對于

?vi,vj∈V,?eij>0

(1)

定義 3截止時間。整個項目所有任務(wù)執(zhí)行完畢所需要時間定義為截止時間,記作T。

(2)

(3)

DAG中每個節(jié)點包含任務(wù)所需資源、任務(wù)所需時間、最早開始時間、最晚開始時間4個參數(shù),工作流圖的表示如圖1所示。

圖1 包含4個參數(shù)的工作流程圖Fig.1 Workflow diagram with four parameters

(4)

2 模型構(gòu)建

2.1 關(guān)鍵任務(wù)的確定

定義 6關(guān)鍵任務(wù)。定義工作流中,對項目整體完成存在顯著影響效果的任務(wù)為關(guān)鍵任務(wù)。例如,在地震救援過程中,關(guān)鍵任務(wù)通常指對救援進程起決定性作用的任務(wù):交通要道搶修、現(xiàn)場指揮部建立等救援過程中的核心任務(wù)。

在不考慮資源約束的工作流圖中,關(guān)鍵路徑上的任務(wù)執(zhí)行時間決定了整個項目的截止時間,因此常把關(guān)鍵路徑上的任務(wù)作為關(guān)鍵任務(wù)。而在考慮資源約束的條件下,可能存在非關(guān)鍵路徑上的任務(wù)對整個項目完成的影響更大的情況。文獻[11]提出用任務(wù)執(zhí)行的成功率作為關(guān)鍵任務(wù)的確定方法;文獻[18]采用遞歸計算動態(tài)關(guān)鍵路徑;文獻[25]采用預(yù)先設(shè)定的優(yōu)先級判斷任務(wù)的關(guān)鍵程度?？梢钥闯?關(guān)鍵任務(wù)的確定不僅是一個定性分析的過程,而且需要定量分析的手段,本文提出關(guān)鍵度的概念來描述任務(wù)的關(guān)鍵程度。

定義 7關(guān)鍵度。任務(wù)的關(guān)鍵度定義為:設(shè)任務(wù)執(zhí)行時間增加1,項目截止時間增加的量,記作δi,計算如下:

(5)

資源約束下的任務(wù)調(diào)度問題存在一定復雜性,若計算n個任務(wù)中每個任務(wù)的關(guān)鍵度,則時間復雜度為O(n2),計算量隨著任務(wù)數(shù)的增加快速增長,無法適應(yīng)例如地震情景下的復雜性、決策快速性要求。因此，選擇使用每個任務(wù)相關(guān)參數(shù)來估計任務(wù)的關(guān)鍵度,算法的時間復雜度降為O(n)。

本文通過構(gòu)建評估函數(shù)來估計工作流中任意任務(wù)的關(guān)鍵性,評估函數(shù)E(vi)表示如下:

(6)

上述評估函數(shù),綜合考慮了可能對任務(wù)關(guān)鍵性產(chǎn)生影響的量,其中η、λ、μ、σj為每個量對應(yīng)的權(quán)重系數(shù)。權(quán)重系數(shù)可以通過經(jīng)驗估計來計算,理想情況下,使得對于所有δa<δb都存在E(va)

2.2 資源約束條件下任務(wù)調(diào)度

由于RCTSP中任務(wù)存在關(guān)聯(lián)和前后邏輯關(guān)系,并且同一時間內(nèi)的資源數(shù)量有限,多項任務(wù)同時開展可能產(chǎn)生資源沖突,需要進行沖突的消解。任務(wù)調(diào)度可以看作是為各個任務(wù)在合適的時間,分配一定量資源的過程。通過調(diào)度實現(xiàn)目標函數(shù)的最優(yōu)化,并且保證滿足約束條件,可以用線性規(guī)劃方程[19]來表示:

(7)

(8)

式中:pi和αi分別表示任務(wù)i所需要的成本和相應(yīng)的加權(quán)系數(shù),式(8)第1行表示關(guān)鍵路徑上任務(wù)執(zhí)行時間和,小于截止時間Td;第2行表示在任意時刻τ的m種資源剩余數(shù)量不為負;bk表示任務(wù)k的開始時刻,cl表示任務(wù)l的完成時刻；第3行表示任務(wù)的完成時刻,大于其所有前驅(qū)任務(wù)最大完成時刻,限制每個任務(wù)在其前驅(qū)任務(wù)完成后才能開始;第4行限制任意任務(wù)i開始時刻不小于0時刻,且救援任務(wù)截止時間大于0。

2.3 彈性資源條件下任務(wù)調(diào)度

通常在任務(wù)調(diào)度問題中,任務(wù)需求資源數(shù)量等于系統(tǒng)分配給任務(wù)的數(shù)量。而在一些實際問題中,資源不充足條件下,任務(wù)依然能夠開始。例如,地震災(zāi)害發(fā)生的初期,地震救援所需要的資源很難完全得到滿足,考慮到救援活動的緊迫性,通常選擇將現(xiàn)有資源先全部投入使用,等待后續(xù)救援。利用這種思想,本文提出為任務(wù)彈性分配資源的方法。

(9)

f(ri)可以分為兩部分,一部分為每種資源量變化獨立對任務(wù)執(zhí)行時間產(chǎn)生影響;另一部分為幾種資源變化共同作用對任務(wù)執(zhí)行時間產(chǎn)生影響。上述函數(shù)的具體形式通常與任務(wù)和資源的具體性質(zhì)相關(guān)。例如:地震救援中搬運作業(yè),通過增加救援力量人數(shù),可以加速任務(wù)完成,而實施挖掘作業(yè),必須同時增加挖機和駕駛員的數(shù)量才能加速任務(wù)的完成。

另外,任務(wù)的執(zhí)行時間與彈性分配的資源數(shù)量并不是線性關(guān)系,當達到最短任務(wù)執(zhí)行時間后,無法繼續(xù)通過分配資源的方式減少任務(wù)的執(zhí)行時間,而繼續(xù)增加資源只能增大任務(wù)完成的成本。例如,救援過程中,在狹窄范圍內(nèi)搜救幸存者時,不會因為投入更多搜救設(shè)備而提升任務(wù)執(zhí)行效率。圖2所示曲線表示該情境中,資源彈性分配的數(shù)量和任務(wù)執(zhí)行時間、消耗成本之間的關(guān)系。因此本文所采用的彈性資源調(diào)度算法,僅考慮為任務(wù)分配小于或等于原本所需數(shù)量的資源,以平衡截止時間和成本的關(guān)系。

圖2 彈性分配資源對任務(wù)的影響Fig.2 Impact of flexible resource allocation on tasks

3 算法介紹

3.1 實現(xiàn)資源沖突消解的任務(wù)調(diào)度算法

針對RCTSP中產(chǎn)生的資源沖突問題,本文從兩個角度出發(fā)進行資源沖突消解,避免在實際項目中因為資源沖突而產(chǎn)生連鎖反應(yīng),或是造成更大混亂,在資源不充足時依然可以保證項目有序且高效推進。

3.1.1 基于貪心策略和拓撲結(jié)構(gòu)的任務(wù)調(diào)度算法

本文提出一種基于貪心策略和拓撲結(jié)構(gòu)的任務(wù)調(diào)度(task scheduling algorithm based on greedy strategy and topological structure, GSTS)算法。GSTS算法首先利用第2.1節(jié)中的方法,計算各個任務(wù)的關(guān)鍵度,通過關(guān)鍵度作為啟發(fā)式信息,確定任務(wù)的優(yōu)先級,之后基于任務(wù)流圖和任務(wù)優(yōu)先級進行任務(wù)調(diào)度。

圖3 調(diào)整網(wǎng)絡(luò)拓撲結(jié)構(gòu)Fig.3 Adjusting the network topology

GSTS算法在任務(wù)開始執(zhí)行前進行對任務(wù)的調(diào)度,以貪心策略安排任務(wù)的開始時間,并通過提前調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)避免了任務(wù)開始后產(chǎn)生的資源沖突。GSTS算法最終輸出結(jié)果為經(jīng)過調(diào)整的工作流圖和各任務(wù)的開始時間點。

3.1.2 基于彈性資源的任務(wù)調(diào)度方法

當RCTSP中每個任務(wù)需求資源可彈性分配時,為解決任務(wù)調(diào)度中出現(xiàn)的資源沖突問題,同時降低整個項目的截止時間,提高資源的利用率,本文基于第2.3節(jié)提出的彈性資源下任務(wù)調(diào)度模型,提出了ER算法。

ER算法任務(wù)調(diào)度過程與任務(wù)執(zhí)行交替展開,當有任務(wù)結(jié)束時,ER算法均會進行資源的重新分配。ER算法輸出信息是為當前正在進行調(diào)度和已開始任務(wù)分配的資源量。

3.1.3 兩種任務(wù)調(diào)度算法的比較

本文提出的GSTS算法和ER算法分別適用于任務(wù)資源不能進行彈性分配和可以進行彈性分配的兩種情景,此外GSTS算法是得到任務(wù)調(diào)度方案和新的工作流圖后開始任務(wù)的執(zhí)行,而ER算法則是任務(wù)調(diào)度和任務(wù)執(zhí)行工作并行,未來可以實現(xiàn)動態(tài)任務(wù)的調(diào)度。

3.2 資源沖突下任務(wù)調(diào)度算法框架

針對資源沖突下任務(wù)調(diào)度問題,結(jié)合第3.1節(jié)所闡述的任務(wù)調(diào)度算法,在已經(jīng)確定任務(wù)工作流圖的情況下,通過設(shè)計相應(yīng)的任務(wù)調(diào)度算法來輔助任務(wù)調(diào)度決策,為了實現(xiàn)在資源約束條件下盡可能早地完成所有任務(wù),本文設(shè)計的任務(wù)調(diào)度算法框架描述如下。

步驟 1基于工作流圖和項目截止時間,遞推得到每個任務(wù)的最早開始時間和最晚開始時間。

步驟 2建立一個用來維護等待調(diào)度任務(wù)的列表Start-List,并將工作流圖的開始任務(wù)加入。

步驟 3更新待調(diào)度任務(wù)列表StartList中的任務(wù)順序。

步驟 4取出StartList中的第一個任務(wù),判斷是否滿足資源約束條件,若滿足進行步驟5,若不滿足則進行步驟6。

步驟 5根據(jù)取出任務(wù)的所需資源、執(zhí)行時間,占用系統(tǒng)中資源,并標記任務(wù)完成時間戳,加入待完成任務(wù)列表EndList,進入步驟7。

步驟 6判斷是否產(chǎn)生資源沖突,是則進入任務(wù)調(diào)度算法。

步驟 7返回步驟4,直到完成StartList中任務(wù)的遍歷。

步驟 8推進時間到EndList中最早完成的任務(wù)。

步驟 9釋放已完成任務(wù)所占用的資源,并將其后繼任務(wù)加入StartList。

步驟 10判斷出口任務(wù)是否完成,否則進入任務(wù)調(diào)度算法。

步驟 11判斷截止時間是否小于預(yù)期時間,是則成功完成任務(wù)調(diào)度,否則任務(wù)調(diào)度失敗。

整個算法框架的流程圖如圖4所示。

圖4 任務(wù)調(diào)度算法流程圖Fig.4 Task scheduling algorithm flowchart

4 案例分析

4.1 案例背景

地震發(fā)生后,現(xiàn)場具有復雜性和不確定性,震后救援涉及全社會、多部門的合作,需要對參與人員和相關(guān)資源進行準確協(xié)調(diào)。地震救援的任務(wù)包括救援隊伍機動、道路疏通、現(xiàn)場搜索、傷員救護等多個方面,無法確保獲取充足的任務(wù)所需資源。因此，地震救援任務(wù)調(diào)度可能直接影響地震救援能否按期完成,關(guān)系到是否可以有效減少生命和財產(chǎn)的損失[26-27]。本文將一次地震救援案例作為驗證任務(wù)調(diào)度算法的算例,驗證本文提出的任務(wù)調(diào)度算法的效果。

地震救援任務(wù)可以分為準備階段、機動階段、救援階段、撤離階段和總結(jié)階段,每個階段都有相關(guān)的典型任務(wù),各個任務(wù)的參數(shù)及關(guān)聯(lián)關(guān)系可以表示為如圖5所示的工作流圖。

圖5 地震救援任務(wù)工作流圖示例Fig.5 Example of an earthquake rescue mission workflow diagram

本案例中考慮的資源只考慮人力資源和救援器械兩種類型,人員和救援器械的總數(shù)分別為100和20。各個任務(wù)消耗的資源量和所需要的執(zhí)行時間如表1所示。

表1 地震救援任務(wù)相關(guān)屬性

4.2 實驗驗證

將案例的相關(guān)數(shù)據(jù)輸入算法,式(6)中η、λ、μ、σ1、σ2分別取2、5、0.5、0.1、0.5,通過評估函數(shù)計算得到各個任務(wù)的關(guān)鍵度,如表1所示。

對上述案例,在資源約束條件下,嚴格按照任務(wù)所需要的資源量進行分配,此條件下最優(yōu)的任務(wù)調(diào)度路徑,如圖6中甘特圖A所示。并分別使用本文提出的兩種任務(wù)調(diào)度算法:GSTS算法可以得到圖6中甘特圖B所示的結(jié)果。通過增加任務(wù)b到任務(wù)e和任務(wù)f到任務(wù)g對應(yīng)節(jié)點的邊(如圖6中點橫線所示),添加新的約束可以完成對資源沖突消解。ER算法的結(jié)果如圖6中甘特圖C所示,其中白色部分為對應(yīng)任務(wù)在資源不足的條件下開始。從對給定的地震救援案例分別使用GSTS算法和ER算法進行調(diào)度的結(jié)果來看,GSTS算法的任務(wù)截止時間僅比嚴格任務(wù)資源分配條件下最優(yōu)解(78 h)多2 h,ER算法則將任務(wù)截止時間壓縮到了68 h。

圖6 任務(wù)調(diào)度結(jié)果的甘特圖表示Fig.6 Gantt chart representation of task scheduling results

RCTSP建模和求解方法主要分為啟發(fā)式算法和元啟發(fā)算法兩大類[15,23-24,28-31]。針對兩類算法,從每一類中選取一種較有代表性的算法與本文提出的算法進行對比,分別是以最大資源工作容量(greatest resource work content, GRWC)作為規(guī)則的啟發(fā)式算法[30]和遺傳算法[31](genetic algorithm,GA)。

為了使得實驗結(jié)果更具有普遍性,利用隨機生成100個允許彈性分配任務(wù)資源的算例,進行對比試驗。各算例分別使用4種算法,得到項目的平均截止時間、人員利用率、救援器械利用率,各個量平均值直方圖并標注標準差誤差線如圖7所示。4種算法均采用C++編碼,在Intel Core i5-6300HQ的處理器上以2.3 GHz的速度運行,各個算法的運行時間如表2所示。

表2 不同算法運行時間

從圖7中對比實驗結(jié)果可以看出ER算法由于采用了彈性資源進行調(diào)度,平均截止時間、資源利用率都高于兩種典型算法,其中平均截止時間作為調(diào)度問題的關(guān)鍵性指標,比GA和GRWC算法分別降低了7.7%和11.4%,資源利用率也都存在一定程度的提高。而本文提出的GSTS算法,對比將任務(wù)時間和消耗資源作為啟發(fā)式信息的GRWC算法,截止時間下降了2.9%,兩項資源的利用率分別提高了2.7%、2.8%,而對比GA,GSTS算法的性能略有劣勢,但GSTS算法的時間復雜度明顯小于GA,更能適應(yīng)如地震救援等時間緊迫的調(diào)度情景,同時對比GA也更容易擴充節(jié)點,來應(yīng)對未來的動態(tài)任務(wù)調(diào)度問題。

圖7 算例分別使用各種算法所得結(jié)果對比Fig.7 Comparison of results obtained by using various algorithmsfor calculation examples

使用100個算例對比ER算法和GSTS算法,從結(jié)果來看,ER算法在85%的算例中有更低的截止時間。如果各個算例中資源不能進行彈性分配,ER算法則會退化成以任務(wù)先后順序為優(yōu)先級的算法。所得結(jié)果如圖8所示。

圖8 任務(wù)資源不能彈性分配條件下使用各種算法所得結(jié)果對比Fig.8 Comparison of results obtained by using various algorithms under the condition that task resources cannot be allocated flexibly

可以看出,GSTS算法在任務(wù)資源不能彈性分配時取得效果更優(yōu)。GSTS算法為任務(wù)調(diào)度與任務(wù)執(zhí)行串行,ER算法為任務(wù)調(diào)度與任務(wù)執(zhí)行并行,并且由于ER算法需要頻繁進行資源的重分配,在實際應(yīng)用中可能會產(chǎn)生更高的成本,因此需要根據(jù)現(xiàn)實情況需求,來合理選擇資源約束條件下的任務(wù)調(diào)度算法。

通過實驗結(jié)果可以看出,本文提出的任務(wù)調(diào)度算法,基于工作流圖解決了RCPSP,對比同類型算法有一定的優(yōu)越性。同時可以適用于地震救援問題,實現(xiàn)資源沖突的消解,使得地震救援活動盡可能快地完成。

5 結(jié) 論

本文基于工作流圖,綜合地震災(zāi)后救援的特點,對資源約束條件下任務(wù)調(diào)度問題進行了研究。本文選用工作流模型更好地描述了地震救援中各項任務(wù)之間的聯(lián)系及任務(wù)調(diào)度的過程,基于資源約束條件下任務(wù)調(diào)度框架提出了兩種任務(wù)調(diào)度方法:GSTS算法適用于任務(wù)資源必須符合需求的情景,使用評估函數(shù)估計任務(wù)關(guān)鍵度,具有計算簡便,信息綜合程度高的特點,利用貪心策略和改變工作流拓撲關(guān)系的方法實現(xiàn)資源沖突消解和任務(wù)調(diào)度;ER算法從彈性資源調(diào)度的角度出發(fā),提高了任務(wù)截止時間和資源利用率。兩類算法和同類算法相比具有一定的優(yōu)勢,存在各自適合的情景,并與本文提出的地震情景相適應(yīng)。

本文未來的工作主要從以下幾個方面開展:研究本文提出的任務(wù)調(diào)度算法在動態(tài)情景中的應(yīng)用,提升算法的動態(tài)性能;進一步明確資源約束條件下項目調(diào)度問題的內(nèi)在機理,針對不同運用場景的不同特征,優(yōu)化調(diào)整現(xiàn)有模型和任務(wù)調(diào)度算法;繼續(xù)優(yōu)化資源約束下任務(wù)調(diào)度算法的性能,使得在有限時間內(nèi)可以達到或更接近理論最優(yōu)解。