王天日,張敏敏,劉 娟,2+,張鵬志

(1.太原理工大學(xué) 經(jīng)濟管理學(xué)院,山西 太原 030024;2.太原理工大學(xué) 省部共建煤基能源清潔高效利用國家重點實驗室,山西 太原 030024)

0 引言

隨著云計算、物聯(lián)網(wǎng)、大數(shù)據(jù)等技術(shù)的發(fā)展及其在制造領(lǐng)域中的滲透,李伯虎等[1]最早提出了“云制造”的概念。在這種生產(chǎn)模式下,生產(chǎn)企業(yè)將制造資源和制造能力發(fā)布到云制造平臺,平臺將這些資源虛擬封裝成云服務(wù),以便用戶按需獲取,從而有助于實現(xiàn)分布式社會化資源的高效配置,進而降低資源的使用成本。

近年來,云制造環(huán)境下面向多任務(wù)制造云服務(wù)組合與調(diào)度引起了廣大研究者的關(guān)注[2-4]。然而,大部分研究面向多任務(wù)需求,從制造云服務(wù)的服務(wù)質(zhì)量(Quality of Service,QoS)屬性進行建模與優(yōu)化求解。LI等[5]從任務(wù)角度建立了以時間、成本和服務(wù)質(zhì)量為優(yōu)化目標的云服務(wù)調(diào)度模型。ZHOU等[6]構(gòu)建了以服務(wù)質(zhì)量和能耗為目標的云服務(wù)組合模型,并設(shè)計了一種多目標進化算法獲得一組非支配解,以滿足不同顧客的偏好。該模型只考慮了同質(zhì)任務(wù)的組合問題,并未考慮制造系統(tǒng)中服務(wù)占用問題。以上研究中的任務(wù)并未涉及多個用戶層面的討論,針對多個用戶任務(wù)的研究還相對欠缺。基于此,ZHOU等[7]從用戶需求多樣化出發(fā)建立了云服務(wù)調(diào)度生產(chǎn)模型,設(shè)定每一任務(wù)分屬不同的用戶,未能考慮一個用戶可能提交多個任務(wù)的情景。

云制造平臺中制造資源的多樣性、分散性、協(xié)同性等給云制造資源的調(diào)度優(yōu)化帶來巨大挑戰(zhàn)[8]。為實現(xiàn)云服務(wù)調(diào)度優(yōu)化,除了QoS屬性外,部分研究考慮了云服務(wù)間的信任特征來構(gòu)建服務(wù)組合或資源調(diào)度模型,如服務(wù)的可靠性與可信性[9]、云服務(wù)信任關(guān)系[10]、云服務(wù)企業(yè)間信任度[11]等。此外,制造云服務(wù)的合作屬性在云服務(wù)的協(xié)同特征中被考慮,但主要集中在云服務(wù)組合方面。具體而言,在云服務(wù)質(zhì)量評價中構(gòu)建基于網(wǎng)絡(luò)協(xié)同模式[12]、云服務(wù)組合協(xié)同效應(yīng)[13]、企業(yè)親密度[14]等模型實現(xiàn)服務(wù)優(yōu)選評價,進而利用蜂群算法、蟻群算法等進行求解。事實上服務(wù)協(xié)同不僅涉及到合作,還涉及到競爭屬性,即在云服務(wù)協(xié)同完成一系列子任務(wù)過程中,具有相同功能屬性的云服務(wù)之間存在競爭關(guān)系。服務(wù)間的合作與競爭關(guān)系會作用于服務(wù)調(diào)度中的選擇與排序,最終影響調(diào)度結(jié)果。

