劉　波　張自力

西南大學(xué),重慶,400715

面向云制造系統(tǒng)復(fù)雜任務(wù)請(qǐng)求的服務(wù)組合優(yōu)化框架

劉波張自力

西南大學(xué),重慶,400715

為破解因多任務(wù)、強(qiáng)QoS約束及任務(wù)過量等因素導(dǎo)致云制造系統(tǒng)組合效果不佳的問題,研究并提出了面向復(fù)雜任務(wù)請(qǐng)求的全局優(yōu)化策略框架。該框架以多任務(wù)全局優(yōu)化、組合服務(wù)捆綁與共享為基本原則,提出了“單組合執(zhí)行每任務(wù)”、“多組合執(zhí)行每任務(wù)”及“多組合執(zhí)行多任務(wù)”三種組合模式并建立了問題模型,最后利用基于混合算子的矩陣編碼遺傳算法予以實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明,該框架能高效、高質(zhì)量響應(yīng)云制造系統(tǒng)的復(fù)雜任務(wù)請(qǐng)求。

云制造；復(fù)雜任務(wù)；服務(wù)組合優(yōu)化；全局策略

0　引言

服務(wù)組合優(yōu)化是云制造中構(gòu)造松耦合敏捷制造方案、實(shí)現(xiàn)資源優(yōu)化配置的關(guān)鍵技術(shù)[1-3]。傳統(tǒng)服務(wù)組合優(yōu)化研究主要圍繞著計(jì)算資源、Web服務(wù)、網(wǎng)格制造資源等服務(wù)類型展開[3-4],并在面向服務(wù)計(jì)算(service-oriented computing,SOC)[5-9]及面向服務(wù)制造(service-oriented manufacturing,SOM)[10-13]等應(yīng)用領(lǐng)域取得了一定研究成果。與傳統(tǒng)研究相比,云制造領(lǐng)域服務(wù)組合優(yōu)化問題的特殊性在于其任務(wù)請(qǐng)求的復(fù)雜性,主要表現(xiàn)在:①普遍存在的“多資源需求型”任務(wù)[10]并行請(qǐng)求服務(wù)的情形;②無法避免的強(qiáng)服務(wù)質(zhì)量(quality of service，QoS)約束[7]情形;③可能存在任務(wù)請(qǐng)求相對(duì)于可用資源過量的情形。對(duì)于任務(wù)請(qǐng)求的上述復(fù)雜性因素,傳統(tǒng)SOC領(lǐng)域及SOM領(lǐng)域尚無法有效應(yīng)對(duì)[14]。因此,如何解決因多任務(wù)、強(qiáng)QoS約束及任務(wù)過量等復(fù)雜性因素導(dǎo)致的云制造系統(tǒng)組合效果不佳的問題，本文通過分析研究提出了面向復(fù)雜任務(wù)請(qǐng)求的服務(wù)組合優(yōu)化全局策略(global optimal strategy for complex task oriented services composition,GOS-CTOSC)框架,并介紹了上述策略框架在云制造原型系統(tǒng)服務(wù)組合優(yōu)化引擎中的實(shí)現(xiàn)及驗(yàn)證。

1　云制造典型的任務(wù)請(qǐng)求場(chǎng)景

本研究首先選取一個(gè)典型的云制造案例即摩托車的生產(chǎn)過程(圖1)來闡述問題場(chǎng)景：摩托車生產(chǎn)包括從“車架生產(chǎn)”到“包裝發(fā)運(yùn)”的6個(gè)生產(chǎn)環(huán)節(jié)(子任務(wù))，每環(huán)節(jié)須在相應(yīng)服務(wù)候選集(candidate service set，CSS)中選取一個(gè)構(gòu)件服務(wù)(component service，CS)來執(zhí)行相應(yīng)的子任務(wù)，如成車總裝可選取宗申或隆鑫裝配線來完成。整體制造任務(wù)則由這些構(gòu)件服務(wù)所構(gòu)成的組合服務(wù)來完成。

圖1　模擬摩托車生產(chǎn)流程

假定每個(gè)服務(wù)候選集均給定3個(gè)可用的構(gòu)件服務(wù),每個(gè)構(gòu)件服務(wù)的QoS指標(biāo)值(以時(shí)間指標(biāo)為例)給定在圖2中。

圖2　各構(gòu)件服務(wù)的給定QoS指標(biāo)值

場(chǎng)景1(多任務(wù)):本場(chǎng)景假定制造任務(wù)T1和T2同時(shí)請(qǐng)求服務(wù),均需從候選集CSS1到候選集CSS6中選取構(gòu)件服務(wù)，并構(gòu)造兩個(gè)組合服務(wù)來響應(yīng)制造任務(wù)T1和T2。其中,給定T1和T2的QoS約束分別為QoS-time1<523，QoS-time2<498。

