云制造環(huán)境下的兩級多任務調度

尹向兵,周 婷

(1.安徽警官職業(yè)學院 教務處,安徽 合肥 230031;2.安徽城市管理職業(yè)學院 商貿管理學院,安徽 合肥 230011)

隨著全球制造業(yè)的發(fā)展,云制造模式備受關注。云制造平臺作為云制造系統(tǒng)體系結構的一個重要組成部分,聚合了不同供應商所提供的分布式資源[1],并對它們進行集中式規(guī)劃管理,從而為客戶提供最佳的云服務[2-3]。然而,在大多數(shù)情況下,由客戶所提交上來的任務是十分復雜的,它們必須被分解為多個子任務,再由聚合的分布式資源進行處理。而分解后的子任務之間往往具有復雜的優(yōu)先級關系。同時,受不同資源能力的限制,并不是每個在平臺上注冊的資源都能滿足各種任務請求。因此,如何調度多個任務以及如何在考慮優(yōu)先級約束和資源服務資格的情況下調度所有必要的子任務,是云制造中一個困難且重要的問題。

迄今為止,已經有許多研究人員對云制造中的調度問題進行了研究,但只有少數(shù)人關注多任務的調度。而大規(guī)模定制會有多種多樣的需求,因此,關注異構多任務的調度更為實際、更為合理。先前的大部分相關工作都將多任務分解后的所有子任務視為相同的任務,并在它們之間進行無差別調度。這樣做可能導致單個任務需要花費很長時間才能完成。除此之外,需要完成的任務不止一項,并且不同任務之間可能存在利益沖突。因此,與其最小化某個任務的最大完工時間,不如最小化所有任務的平均完工時間。同時,從云制造平臺的角度來看,所有的請求也應該盡快完成,這樣,相關的資源服務不僅能得到高效利用,還有機會對即將到來的新任務集進行快速響應。所以,多個任務的總完成時間也應該最小化。

基于上述思路,本文提出了一種新的兩級調度模型,用于處理提交給平臺的多個任務調度請求。該模型包括任務級和子任務級調度,其目標是在考慮優(yōu)先級約束和資源能力約束的情況下,最小化每個復雜任務請求的最大完工時間。針對所提出的兩級調度模型,設計了兩種不同的解決方案進行比較,即兩級一優(yōu)化調度(two-level-one-optimization scheduling,TLOOS)和兩級二優(yōu)化調度(two-level-two-optimization scheduling,TLTOS)。這兩種方案都采用了Liao等[4]提出的有效改進蟻群算法并應用于子任務的調度。具體來說,TLOOS方法根據(jù)“先進先出”規(guī)則對多個任務進行排序,而TLTOS策略則是尋找一個接近最優(yōu)的任務序列,目標是最小化所有請求的總完成時間。為了評估所提出的模型和解決方案的優(yōu)點,隨后對隨機生成的數(shù)據(jù)進行了大量計算實驗。

1 相關工作

近年來,有關人員研究了云制造環(huán)境中的調度相關問題。許多研究從不同的角度處理調度問題,本文從任務數(shù)量、任務特征、調度方法、調度目標和優(yōu)化方法等角度對各項工作進行了總結。

對于多個復雜任務的調度已經研究了很多年。為了解決云設計資源調度問題,文獻[5]設計了一個調度模型,并通過遺傳算法實現(xiàn)。該算法使用了線性加權多目標定義的適應度函數(shù),以最小化成本和時間并最大化服務質量。文獻[6]在考慮任務優(yōu)先級約束和資源限制的情況下,開發(fā)了一種改進的遺傳算法,用于調度云制造中的多個簡單任務,目標是最小化最大完工時間。

上述所有論文的優(yōu)化方法都是基于單一目標或者將多目標轉化為單一目標。其他一些研究則關注多目標優(yōu)化。文獻[7]建立了一個基于云的拆卸系統(tǒng)的數(shù)學模型,該系統(tǒng)為多個請求提供拆卸服務,并應用多目標遺傳算法,以最小化總完工時間和總成本兩個優(yōu)化目標來求解該模型。文獻[8]提出了一種多目標優(yōu)化調度模型以提高可重構裝配線的生產效率,并采用基于距離排序粒子群優(yōu)化的有效方法對該模型進行求解,其目標是將裝配線改造成本降至最低,實現(xiàn)生產負荷均衡,并最大限度地減少工作量的延遲。

