韋智勇 楊曉武

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

0 引 言

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

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

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

1 問題分析

1.1 調(diào)度過程描述

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

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

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

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

1.2 服務資源描述

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

NS=

(1)

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

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

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

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

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

1.3 任務需求描述

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

TS=

(2)

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

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

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

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

P={p1,p2,…,pm}：任務優(yōu)先級集合，pi表示taski的優(yōu)先級系數(shù)。

2 模型構建

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

表1 部分符號說明

(3)

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

(4)

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

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

(5)

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

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

(6)

約束2：任務的執(zhí)行時段應處于其允許執(zhí)行窗口中，占用資源時段應處于其所分配服務節(jié)點的可用時間窗口內(nèi)。

(7)

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

(8)

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

(9)

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

(10)

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

(11)

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

3 算法設計

3.1 基本結(jié)構

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

圖1 求解算法的主要構成

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

Step1主控算法接收任務需求隊列，則觸發(fā)規(guī)劃活動；

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

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

Step4主控層評估規(guī)劃結(jié)果，若決定繼續(xù)迭代，轉(zhuǎn)入Step 2；否則，直接輸出規(guī)劃方案，算法結(jié)束。

3.2 IPSO算法

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

3.2.1粒子編碼規(guī)則

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

(12)

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

(13)

3.2.2位置更新方式

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

(14)

(15)

(16)

3.2.3基于云模型的變異策略

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

(16)

(17)

(18)

3.3 CAS策略

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

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

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

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

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

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

定義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 實驗分析

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

4.1 測試場景設置

批量生成場景數(shù)據(jù)，調(diào)用不同算法進行實驗，以統(tǒng)計指標的平均值作為測試結(jié)果，場景要素的設置方法如下：

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

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

表2 服務資源的設置情況

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

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

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

表3 測試算法的組合方式

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

4.2 算法的搜索質(zhì)量分析

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

(a) 任務滿足率

(b) 資源使用率圖2 不同任務規(guī)模下的調(diào)度結(jié)果對比

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

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

4.3 算法搜索速率分析

在不同任務強度下測試算法的運算時間，統(tǒng)計結(jié)果如圖3所示。

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

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

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

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

t=-7.597 7+0.086 6m

(20)

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

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

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

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

5 結(jié) 語

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