考慮執(zhí)行能力的云制造服務(wù)資源組合優(yōu)化研究

謝程龍 石宇強(qiáng)

(西南科技大學(xué)制造科學(xué)與工程學(xué)院 四川綿陽(yáng) 621010)

云制造[1]是一種面向服務(wù)的、高效低耗和基于知識(shí)的網(wǎng)絡(luò)化、敏捷化制造模式[2]，能夠有效整合服務(wù)資源，更快地響應(yīng)市場(chǎng)需求，降低服務(wù)成本，提高服務(wù)效率。隨著云制造任務(wù)的日益復(fù)雜，使得單一的云制造服務(wù)已經(jīng)難以滿足需求者的任務(wù)需求，因此云平臺(tái)通過(guò)云制造服務(wù)資源組合來(lái)滿足復(fù)雜的任務(wù)需求[3]。云制造服務(wù)資源組合優(yōu)化是云制造中的關(guān)鍵技術(shù)之一，云制造任務(wù)分解為多個(gè)子任務(wù)，每個(gè)子任務(wù)匹配得到相應(yīng)的服務(wù)資源集合，研究如何選擇服務(wù)資源，形成合適的服務(wù)組合方案來(lái)執(zhí)行任務(wù)具有重要意義。

國(guó)內(nèi)外文獻(xiàn)大多數(shù)以服務(wù)質(zhì)量(Quality of Service，QoS)作為評(píng)價(jià)指標(biāo)來(lái)進(jìn)行云制造組合優(yōu)化。Ding等[4]建立多層次制造服務(wù)組合評(píng)價(jià)模型，其中考慮的主要指標(biāo)是時(shí)間、成本和信譽(yù)。李永湘等[5]將服務(wù)可靠性、可信性、組合復(fù)雜度、協(xié)同度、執(zhí)行時(shí)間、執(zhí)行費(fèi)用相結(jié)合來(lái)構(gòu)建QoS評(píng)價(jià)模型。Yuan等[6]結(jié)合時(shí)間、可組合性、質(zhì)量、可用性、可靠性、成本等目標(biāo)，提出服務(wù)組合的QoS指標(biāo)體系，使用改進(jìn)的模糊綜合評(píng)估法確定QoS評(píng)估中每個(gè)指標(biāo)的權(quán)重。陳友玲等[7]構(gòu)建面向云制造的多供應(yīng)商協(xié)同生產(chǎn)任務(wù)分配優(yōu)化模型。Zhao等[8]為了更準(zhǔn)確地從復(fù)雜的服務(wù)網(wǎng)絡(luò)中找到個(gè)性化的制造服務(wù)組合，將組合優(yōu)化與協(xié)同過(guò)濾相結(jié)合，通過(guò)使用具有服務(wù)質(zhì)量約束的組合優(yōu)化模型來(lái)選擇最佳服務(wù)組合。Ren等[9]針對(duì)制造服務(wù)的社會(huì)協(xié)作特點(diǎn)，提取出5類社會(huì)關(guān)系來(lái)計(jì)算協(xié)同效應(yīng)，然后建立一種基于最大化整體協(xié)同效應(yīng)的服務(wù)組合優(yōu)化模型。Wu等[10]提出一種從經(jīng)濟(jì)、環(huán)境和社會(huì)等方面評(píng)估云制造可持續(xù)性的綜合方法，從而建立組合優(yōu)化模型。因?yàn)樵浦圃旖M合優(yōu)化問(wèn)題是NP難問(wèn)題，許多學(xué)者使用遺傳算法[11-12]、粒子群算法[13]、人工蜂群算法[14]等求解云制造服務(wù)組合優(yōu)化問(wèn)題。