場(chǎng)景2(強(qiáng)QoS約束):本場(chǎng)景在場(chǎng)景1的基礎(chǔ)上,進(jìn)一步假定制造任務(wù)T2為強(qiáng)QoS約束(對(duì)完成時(shí)間要求極高),即給定T2的QoS約束為QoS-time2<350,T1的QoS約束仍為QoS-time1<523。

場(chǎng)景3(任務(wù)過量):假設(shè)出現(xiàn)了同時(shí)請(qǐng)求的制造任務(wù)(不含強(qiáng)QoS約束的任務(wù))多于可用服務(wù)的情況,即假定制造任務(wù)T1、T2、T3、T4同時(shí)請(qǐng)求服務(wù)，其QoS約束分別為QoS-time1<550,QoS-time2<1200,QoS-time3<1800,QoS-time4<1600。

2　傳統(tǒng)服務(wù)組合優(yōu)化策略概述與應(yīng)用分析

2.1傳統(tǒng)服務(wù)組合優(yōu)化策略概述

傳統(tǒng)服務(wù)組合優(yōu)化方法在實(shí)施組合優(yōu)化時(shí)主要基于以下四種策略：①局部策略[6]。局部策略從每個(gè)子任務(wù)對(duì)應(yīng)的構(gòu)件服務(wù)候選集中選擇QoS最優(yōu)的構(gòu)件服務(wù)，構(gòu)造整體QoS較優(yōu)的組合服務(wù)。②全局策略[6-7,10,14-15]。傳統(tǒng)全局策略以單一“多資源需求型”任務(wù)請(qǐng)求為基本假設(shè)條件，依據(jù)構(gòu)件服務(wù)對(duì)組合服務(wù)整體QoS水平提升的貢獻(xiàn)大小來實(shí)施優(yōu)選，尋求面向整體任務(wù)QoS最優(yōu)的服務(wù)組合方案。③混合策略[16-18]?；旌喜呗缘幕舅悸肥菍⒄w任務(wù)的全局QoS約束分解為各子任務(wù)的局部QoS約束，進(jìn)而實(shí)施分布式的優(yōu)選過程。④改進(jìn)全局策略[7,19]。由于全局策略可能無法找到可行組合服務(wù)，故改進(jìn)全局策略加入了服務(wù)等級(jí)協(xié)議(service level agreement,SLA)協(xié)商機(jī)制。發(fā)生可行組合失敗時(shí),該機(jī)制松弛QoS約束直至最佳可行方案出現(xiàn),以最大限度地保證SLA被滿足。

2.2傳統(tǒng)服務(wù)組合優(yōu)化策略應(yīng)用分析

2.2.1多任務(wù)場(chǎng)景下的組合優(yōu)化

針對(duì)場(chǎng)景1,直接運(yùn)用局部策略,即同時(shí)到達(dá)的制造任務(wù)T1和T2在局部策略的作用下將分別從各個(gè)云服務(wù)候選集中挑選出最佳的基礎(chǔ)云服務(wù)，如圖3所示。由圖3可知，在多任務(wù)場(chǎng)景下，基于相同的評(píng)估指標(biāo)體系、優(yōu)選模型、優(yōu)化算法,同一批優(yōu)秀的候選服務(wù)易被多個(gè)復(fù)雜任務(wù)中相同類型的子任務(wù)同時(shí)選中，進(jìn)而造成選擇沖突。

再就場(chǎng)景1,考慮直接運(yùn)用傳統(tǒng)全局策略的情況:在全局策略的作用下，系統(tǒng)將逐一面向復(fù)雜任務(wù)T1和T2構(gòu)造全局最佳的組合服務(wù)，如圖4所示。

由圖4分析可知:將復(fù)雜多任務(wù)請(qǐng)求轉(zhuǎn)化為多次單任務(wù)請(qǐng)求后，可能出現(xiàn)先序任務(wù)用盡較優(yōu)候選服務(wù)而后序任務(wù)難以保障SLA的現(xiàn)象，即次序沖突。

2.2.2強(qiáng)QoS約束場(chǎng)景下的組合優(yōu)化

針對(duì)場(chǎng)景2，當(dāng)強(qiáng)QoS約束任務(wù)請(qǐng)求時(shí)，傳統(tǒng)全局策略存在無法找到可行組合服務(wù)的可能[7](圖5)。局部策略、混合策略不可能構(gòu)造成比傳統(tǒng)全局策略QoS更優(yōu)的組合服務(wù)，也無法克服強(qiáng)QoS約束下難以找到可行組合服務(wù)的缺陷。改進(jìn)全局策略雖可通過協(xié)商SLA來降低某些QoS約束條件以最大限度保證SLA的滿足,但不能避免因松弛QoS約束引發(fā)的組合服務(wù)QoS水平不足；即使形成最優(yōu)組合服務(wù)，也是通過降低用戶某些方面的QoS期望得到的結(jié)果，無疑是一種迫不得已的折中方案。

