考慮云制造服務(wù)協(xié)同的多用戶任務(wù)調(diào)度優(yōu)化

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

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

0 引言

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

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

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

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

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

1.1 問題描述

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

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

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

1.2.1 模型假設(shè)

模型假設(shè)如下：

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

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

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

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

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

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

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

表1 符號(hào)定義表

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

(1)用戶滿意度

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

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

(1)

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

(2)

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

(3)

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

(4)

(5)

(6)

(7)

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

(8)

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

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

1)合作親密度。

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

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

(9)

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

2)距離親密度。

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

(10)

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

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

SImm′=c1CFmm′+c2DImm′。

(11)

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

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

(12)

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

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

(13)

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

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

(14)

(3)模型約束

該模型的基本約束如下：

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

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

(15)

2)云服務(wù)約束。同一個(gè)云服務(wù)上加工的兩個(gè)子任務(wù)加工時(shí)間不能重疊,如子任務(wù)stijl與stabp在同一個(gè)云服務(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)完工時(shí)間與開始時(shí)間的約束如式(17)所示,每個(gè)用戶任務(wù)的開始時(shí)間大于等于0,如式(18)所示：

(17)

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

(18)

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

(19)

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

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

2.1 問題編碼

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

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

圖2 染色體編碼

2.2 社會(huì)領(lǐng)導(dǎo)層級(jí)機(jī)制

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

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

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

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

2.3 捕食行為機(jī)制

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

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

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

(20)

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

(21)

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

(22)

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

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

交叉步驟如下：

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

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

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

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

2.4 模擬退火算法

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

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

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

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

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

(3)負(fù)載平衡策略

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

1)計(jì)算每個(gè)云服務(wù)的最大完工時(shí)間(LFTm)：

(23)

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

(24)

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

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

(25)

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

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

(26)

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

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

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

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

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

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

(27)

2.5 算法流程

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

圖4 GWO-SA算法流程圖

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

3.1 測(cè)試算例

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

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

表4 云服務(wù)競(jìng)爭(zhēng)能力之差

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

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

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

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

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

算法運(yùn)行平臺(tái)的參數(shù)為Intel Core i5-4210M,CPU 2.60 GHz,4 GB內(nèi)存,在Windows 10系統(tǒng)下采用MATLAB 2018a軟件進(jìn)行試驗(yàn),試驗(yàn)獨(dú)立進(jìn)行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所示。云平臺(tái)運(yùn)營(yíng)者可以從多個(gè)解中權(quán)衡兩個(gè)目標(biāo)函數(shù)的重要性,選擇合適的決策方案。以用戶平均滿意度最大的解為例(此時(shí)任務(wù)平均服務(wù)協(xié)同能力最弱)與模型二的最優(yōu)解進(jìn)行比較,試驗(yàn)結(jié)果如表6所示。

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

圖6 最終Pareto解集

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

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

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

3.2 算法性能分析

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

表7 4組試驗(yàn)信息

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

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

圖9 各算例Pareto解集

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

4 結(jié)束語(yǔ)

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