協(xié)同配置分布式的制造資源服務(wù)是云制造生產(chǎn)模式的典型特征。因此本文在分布式制造環(huán)境下,考慮了不同用戶提交多項任務(wù)的情景,挖掘云服務(wù)的社會屬性以有效提高云服務(wù)的社會參與度和合作能力。首先,在云制造平臺制造服務(wù)調(diào)度框架下,面向多個用戶任務(wù)需求,從合作與競爭的角度考慮云服務(wù)間的協(xié)同效應(yīng),以平均用戶滿意度最大化、制造服務(wù)協(xié)同效應(yīng)最大化為優(yōu)化目標構(gòu)建面向多用戶的制造云服務(wù)雙目標調(diào)度模型。然后,考慮到灰狼優(yōu)化算法收斂速度快及較強的全局搜索能力,針對所提問題特點,在灰狼優(yōu)化(Grey Wolf Optimizer,GWO)算法框架下引入模擬退火算法,利用其魯棒優(yōu)化能力,改進GWO算法的局部搜索性能。最后,通過試驗驗證了所提模型在改進云服務(wù)協(xié)同方面的優(yōu)勢,同時與其他算法相比,展示了所提算法在求解該模型的高效性,從而豐富了相關(guān)研究。

1 問題描述與模型構(gòu)建

1.1 問題描述

云制造系統(tǒng)中涉及用戶、云制造平臺和制造資源提供者。不同的用戶可以隨時向云制造平臺提交任務(wù)請求,如圖1所示為云制造模式下多用戶任務(wù)的調(diào)度框架。為了滿足用戶任務(wù)的調(diào)度需求,云制造平臺通常將不同時間段提交的任務(wù)劃分在不同的調(diào)度窗口,在同一任務(wù)提交窗口內(nèi)的用戶任務(wù)被劃分在相同的調(diào)度窗口。假設(shè)N個用戶向云平臺同時提交多個制造任務(wù),用戶集合為U={U1,U2,…,Ui,…,UN},第i個用戶有Ji個任務(wù),其第j個任務(wù)可以分解為Lij個子任務(wù),且各子任務(wù)都可由云服務(wù)平臺注冊的M個云服務(wù)執(zhí)行。

圖1 云制造模式下用戶任務(wù)調(diào)度框架

1.2 數(shù)學(xué)模型

1.2.1 模型假設(shè)

模型假設(shè)如下：

(1)用戶的所有任務(wù)之間是相互獨立的,且每個任務(wù)都可分解為多個子任務(wù);

(2)每個云服務(wù)可完成多種類型的子任務(wù),但某一時刻僅能處理一項子任務(wù);

(3)每個子任務(wù)可選的云服務(wù)有多種,但只能由一個云服務(wù)執(zhí)行,且一旦執(zhí)行不可被打斷;

(4)按照用戶提交時間和交貨期的要求,將所有任務(wù)開始時刻轉(zhuǎn)化為零;

(5)不同云服務(wù)完成某一子任務(wù)的時間、成本不同,并且提前已知。

1.2.2 數(shù)學(xué)模型

基于以上的問題描述構(gòu)建多用戶任務(wù)調(diào)度的數(shù)學(xué)模型,涉及到的相關(guān)符號如表1所示。

表1 符號定義表

該模型以用戶滿意度和云服務(wù)協(xié)同效應(yīng)為優(yōu)化目標,具體描述如下：

(1)用戶滿意度

為構(gòu)建用戶滿意度指標,綜合考慮完工時間、完工成本和完工質(zhì)量3個QoS因素。

1)用戶的完工時間由最晚交付給用戶的任務(wù)完工時間決定,表示為：

(1)

2)用戶的完工成本等于用戶所有任務(wù)的完工成本之和,表示為：

(2)

3)云服務(wù)的質(zhì)量合格率可以體現(xiàn)服務(wù)質(zhì)量,可通過以往用戶對制造云服務(wù)的歷史評分進行度量。由于每個用戶有多個任務(wù),將某用戶所有任務(wù)的最小服務(wù)質(zhì)量作為影響該用戶服務(wù)質(zhì)量的指標,表示為：

(3)

因此,第i個用戶的滿意度表示為：

(4)

(5)

(6)

(7)

以平均用戶滿意度作為第一個優(yōu)化目標,計算方式如下：

(8)

(2)云服務(wù)協(xié)同效應(yīng)

制造云服務(wù)的社會屬性涉及合作與競爭兩個方面。當(dāng)云服務(wù)需要合作完成兩個相繼的子任務(wù)時必然存在信息交流與互動,云服務(wù)企業(yè)之間由于軟硬件設(shè)施的不同則會造成云服務(wù)間合作關(guān)系的不同。同時,當(dāng)多個云服務(wù)都能夠完成某項子任務(wù)時,存在競爭關(guān)系的云服務(wù)會對同一個子任務(wù)進行搶奪,競爭力強的服務(wù)會獲得該子任務(wù)訂單。本文利用合作親密度和距離親密度衡量兩個云服務(wù)之間的合作水平。