圖3　局部策略下多任務(wù)服務(wù)組合的選擇沖突

圖4　全局策略下多任務(wù)服務(wù)組合的次序沖突

圖5　強(qiáng)QoS約束下傳統(tǒng)全局策略的失效

傳統(tǒng)組合優(yōu)化策略的局限性在于任務(wù)與組合服務(wù)之間存在雙射限定。而單個(gè)組合服務(wù)所能提供的QoS存在上限，一旦任務(wù)的QoS約束增強(qiáng)到所有組合服務(wù)的能力上限之外時(shí)，即發(fā)生可行組合失敗。

2.2.3任務(wù)過量場(chǎng)景下的組合優(yōu)化

在場(chǎng)景3的實(shí)例中,由于各候選集中均只有3個(gè)候選服務(wù)，故只可產(chǎn)生3個(gè)組合服務(wù)。依據(jù)傳統(tǒng)策略，3個(gè)組合服務(wù)僅能響應(yīng)3個(gè)制造任務(wù)請(qǐng)求，因而總有一個(gè)任務(wù)請(qǐng)求會(huì)發(fā)生服務(wù)響應(yīng)失敗(圖6)。

圖6　任務(wù)過量場(chǎng)景下傳統(tǒng)組合優(yōu)化策略的失效

實(shí)際上,從場(chǎng)景3的給定條件來看,3個(gè)組合服務(wù)的QoS較高,而4個(gè)任務(wù)給定的QoS約束偏低,因此存在完全響應(yīng)4個(gè)任務(wù)請(qǐng)求的可能性。但傳統(tǒng)組合優(yōu)化策略限定組合與任務(wù)間“一一映射”關(guān)系，特別是任意組合服務(wù)只可為單個(gè)任務(wù)請(qǐng)求提供服務(wù)(獨(dú)占性條件)，使得某些任務(wù)享有的服務(wù)能力有余，而另一些任務(wù)的組合需求卻無法得到滿足。

3　云制造中面向復(fù)雜任務(wù)請(qǐng)求的服務(wù)組合優(yōu)化全局策略

基于對(duì)傳統(tǒng)組合優(yōu)化策略的應(yīng)用分析，本文認(rèn)為云制造中的服務(wù)組合優(yōu)化策略需考慮以下三大原則：①多任務(wù)全局優(yōu)化，即構(gòu)造面向復(fù)雜多任務(wù)的、整體全局策略；②組合服務(wù)捆綁，即突破任務(wù)請(qǐng)求只允許由一個(gè)組合服務(wù)來執(zhí)行的基本假設(shè)；③組合服務(wù)共享，即破除加諸組合服務(wù)上的獨(dú)占性條件。

根據(jù)上述原則,本文設(shè)計(jì)了云制造中面向復(fù)雜任務(wù)請(qǐng)求的GOS-CTOSC框架。GOS-CTOSC框架包含了由簡(jiǎn)至繁的三類組合模式定義。

3.1單組合執(zhí)行每任務(wù)組合模式

定義1單組合執(zhí)行每任務(wù)(each composition for each task,ECET)組合模式,即針對(duì)每個(gè)任務(wù)請(qǐng)求只構(gòu)造一個(gè)組合服務(wù)予以執(zhí)行。

ECET組合模式適用于解決不含強(qiáng)QoS約束和任務(wù)過量的復(fù)雜多任務(wù)服務(wù)組合優(yōu)化問題(場(chǎng)景1)。它是GOS-CTOSC框架中最簡(jiǎn)單的多任務(wù)服務(wù)組合優(yōu)化全局策略,包含兩個(gè)特征:①面向所有任務(wù)請(qǐng)求實(shí)施整體決策(區(qū)別于傳統(tǒng)全局策略)。②任務(wù)請(qǐng)求與組合服務(wù)之間仍沿用“一一映射”假設(shè)條件。

根據(jù)定義1,其問題模型建立過程如下。

(1)設(shè)定決策變量x(i,j,k)。x(i,j,k)=1,即候選服務(wù)集CSSj中的第k個(gè)構(gòu)件服務(wù)CS(j,k)被選取到組合服務(wù)Si中,用于執(zhí)行任務(wù)Ti;反之，則x(i，j，k)=0。

