基于分層優化的資源受限系統任務拆分調度方法

韋智勇 楊曉武

1(南寧職業技術學院 廣西 南寧 530008)2(中南大學機電工程學院 湖南 長沙 410083)

0 引 言

當前，資源受限系統[1-3]調度問題廣泛存在于企業生產和社會實踐中，對其研究的重要性和必要性不言而喻。一般而言，資源受限系統調度問題是以若干任務需求為處置對象，以消耗有限的服務資源為代價，在滿足一定使用規則前提下，尋找能夠促使特定指標得以優化的可行方案[4-5]。通常情況下，資源受限系統調度問題屬于NP-hard問題，具有明顯的復雜性特征。許多學者致力于為其尋找高效求解算法，通過調整任務編排方案以最大化資源使用效益。在此過程中，啟發式算法和群智能算法應用普遍。

近年來針對資源受限系統調度問題的研究較多，例如，張憶文等[6]以并行處理器的節能調度策略為研究背景，在考慮任務執行時間與CPU處理速率為非線性關系的情況下，建立任務調度模型，并結合動態電壓調節技術和功耗管理技術設計出低能耗資源調配算法。何杰光等[7]針對資源受限系統調度問題提出一種動態多樣性群智能算法，主要思路是采用兩點交叉算子和變異算子進化個體，基于精英保留策略優化種群，算法能夠在全局搜索和局部優化之間進行平衡。GABREL等[8-9]對成像衛星觀測任務調度問題開展研究，通過抽象約束條件建立出任務規劃模型，并采用加權有向無環圖方法進行求解。Arnaout等[10]分析了無聯系并行機的調度策略，將蟻群算法ACO(Ant colony optimization)應用于問題求解，通過兩階段問題轉換，獲取最短任務完成時長的優化方案。在上述研究中，共性的基本假設之一是任務不可拆分，即每個任務若可被安排執行，只能一次完成，執行過程不能停頓。但是實際應用中，對長耗時任務進行切割以提升滿足概率是被允許的。此外，任務切割還可以更好地利用調度過程中產生的碎片化資源，提升資源利用率。

本文針對任務可拆分條件下的資源調度方法開展研究，探討采用何種切割方式提升任務滿足概率。為保證調度效果，采用改進粒子群算法IPSO(Improve particle swarm optimization)[11-13]進行全局搜索。為降低資源使用的沖突程度，在執行時段優選時引入沖突規避策略CAS(Confliction avoid strategy)。文中給出了沖突集的概念，構建了沖突度模型。通過對比測試，對文中所提出方法的有效性進行了驗證。

1 問題分析

1.1 調度過程描述

對于一個完備的資源調度系統[14-15]，應至少包含若干服務節點(服務資源)和任務需求(服務對象)，調度過程可從以下角度進行描述：

(1) 從服務資源的角度描述。在初始時刻，各服務節點均為空閑狀態。調度開始后，規劃器實時獲取各服務節點的繁忙狀態，根據一定規則挑選任務指派給服務節點。獲取任務的服務資源被占用一定時長，完成服務后再轉入空閑狀態。

(2) 從服務對象的角度描述。在調度開始前，不同用戶提交的資源使用申請匯聚形成待調度任務隊列?？蓾M足的任務匯入等待服務任務隊列，到達預定服務時限后轉入服務隊列接收處置，服務完畢后再轉入完成服務任務隊列。在此過程中，可對部分任務進行拆分，通過化整為零方式執行，提升任務滿足可能性。

結合實際應用背景，資源調度過程通常追尋特定優化目標。從服務資源的角度考量，資源利用率最大化是追求的重要指標。從服務對象的角度考量，任務滿足率一般作為評價標準，這兩項指標存在關聯性，即高任務滿足率往往對應著高資源利用率。但對于資源受限系統而言，通常存在服務資源稀缺的情況，即系統的服務能力僅能滿足部分而非全部服務需求，這就要求設計合理的資源調配方法，使有限的服務資源得到高效利用。采用任務拆分方式，能夠有效利用破碎化的資源時段，促使原本不可滿足的任務得以執行。在此過程中，如何選擇拆分對象，以何種粒度拆分是必須解決的問題。

1.2 服務資源描述

考慮資源受限系統服務節點異構，具體表現為狀態準備時間、任務處置速率、狀態恢復時間存在差異。采用五元組對服務節點進行形式化描述，表示為：