上述研究在解決云制造組合優(yōu)化問(wèn)題時(shí)大多是關(guān)注任務(wù)需求，其中大多考慮的是成本、時(shí)間、質(zhì)量等QoS指標(biāo)，但是對(duì)于服務(wù)資源執(zhí)行任務(wù)的歷史執(zhí)行情況及其時(shí)效性考慮較少，使得服務(wù)資源對(duì)任務(wù)的執(zhí)行能力是否可信或者可靠不得而知，具有不確定性。當(dāng)執(zhí)行能力可信度低的服務(wù)資源執(zhí)行子任務(wù)時(shí)可能會(huì)出現(xiàn)更多突發(fā)問(wèn)題，例如設(shè)備故障使得交貨期延長(zhǎng)，成功執(zhí)行子任務(wù)的概率將降低，最終可能會(huì)導(dǎo)致整個(gè)任務(wù)失敗，不但影響需求方利益同時(shí)也對(duì)云平臺(tái)利益及聲譽(yù)造成影響。因此，有必要同時(shí)考慮服務(wù)資源的QoS指標(biāo)以及歷史執(zhí)行情況來(lái)解決考慮執(zhí)行能力的云制造服務(wù)組合優(yōu)化問(wèn)題。

1 問(wèn)題描述

云平臺(tái)將需求方任務(wù)按規(guī)則分解為若干子任務(wù)，ST={STi|i=1,2,…n}表示分解后的子任務(wù)集合，n表示子任務(wù)數(shù)，STi表示第i項(xiàng)子任務(wù)。Si={Sij|j=1,2,…mi}表示STi的候選服務(wù)資源集合，mi表示Si中的服務(wù)資源數(shù)，Sij表示Si中的第j個(gè)服務(wù)資源。

需求方關(guān)注的是任務(wù)需求[11]，即成本、時(shí)間、合格率等QoS指標(biāo)，不同服務(wù)資源的QoS指標(biāo)可能不同。云平臺(tái)更加關(guān)注任務(wù)是否可以順利完成，即云制造服務(wù)資源的執(zhí)行能力是否可信。服務(wù)資源執(zhí)行能力是否可信可以通過(guò)其歷史執(zhí)行情況來(lái)判斷，而云制造服務(wù)資源的歷史執(zhí)行情況會(huì)隨時(shí)間變化，具有不確定性。若在云制造服務(wù)資源組合優(yōu)化決策過(guò)程中僅考慮成本、時(shí)間、合格率等QoS指標(biāo)，忽略云制造服務(wù)資源的歷史執(zhí)行情況，對(duì)服務(wù)方任務(wù)執(zhí)行能力考慮不足，可能導(dǎo)致任務(wù)執(zhí)行失敗。因此，應(yīng)綜合考慮需求方所關(guān)注的成本、時(shí)間、合格率等QoS指標(biāo)和云平臺(tái)所關(guān)注的服務(wù)資源歷史執(zhí)行情況信息，進(jìn)行服務(wù)資源組合優(yōu)化，使組合方案達(dá)到最優(yōu)。

2 組合優(yōu)化模型

云制造需求方主要關(guān)注任務(wù)需求，即完成任務(wù)所需的成本、時(shí)間、合格率均達(dá)到最優(yōu)。云平臺(tái)更多關(guān)注服務(wù)資源執(zhí)行能力是否可信，而可靠性和可維護(hù)性能夠客觀反映服務(wù)資源在執(zhí)行任務(wù)時(shí)的真實(shí)情況。可靠性是指服務(wù)資源成功執(zhí)行任務(wù)次數(shù)與執(zhí)行任務(wù)總次數(shù)之比[3]；可維護(hù)性是指服務(wù)資源執(zhí)行任務(wù)中成功處理意外的次數(shù)與意外發(fā)生的次數(shù)之比[15]。當(dāng)服務(wù)資源可靠性和可維護(hù)性越大時(shí)，執(zhí)行任務(wù)的穩(wěn)定性越好，執(zhí)行能力越可信。因此，本文以服務(wù)成本、時(shí)間、合格率、可靠性、可維護(hù)性為決策目標(biāo)建立組合優(yōu)化數(shù)學(xué)模型，并且考慮服務(wù)資源歷史執(zhí)行情況信息的時(shí)效性，建立時(shí)間段權(quán)重衰減函數(shù)。