為了克服單獨優(yōu)化整個系統(tǒng)的局限性,文獻[9]提出了面向多任務的一個云制造服務組合與調度模型,該模型考慮了云制造的關鍵因素,如服務導向、物流參與和服務可用性的動態(tài)變化。文獻[10]建立了一個多任務調度模型,并用以客戶為中心的方法和綜合方法等不同的設計視角進行求解。

上述文獻中提出的任務調度策略都是集中式的。為了實現(xiàn)實時數(shù)據(jù)驅動的調度,文獻[11]提出了一種基于博弈論的云制造柔性作業(yè)車間調度問題的動態(tài)優(yōu)化模型。與集中式調度策略不同,該模型中的每臺機器都是一個活動實體,在考慮最小化負載指數(shù)和最大化利用率的情況下,請求處理任務以使其收益最大化。文獻[12]提出了一個支持RFID的實時制造執(zhí)行系統(tǒng),可以為計劃和調度決策提供實時數(shù)據(jù)。實時調度策略可以極大地消除調度與執(zhí)行之間的偏差,但需要依靠實時數(shù)據(jù),因此,實時調度并非總是可用的。基于以上情況,本文遵循集中式調度策略。

2 問題描述

考慮在調度期開始時提交給云制造平臺的n個任務。這n個任務根據(jù)接收到的順序被標記為T={T1,T2…Tn}。令w={w1,w2…wn}表示所有任務的工作負載集,即每個任務的數(shù)量。任務i可以分解為im個子任務,即Ti={ti1,ti2…tim}。對于每項任務,分解后的子任務的依賴關系不是簡單的序列結構,而是并行和序列結構的結合。此外,每個子任務只能由可用服務的子集來完成,具體可由式(1)來形式化描述。ESij(k)表示服務k對于任務i的子任務j的資格,當它等于1時,意味著服務k可以完成任務i的子任務j。

(1)

如上所述,不同的任務在子任務之間具有不同的優(yōu)先級關系,其約束形式可以表示為式(2)。RCjl表示子任務j和子任務l之間的關系約束。

(2)

影響每個子任務完成時間的因素有三種,即處理時間、設置時間和傳輸時間。處理時間是所選服務執(zhí)行每單位工作負載的某個子任務所花費的時間。如果任務i中的子任務j被安排在服務k上,那么單位工作負載的處理時間可以表示為Pij(k)。因此,總處理時間為PTij(k)=Pij(k)*wi。設置時間是指服務準備處理子任務的時間。傳輸時間指將已完成的先前子任務轉移到所選服務所在位置,以執(zhí)行后續(xù)子任務所需的時間,包括打包、文檔和運輸時間。假設服務始終可用,則服務k上任務i的子任務j的預測開始時間,即PSTij(k)可以用式(3)表示:

(3)

其中mn(k)指服務k在tij之前執(zhí)行的任務tmn。因此,STmn(k)ij(k)表示在服務k上從執(zhí)行任務tmn到tij的設置時間。服務k和服務g應遵循等式(4)中的約束。這意味著服務k應該完成子任務tmn和子任務tij,而服務g應該完成子任務til。

ESil(g)=ESij(k)=ESmn(k)=1

(4)

如果在服務k上的tij之前沒有執(zhí)行任務,則STmn(k)ij(k)=ST0ij(k),表示服務k上的tij的初始設置時間。FTil(g)是服務g處理的前一個子任務til的完成時間,其中,l∈preij,其中preij表示子任務tij的前一個子任務的集合,可以通過preij={l|l∈RCjl=1}獲得。TTil(g)ij(k)是將服務g執(zhí)行的任務til轉移到服務k執(zhí)行的任務tij所需的時間。如果服務g和k都由同一家企業(yè)提供,則TTil(g)ij(k)為零。

事實上,從任務i分解出來的子任務j的實際開始時間還取決于所選服務k的可用時間ATij(k),即服務k可用于處理當前請求的最早時間。因此,資源k處理任務i的子任務j的實際開始時間和結束時間(分別表示為ASTij(k)和FTij(k))計算如式(5)(6):

ASTij(k)=max(PSTij(k),ATij(k))