(2)輸入?yún)?shù)。qm(CS(j,k))(m=1，2,…,M)表示任意構(gòu)件服務(wù)CS(j,k)所能提供的某種維度的QoS水平,例如q1(CS(j,k))可代表CS(j,k)時(shí)間維度的QoS水平,q2(CS(j,k))可代表CS(j,k)成本維度的QoS水平,q3(CS(j,k))可代表CS(j,k)可靠性維度的QoS水平。CS(j,k)所能提供的整體QoS水平,可用全維度的向量Q(CS(j,k))=(q1(CS(j,k)),q2(CS(j,k)),…,qM(CS(j,k)))來表示。qm(Ti)表示任意復(fù)雜任務(wù)請(qǐng)求Ti給定的某種維度的QoS約束。Ti給定的整體QoS約束可用向量Q(Ti)=(q1(Ti),q2(Ti),…,qM(Ti))表示。

(3)問題模型:

(1)

(2)

(3)

(4)

(5)

針對(duì)場(chǎng)景1的求解,由圖7可知,盡管ECET組合模式針對(duì)單個(gè)任務(wù)構(gòu)造的組合服務(wù)QoS未必是最優(yōu)(執(zhí)行T1的組合服務(wù)QoS只有520,小于它所能達(dá)到的最優(yōu)結(jié)果490)，卻能在多個(gè)任務(wù)間做到統(tǒng)籌規(guī)劃,最終獲得滿足所有任務(wù)請(qǐng)求QoS約束的全局最優(yōu)QoS值。

圖7　ECET組合模式下針對(duì)T1和T2的組合結(jié)果

3.2多組合執(zhí)行每任務(wù)組合模式

定義2多組合執(zhí)行每任務(wù)(multi-composition for each task,MCET)組合模式,即針對(duì)每個(gè)任務(wù)請(qǐng)求,由多個(gè)組合服務(wù)捆綁后形成一個(gè)組合服務(wù)組予以執(zhí)行。

MCET組合模式適用于解決含強(qiáng)QoS約束的復(fù)雜多任務(wù)服務(wù)組合優(yōu)化問題(場(chǎng)景2)。它包含兩部分的整體決策：①利用可用的構(gòu)件服務(wù)決策組合服務(wù)的構(gòu)造、優(yōu)選過程；②利用構(gòu)造好的組合服務(wù)，決策組合服務(wù)組的形成過程。該模式破解強(qiáng)QoS約束任務(wù)請(qǐng)求的關(guān)鍵在于：以面向所有任務(wù)請(qǐng)求的整體決策為基礎(chǔ)，通過將能力不足的若干組合服務(wù)捆綁來響應(yīng)強(qiáng)QoS約束的任務(wù)請(qǐng)求，即允許組合服務(wù)與任務(wù)請(qǐng)求之間多對(duì)一的關(guān)系。

根據(jù)定義2，其問題模型建立過程如下。

(1)設(shè)定決策變量x(l,j,k)與y(l,i)。其中，x(l,j,k)=1表示第k個(gè)構(gòu)件服務(wù)CS(j,k)自第j個(gè)候選服務(wù)集CSSj被選取到第l個(gè)組合服務(wù)Sl中;反之則x(l,j,k)=0。當(dāng)y(l,i)=1時(shí),表示第l個(gè)組合服務(wù)Sl被捆綁到第i個(gè)組合服務(wù)組SGi中,為任務(wù)Ti服務(wù)；反之則y(l，i)=0。

(2)輸入?yún)?shù)。qm(CS(j,k))表示任意構(gòu)件服務(wù)CS(j,k)所能提供的某種維度的QoS水平。CS(j,k)所能提供的整體QoS水平用向量Q(CS(j,k))=(q1(CS(j,k)),q2(CS(j,k)),…,qM(CS(j,k)))來表示。qm(Ti)表示任意復(fù)雜任務(wù)請(qǐng)求Ti給定的某種維度的QoS約束。Ti給定的整體QoS約束可用向量Q(Ti)=(q1(Ti),q2(Ti),…,qM(Ti))表示。

(3)問題模型：

(6)

(7)

(8)

Q(SGi)=fin_out(Q(CS(j,k)),x(l,j,k),y(l,i))

(9)

(10)

式(6)～式(10)的意義與ECET的問題模型類似。MCET問題模型特殊在于：①目標(biāo)函數(shù)(式(6))及約束條件(式(7)、式(8))的構(gòu)成元素由組合服務(wù)替換成了組合服務(wù)組，以反映MCET下組合服務(wù)與任務(wù)請(qǐng)求之間的“多對(duì)一”關(guān)系以及“合眾為一”的組合服務(wù)捆綁策略;②式(9)代表了如何從構(gòu)件服務(wù)的QoS計(jì)算得出組合服務(wù)QoS，再得到組合服務(wù)組QoS的過程，該過程需運(yùn)用內(nèi)部組合結(jié)構(gòu)模式及其表達(dá)式計(jì)算得到組合服務(wù)QoS[5],以此為基礎(chǔ),再運(yùn)用外部組合結(jié)構(gòu)模式及其表達(dá)式得出組合服務(wù)組QoS[14],其中,函數(shù)fin_out代表運(yùn)用內(nèi)部及外部組合結(jié)構(gòu)模式的計(jì)算表達(dá)式實(shí)施運(yùn)算。