決策變量如下：

(1)

式中Xij為決策變量。

2.1 時(shí)間段權(quán)重

服務(wù)資源在不同時(shí)間段的歷史執(zhí)行情況可能不同，考慮到服務(wù)資源歷史執(zhí)行情況的時(shí)效性，建立時(shí)間段權(quán)重線性衰減函數(shù)為每個(gè)時(shí)間段賦予權(quán)重。越靠近當(dāng)前時(shí)間點(diǎn)的時(shí)間段權(quán)重越大，越遠(yuǎn)則時(shí)間段權(quán)重越小。H表示總時(shí)間間隔段數(shù)，即能對(duì)執(zhí)行情況進(jìn)行評(píng)價(jià)的時(shí)間段數(shù)。權(quán)重衰減函數(shù)公式如下：

(2)

式中：h表示時(shí)間段，假設(shè)云制造服務(wù)資源在每個(gè)時(shí)間段內(nèi)均有執(zhí)行任務(wù)；φh表示時(shí)間段h的權(quán)重。在該衰減函數(shù)中，云平臺(tái)可以根據(jù)自己需要對(duì)最大間隔數(shù)H和最遠(yuǎn)時(shí)間段權(quán)重φH進(jìn)行設(shè)置，其中H≥1，0≤φH≤1。

2.2 優(yōu)化目標(biāo)

總服務(wù)成本(C)決策目標(biāo)如下：

(3)

式中：C表示服務(wù)組合方案的總服務(wù)成本；Cij表示Sij對(duì)STi的服務(wù)成本。

總服務(wù)時(shí)間(T)決策目標(biāo)如下：

(4)

式中：T表示服務(wù)組合方案的總服務(wù)時(shí)間；Tij表示Sij對(duì)STi的服務(wù)時(shí)間。

合格率(Q)決策目標(biāo)如下[16]：

(5)

式中：Q表示服務(wù)組合方案的平均合格率；Qij表示Sij對(duì)STi的合格率。

可靠性(SR)目標(biāo)是使服務(wù)組合方案的平均可靠性最大。首先利用時(shí)間段權(quán)重，確定各服務(wù)資源可靠性，然后基于標(biāo)準(zhǔn)差[17]對(duì)可靠性進(jìn)行獎(jiǎng)懲修正。

可靠性決策目標(biāo)如下:

(6)

(7)

(8)

可維護(hù)性(SM)目標(biāo)是使服務(wù)組合方案的平均可維護(hù)性最大。首先利用時(shí)間段權(quán)重，確定各服務(wù)資源可維護(hù)性，然后對(duì)可維護(hù)性進(jìn)行獎(jiǎng)懲修正?？删S護(hù)性決策目標(biāo)如下:

(9)

(10)

(11)

2.3 約束條件

組合優(yōu)化模型約束條件如下：

(12)

式中：每個(gè)子任務(wù)由一個(gè)服務(wù)資源服務(wù)。

(13)

式中：Cmax表示可接受的最大總服務(wù)成本；Tmax表示可接受的最長(zhǎng)總服務(wù)時(shí)間；Qmin表示可接受的最低合格率；SRmin表示可接受的最小可靠性；SMmin表示可接受的最小可維護(hù)性。

2.4 總目標(biāo)

將各目標(biāo)進(jìn)行歸一化[7]，總目標(biāo)最小的服務(wù)資源組合方案則為最優(yōu)組合?？偰繕?biāo)公式如下：

minF=ω1·T*+ω2·C*+ω3·Q*+

ω4·SR*+ω5·SM*

(14)

(15)