(5)

FTij(k)=ASTij(k)+PTij(k)

(6)

目標函數(shù)可以從完工時間、延誤成本和資源利用率等多個方面以不同的方式定義。本文采用的性能標準是最大完工時間,包括以下兩種:單個任務的最大完工時間和總任務的最大完工時間。

對于單個任務i,目標是最小化其所有子任務的最大完成時間,該時間可通過公式(7)計算,其中ASij(k)∈{ES|ESij(k)=1}。這意味著處理任務i的子任務j的實際服務k(用ASij(k)表示)屬于使ESij(k)等于1的集合。在式(7)中,i是一個從任務集T中選擇的任務。

(i=T1,T2,…,Tn)

(7)

從云制造平臺的角度來看,調度目標是找到一個完成所有任務的時間最短的方案,具體如式(8):

(8)

除了(1)和(2),優(yōu)化還受到附加約束,如式(9):

(9)

如果Prijcdk=1,FTij(k)≤ASTcd(k)

(10)

(11)

約束(9)意味著每個子任務應該只分配給一個合格的服務。在約束(10)中,Prijcdk=1表示任務i的子任務j被安排在任務c的子任務d之前的服務k上。約束(10)確保服務在任何給定時間只能執(zhí)行任務的一個子任務。約束(11)表示并非所有服務都能滿足任何請求,即對每個服務都有資格限制。

3 方法設計

3.1 一級調度方法

一級調度,也稱為一級優(yōu)化調度(one-level-one-optimization scheduling,OLOOS),即對所有任務分解得到的子任務在不違反優(yōu)先級關系的前提下進行無差別調度。在為子任務選擇服務時,必須考慮資源的資格,并非所有資源都可以用于每個子任務。子任務級調度被用作一級調度方案,其目標是在不考慮每個單獨任務完成時間的情況下盡早完成所有子任務。一級調度的目標函數(shù)如式(8)所示,這表示最小化所有任務的總完成時間。本文成功地驗證了蟻群算法ACO4STLS(ant colony optimization for subtask-level scheduling)在確定一級調度最優(yōu)解方面的有效性(具體細節(jié)見3.3節(jié))。

3.2 兩級調度方法

本文提出的兩級多任務調度方法包括任務級調度和子任務級調度。兩級調度包括三個部分:所有任務的排序、每個任務子任務的資源選擇和子任務的排序。任務級調度涉及第一部分,后兩部分由子任務級調度處理,不違反與每個任務相關的子任務的優(yōu)先級約束和服務資格。

根據(jù)該模型,多個任務的順序起著重要作用。因此,在上層,本文考慮了兩種任務級調度方法。第一種方法根據(jù)簡單的“先進先出”規(guī)則對所有任務進行排序。而為了探索更好的序列,以實現(xiàn)更短的總完工時間,第二種方法使用了ACO4TLS(ant colony optimization for task-level scheduling)算法進行任務級調度,將在3.3節(jié)中具體介紹。ACO4TLS算法能夠有效地分配每個任務的處理順序,目標是根據(jù)等式(8)最小化總完工時間。

基于本文提出的任務級和子任務級調度方法,得到了兩級多任務調度方法:兩級一優(yōu)化調度(TLOOS)方法和兩級二優(yōu)化調度(TLTOS)方法。

結合一級調度方法和兩級調度方法,上述三種調度方法的示意圖如圖1所示。具體地說,對于OLOOS,優(yōu)化目標是最小化整體完工時間,如式(8)所示。對于TLOOS方法,優(yōu)化目標是根據(jù)式(7)最小化每個單獨任務的完工時間,總完工時間是所有任務中的最大完工時間。另外,對于TLTOS,上層調度的優(yōu)化目標是最小化式(8)中所示的整體完工時間,而下層調度的目標是最小化式(7)中每個單獨任務的完工時間。

圖1 三種調度方法的框架

3.3 ACO4STLS和ACO4TLS

3.3.1 ACO4STLS

