国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2021-11-29 05:52路程昭龔建興
關(guān)鍵詞:任務(wù)調(diào)度關(guān)鍵救援

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

(國(guó)防科技大學(xué)智能科學(xué)學(xué)院, 湖南 長(zhǎng)沙 410073)

0 引 言

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

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

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

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

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

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

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

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

1 問(wèn)題描述

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

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

?vi,vj∈V,?eij>0

(1)

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

(2)

(3)

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

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

(4)

2 模型構(gòu)建

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

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

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

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

(5)

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

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

(6)

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

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

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

(7)

(8)

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

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

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

(9)

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

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

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

3 算法介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟 1基于工作流圖和項(xiàng)目截止時(shí)間,遞推得到每個(gè)任務(wù)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間。

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

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

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

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

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

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

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

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

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

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

整個(gè)算法框架的流程圖如圖4所示。

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

4 案例分析

4.1 案例背景

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

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

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

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

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

4.2 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

表2 不同算法運(yùn)行時(shí)間

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

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

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

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

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

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

5 結(jié) 論

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

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

猜你喜歡
任務(wù)調(diào)度關(guān)鍵救援
硝酸甘油,用對(duì)是關(guān)鍵
緊急救援
高考考好是關(guān)鍵
3D打印大救援
基于改進(jìn)NSGA-Ⅱ算法的協(xié)同制造任務(wù)調(diào)度研究
基于時(shí)間負(fù)載均衡蟻群算法的云任務(wù)調(diào)度優(yōu)化
云計(jì)算環(huán)境中任務(wù)調(diào)度策略
云計(jì)算中基于進(jìn)化算法的任務(wù)調(diào)度策略
救援行動(dòng)
生意無(wú)大小,關(guān)鍵是怎么做?