1)合作親密度。

云服務(wù)間能夠通過信息交流相互合作共同完成一項任務(wù),在大數(shù)據(jù)環(huán)境下可以根據(jù)歷史記錄信息得到云服務(wù)之間的合作次數(shù),因此合作親密度CF可根據(jù)下式進行計算：

CFmm′=1-e-λ×CTmm′。

(9)

式中：CTmm′表示第m個云服務(wù)與第m′個云服務(wù)的合作次數(shù),λ表示合作緊密系數(shù),為常量。

2)距離親密度。

由于生產(chǎn)云服務(wù)地理位置的分散性,越短的地理距離越有助于減少子任務(wù)之間物流運輸?shù)淖枞鸞15]。本文利用式(10)將兩個云服務(wù)之間的地理距離映射為數(shù)值在0～1之間的距離親密度：

(10)

式中DS、DM及DL分別為衡量距離親密度高、中、低的3個閾值常量。

綜上,云服務(wù)m和m′的合作水平SImm′可由下式表示：

SImm′=c1CFmm′+c2DImm′。

(11)

式中：c1、c2表示兩個云服務(wù)之間合作親密度和距離親密度分別對二者之間合作水平的貢獻程度大小,可依據(jù)專家評價進行設(shè)定,且c1+c2=1。

競爭屬性指云服務(wù)企業(yè)的市場競爭力,本文用市場占有率衡量其競爭力,具體由云企業(yè)某類產(chǎn)品或服務(wù)在一定時期內(nèi)和一定區(qū)域內(nèi)的市場銷售中占有同類產(chǎn)品或服務(wù)的比例表示,其計算公式如下：

(12)

式中：pm為云服務(wù)m的市場營業(yè)額,P為能提供與云服務(wù)m相同服務(wù)的所有云服務(wù)的營業(yè)額。

云服務(wù)之間競爭力差異越大,說明其市場優(yōu)勢差異越明顯。此時,競爭力強的云服務(wù)之間在需要合作時更容易彼此認同;競爭力弱的云服務(wù)則可共同提高服務(wù)利用率。競爭力差異大的云服務(wù)之間則會產(chǎn)生與上述兩種情況相反的傾向,即合作意向減弱,對協(xié)同效應(yīng)產(chǎn)生負向影響。即使二者之間原先有很高的親密度,由于一方受市場中其他服務(wù)影響從而競爭力變小拉大差距,最后服務(wù)協(xié)同性也會降低。因此,為更好地衡量云服務(wù)間的協(xié)同效應(yīng),應(yīng)該同時考慮云服務(wù)m和m′之間的合作關(guān)系與競爭關(guān)系。其協(xié)同效應(yīng)

(13)

采用云服務(wù)協(xié)同矩陣直觀地表示不同制造云服務(wù)之間的協(xié)同能力,矩陣中數(shù)值可根據(jù)以上的協(xié)同效應(yīng)計算公式計算得出,所有數(shù)值均在0～1之間。

作為第2個優(yōu)化目標,所有用戶任務(wù)的平均服務(wù)協(xié)同效應(yīng)如下：

(14)

(3)模型約束

該模型的基本約束如下：

1)子任務(wù)約束。式(15)表示同一任務(wù)的各子任務(wù)滿足預(yù)先定義的加工順序,某一子任務(wù)的前序子任務(wù)都完工之后,該子任務(wù)才能進行加工。

i=1,2,…,N;j=1,2,…,Ji;l=2,…,Lij。

(15)

2)云服務(wù)約束。同一個云服務(wù)上加工的兩個子任務(wù)加工時間不能重疊,如子任務(wù)stijl與stabp在同一個云服務(wù)上加工,且stijl的順序優(yōu)先于stabp,則有：

i=1,2,…,N;j=1,2,…,Ji;l=1,2,…,Lij;

a=1,2,…,N;b=1,2,…,Ja;p=1,2,…,Lab;

m,m′=1,2,…,M。

(16)