NS=

(1)

Node={node1,node2,…,noden}：服務資源集合，nodei為所有資源中的第i個服務節點，n為服務節點的數量；

TW={tw1,tw2,…,twn}：可用時間窗口集合，twi=[twbi,twei]為nodei的可用時段，twbi和twei分別為twi的起始時間和結束時間；

SP={sp1,sp2,…,spn}：任務處理速率集合，spi為nodei的任務處置速率；

TP={tp1,tp2,…,tpn}：狀態準備時間集合，tpi為nodei開始任務前所需的狀態準備時間；

TR={tr1,tr2,…,trn}：狀態恢復時間集合，tri為nodei完成任務后，再開展下一次任務前所需的狀態恢復時間。

1.3 任務需求描述

對用戶提交各種請求進行規范化處理，形成標準化待任務需求。本文考慮的任務需求均為相互獨立的無關聯任務，采用五元組對服務節點進行形式化描述，表示為：

TS=

(2)

Task={task1,task2,…,taskm}：任務需求集合，taski為第i個任務，m為任務數量；

TA={ta1,ta2,…,tam}：任務允許執行最早時間集合，tai表示taski允許被執行的最早時刻；

TD={td1,td2,…,tdm}：任務執行截止期集合，tdi表示taski的執行截止期；

DL={dl1,dl2,…,dlm}：任務數據量集合，dli表示taski的指令長度；

P={p1,p2,…,pm}：任務優先級集合，pi表示taski的優先級系數。

2 模型構建

任務規劃的結果是完成服務資源與任務需求匹配，形成合理的規劃方案，而構建資源調度模型是實現該目標的前提條件，其主要由決策變量集，優化目標集，約束條件集等要素構成。為便于后續描述，表1給出部分符號說明。

表1 部分符號說明

(3)

決策變量Y=[yi]用于標識任務的可執行性，明確任務是否分配資源，賦值方法如下：

(4)

式中:yi=1表示taski被分配資源(安排執行)；yi=0表示taski未被分配資源(拒絕執行)。

決策變量ETW=[]用于標識任務的有效服務時段。對于staski,j，其資源占用時段與有效服務時段存在以下關系：

(5)

在籌劃任務規劃方案階段，所需遵循的主要約束條件如下：

約束1：如果任務被安排執行(yi=1)，對其累計有效服務時長不低于所需最少保障時間。

(6)

約束2：任務的執行時段應處于其允許執行窗口中，占用資源時段應處于其所分配服務節點的可用時間窗口內。

(7)

約束3：若任務被分解執行，其子任務不能被并行處理。

(8)

約束4：資源具有獨占性，即每個服務節點同一時刻最多處理一個任務(子任務)。

(9)

約束5：若安排任務執行(yi=1)，其子任務應當全部得到滿足。

(10)

本文考慮以任務滿足率作為主要優化目標，以資源利用率為次要優化目標，表示為：

(11)

式中：Q1、Q2為X和Y的可行域；GT(X)為可用服務資源的利用率；GR(Y)為考慮優先級后的加權任務滿足率。

3 算法設計

3.1 基本結構

本文在算法設計中引入了分層優化的算法結構，這是基于兩點考慮：一是本文研究的問題既要考慮傳統的任務資源匹配問題，還要考慮任務切分問題，所考慮的約束存在關聯性，這增加了問題求解難度。采用分層優化的方法可以化繁為簡，分而治之，更容易工程實現。二是從求解效率上來看，任務資源匹配問題和任務切分問題存在強耦合關系，若采用整體優化方式，搜索解空間較大。采用分層優化方式可逐層消減解空間規模，有利于有化解的快速產生。整體算法結構包括主控層、決策層和邏輯層，如圖1所示。

圖1 求解算法的主要構成

主控層負責掌控算法狀態，控制迭代過程；決策層用于選擇搜索方向，產生任務指派順序；邏輯層負責挑選拆分任務，解算有效服務時段，具體生成任務規劃方案。算法的基本流程如下：

Step1主控算法接收任務需求隊列，則觸發規劃活動；

Step2決策層采用IPSO算法優化任務指派序列，并將結果傳遞給邏輯層；

Step3邏輯層完成約束消解，對決策變量X、Y、ETW賦值，并傳遞給主控層；

Step4主控層評估規劃結果，若決定繼續迭代，轉入Step 2；否則，直接輸出規劃方案，算法結束。