式中：T*，C*，Q*，SR*，SM*分別表示歸一化后的服務(wù)時(shí)間、成本、合格率、可靠性、可維護(hù)性目標(biāo)；ωe表示各子目標(biāo)的權(quán)重值，E=5。

3 JADE算法求解

JADE算法[19]是DE算法[20]的變體，其優(yōu)勢(shì)在于通過(guò)使用帶有外部歸檔的變異策略(DE/current-to-pbest/1 with archive)以及通過(guò)自適應(yīng)方式對(duì)變異概率μF和交叉概率μCR進(jìn)行更新來(lái)優(yōu)化算法性能。本文在JADE算法的基礎(chǔ)上使用反向?qū)W習(xí)種群初始化并引入DE/rand/1變異策略。

3.1 種群初始化

首先產(chǎn)生初始種群，再產(chǎn)生反向種群[21]：

(16)

3.2 變異策略

針對(duì)個(gè)體變異概率Fi，標(biāo)準(zhǔn)JADE算法采用的是柯西分布生成，本文中Fi的生成方式調(diào)整為正態(tài)分布生成，具體公式如下：

Fi=randni(μF,0.1)

(17)

μF=(1-c)·μF+c·meanA(SF)

(18)

式中：Fi表示個(gè)體i的變異概率；μF為變異概率；Fi根據(jù)平均值為μF、標(biāo)準(zhǔn)差為0.1的正態(tài)分布產(chǎn)生；式(18)表示變異概率μF的更新方式，與交叉概率μCR更新方式相同；SF表示成功變異的個(gè)體對(duì)應(yīng)的Fi組成的集合；meanA(SF)表示對(duì)SF集合中的參數(shù)取平均；c=0.1。

本文中將DE/rand/1策略和DE/current-to-pbest/1 with archive策略相結(jié)合來(lái)進(jìn)行變異，具體公式如下：

(19)

3.3 算法流程

算法流程如圖1所示。具體步驟如下：

Step 1:設(shè)置種群規(guī)模NP，個(gè)體維數(shù)Dim，個(gè)體取值范圍Xmax，Xmin，當(dāng)前迭代數(shù)g，最大迭代數(shù)Gmax，初始化變異概率μF，交叉概率μCR，初始化外部存檔集合A=?等參數(shù)；基于反向?qū)W習(xí)的種群初始化；

Step 2:判斷是否滿足g>Gmax，若滿足，則輸出最優(yōu)解；否則轉(zhuǎn)入Step 3；

Step 3:設(shè)置個(gè)體成功交叉所對(duì)應(yīng)的交叉概率CRi組成的集合SCR=?，成功變異所對(duì)應(yīng)的變異概率Fi組成的集合SF=?；

Step 4:為種群中個(gè)體i產(chǎn)生交叉概率CRi、變異概率Fi；

Step 5:為種群中個(gè)體選擇變異策略來(lái)進(jìn)行變異操作；

Step 6:對(duì)種群中個(gè)體進(jìn)行交叉操作；

Step 7:對(duì)種群中個(gè)體進(jìn)行選擇操作和存檔操作，更新A，SCR，SF；

Step 8:更新交叉概率μCR和變異概率μF，g=g+1,轉(zhuǎn)到Step 2。

圖1 算法流程圖Fig.1 Algorithm flowchart

4 實(shí)驗(yàn)仿真

假設(shè)某任務(wù)由云平臺(tái)分解為8項(xiàng)子任務(wù)，表示為{ST1,ST2,…ST8}，各子任務(wù)的候選服務(wù)資源均為8個(gè)，子任務(wù)按順序執(zhí)行，為各子任務(wù)選擇服務(wù)資源，形成最優(yōu)組合方案。假設(shè)各服務(wù)資源成本取值范圍[1,6]萬(wàn)元、時(shí)間取值范圍[3,12]天、合格率取值范圍[90%，99%]、各時(shí)間段可靠性取值范圍[0.80，1]、各時(shí)間段可維護(hù)性取值范圍[0.70,1]。設(shè)置兩組實(shí)驗(yàn)，在實(shí)驗(yàn)一中，只考慮時(shí)間、成本、合格率目標(biāo)，權(quán)重均為1/3；在實(shí)驗(yàn)二中，考慮時(shí)間、成本、合格率、可靠性、可維護(hù)性目標(biāo)，權(quán)重均為0.2。部分云制造服務(wù)資源的QoS指標(biāo)信息和各時(shí)段歷史執(zhí)行情況信息分別如表1、表2所示。