針對(duì)場(chǎng)景2的求解,由圖8可知，基于MCET模式,當(dāng)T1的強(qiáng)QoS約束導(dǎo)致單個(gè)組合服務(wù)無法滿足時(shí),可將多個(gè)組合服務(wù)再次聚集到一起，捆綁成一個(gè)組合服務(wù)組，共同響應(yīng)強(qiáng)QoS約束的任務(wù)請(qǐng)求。

圖8　MCET組合模式下針對(duì)T1和T2的組合結(jié)果

3.3多組合執(zhí)行多任務(wù)組合模式

定義3多組合執(zhí)行多任務(wù)(multi-composition for multi-task,MCMT)組合模式。即若干任務(wù)可組成一個(gè)任務(wù)組,若干組合服務(wù)可組成一個(gè)組合服務(wù)組；一個(gè)任務(wù)組中的多個(gè)任務(wù)可共享使用一個(gè)組合服務(wù)組中的多個(gè)組合服務(wù)。

MCMT組合模式適用于有任務(wù)過量的復(fù)雜多任務(wù)服務(wù)組合優(yōu)化問題(場(chǎng)景3),其整體決策包含三個(gè)部分:①合理的任務(wù)組劃分；②組合服務(wù)的構(gòu)造、優(yōu)選決策；③合理的組合服務(wù)組構(gòu)造。MCMT模式破解任務(wù)過量問題的關(guān)鍵在于:它同時(shí)滿足多任務(wù)全局優(yōu)化、組合服務(wù)捆綁、組合服務(wù)共享三個(gè)原則，允許組合服務(wù)與任務(wù)請(qǐng)求之間最一般的多對(duì)多關(guān)系，以最大限度地挖掘現(xiàn)有資源的潛力。

根據(jù)定義3,其問題模型建立過程如下。

(1)設(shè)定決策變量z(i,n)、x(l,j,k)、y(l,n)。z(i，n)=1代表第i個(gè)任務(wù)請(qǐng)求Ti被配屬到第n個(gè)任務(wù)組TGn;反之則z(i,n)=0。

x(l,j,k)=1代表第k個(gè)構(gòu)件服務(wù)CS(j,k)自第j個(gè)候選服務(wù)集CSSj被選取組合到第l個(gè)組合服務(wù)Sl中;反之則x(l,j,k)=0。y(l,n)=1代表第l個(gè)組合服務(wù)Sl被捆綁到第i個(gè)組合服務(wù)組SGi中,共享給第n個(gè)任務(wù)組TGn中的所有任務(wù)使用;反之則y(l,n)=0。

(2)輸入?yún)?shù)。輸入?yún)?shù)與多組合執(zhí)行每任務(wù)組合模式輸入?yún)?shù)相同。

(3)問題模型：

(11)

(12)

(13)

Q(SGi)=fin_out(Q(CS(j,k)),x(l,j,k),y(l,n))

(14)

(15)

式(11)～式(15)的意義與ECET及MCET問題模型類似,MCMT問題模型的特殊之處在于:它新增了任務(wù)請(qǐng)求的分組過程(式(15))，并利用任務(wù)組對(duì)應(yīng)組合服務(wù)組(式(12))，構(gòu)成了GOS-CTOSC框架中最一般的“多對(duì)多”映射關(guān)系,形成了該框架中最一般的問題模型。但正因它的一般性,使之具有了極高的問題復(fù)雜度,也更依賴高效算法的設(shè)計(jì)與實(shí)現(xiàn)。

需要說明的是,組合服務(wù)組和任務(wù)組規(guī)模不會(huì)無限膨脹，且組合服務(wù)組也不會(huì)被無限劃分。原因在于:①組合服務(wù)捆綁規(guī)模的增長會(huì)自然受到QoS指標(biāo)體系的約束，例如：實(shí)施捆綁策略固然可利于QoS時(shí)間指標(biāo)優(yōu)化(更多資源執(zhí)行任務(wù)使工期縮短)，但同時(shí)也導(dǎo)致QoS成本、可靠性等指標(biāo)惡化(租用更多資源需支付更多租金,協(xié)同更多服務(wù)環(huán)節(jié)使風(fēng)險(xiǎn)增加),故一定捆綁規(guī)模下會(huì)形成Max-min問題下的平衡態(tài);②由于構(gòu)件服務(wù)的QoS有限,則組合服務(wù)組必然存在QoS上限,故任務(wù)組規(guī)模擴(kuò)張也將受到遏制;③由于資源共享將導(dǎo)致管理、物流、協(xié)同等額外開銷，故組合服務(wù)組被無限劃分共享的情況也會(huì)受到遏制。