3)完工時間與開始時間的約束如式(17)所示,每個用戶任務(wù)的開始時間大于等于0,如式(18)所示：

(17)

STijl≥0,i=1,2,…,N;j=1,2,…,Ji;l=1,2,…,Lij。

(18)

4)每個子任務(wù)只能在一個云服務(wù)上進行加工,如式(19)所示：

(19)

2 GWO-SA算法設(shè)計

任務(wù)調(diào)度問題是一個典型的NP-hard問題[16],為了獲得更優(yōu)的決策解,本文采用離散的灰狼優(yōu)化算法[17]。由于參數(shù)少、收斂速度快且具有較好的全局搜索能力,該算法目前已經(jīng)被廣泛應(yīng)用于求解各類工程問題[18-19]。然而,原始的GWO在求解連續(xù)問題時其求解精度與穩(wěn)定性方面有較大優(yōu)勢,而對于離散問題的求解并不能直接應(yīng)用。因此,本文基于模擬退火(Simulated Annealing,SA)算法的局部搜索能力,在GWO算法框架上進行算法改進,從而設(shè)計了GWO-SA算法,該算法能提高解的質(zhì)量,最終獲得滿足決策者的優(yōu)化調(diào)度方案。

2.1 問題編碼

由于該模型涉及兩個問題：首先需要為每個子任務(wù)從可選的云服務(wù)候選集中選擇一個可用的云服務(wù);其次對同一個云服務(wù)上的多個子任務(wù)進行排序。根據(jù)問題特性,本文采用二向量實數(shù)編碼方式對決策變量進行編碼,染色體分為二向量：第一向量為子任務(wù)選擇云服務(wù),第二向量對子任務(wù)進行排序。

假設(shè)有兩個用戶同時向云制造系統(tǒng)中提交了生產(chǎn)任務(wù)。云系統(tǒng)中有5個云服務(wù)能夠處理所有子任務(wù),分別編號1～5。第1個用戶有2個任務(wù),分別分解得到2、3個順序執(zhí)行的子任務(wù)。第2個用戶有1個任務(wù),分解得到的子任務(wù)數(shù)量為3,其染色體如圖2所示。從圖中可看出染色體長度為子任務(wù)總數(shù)的2倍。對于云服務(wù)選擇部分,從左到右每個基因位上的數(shù)字表示該位置對應(yīng)的子任務(wù)選擇了編號為這一數(shù)字的云服務(wù)。例如,第5個數(shù)字2表示第1個用戶的第2個任務(wù)的第3個子任務(wù)選擇了編號為2的云服務(wù)。其他基因位的表示方法類似。對于子任務(wù)排序部分,后半段染色體基因位數(shù)代表總的子任務(wù)數(shù),子任務(wù)用其對應(yīng)任務(wù)的序號表示,且某序號出現(xiàn)的次數(shù)代表對應(yīng)任務(wù)的子任務(wù)數(shù)。進行排序的編譯依據(jù)是對應(yīng)任務(wù)的序號次序,即從左側(cè)開始掃描后半段染色體,同一任務(wù)序號出現(xiàn)的第k次代表該任務(wù)的第k個子任務(wù)。如圖2所示的調(diào)度問題,基因串中的兩個1依次表示第一個任務(wù)的兩個子任務(wù),從左到右,第一個基因位上的1表示第一個任務(wù)的第一個子任務(wù),第6個基因位上的1表示第一個任務(wù)的第二個子任務(wù),用此種編碼方式能夠使得一個任務(wù)經(jīng)分解得到的子任務(wù)之間保持先后順序。

圖2 染色體編碼

2.2 社會領(lǐng)導(dǎo)層級機制

GWO的核心思想是找到種群中3個適應(yīng)值最好的灰狼(α,β,δ),其他個體(ω)利用這些個體的引導(dǎo)對整個解空間進行探索,這種利用優(yōu)良個體信息的方式能夠加快種群的收斂。在多目標優(yōu)化問題中,個體的適應(yīng)值可由支配等級表示,根據(jù)帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-II)的支配等級計算和擁擠度計算可將種群劃分為多個非支配層,因此,α,β,δ的確定可根據(jù)以下規(guī)則：

(1)若種群只有一個非支配層,根據(jù)擁擠距離采用二元錦標賽機制選取3個個體作為α,β,δ。

