基于E-CARGO模型的云制造服務組合方法

錢 晨，張以文，吳其林，胡 博

1(安徽大學 計算機科學與技術學院，合肥 230601)2(巢湖學院 信息工程學院，合肥 238000)3(深圳易伙科技有限責任公司，深圳 518055)

E-mail ：zywahu@qq.com

1 引 言

近年來，為滿足客戶的多元化需求，力爭在國際市場上立足，全球制造業(yè)積極進行轉(zhuǎn)型發(fā)展.世界各地相關學者的研究方向和企業(yè)生產(chǎn)發(fā)展的重點均轉(zhuǎn)向智能化、個性化、服務化、敏捷化和協(xié)作化.在此背景下，出現(xiàn)了許多新的技術和理念來改善制造業(yè)生態(tài)，云制造概念隨之產(chǎn)生.

云制造是一種利用網(wǎng)絡和云制造服務平臺，按用戶需求組織網(wǎng)上制造資源，為用戶提供各類按需制造服務的一種網(wǎng)絡化制造新模式[1].云制造借鑒云計算的思想[2]，利用服務計算和制造技術，將制造資源和制造能力轉(zhuǎn)化為制造服務，實現(xiàn)制造資源和制造能力的智能統(tǒng)一管理和運營，實現(xiàn)制造資源和制造能力的充分共享和流通[3].云制造系統(tǒng)是由云制造服務請求者、云制造服務提供者和云制造服務平臺組成.服務提供者將閑置的硬件資源(如設備資源、計算資源、物料資源等)或軟件資源(如應用軟件資源、技術和知識資源、數(shù)據(jù)和信息資源等)提交至云平臺，然后由云平臺將這些閑置資源進行網(wǎng)絡虛擬化并進一步封裝后發(fā)布到云制造平臺上.當服務請求者向云平臺提交任務需求時，任務被分解成不可再分的子任務，并對這些子任務在云平臺上進行搜索匹配，給出滿足任務需求的服務組合，然后由一個或多個服務提供者完成服務請求者提交的任務.

由于協(xié)同性是云制造的典型特征，通過多個服務之間的協(xié)作實現(xiàn)協(xié)同完成制造任務；且云制造服務組合方案具有明顯的動態(tài)性、不確定性等特點[4].因此，本文從基于角色的協(xié)同[5](Role-Based Collaboration，RBC)的角度研究云制造服務組合問題并對其建模.本文的主要貢獻如下：

1)基于E-CARGO模型對云制造服務組合問題進行建模，提出一種基于角色的協(xié)同云制造服務組合優(yōu)化方法.該方法建立了服務組合問題和E-CARGO模型間的映射關系，構建了基于角色的協(xié)同云制造服務組合模型.

2)針對云制造服務歷史QoS的不確定性，引入云模型理論對動態(tài)QoS進行分析，并計算QoS云模型的相似度，進而得到資格評估矩陣，然后對基于角色的協(xié)同云制造服務組合問題進行求解，得到最優(yōu)云制造服務組合方案.

2 相關工作

2.1 云制造服務組合

隨著網(wǎng)絡化協(xié)同制造模式的發(fā)展，制造服務的數(shù)量不斷增長，云制造服務系統(tǒng)將會出現(xiàn)嚴重的信息過載.云制造服務平臺為服務請求者在大量的制造資源中選擇合適的服務進行服務組合遇到了很大的困難[6]，在此背景下云制造服務組合問題得到了廣泛的關注.高新勤等[7]為了實現(xiàn)服務供給與服務請求的快速匹配，提出了基于相似度的加工設備云服務聚類方法；簡琤峰等[8]提出一種基于ONBA并結合二階振蕩和差分進化算法的改進算法，利用改進算法獲取云制造模型的調(diào)度數(shù)據(jù)，并通過該調(diào)度數(shù)據(jù)對IDBN深度學習模型進行訓練；管力明等[9]提出一種基于綜合信譽度的云制造服務組合算法，算法從用戶對時間、成本和質(zhì)量等屬性的重視度和期望值綜合得出服務組合的信譽度，通過調(diào)整屬性權重值達到多目標優(yōu)化的目的.此外，基于語義的服務組合[10]、面向多任務的服務組合[11]、基于服務質(zhì)量的服務組合[12，13]等方法也被提出.同時，智能算法也被廣泛的用于云制造服務組合中，如人工蜂群算法[14]、粒子群算法[15，16]等.如今，國內(nèi)外對云制造服務組合問題的研究已經(jīng)取得很大進展，但很少有方法能夠考慮到云制造的協(xié)同性.本文從RBC的角度研究云制造服務組合問題，提出一種基于角色的協(xié)同云制造服務組合優(yōu)化方法.