ACO4STLS算法是一種用于一級調度和二級調度下層的子任務調度方案。ACO4STLS算法基于文獻[3]中提出的改進ACO算法(IACO)。IACO是一個依賴于兩個向量的兩階段調度過程。第一個向量稱為分配向量,其大小與要調度的子任務數(shù)相同。因此,向量大小是一級調度中所有任務的子任務數(shù),而向量大小等于兩級調度中與被調度任務相關聯(lián)的子任務數(shù)。向量中的每個值表示分配給所選子任務的服務。第二個向量是子任務序列排列的向量,它也具有相同大小的子任務。為了得到可行的調度方案,需要兩個用于服務分配和子任務排序的概率矩陣。對于服務分配過程,服務k被分配到任務i的子任務j的概率矩陣如式(12)所示:

(12)

其中

(13)

其中,PTij(k)是服務k執(zhí)行任務i的子任務j的處理時間。

對于子任務排序的步驟,子任務j將在子任務i確定后安排,如式(14):

(14)

上述兩個概率矩陣中的信息素矩陣更新如式(15):

(15)

如前所述,屬于同一任務的子任務具有優(yōu)先約束。因此,子任務序列應該符合優(yōu)先約束。如果違反了優(yōu)先約束,則需要調整順序。ACO4STLS算法在一級調度方法中只調用一次,但調用次數(shù)與TLOOS方法中的任務數(shù)相同。

3.3.2 ACO4TLS

ACO4TLS用于TLTOS的上層調度。ACO4TLS與ACO4STL類似,但在以下方面有所不同。首先,如前所述,它們在目標函數(shù)上有所不同。其次,ACO4TLS中的候選解決方案是將一系列任務用向量表示,這與ACO4STLS中使用的第二個向量類似。然而,兩個向量的大小很可能不同。第三,ACO4TLS與ACO4STL排序部分的不同之處在于信息素矩陣和啟發(fā)式信息矩陣的更新方式。在ACO4TLS中,從任務i到任務j的信息素由以下等式更新:

τij(itr+1)=(1-ρ)τij(itr)+Δτij

(16)

式中,itr是迭代次數(shù)。Δτij的計算如式(17):

(17)

其中M是螞蟻的數(shù)量,Q是一個常數(shù)(在本文中設置為1),TMm是目前為止由螞蟻m構造的序列的最大完工時間。與經典的旅行商問題不同,任何一對任務之間都沒有明顯的啟發(fā)式信息。因此,將啟發(fā)式信息矩陣設置為單位矩陣。最后,與ACO4STL中的子任務排序不同,ACO4TLS中的任務排序沒有優(yōu)先級約束問題。TLTOS方法只是ACO4TLS和ACO4STL的組合。

4 實例分析

4.1 數(shù)據(jù)生成

為了評估和比較不同的多任務調度方法,生成數(shù)據(jù),通過改變服務數(shù)量、任務數(shù)量和每個任務的子任務數(shù)量來模擬不同規(guī)模的問題。服務的數(shù)量取三個值:4、8和12?？梢赃x擇每個服務來執(zhí)行多個子任務。任務的數(shù)量在三個級別上選取:4、8和12,而子任務的數(shù)量在8、10和12上有所不同。因此,總共可以形成33=27個問題大小的組合。受正交實驗設計的數(shù)據(jù)選擇策略的啟發(fā),從這27個組合中選擇了9個,即4s4t8st、4s8t10st、4s12t12st、8s4t10st、8s8t12st、8s12t8st、12s4t12st、12s8t8st、12s12t10st,以測試不同調度算法的有效性和效率。此外,表1總結了生成數(shù)據(jù)集的處理時間、設置時間、傳輸時間和工作負載的范圍。

表1 不同數(shù)據(jù)集的時間和工作負載范圍

4.2 蟻群算法參數(shù)

表2給出了子任務級調度中使用的ACO4STLS算法的參數(shù),以及任務級調度中使用的ACO4TLS算法的參數(shù)。[·]是整數(shù)運算。具體來說,對于兩級多任務調度,將螞蟻的數(shù)量設置為與每次調用ACO4STLS算法時的子任務數(shù)|ST|成正比,即|ST|等于任務i的子任務數(shù),即當前正在考慮的任務。另外,對于一級多任務調度,ST是所有任務的所有子任務集合。T的基數(shù)|T|等于調用ACO4TLS算法時要調度的任務數(shù)。對于每個問題,每個調度方法重復運行10次,以獲得關于最優(yōu)解質量的統(tǒng)計信息。

表2 不同方案中使用的ACO算法的參數(shù)

