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

劉　波　張自力

西南大學,重慶,400715

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

劉波張自力

西南大學,重慶,400715

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

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

0　引言

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

1　云制造典型的任務請求場景

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

圖1　模擬摩托車生產流程

假定每個服務候選集均給定3個可用的構件服務,每個構件服務的QoS指標值(以時間指標為例)給定在圖2中。

圖2　各構件服務的給定QoS指標值

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

場景2(強QoS約束):本場景在場景1的基礎上,進一步假定制造任務T2為強QoS約束(對完成時間要求極高),即給定T2的QoS約束為QoS-time2<350,T1的QoS約束仍為QoS-time1<523。

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

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

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

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

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

2.2.1多任務場景下的組合優(yōu)化

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

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

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

2.2.2強QoS約束場景下的組合優(yōu)化

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

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

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

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

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

2.2.3任務過量場景下的組合優(yōu)化

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

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

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

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

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

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

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

定義1單組合執(zhí)行每任務(each composition for each task,ECET)組合模式,即針對每個任務請求只構造一個組合服務予以執(zhí)行。

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

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

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

(2)輸入?yún)?shù)。qm(CS(j,k))(m=1，2,…,M)表示任意構件服務CS(j,k)所能提供的某種維度的QoS水平,例如q1(CS(j,k))可代表CS(j,k)時間維度的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)表示任意復雜任務請求Ti給定的某種維度的QoS約束。Ti給定的整體QoS約束可用向量Q(Ti)=(q1(Ti),q2(Ti),…,qM(Ti))表示。

(3)問題模型:

(1)

(2)

(3)

(4)

(5)

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

圖7　ECET組合模式下針對T1和T2的組合結果

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

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

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

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

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

(2)輸入?yún)?shù)。qm(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)表示任意復雜任務請求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問題模型特殊在于：①目標函數(shù)(式(6))及約束條件(式(7)、式(8))的構成元素由組合服務替換成了組合服務組，以反映MCET下組合服務與任務請求之間的“多對一”關系以及“合眾為一”的組合服務捆綁策略;②式(9)代表了如何從構件服務的QoS計算得出組合服務QoS，再得到組合服務組QoS的過程，該過程需運用內部組合結構模式及其表達式計算得到組合服務QoS[5],以此為基礎,再運用外部組合結構模式及其表達式得出組合服務組QoS[14],其中,函數(shù)fin_out代表運用內部及外部組合結構模式的計算表達式實施運算。

針對場景2的求解,由圖8可知，基于MCET模式,當T1的強QoS約束導致單個組合服務無法滿足時,可將多個組合服務再次聚集到一起，捆綁成一個組合服務組，共同響應強QoS約束的任務請求。

圖8　MCET組合模式下針對T1和T2的組合結果

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

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

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

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

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

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

(2)輸入?yún)?shù)。輸入?yún)?shù)與多組合執(zhí)行每任務組合模式輸入?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問題模型的特殊之處在于:它新增了任務請求的分組過程(式(15))，并利用任務組對應組合服務組(式(12))，構成了GOS-CTOSC框架中最一般的“多對多”映射關系,形成了該框架中最一般的問題模型。但正因它的一般性,使之具有了極高的問題復雜度,也更依賴高效算法的設計與實現(xiàn)。

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

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

圖9　MCMT組合模式下針對過量任務的組合結果

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

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

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

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

注:A.單/多個“單資源需求型”任務或單個“多資源需求型”任務請求情形;B.不含強QoS約束和任務過量情形。

我們在前期研發(fā)的云制造原型系統(tǒng)[20]的服務組合優(yōu)化引擎中設計實現(xiàn)了任務請求探測模塊。該模塊在調用GOS-CTOSC框架中不同的組合模式之前，會檢測任務請求的類型，以便組合執(zhí)行模塊調用最適宜的組合模式執(zhí)行服務組合優(yōu)化過程。

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

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

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

4.2模擬實驗

基于4.1節(jié)的GOS-CTOSC框架實現(xiàn),我們在云制造原型系統(tǒng)中分別模擬了多任務、強QoS約束、任務過量的情形。原型系統(tǒng)模擬生成上述三類情形的步驟如下：

(1)隨機生成各候選構件服務的QoS指標值。

(2)從各個構件服務候選集中找到時間、成本、可靠性三種維度的最大、最小指標值；利用這些值計算組合服務的絕對最小、最大QoS評估值[6](用Qmin、Qmax表示)。

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

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

表2　給定20×6個候選構件服務下

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

圖11　不同組合模式在不同問題實例下的請求響應時間

5　結論

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

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

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

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

[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]陶飛,張霖,郭華,等.云制造特征及云服務組合關鍵問題研究[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服務組合技術框架及其研究進展[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)寧，劉波，孫棣華. 面向多任務的制造云服務組合[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)寧,孫棣華,等.自適應制造資源動態(tài)服務組合與優(yōu)化框架[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

國家科技支撐計劃資助項目(2012BAD35B08)；中央高校基本科研業(yè)務費專項資金資助項目(XDJK2014C042，SWU113028)

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

劉波,男,1981年生。西南大學計算機與信息科學學院講師、博士。主要研究方向為云制造、云計算、服務組合。發(fā)表論文8篇。張自力,男,1964年生。西南大學計算機與信息科學學院教授、博士研究生導師。