2.2 基于角色的協(xié)同(RBC)

在協(xié)作系統(tǒng)中，RBC是一種新興的計算方法學，它以角色為核心機制，描述并支持解決協(xié)同問題.E-CARGO模型是RBC中最重要的模型，以六元組(環(huán)境、類、代理、角色、組、對象)的形式清晰的描述了RBC系統(tǒng)[17].E-CARGO模型的研究成果為群組角色分配問題[18](Group Role Assignment，GRA)、沖突代理的GRA問題[19](GRA With Conflict Agents，GRACA)、群組多角色分配問題[20](Group Multi-Role Assignment，GMRA)等提供了理論模型及解決方案.最近，E-CARGO模型已經(jīng)被成功應用到混合云中數(shù)據(jù)密集型應用的服務組合中[21].協(xié)同性是云制造的典型特征，為清晰的描述云制造的協(xié)同性問題，本文首次將E-CARGO模型應用到云制造場景中.

3 云制造服務組合

3.1 問題描述

3.2 E-CARGO建模

2006年朱海濱教授提出E-CARGO模型，并采用此模型刻畫和描述了一個協(xié)作系統(tǒng).E-CARGO模型采用9元組形式化描述一個RBC系統(tǒng).一個協(xié)作系統(tǒng)∑由9個元組構成：

∑::=

(1)

其中，C,O,A,M,R,E,G,s0,H分別代表協(xié)作系統(tǒng)中的類(Class)、對象(Object)、代理(Agent)、消息(Message)、角色(Role)、環(huán)境(Environment)、組(Group)、協(xié)作系統(tǒng)的初始狀態(tài)s0和用戶(User)的有限集.

協(xié)作系統(tǒng)中應用E-CARGO模型主要關注的元素為E，C，O，R，A，G.在本文中E表示為問題的環(huán)境，即一組制造服務的計劃和建議.C是一組表示與E相關的抽象概念定義的類.O是一組和C相關的具體對象.R是云制造中屬于同一類型子任務的集合.A是云制造中同一類型子任務的服務候選集.G是一個組，為了獲得最優(yōu)的組，需要將合適的服務分配給合適的任務.

如圖1 所示，子任務、服務和角色、代理的映射關系如下：

圖1 云制造服務組合和E-CARGO模型的映射關系Fig.1 Mapping the cloud manufacturing service composition and the E-CARGO model

文中，Ru、Au對應了一個E-CARGO模型，即每種類型的子任務集合都建立一個E-CARGO模型，以Tu類型的子任務為例，運用E-CARGO模型還需要定義如下4個參數(shù)：

4)組評估值ρ，表示在滿足約束條件的情況下，一個組中被分配的服務的資格評估值之和.

基于以上分析，目標函數(shù)定義為：

(2)

s.t.