(2)當(dāng)種群有兩個非支配層,隨機選擇第一層中一個灰狼并將其視為α,第二層利用擁擠度計算采用二元錦標賽機制選取兩個個體作為β,δ。

(3)當(dāng)種群有3個非支配層,則從第1,2,3層各自隨機選擇一個個體作為α,β,δ。

2.3 捕食行為機制

原始的GWO每只ω狼隨機選擇領(lǐng)導(dǎo)個體進行追隨,這種方式并不能確保一個好的搜尋方向。由于相似個體之間的信息交流往往更有利于生成優(yōu)良個體,為了保持種群有一個良好的搜尋方向,本文設(shè)計的算法使每只ω狼可根據(jù)在當(dāng)前種群中的非支配等級選擇領(lǐng)導(dǎo)個體。新個體生成策略如下：

(1)若ω狼在第1個非支配等級,則Xnew=CR(Xα,X);

(2)若ω狼在第2個非支配等級,則

(20)

(3)若ω狼的非支配等級大于等于3,則隨機選擇領(lǐng)導(dǎo)個體：

(21)

根據(jù)問題特性,染色體的前后兩部分分別應(yīng)用兩種不同的交叉(Crossover,CR)操作。對子任務(wù)排序部分,采用POX(precedence operation crossover)交叉[20]。為增加種群多樣性、防止算法陷入局部最優(yōu),云服務(wù)選擇部分則采用自適應(yīng)性交叉機制。首先定義一個個體G的引導(dǎo)概率pf,其計算公式如下：

(22)

式中：pf(t)表示第t次迭代的領(lǐng)導(dǎo)個體引導(dǎo)概率,pfmin、pfmax表示最小值和最大值,maxIt指最大迭代次數(shù)。根據(jù)該式可以看出個體的引導(dǎo)概率在逐漸減小,這有利于防止算法陷入局部最優(yōu)。具體交叉過程如圖3所示。

圖3 自適應(yīng)性交叉

交叉步驟如下：

步驟1隨機生成一個取值在0～1間的數(shù)組。

步驟2找到小于pf的位置,將G相應(yīng)位置的基因位繼承給新個體。

步驟3新個體其他基因位則由原個體繼承。

基于問題特征本文采用不同的變異算子。對于云服務(wù)選擇部分,隨機選擇一個變異點,從該子任務(wù)的可選云服務(wù)序號中隨機選擇一個進行替換;對于子任務(wù)排序部分,隨機選擇兩個基因位然后交換各自的值,這樣產(chǎn)生的后代不會破壞解的可行性。

2.4 模擬退火算法

領(lǐng)導(dǎo)個體的引導(dǎo)雖然會加快算法的收斂速度,但是個體的追隨策略會使GWO陷入局部最優(yōu)[19]。因此,采用以下3種策略作為模擬退火算法的狀態(tài)轉(zhuǎn)移方式進行局部搜索,從而提高解的多樣性和解的質(zhì)量。

(1)云服務(wù)最優(yōu)配置

隨機選擇一個子任務(wù),為其隨機選擇服務(wù)成本最小、服務(wù)時間最小或者服務(wù)質(zhì)量最大的云服務(wù)。

(2)增加協(xié)同策略

隨機選擇一個用戶,逐步判斷該用戶每一任務(wù)的所有子任務(wù)是否可以在同一個云服務(wù)上進行服務(wù)。如果可以,則將相繼的兩個子任務(wù)安排在同一個云服務(wù)上以減少物流時間和成本,同時增加任務(wù)的協(xié)同能力。

(3)負載平衡策略

該方法是基于云服務(wù)負載均衡的啟發(fā)式策略。保持子任務(wù)的排序不動,對云服務(wù)選擇部分進行重新布置,配置策略如下：

1)計算每個云服務(wù)的最大完工時間(LFTm)：

(23)

2)計算每個子任務(wù)可選云服務(wù)的選擇概率：

(24)

式中m為子任務(wù)可選擇云服務(wù)的序號。

3)計算可選云服務(wù)的被選擇概率：

(25)

4)采用輪盤賭的方法重新對云服務(wù)進行選擇。