基于上述問題模型,求解場(chǎng)景3如圖9所示。針對(duì)場(chǎng)景3的求解,由圖9可知,當(dāng)組合服務(wù)相對(duì)任務(wù)請(qǐng)求發(fā)生數(shù)量上的緊缺時(shí)，可依據(jù)MCMT模式：一方面按照最適宜的分組數(shù)量對(duì)任務(wù)請(qǐng)求進(jìn)行分組，另一方面按相同分組數(shù)量將構(gòu)造的組合服務(wù)捆綁成若干組合服務(wù)組，并將組合服務(wù)組配置給各任務(wù)請(qǐng)求組共享使用，以此來化解組合服務(wù)緊缺的矛盾。

圖9　MCMT組合模式下針對(duì)過量任務(wù)的組合結(jié)果

4　GOS-CTOSC框架的實(shí)現(xiàn)與驗(yàn)證

4.1GOS-CTOSC框架在云制造原型系統(tǒng)服務(wù)組合優(yōu)化引擎中的實(shí)現(xiàn)

GOS-CTOSC框架實(shí)現(xiàn)了三類組合模式：ECET、MCET及MCMT。其特性如表1所示。從表1可知,GOS-CTOSC框架中,三類組合模式的優(yōu)勢(shì)和局限均十分突出,沒有一種組合模式可將其他模式完全代替。故在云制造應(yīng)用中，可根據(jù)實(shí)際在適用范圍、復(fù)雜度、難度間進(jìn)行權(quán)衡和抉擇。

表1　GOS-CTOSC框架中各組合模式的特性比較

注:A.單/多個(gè)“單資源需求型”任務(wù)或單個(gè)“多資源需求型”任務(wù)請(qǐng)求情形;B.不含強(qiáng)QoS約束和任務(wù)過量情形。

我們?cè)谇捌谘邪l(fā)的云制造原型系統(tǒng)[20]的服務(wù)組合優(yōu)化引擎中設(shè)計(jì)實(shí)現(xiàn)了任務(wù)請(qǐng)求探測(cè)模塊。該模塊在調(diào)用GOS-CTOSC框架中不同的組合模式之前，會(huì)檢測(cè)任務(wù)請(qǐng)求的類型，以便組合執(zhí)行模塊調(diào)用最適宜的組合模式執(zhí)行服務(wù)組合優(yōu)化過程。

GOS-CTOSC框架采用Java語言編程實(shí)現(xiàn);同時(shí),利用MATLAB實(shí)現(xiàn)了ECET、MCET及MCMT三種組合模式,并封裝成可供調(diào)用的.jar文件。其中,ECET、MCET及MCMT實(shí)現(xiàn)模塊均選取了時(shí)間、成本、可靠性三個(gè)維度的QoS指標(biāo)，并分別基于3種組合模式的問題模型實(shí)現(xiàn)了對(duì)應(yīng)的求解算法；求解算法采用了基于混合算子的矩陣編碼遺傳算法(hybrid-operator based matrix coded genetic algorithm,HO-MCGA)予以實(shí)現(xiàn)。在筆者的前期研究中，該算法對(duì)較復(fù)雜的組合優(yōu)化問題具有良好的求解性能[14]。

GOS-CTOSC中實(shí)現(xiàn)多任務(wù)請(qǐng)求與組合模式的執(zhí)行邏輯如圖10所示。

圖10　多任務(wù)請(qǐng)求與三種組合模式的執(zhí)行邏輯

4.2模擬實(shí)驗(yàn)

基于4.1節(jié)的GOS-CTOSC框架實(shí)現(xiàn),我們?cè)谠浦圃煸拖到y(tǒng)中分別模擬了多任務(wù)、強(qiáng)QoS約束、任務(wù)過量的情形。原型系統(tǒng)模擬生成上述三類情形的步驟如下：

(1)隨機(jī)生成各候選構(gòu)件服務(wù)的QoS指標(biāo)值。

(2)從各個(gè)構(gòu)件服務(wù)候選集中找到時(shí)間、成本、可靠性三種維度的最大、最小指標(biāo)值；利用這些值計(jì)算組合服務(wù)的絕對(duì)最小、最大QoS評(píng)估值[6](用Qmin、Qmax表示)。