4.3 實驗結果及分析

測試結果從兩個角度組織和呈現(xiàn):單個任務的最大完工時間和所有任務的總完工時間。從單個任務的完工時間的角度出發(fā),分別計算了10次運行期間所有任務完工時間的平均值和標準偏差。由于每個數(shù)據(jù)集中都包含多個任務,因此,在每次運行中都會計算所有單個任務的最大完工時間的平均值和標準偏差。表3總結了不同調度方法的測試結果。從表3可以看出:

表3 不同調度方案得到的單個任務完工時間的均值和標準差的平均值

(1)兩級調度方法TLOOS、TLTOS在所有情況下都優(yōu)于OLOOS;

(2)在所有18個測試數(shù)據(jù)集中,TLTOS在16個數(shù)據(jù)集中得到低于TLOOS的平均值(以粗體突出顯示),而TLOOS在2個數(shù)據(jù)集中得到低于TLTOS的平均值。因此,TLTOS明顯優(yōu)于TLOOS。

從平臺的角度來看,如果一批計劃的所有任務都可以盡早完成,那么被調用的服務可以更快地開始處理下一批任務。因此,總任務的完成時間也非常重要。為了從平臺的角度比較不同調度方案的性能,在每次運行中計算完成每個仿真案例中所有任務的總完工時間。表4總結了批量完成10次以上的所有任務的最大完工時間的平均值和標準偏差。結果表明:

(1)當服務和任務數(shù)量較少時,TLOOS未能獲得比OLOOS和TLTOS更好的時效;

(2)當服務的數(shù)量較大時,TLTOS在整體完工時間上優(yōu)于其他兩個方案;

(3)上述觀察結果適用于從不同值范圍生成的兩組數(shù)據(jù),這意味著性能差異主要來自調度方案本身,對數(shù)據(jù)生成不敏感。

圖2顯示了三種方案在處理所選數(shù)據(jù)集(即組1的8s4t10st)時的收斂過程。對于每個調度方案,描繪了兩個收斂曲線:一個是所有單個任務完成時間的平均值,另一個是所有重復測試的總完成時間的平均值。結果表明:

(1)無論從整體完工時間還是單個完工時間的角度來看,所提出的兩級調度模型在大多數(shù)情況下都優(yōu)于一級調度模型;

(2)TLTOS的收斂速度低于TLOOS;

(3)所有配置文件都會收斂,表明設置的停止運行的迭代次數(shù)是足夠的。

總之,TLTOS不僅在最小化單個任務的最大完工時間方面優(yōu)于其他兩種調度方法,而且在最小化被調度的整批任務的最大完工時間方面也優(yōu)于其他兩種調度方法。然而,TLTOS的這種優(yōu)異性是以計算時間為代價的。TLTOS的復雜度高于其他兩種方法,這從表5所示的CPU時間可以看出?？梢杂^察到,在三種調度方案中,TLOOS占用的時間最短,而TLTOS占用的CPU時間最長。因此,對于希望以較低計算質量為代價獲得快速響應的請求,TLOOS方法相比于其他調度模式是更好的選擇。然而,在復雜的制造要求需要很長時間才能完成的情況下,縮短完工時間比增加CPU時間帶來的懲罰更重要。因此,在云制造環(huán)境中,使用TLTOS來尋找一個更好的、時間更短的時間表來調度多個復雜的請求是有意義的。

表5 不同調度方案對應的CPU時間的均值和標準差

5 結語

本文提出了一種新的兩級調度模型,在考慮子任務優(yōu)先約束和資源服務資格的情況下,描述了云制造環(huán)境下的多任務調度問題?；谠撃Ｐ?提出了兩種新的兩級調度優(yōu)化方法,即兩級一優(yōu)化方法和兩級二優(yōu)化方法。為了驗證所提出的模型和求解方法的有效性,將其與常用的一級調度模型和求解方法進行了比較。針對時間目標,基于隨機生成的不同規(guī)模的數(shù)據(jù)集進行了計算實驗。試驗結果表明,所提出的兩級調度模型在單個任務的最大完工時間以及所有任務的完工時間方面優(yōu)于一級調度模型,所提出的兩級二優(yōu)化調度方法也優(yōu)于其他兩種優(yōu)化方案。