進行遺傳操作后,對種群中的個體以概率pr進行模擬退火搜索,增加解的多樣性。冷卻溫度計算如式(26)所示,可以看出冷卻溫度是自適應(yīng)的、非線性的、緩和的。

(26)

式中：k為退火速度,it表示當(dāng)前迭代次數(shù),T0為一個常數(shù)。

模擬退火算法的步驟如下：

步驟1輸入種群,模擬退火最大迭代次數(shù)Maxit,令it=1,根據(jù)式(26)計算冷卻溫度。

步驟2判斷it是否大于Maxit,若是,則結(jié)束;否則轉(zhuǎn)步驟3。

步驟3隨機選擇一種狀態(tài)轉(zhuǎn)移方式生成新個體xnew。

步驟4比較新解xnew與舊解xold的目標函數(shù),根據(jù)支配關(guān)系和Metropolis準則接受新解,若xnew支配xold,則用xnew替換掉xold,跳出循環(huán);若xold支配xnew,則轉(zhuǎn)步驟2;若兩個個體之間相互不支配,則隨機選擇一個目標函數(shù)比較兩個個體,并按照Metropolis準則以式(27)接受新解,返回步驟2。

(27)

2.5 算法流程

GWO-SA的算法流程圖如圖4所示。

圖4 GWO-SA算法流程圖

3 試驗仿真與結(jié)果分析

3.1 測試算例

表2 云服務(wù)某一時期合作次數(shù)

表3 云服務(wù)地理距離 km

表4 云服務(wù)競爭能力之差

表5 云服務(wù)協(xié)同效應(yīng)

圖5 FAG磨輥軸承的生產(chǎn)流程

比較以下兩個模型下的結(jié)果：

(1)模型一：考慮兩個優(yōu)化目標(用戶平均滿意度和服務(wù)協(xié)同能力),即本文提出的服務(wù)選擇模型;

(2)模型二：僅考慮一個優(yōu)化目標(用戶平均滿意度),在所提出的GWO-SA基礎(chǔ)上求解單目標制造云服務(wù)選擇與調(diào)度模型。

算法運行平臺的參數(shù)為Intel Core i5-4210M,CPU 2.60 GHz,4 GB內(nèi)存,在Windows 10系統(tǒng)下采用MATLAB 2018a軟件進行試驗,試驗獨立進行20次。種群大小和最大迭代次數(shù)設(shè)置為100,交叉和變異概率分別為0.9和0.1,T0=50,k=0.05,Maxit=5,pr=0.1,pfmax、pfmin分別為0.5、0.4。

模型一的最終Pareto解集如圖6所示。云平臺運營者可以從多個解中權(quán)衡兩個目標函數(shù)的重要性,選擇合適的決策方案。以用戶平均滿意度最大的解為例(此時任務(wù)平均服務(wù)協(xié)同能力最弱)與模型二的最優(yōu)解進行比較,試驗結(jié)果如表6所示。

表6 模型比較結(jié)果

圖6 最終Pareto解集

模型二由于過分追求QoS相關(guān)的滿意度而忽略了服務(wù)之間的社會屬性,雖然用戶平均滿意度最優(yōu),但是最優(yōu)解的協(xié)同效應(yīng)基本都明顯低于模型一,即單目標情形下云服務(wù)的協(xié)同能力明顯偏弱,其中只有最后一個任務(wù)的協(xié)同效應(yīng)略高于模型一的結(jié)果。圖7和圖8展示了兩個模型最優(yōu)解的甘特圖。與模型二相比,模型一雖然損失了一部分用戶滿意度,但模型一由于考慮了云服務(wù)的協(xié)同效應(yīng),第2個任務(wù)的2、3、5個子任務(wù)在同一個云服務(wù)上進行加工,第7個任務(wù)的2、3、4個子任務(wù)也在同一個云服務(wù)上進行加工。這種任務(wù)加工方式顯然更有利于減少物流運輸,從而提高云服務(wù)的協(xié)同能力以及云制造系統(tǒng)的可持續(xù)性。該結(jié)果也驗證了所提模型的可行性及有效性。

圖7 模型一用戶滿意度最大解甘特圖

圖8 模型二最優(yōu)解甘特圖

3.2 算法性能分析