表1 部分服務(wù)資源QoS指標(biāo)信息Table 1 QoS indicator information of some service resources

表2 部分服務(wù)資源歷史執(zhí)行情況信息Table 2 Historical performance information of some service resources

模型參數(shù)設(shè)置：服務(wù)資源可靠性波動(dòng)閾值λSR=0.05；修正后的可靠性范圍0.8≤SRij≤1；服務(wù)資源可維護(hù)性波動(dòng)閾值λSM=0.05；修正后的可維護(hù)性范圍0.7≤SMij≤1。時(shí)間段最小權(quán)重φH=0.2，總間隔數(shù)H=5。約束設(shè)置：總成本C≤20萬(wàn)元；總時(shí)間T≤45 d；合格率Q≥95%；可靠性SR≥90%；可維護(hù)性SM≥82%。

算法參數(shù)設(shè)置：種群規(guī)模NP=50、最大迭代次數(shù)Gmax=100、運(yùn)行50次；JADE算法與本文改進(jìn)的JADE算法初始交叉概率μCR=0.3，初始變異概率μF=0.5，適應(yīng)度值占優(yōu)比例p=0.1；不同變異策略種群比例q=0.3；粒子群(PSO)算法速度更新參數(shù)c1=0.5，c2=0.5，速度最大值Vmax=5，最小值Vmin=-5。將本文改進(jìn)JADE算法與PSO算法、JADE算法進(jìn)行對(duì)比，運(yùn)行50次后，兩組實(shí)驗(yàn)平均解迭代過(guò)程如圖2、圖3所示，算法結(jié)果對(duì)比如表3、表4所示。

圖3 實(shí)驗(yàn)二平均解迭代過(guò)程Fig.3 Experiment 2 average solution iteration

表3 實(shí)驗(yàn)一運(yùn)行結(jié)果對(duì)比Table 3 Comparison of experiment 1 running results

表4 實(shí)驗(yàn)二運(yùn)行結(jié)果對(duì)比Table 4 Comparison of experiment 2 running results

從圖2、圖3可以看出，采用反向?qū)W習(xí)的初始化種群，在迭代初期獲得的解更優(yōu)，證明反向?qū)W習(xí)的有效性。同樣可以看出，本文改進(jìn)的JADE算法相對(duì)于JADE算法收斂性更好。從表3、表4中可以看出，獨(dú)立運(yùn)行50次后，本文改進(jìn)JADE算法每次運(yùn)行均能尋得相同最優(yōu)解，而PSO算法適應(yīng)度平均值大于其他兩種算法。在求得最優(yōu)解的平均迭代數(shù)方面，本文改進(jìn)的JADE算法在實(shí)驗(yàn)一、二中分別比JADE算法少7代和6代，因此本文改進(jìn)的JADE算法的收斂性較好。