(3)分別生成三類情形:①多任務(wù)情形。在[Qmin,Qmax)內(nèi)隨機(jī)生成若干任務(wù)請(qǐng)求的QoS約束,且任務(wù)數(shù)量少于給定的構(gòu)件服務(wù)所能組成的組合服務(wù)的規(guī)模。②強(qiáng)QoS約束情形。在[Qmin,Qmax]內(nèi)靠近Qmax一側(cè),隨機(jī)生成若干任務(wù)請(qǐng)求的QoS約束,當(dāng)其值接近Qmax時(shí),即出現(xiàn)強(qiáng)QoS約束。③任務(wù)過量的情形。在[Qmin,Qmax)內(nèi)隨機(jī)生成若干任務(wù)請(qǐng)求的QoS約束，且任務(wù)數(shù)量可多于給定的構(gòu)件服務(wù)所能組成的組合服務(wù)的規(guī)模。

從服務(wù)組合優(yōu)化引擎的運(yùn)行狀況來看,GOS-CTOSC框架能高效高質(zhì)量地求解多任務(wù)或強(qiáng)QoS約束場(chǎng)景下的服務(wù)組合問題(表2及圖11)；傳統(tǒng)全局策略因出現(xiàn)了無法滿足某些任務(wù)QoS約束的情況,以致組合結(jié)果的QoS受懲罰而下降(表2)。此外，當(dāng)任務(wù)過量時(shí),GOS-CTOSC也能

表2　給定20×6個(gè)候選構(gòu)件服務(wù)下

以顯著高于傳統(tǒng)策略的QoS響應(yīng)所有任務(wù)請(qǐng)求(表2)。但在該場(chǎng)景下，GOS-CTOSC僅適合處理較小的問題規(guī)模，當(dāng)問題規(guī)模逐漸增大時(shí)，其時(shí)間性能漸成瓶頸(見圖11)。

圖11　不同組合模式在不同問題實(shí)例下的請(qǐng)求響應(yīng)時(shí)間

5　結(jié)論

(1)指出了云制造系統(tǒng)任務(wù)請(qǐng)求的特殊性及傳統(tǒng)服務(wù)組合優(yōu)化策略應(yīng)用于云制造典型場(chǎng)景存在的選擇沖突、次序沖突、可行組合失敗、服務(wù)響應(yīng)失敗等局限與原因，并提出了服務(wù)組合優(yōu)化策略設(shè)計(jì)的原則。

(2)設(shè)計(jì)了面向復(fù)雜任務(wù)請(qǐng)求的服務(wù)組合優(yōu)化全局策略框架，突破了傳統(tǒng)策略面向單任務(wù)及加諸于任務(wù)請(qǐng)求和組合服務(wù)之上的“一一映射”基本假設(shè)，建立了以多任務(wù)全局優(yōu)化、組合服務(wù)捆綁、組合服務(wù)共享為原則,適宜于云制造環(huán)境的ECET、MCET及MCMT組合模式。

(3)提出了以面向復(fù)雜任務(wù)請(qǐng)求的服務(wù)組合優(yōu)化全局策略框架為基礎(chǔ)的服務(wù)組合優(yōu)化引擎實(shí)現(xiàn)方案，并在云制造原型系統(tǒng)中初步驗(yàn)證了其可用性。

(4)下一步工作將設(shè)計(jì)針對(duì)MCMT組合模式的高效智能算法,以破除服務(wù)組合優(yōu)化引擎在任務(wù)過量場(chǎng)景下的時(shí)間性能瓶頸。

[1]Tao F,Laili Y,Xu L,et al.FC-PACO-RM:A Parallel Method for Service Composition Optimal-selection in Cloud Manufacturing System[J].IEEE Transactions on Industrial Informatics,2013,9(4):2023-2033.

[2]Laili Y,Tao F,Zhang L,et al.A Study of Optimal Allocation of Computing Resources in Cloud Manufacturing Systems[J].International Journal of Advanced Manufacturing Technology,2012,63:671-690.