為驗證所提算法的性能,設(shè)計4組試驗算例進行比較,各組試驗的數(shù)據(jù)如表7所示。

表7 4組試驗信息

每個任務(wù)可分解為順序執(zhí)行的多個子任務(wù),每個子任務(wù)可選擇的云服務(wù)個數(shù)為所有云服務(wù)個數(shù)的40%～80%,云服務(wù)的相關(guān)數(shù)據(jù)服從3.1節(jié)中的均勻分布,云服務(wù)之間的協(xié)同效應(yīng)服從U(0.6,1)。為了驗證GWO-SA的性能,將其與5種多目標進化算法NSGA-II[21]、改進的強度Pareto進化算法(improving the Strength Pareto Evolutionary Algorithm,SPEA2)[22]、進化多目標灰狼優(yōu)化(Evolutionary Multi-Objective Grey Wolf Optimizer,EMOGWO)算法[23]、離散粒子群模擬退火混合優(yōu)化(Discrete Particle Swarm Optimization with Simulated Annealing,DPSO-SA)算法[24]、改進的人工蜂群(Improved Artificial Bee Colony,IABC)算法[25]進行比較,算法基本參數(shù)設(shè)置同GWO-SA,其他參數(shù)根據(jù)原始文獻設(shè)置。本文提出的混合算法部分參數(shù)設(shè)置見3.1節(jié)。

本文采用反世代距離[26](Inverted Generational Distance,IGD)和超體積[27](Hyper Volume,HV)兩個常用的多目標評價指標對各算法進行比較。IGD衡量算法的收斂性能,HV衡量算法的綜合性能。由于問題本身的真實Pareto前沿?zé)o法獲得,在測試中匯總所有算法的最終結(jié)果并進行非支配排序,將得到的非支配解集作為真實Pareto解集。如圖9所示為所有算例中各個算法最終的Pareto解的分布情況,從圖中可以看出,6種算法中,GWO-SA具有較好的支配性,解的分布更加均勻,尤其對于問題規(guī)模較大時展示出的性能更為明顯。GWO-SA在4組試驗中都產(chǎn)生了高質(zhì)量的解,說明該算法能夠產(chǎn)生更穩(wěn)定、更有效的解。如圖10所示為20次試驗中各個算例中6種算法IGD和HV的數(shù)值分布情況,其中G、N、S、E、D、I分別表示GWO-SA、NSGA-II、SPEA2、EMOGWO、DPSO-SA、IABC。由圖10a可知,4組測試試驗中,GWO-SA的IGD值分布情況相比于其他5種算法更小,這說明GWO-SA更接近真實的Pareto前沿,具有更好的收斂性。另外如圖10b所示的4組試驗中,GWO-SA的HV指標相比于其他5種算法具有更大的值,這反映了GWO-SA良好的多樣性和收斂性。

圖9 各算例Pareto解集

a IGD值 b HV值圖10 算法性能箱線圖

4 結(jié)束語

以往的制造云服務(wù)選擇與調(diào)度研究大多只考慮云服務(wù)的QoS屬性。在此基礎(chǔ)上,本文面向多用戶任務(wù)需求,將云服務(wù)之間的競爭與合作協(xié)同效應(yīng)引入云服務(wù)調(diào)度模型中,構(gòu)建了以最大化用戶平均滿意度、最大化云服務(wù)協(xié)同效應(yīng)為目標的服務(wù)選擇與調(diào)度模型,設(shè)計了GWO-SA算法對該模型進行優(yōu)化求解。結(jié)果表明,本文提出的GWO-SA算法能夠有效提高Pareto解的質(zhì)量,該算法在較大規(guī)模的算例中可以獲得更好的解。同時,比較對模型一和模型二的求解結(jié)果可知,考慮協(xié)同效應(yīng)更加貼合實際,能通過影響調(diào)度策略進而減少物流運輸、增加整個平臺中任務(wù)執(zhí)行以及云服務(wù)調(diào)用的可持續(xù)性等。然而,本文所提模型并未考慮云制造平臺中制造服務(wù)的動態(tài)性,為此,在后期工作中可以對動態(tài)環(huán)境下制造云服務(wù)選擇與調(diào)度優(yōu)化開展深入研究。