T[i,j]∈{0,1}(0≤i

(3)

(4)

(5)

式(3)表示服務只有被分配和不分配兩種選擇；式(4)表示該問題必須滿足子任務需求向量L的約束，即規(guī)定子任務需要多少個服務來協(xié)同完成；式(5)表示一個服務只能被分配給一個子任務.

3.3 資格評估矩陣

(6)

根據(jù)式(6)，候選服務集RSSu中m個服務對n個Tu類型子任務的QoS云模型矩陣可表示為：

(7)

由于服務狀態(tài)和能力的多樣化，即使相同的任務被執(zhí)行多次，每次的QoS也不會完全相同.因此，一個好的服務應當提供穩(wěn)定的QoS，即多次完成同一任務得到相同或相近的QoS.En和He的值越小，QoS越穩(wěn)定.由此，我們定義了理想解，在最好情況下的cm為：

(8)

同理，最壞情況下的cm為：

(9)

為了給任務選擇合適的服務，通過計算QoS云模型之間的相似度來識別服務QoS之間的差異是至關重要的.這里我們采用歐式距離來計算相似度.歐式距離的公式如下：

(10)

(11)

3.4 基于角色的協(xié)同云制造服務組合優(yōu)化方法求解

3.4.1 方法流程

根據(jù)以上分析，基于角色的協(xié)同云制造服務組合優(yōu)化方法流程如下：

1)用戶提交任務Γ，任務Γ被分解為子任務，再按照子任務的類型組合，屬于同一種類型的子任務構成任務類型集合；

2)每種任務類型集合對應一個候選服務集，每個服務只能完成一個子任務，一個子任務可能需要多個服務協(xié)同完成；

3)每種任務類型及對應的候選服務集構建一個E-CARGO模型，子任務、服務與E-CARGO模型中的角色、代理構建了映射關系；

4)以Tu類型子任務及對應的候選服務集RSSu為例，進行下述步驟計算，其他任務類型進行相同計算；

9)求解在滿足約束3)、4)、5)條件下的目標函數(shù)式(2)；

10)解出分配矩陣T，得到最優(yōu)服務組合方案.

3.4.2 方法求解

使用CPLEX求解目標函數(shù)包含如下兩個步驟：

1)確定CPLEX需要的目標函數(shù)系數(shù)、約束系數(shù)、右側(cè)約束值和上下界.本文使用Q，L，T定義CPLEX中的線性規(guī)劃問題.Q是目標函數(shù)的系數(shù)，T是變量，它的上下界是1和0；

2)添加目標函數(shù)和約束的表達式.云制造服務組合問題的目標函數(shù)可以用Q和T的一維數(shù)組形式描述.

偽代碼如下所示.

求解算法:

輸入：Qualification matrixQand Lower bound vectorL

輸出：Group performanceρand assignment matrixT

Begin

1. Initialize an IloCplex object；

2. Initialize assignment one-dimensional arrayX；

3. transform matrixQinto one-dimensional arrayQT；

4. add the optimization objective Equation(2)；

5. add the constraint Equation(4)；

6. add the constraint Equation(5)；

7. Invoke the solve() method of CPLEX；

End

第1行，創(chuàng)建IloCplex對象，IloCplex類是用來創(chuàng)建和求解多種數(shù)學編程模型的類.第2行，初始化分配矩陣T，調(diào)用IloCplex對象的方法intVarArray(m*n，0，1)返回一維數(shù)組X，方法中的第一個參數(shù)是以一維數(shù)組X的形式表示了分配矩陣T，第二個和第三個參數(shù)定義了數(shù)組中每個變量的范圍.第3行，Q矩陣用一維數(shù)組QT表示.第4行，使用IloCplex對象的方法addMaximize(IloCplex.scalProd(X，QT))創(chuàng)建目標函數(shù).第5、6行是為CPLEX添加約束：①調(diào)用IloCplex對象的方法linearNumExpr()聲明表達式對象，并返回IloLinearNumExpr對象；②通過調(diào)用方法將所有項添加到對象IloLinearNumExpr中；③調(diào)用IloCplex對象的方法(addEq(IloLinearNumExpr))或addLe(IloLinearNumExpr))將約束表達式添加到CPLEX中.第7行，調(diào)用IloCplex對象的方法solve()求解該問題.

4 實 驗

4.1 實驗環(huán)境

開發(fā)平臺為Eclipse，編程語言為Java，機器配置為core i7-49703處理器，16G內(nèi)存，windows 10操作系統(tǒng).