3.2 IPSO算法

經典PSO算法的基本思想是通過驅動粒子以位移的方式搜索問題解空間，而個體根據種群間的交互信息確定移動方向和速度。其中，每個粒子均表示決策層的一個方案，種群挑選個體最佳位置作為群體最優位置。

3.2.1粒子編碼規則

設種群由SN個粒子構成，其中pari為種群中的第i個粒子，其在第t次進化時的位置向量為：

(12)

例如，隨機生成一個粒子pari，其位置向量及表示的任務指派序列為：

(13)

3.2.2位置更新方式

首先給出種群的適應度函數，用于評估粒子所在位置的優劣，如下所示：

(14)

(15)

(16)

3.2.3基于云模型的變異策略

為避免種群陷入早熟，引入變異操作。首先借鑒云模型產生變異概率，然后根據個體適應度挑選變異對象。

(16)

(17)

(18)

3.3 CAS策略

針對決策層傳遞的任務指派序列，利用CAS策略進行解析，生成具體的資源調配方案。在此過程中，需根據任務狀態構建若干集合：

WSTSet：等待規劃任務集，用于存儲尚未參與調度的(子)任務隊列；

WETSet：等待執行任務集，用于存儲已分配資源但未執行的(子)任務隊列；

RETSet：無法滿足任務集，用于儲存已參與調度但未滿足的(子)任務隊列；

FETSet：完成執行任務集，用于儲存執行完畢的(子)任務隊列。

在上述集合中，WSTSet是規劃系統的處置對象，可滿足的任務移至WETSet中，無法滿足的任務移至RETSet中，而FETSet中的元素對對規劃過程無影響。

定義1對于taski∈WSTSet和給定時間窗口TS，稱taski在TS中具有需求沖突，記為Conf(TS,taski)=1，若滿足以下關系：

TS∩[tai,tdi]≠?

(19)

算法1Pseudocode ofCAS

01:DeletetaskifromWSTSet;

02:fornodekinNode

03:FTWSik←[tai,tdi];

04:forstaski′,j′inWETSet

05:ifxi′,j′k=1then

06:FTWSik←FTWSik∩([tsbi′,j′,tsei′,j′])C;

07:endif

08:endfor

09:forftwi,jkinFTWSik

10:ifspan(ftwi,jk)

11:Deleteftwi,jkfromFTWSik;

12:else

13:hdci,jk←0;

14:fortaski′inWSTSet

15:hdci,jk←hdci,jk+Conf(ftwi,jk,taski′);

16:endfor

17:endif

18:endfor

19:VTWSik←FTWSik;

20:endfor

21:Return;

算法2Pseudocode ofPTC

01:fortaskiinWSTSet

02: Calculate i=1,2,…，nby 算法1;

03: SortVTWi,jkbyHDCSi,jkin increasing order;

04:Rem_len←dli,dni←0,yi=0;

10:tsbi,dni=tvbi,dni+trk′,tsei,dni=tvei,dni+tpk′;

11:tsli,dni←tsei,dni-tsbi,dni,tvli,dni←tvei,dni-tvbi,dni;

12:Rem_len←Rem_len-tvei,dni+tvbi,dni;

13:endwhile

14:ifRem_len=0then

15:yi←1;

16:else

17:dni←0;

18:tsli,j←Null,tvli,j←Null,tvbi,j←Null,tvei,j←Null,tsbi,j←Null,tsei,j←Null,xi,jk←0,j=1,2,…，dni,k=1,2,…，m;

19:endif

20: LetX=[xi,jk],Y=[yi],ETW=[];

21:Return;

4 實驗分析

本節中模擬生成任務規劃場景，對文中所提方法的有效性進行對比分析。

4.1 測試場景設置

批量生成場景數據，調用不同算法進行實驗，以統計指標的平均值作為測試結果，場景要素的設置方法如下：

1) 整個任務規劃活動的周期跨度為24 h；

2) 設置3個服務節點，服務能力指標根據參數設置情況隨機生成，如表2所示。

表2 服務資源的設置情況

3) 任務數量為100～300個，任務數據量包括150～250 min、250～350 min、350～450 min三種類型，任務允許執行最早時間和截止期在規劃活動周期內隨機生成。