兩組實(shí)驗(yàn)最優(yōu)組合方案的子目標(biāo)值如表5所示，實(shí)驗(yàn)一組合方案為[S13,S22,S36,S45,S54,S63,S78,S87]，實(shí)驗(yàn)二組合方案為[S15,S27,S36,S44,S51,S66,S72,S86]。對(duì)兩組實(shí)驗(yàn)進(jìn)行比較，當(dāng)實(shí)驗(yàn)一組合方案按實(shí)驗(yàn)二中考慮的5目標(biāo)并且各目標(biāo)權(quán)重均為0.2的情況下進(jìn)行計(jì)算時(shí)，可靠性為0.906 5，可維護(hù)性為0.823，適應(yīng)度值為0.487 67，適應(yīng)度值大于實(shí)驗(yàn)二最優(yōu)解?？煽啃院涂删S護(hù)性能夠客觀反映服務(wù)資源在執(zhí)行任務(wù)時(shí)的真實(shí)情況，即可靠性和可維護(hù)性越大時(shí)，其執(zhí)行任務(wù)的穩(wěn)定性越好，執(zhí)行能力越可信。實(shí)驗(yàn)二服務(wù)資源組合方案的可靠性和可維護(hù)性優(yōu)于實(shí)驗(yàn)一，則實(shí)驗(yàn)二服務(wù)資源組合方案執(zhí)行能力更可信，執(zhí)行任務(wù)時(shí)穩(wěn)定性更好。雖然實(shí)驗(yàn)一服務(wù)資源組合方案的服務(wù)成本、時(shí)間、合格率優(yōu)于實(shí)驗(yàn)二，但是實(shí)驗(yàn)一服務(wù)資源組合方案未按承諾完成任務(wù)的風(fēng)險(xiǎn)更高，一旦未按承諾完成任務(wù)，使得任務(wù)失敗將造成更大的損失。因此，為降低服務(wù)資源組合方案未按承諾完成任務(wù)的風(fēng)險(xiǎn)，選擇執(zhí)行能力更可信的服務(wù)資源組合方案是有必要的。

表5 最優(yōu)服務(wù)組合子目標(biāo)值Table 5 Optimal service group target value

在不考慮對(duì)服務(wù)資源可靠性和可維護(hù)性進(jìn)行獎(jiǎng)懲修正的情況下，實(shí)驗(yàn)二最優(yōu)組合方案為[S15,S27,S36,S44,S53,S66,S72,S86]，與考慮修正情況下的最優(yōu)組合方案主要區(qū)別在于子任務(wù)ST5對(duì)于服務(wù)資源的選擇，服務(wù)資源S51,S53的可靠性和可維護(hù)性標(biāo)準(zhǔn)差如表6所示。從表6可以看出服務(wù)資源S51可靠性和可維護(hù)性標(biāo)準(zhǔn)差均低于服務(wù)資源S53，說(shuō)明服務(wù)資源S51的可靠性和可維護(hù)性的波動(dòng)相對(duì)于服務(wù)資源S53較小。通過(guò)對(duì)服務(wù)資源的可靠性和可維護(hù)性進(jìn)行獎(jiǎng)懲修正后，最終選擇的服務(wù)資源組合方案為[S15,S27,S36,S44,S51,S66,S72,S86]。

表6 S51，S53的可靠性和可維護(hù)性標(biāo)準(zhǔn)差Table 6 Standard deviation for reliability and maintainability Of S51 and S53

5 結(jié)論

本文針對(duì)云制造服務(wù)資源組合優(yōu)化中服務(wù)資源執(zhí)行能力存在不確定性等問(wèn)題，建立一種考慮需求方所關(guān)注的QoS指標(biāo)和云平臺(tái)所關(guān)注的服務(wù)資源執(zhí)行能力的組合優(yōu)化模型。結(jié)果表明考慮服務(wù)資源執(zhí)行能力的組合優(yōu)化方法所選擇的組合方案在執(zhí)行任務(wù)時(shí)的執(zhí)行能力更可信，且改進(jìn)的JADE算法在兩組實(shí)驗(yàn)中收斂性相比原算法更好。在下一步的研究中，將考慮面向多任務(wù)以及多任務(wù)之間存在優(yōu)先級(jí)關(guān)系的云制造服務(wù)組合優(yōu)化，運(yùn)用多目標(biāo)優(yōu)化算法進(jìn)行最優(yōu)組合方案的選擇。