[3]陶飛,張霖,郭華,等.云制造特征及云服務(wù)組合關(guān)鍵問題研究[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(3):477-486.

Tao Fei,Zhang Lin,Guo Hua,et al.Typical Characteristics of Cloud Manufacturing and Several Key Issues of Cloud Service Composition[J].Computer Integr ated Manufacturing Systems,2011,17(3):477-486.

[4]鄧水光,黃龍濤,尹建偉,等.Web服務(wù)組合技術(shù)框架及其研究進(jìn)展[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(2):404-412.

Deng Shuiguang,Huang Longtao,Yin Jianwei,et al.Technical Framework for Web Services Composition and Its Progress[J].Computer Integrated Manufacturing Systems,2011,17(2):404-412.

[5]Cardoso J,Sheth A,Miller J,et al.Quality of Service for Workflows and Web Service Processes[J].Journal of Web Semantics,2004(1):281-308.

[6]Zeng L,Benatallah B,Ngu A H H，et al.QoS-aware Middleware for Web Services Composition[J].IEEE Transactions on Software Engineering,2004,30(5):311-327.

[7]Ardagna D,Pernici B.Adaptive Service Composition in Flexible Processes[J].IEEE Transactions on Software Engineering,2007,33(6):369-384.

[8]Laili Y,Tao F,Zhang L,et al.A Ranking Chaos Algorithm for Dual Scheduling of Cloud Service and Computing Resource in Private Cloud[J].Computer in Industry,2013,64(4):448-463.

[9]Tao F,Guo H,Zhang L,et al.Modelling of Combinable Relationship-based Composition Service Network and Theoretical Proof of Its Scale-free Characteristics[J].Enterprise Information Systems,2012,6(4):373-404.

[10]Tao F,Zhao D,Hu Y,et al.Resource Service Composition and Its Optimal-selection Based on Particle Swarm Optimization in Manufacturing Grid System[J].IEEE Transactions on Industrial Informatics,2008,4(4):315-327.

[11]Tao F,Hu Y,Zhou Z,et al.Application and Modeling of Resource Service Trust-QoS Evaluation in Manufacturing Grid System[J].International Journal of Production Research,2009,47(6):1521-1550.

[12]Tao F,Zhao D,Hu Y,et al.Correlation-aware Resource Service Composition and Optimal-selection in Manufacturing Grid[J].European Journal of Operational Research,2010,201(1):109-143.

[13]Tao F,Zhang L,Lu K,et al.Research on Manufacturing Grid Resource Service Optimal-selection and Composition Framework[J].Enterprise Information Systems,2012,6(2)：237-264.

[14]Liu W,Liu B,Sun D,et al.Study on Multi-task Oriented Services Composition and Optimization with the “Multi-composition for Each Task” Pattern in Cloud Manufacturing Systems[J].International Journal of Computer Integrated Manufacturing,2013,26(8):86-805.

[15]劉衛(wèi)寧，劉波，孫棣華. 面向多任務(wù)的制造云服務(wù)組合[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2013，19(1)：199-209.

Liu Weining,Liu Bo,Sun Dihua.Multi-task Oriented Service Composition[J].Computer Integrated Manufacturing Systems,2013,19(1):199-209.

[16]Alrifai M,Risse T,Nejdl W.A Hybrid Approach for Efficient Web Service Composition with End-to-end QoS Constraints[J].ACM Transactions on the Web,2012,6(2):1-31.

[17]Li J,Zhao Y,Sun H,et al.DH4SS:A Distributed Heuristic for QoS-based Service Selection[J].International Journal of Web and Grid Services,2011,7(4):388-409.

[18]Richter J,Baruwal C M,Kowalczyk R,et al.Establishing Composite SLAs through Concurrent QoS Negotiation with Surplus Redistribution[J].Concurrency and Computation:Practice and Experience,2012,24(9):938-955.

[19]Lin C,Sheu R,Chang Y,et al.A Relaxable Service Selection Algorithm for QoS-based Web Service Composition[J].Information and Software Technology,2011,53(12):1370-1381.

[20]劉波,劉衛(wèi)寧,孫棣華,等.自適應(yīng)制造資源動(dòng)態(tài)服務(wù)組合與優(yōu)化框架[J].中國機(jī)械工程,2012,23(10):1187-1193.

Liu Bo,Liu Weining,Sun Dihua,et al.A Self-adaptive Dynamic Service Composition and Optimization Framework for Manufacturing Resource[J].China Mechanical Engineering,2012,23(10):1187-1193.

(編輯張洋)

Framework of Complex Task Oriented Service Composition and Optimization in Cloud Manufacturing Systems

Liu BoZhang Zili

Southwest University,Chongqing,400715

To circumvent the problems of SCO in the typical scenarios of complex multi-task requests,severe QoS constraints on tasks,and services shortage relative to tasks in cloud manufacturing systems,a framework of global optimal strategy for complex task oriented services composition(GOS-CTOSC) was presented.In this framework,the principles of multi-task oriented holistic optimization and the ideas of composite services binding and sharing were proposed to eliminate the drawbacks of traditional SCO approaches.Based on the principle,the composition patterns of “each composition for each task”,“multi-composition for each task” and “multi-composition for multi-task” were designed in the framework,and the related problem models were also formulated.The implementation and evaluation of the framework were conducted in a prototype system,by means of the hybrid-operator based matrix coded genetic algorithm.The experimental results indicate the presented framework is sound performance-wise.

cloud manufacturing;complex task;service composition and optimization(SCO);global strategy

2014-05-19

國家科技支撐計(jì)劃資助項(xiàng)目(2012BAD35B08)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(XDJK2014C042，SWU113028)

TH166DOI：10.3969/j.issn.1004-132X.2015.08.011

劉波,男,1981年生。西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院講師、博士。主要研究方向?yàn)樵浦圃?、云?jì)算、服務(wù)組合。發(fā)表論文8篇。張自力,男,1964年生。西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院教授、博士研究生導(dǎo)師。