在求解方法設計時，同時嵌入了啟發式算法和智能優化算法。其中，啟發式算法用于快速提升解的質量，本文主要測試其有效性。IPSO算法單次運行時間較長，理論上而言，足夠長的迭代次數均能獲取較優的可行解，因此本文更關注其搜索效率。采用分步驗證方法進行實驗，測試內容主要包括以下兩項：

(1) 算法的搜索質量分析。主要是CAS策略和PTC規則的有效性。決策層固定使用IPSO算法，邏輯層引入Greedy策略和禁止任務切割FTC(Forbid task cutting)規則，與之前所提算法進行對比。主控層算法根據對比算法的組合方式命名，如表3所示。

表3 測試算法的組合方式

(2) 算法的搜索速率分析。主要是加入CAS策略和PTC規則后對算法運行時間的增量，以及IPSO算法的收斂速率。

4.2 算法的搜索質量分析

在不同任務強度下對比三種組合算法的實驗結果，統計指標包括任務滿足率和資源利用率，如圖2所示。

(a) 任務滿足率

(b) 資源使用率圖2 不同任務規模下的調度結果對比

從圖2可以看出，隨著任務強度的增加，任務滿足率迅速下降，而資源使用率在快速增長后趨近平穩。系統資源的服務能力經歷了由充足到飽和的過程，說明所選測試場景能夠較為全面地呈現出多種供需狀態，具有一定的代表性。

根據測試結果，在不同測試場景下，IPSOPG的求解結果均優于IPSOFG，這是由于PTC規則通過任務切割能夠使原本無法滿足的任務得到執行，由此說明該策略的有效性；IPSOPC的求解結果均優于IPSOPG，這是優于在具體指派資源時，CAS策略能夠預見性的規避需求沖突，最大程度地保留后續任務的滿足機會，因而求解效果更好。綜上可以得出結論，CAS策略和PTC規則對于提升算法搜索質量是有效的。

4.3 算法搜索速率分析

在不同任務強度下測試算法的運算時間，統計結果如圖3所示。

圖3 不同任務規模下的算法耗時對比

從圖3可以看出，以IPSOPC算法的耗時最高，IPSOFG與IPSOPG算法的耗時接近。由此可以說明，采用FTC規則對于算法造成的負擔不顯著，而引入CAS策略會明顯增加算法的時間復雜度。為進一步分析CAS策略和FTC規則對算法搜索速率的影響，以IPSOFG算法為基準，分析其他兩種算法的相對搜索時間增量，如圖4所示。

圖4 相對搜索時間增量的變化趨勢

在圖4中，隨任務強度的增加，IPSOFG算法的搜索時間增量穩定處于較低水平，說明FTC規則對于算法搜索速率的影響較弱。IPSOPC算法搜索時間的增量呈線性變化，本文采用最小二乘法進行擬合，得到的近似關系式為：

t=-7.597 7+0.086 6m

(20)

由此可以說明，CAS策略雖會延緩算法的搜索速率，但該策略不會導致算法的搜索時間呈爆發式增長，其時間復雜度在可接收范疇。

IPSOPC為本文提出的主要算法，對算法中的種群適應度演變過程進行統計，以分析算法的搜索效率，如圖5所示。

圖5 種群適應度的演變過程

從圖5可以看出，種群在第1～7代進化明顯，在第7～23代進化平穩，在第23代后逐漸停止進化。說明IPSO算法在迭代早期能夠快速搜索解空間，獲取問題的初始優化解集。在迭代中期，能夠不斷提升種群適應度，持續改進優化解的質量。在迭代末期，能夠保持種群的穩定，對優化解集進行收斂?；谏鲜鲞^程，IPSO算法基本實現了在確保收斂前提下避免過早陷入局部最優的目標，能夠以較為高效的搜索速率獲得理想結果。

5 結 語

本文針對任務可拆分條件下的資源受限系統調度問題開展研究，以最大化任務滿足率和資源利用率為優化目標，建立了約束模型。為降低求解復雜度，在算法設計時，構建了多層求解結構，并分別提出了優化算法。其中，IPSO算法應用于決策層，該算法是在經典PSO算法的基礎上加入了部分改進策略，能夠避免種群陷入早熟。CAS策略和PTC規則被應用于邏輯層，用于服務資源的指派和任務執行時段的明確。在實驗部分，通過測試對文中所提方法的有效性進行了驗證。需要指出的是，本文所提算法仍有很大改進空間，后續將根據項目背景作進一步研究。