4.2 實 例

表1 服務的QoS歷史記錄Table 1 QoS history of service

根據(jù)式(6)可計算出服務對各子任務的三個云數(shù)字特征，如表2所示.

表2 服務的云數(shù)字特征Table 2 Cloud digital characteristics of services

根據(jù)式(8)、式(9)計算出理想情況下的云數(shù)字特征cm+={0.82,0,0}、cm-={0,0.30,0.15}.再由式(11)計算出服務對各子任務的勝任程度.

表3 服務的值Table value of the service

如表3所示，將表3作為資格評估矩陣Q，根據(jù)E-CARGO模型，L=[1,1,2,1]，由式(2)、式(3)、式(4)、式(5)，利用IBM ILOG CPLEX工具包可計算出分配矩陣T：

4.3 實驗分析

為了驗證所提出方法的性能，我們將所提出的方法與貪心算法作比較.每給定一個m和n的值，均重復實驗200次，每一次實驗Q和L都隨機更新.為了比較n/m的比值對性能的影響，我們組成兩組測試，比值分別為1/2和1/3.分別記錄當m和n取不同值時求解服務組合問題的平均時間、最大時間和最小時間.同時還列出了CPLEX得到的組評估值比貪心算法得到的組評估值大的次數(shù).

表4 CPLEX與貪心算法的比較Table 4 Comparison of CPLEX and greedy algorithm

由表4可以看出，本文方法的性能與m和n的大小有明顯的關系.m和n的值越小，方法求解所需要的時間越少.例如，當m=10，n=5時，平均運行時間是2.00ms，而當m=60，n=30時，平均運行時間是9.87ms.由于貪心算法只考慮了每一步中的最好情況，在運行時間上自然更短，但是容易陷入局部最優(yōu).由實驗可以看出，貪心算法得出的組的最大評估值往往不是最優(yōu)的.當m的值較小時，貪心算法有一定的幾率得到最優(yōu)解，例如，當m=10，n=5，貪心算法在200次的實驗中有29次和使用CPLEX求解一樣達到了最優(yōu)解.不過隨著m的增大，貪心算法幾乎不會達到最優(yōu)解，只是近似最優(yōu)解.

m和n是解決問題復雜度的重要參數(shù)，對本文方法性能的影響重大.因此下面的實驗我們研究改變m和n的值對本文方法性能的影響.m的范圍從20到120，步長20，n/m比值分別為1/2、1/3、1/5和1/10，同一組m和n的值均運行200次.實驗結果如圖2所示.

圖2 性能分析Fig.2 Analysis of performance

由實驗結果可以看出，m和n的值越大，求解花費的時間越多.在m相同的情況下，n的值越小，求解時間越短.最大求解時間對應了給定m和n的值，200次重復實驗中的一組特定數(shù)據(jù)，隨著m和n的增長，最大求解時間呈波動增長.最大求解時間曲線的波動和下降意味著，求解一個較大規(guī)模的服務組合問題可能比求解較小規(guī)模服務組合問題花費的時間更少.最小求解時間隨著m和n的增長而增長，最小求解時間和平均求解時間曲線是近似的，說明除了特定數(shù)據(jù)，大部分數(shù)據(jù)求解時間都是近似最小求解時間的.實驗證明了本文提出方法的有效性，當問題規(guī)模增大到m=120，n=60時，最大求解時間是0.142s，最小求解時間是0.03s，平均求解時間是0.038s.

5 總 結

考慮到協(xié)同性作為云制造的典型特征，本文基于E-CARGO模型對云制造服務組合問題進行建模，提出一種基于角色的協(xié)同云制造服務組合優(yōu)化方法.首先確立了服務組合問題和E-CARGO模型間的映射關系；其次將服務的不確定QoS轉(zhuǎn)換為云模型的數(shù)字特征，通過相似度計算得到資格評估矩陣；最后解出最優(yōu)服務組合方案.在接下來的研究工作中，我們將考慮服務間的約束關系，解決在復雜約束條件下的云制造服務組合問題.