時序約束下面向混合任務的制造云服務組合優化*

劉 志，龔本剛，唐 娟，桂云苗

(安徽工程大學 管理工程學院, 安徽 蕪湖 241000)

時序約束下面向混合任務的制造云服務組合優化*

劉 志，龔本剛，唐 娟，桂云苗

(安徽工程大學 管理工程學院, 安徽 蕪湖 241000)

針對面向混合任務的制造云服務組合問題，建立了優化模型并提出求解算法。首先對該問題流程進行了描述，分為混合任務分解，候選云服務推薦和云服務組合優化三個步驟；其次，以整體服務質量最優為目標建立該問題的優化模型。根據問題的特點，使用改進遺傳算法對其進行了求解，同時在這一算法中采用基于擴展子任務排序的雙層編碼和POX交叉算子。最后，通過在服務資源豐富和受限兩種情況下的仿真實例驗證了優化模型和算法的可行性和有效性。

云制造；服務組合；服務質量；時序約束；混合任務

0 引言

隨著國際化市場競爭加劇與信息技術的快速發展，制造模式正經歷著由原先依賴企業內部制造資源向借助信息技術和網絡技術充分利用外部制造資源的變化。以應用服務提供商(Application Service Provider, ASP)、制造網格[1](Manufacturing Grid, MGrid)等為代表的網絡化制造模式取得成效，但因提供的資源服務類型、數量、能力和使用方式有限[2]，使得基于網絡化制造的信息共享不暢、資源利用率不高、產品設計中知識重用及創新力不足，制約了其應用的推廣和發展。為此，李伯虎在融合先進制造模式與技術及云計算、物聯網、虛擬化、語義Web和服務計算等信息技術的基礎上，提出了一種面向服務、高效低耗、基于知識的網絡化智能制造新模式——云制造。云制造將制造資源和制造能力虛擬化、服務化，構建一個資源、能力的共享協同與按需使用的制造服務云體系[3-6]。

在實際應用中，制造云服務的需求日趨多樣化和復雜化，使得功能相對單一的制造云服務已經無法滿足應用需求，因此，將多個制造云服務組合成一個功能更強大的服務成為了一種必然選擇[5]。然而，由于云制造系統中存在大量具有相同制造功能和不同服務質量的制造云服務，使得服務組合成為一種典型的NP-hard問題[7]。

云制造系統中同時收到的多個任務可分為異類型、同類型和混合型三種[5]：異類型是指各制造任務的所有子任務序列不同；同類型是指各任務之間有完全相同的子任務序列；混合型是指各制造任務之間有部分相同的子任務序列，共享部分候選制造云服務集合，其中混合型任務最符合實際情況也最為復雜。同時，制造任務對制造云服務的使用時間較長[7]，任務之間存在時序約束和共享候選云服務問題，使得云服務狀態在服務組合執行過程中實時變化，而現有研究主要針對系統中空閑云服務資源，較少考慮已分配任務的云服務在執行空閑時間段可再次分配任務的情況，導致候選云服務未能得到充分的利用。因此，本文針對面向混合任務的制造云服務組合問題(Hybrid-task oriented manufacturing cloud service composition, HTO-MCSC)，在充分考慮時序約束和云服務實時狀態變化的前提下，構建云服務組合優化模型和求解算法，以充分利用候選云服務，提高服務組合效率和質量。

1 HTO-MCSC問題

1.1 HTO-MCSC問題描述

云制造系統同時接受多個不同類型制造任務請求時，其服務組合過程復雜多變，為了便于分析和優化，進行以下約束來簡化HTO-MCSC問題：

(1)制造任務分解得到的原子任務有著一定的時序約束，并按時序關系順序執行；

(2)各制造云服務(包括硬資源和軟資源)，在完成指定的子任務后，經短暫調整后能夠重新被釋放，并可再次使用，調整時間記入服務執行時間；

(3)已分配任務的云服務在執行未開始前的空閑時間段，能夠執行其他制造任務并盡可能早執行。

時序約束下HTO-MCSC的流程可以描述如下：

1)混合任務分解

云制造系統收到由多個不同類型制造任務執行請求組成的混合任務集T={T1,T2,…,Ti, …,Tm}，任意制造任務Ti(i=1,2,…,m)分別具有相應的服務質量需求，可用服務質量約束向量Ci表示，Ci={Ci1,Ci2,…,Cij,…,Cil},其中l表示服務質量約束數量，Cij(j=1,2,…,l)為第j個服務質量約束指標。制造任務按照其子任務序列和產品BOM逐層分解，得到一系列關聯的、存在于系統中的云制造原子任務為原子云任務鏈，Ti分解的原子云任務鏈Ti={ATi1,ATi2,…,ATij, …,ATin}，其中n表示該任務鏈的原子數量，ATij為Ti分解的第j個原子任務。

2) 云服務推薦

3) 時序約束下云服務組合優化

將各制造企業在云制造平臺提供的云服務，根據原子任務鏈的時序關系，按照一定順序組合形成的一個整體服務鏈，稱之為云制造服務鏈。在該服務鏈中，每個節點都是由制造服務的時序約束關系對應的任務來確定。云制造系統中任務與云服務之間的組合是一個多目標優化問題，對于服務質量的不同方面需要做出平衡，不同服務質量屬性具有各自的權重，可用向量Wi={Wi1,Wi2,…,Wih}來表示。HTO-MCSC問題的優化目標是為每個制造任務都分配最合適的制造服務，確定每個服務的最佳編排順序和服務開始時間，使整個系統的服務質量達到最佳。

1.2 HTO-MCSC優化數學模型

在構建HTO-MCSC優化數學模型之前，首先明確兩個相關概念及其運算過程。

(1) 服務質量QoS的集成和預處理

假設服務組合優化目標采用的標準是：目標函數數值越大，性能越佳。但服務質量QoS的屬性有正屬性和負屬性之分，其中，正屬性是指數值越大、性能越佳的屬性，負屬性則相反；同時每種屬性的量綱也不同，因此，需對云制造服務的QoS進行預處理。系統選擇時間T、成本C、合格率P和可靠性R作為QoS屬性，其中，T和C是負屬性，P和R為正屬性，可靠性R使用服務被成功執行的次數Nc與服務總請求執行次數的K的比值Nc/K表示。此時，服務質量約束向量Ci包含時間T、成本C、合格率P和可靠性R四個方面，分別用Cit、Cic、Cie和Cir表示，則Ci={Cit,Cic,Cie,Cir}。

(1) 表1 服務質量屬性的集成

對于任意任務Ti的服務質量QoSi可采用簡單加權法[9]進行預處理，具體見公式(2)～(5)，預處理后的各服務質量不僅方向一致，同時具有統一量綱。

(2)

(3)

(4)

(5)

(2) 整體服務質量TQoS

(6)

服務組合優化目標為整體服務質量最佳，HTO-MCSC優化問題的數學模型可構建如公式(7)所示。

(7)

2 改進遺傳算法求解HTO-MCSC優化問題

某汽車零部件區域云制造系統中，零部件L具有兩種不同的型號A和B，其中型號A的原子任務鏈為“分裝—總裝—測試”，型號B的原子任務鏈為“分裝—總裝”。系統中有8個候選制造服務，在t1時刻，系統同時接受到由2個A和1個B組成的制造任務集{T1，T2，T4}(此時為資源豐富情況)；在t2時刻，系統同時接受到由3個A和2個B組成的制造任務集{T1，T2，T3，T4，T5}(此時為資源受限情況)；t1時刻與t2時刻任務相互獨立。所有制造任務分解及對應的候選服務質量QoS如表2所示，要求為兩種情況下的所有制造任務分配服務。本文使用改進遺傳算法對HTO-MCSC優化問題進行求解，資源豐富和受限兩種情況下，改進的遺傳算法同樣適用，為便于說明，算法中的編解碼和交叉變異操作僅分析較為復雜的資源受限情況。

表2 制造任務分解及候選服務QoS

任務原子任務候選服務和服務質量QoSCS5CS6CS7CS8T1AT11————AT12(7,2,0.99,0.95)(5,8,0.97,0.99)—AT13——(3,5,0.95,0.96)(6,5,0.96,0.99)T2AT21————AT22(5,2,0.96,0.95)(4,8,0.97,0.99)——AT23——(4,5,0.95,0.96)(7,5,0.96,0.99)T3AT31————AT32(6,2,0.99,0.96)(8,8,0.97,0.99)——AT33——(7,6,0.95,0.96)(8,6,0.97,0.97)T4AT41————AT42(5,7,0.99,0.95)(6,7,0.97,0.93)——T5AT51————AT52(8,7,0.99,0.95)(9,7,0.99,0.96)——

2.1 編碼與解碼

編碼與解碼是指染色體和服務組合方案之間進行相互轉換。根據HTO-MCSC問題的特點，采用一種擴展的基于子任務排序的雙層編碼，上層是基于子任務排序的編碼，它是用來確定子任務的執行順序；下層是基于服務分配的編碼，該編碼中的服務按每個子任務順序進行排列，它是用來給每個子任務分配合適的服務。結合這兩層編碼，可以得到HTO-MCSC問題的一個可行解，圖1為針對表2中混合制造任務的一個編碼實例。

本文將一個插入式貪婪解碼過程擴展到制造云服務組合優化中，以確定解碼后能生成活性組合方案，插入式貪婪解碼算法描述如下：首先按照子任務的執行順序進行解碼，然后將每個子任務分配到其對應的制造云服務上，并盡可能早的進行服務執行，按照這種方式編碼，直到所有子任務都分配在最合適的制造云服務。

圖1 擴展的基于子任務排序的編碼

2.2 交叉與變異操作

交叉是將種群中個體中的某些基因隨機進行交接，以產生新的基因組合，交叉的目的是將優良的基因進行組合，以使子代較好地繼承優良的父代基因。對于兩層編碼分別采用不同的交叉操作。對于基于子任務排序上層編碼部分，采用POX (Precedence Operation Crossover)交叉算子[10]進行操作；POX交叉算法中P1和P2代表兩個父代染色體，C1和C2代表交叉后生成的子代染色體。POX交叉操作過程如圖2所示，具體流程如下：

(1) 隨機將所有的任務集合劃分為兩個非空的子集J1和J2；

(2) 復制P1包含在J1的任務到C1，P2包含在J2的任務到C2，并保留它們的位置不變；

(3) 復制P2包含在J2的任務到C1，P1包含在J1的任務到C2，并保留它們的位置不變。

圖2 POX交叉操作

變異操作的目的是改善算法的局部搜索能力，有助于維持進化群體的多樣性，防止算法過早陷入局部最優。針對擴展的基于子任務排序的編碼特點，對于兩部分編碼分別采用不同的變異操作。針對基于子任務排序編碼部分，采用是插入變異操作：首先在此編碼部分隨機選擇一個子任務，將它隨機地插入到另一個子任務的前面，同時保持所有基于服務分配編碼不變。針對基于服務分配編碼部分，隨機選擇兩個位置上的服務基因，然后在該位上子任務的可選服務集合中隨機選擇其他服務進行替代。

2.3 適應度函數

(8)

2.4 改進遺傳算法步驟

智能優化算法是解決NP問題的有效方法，本文使用遺傳算法作為基本算法對HTO-MCSC問題進行優化計算，但是遺傳算法存在收斂速度慢，容易陷入局部最優的缺陷，因此，需要對遺傳算法進行改進。本文設計了一種改進遺傳算法，其具體求解流程圖可以表示如圖3所示。

該算法融入了粒子群算法的“極值”概念，即在遺傳算法進行交叉算法時設置一個個體極值染色體和一個全局極值染色體，在染色體進行交叉運算時以一定概率按照個體極值和全局極值進行更新，即首先求出所有染色體的適應度作為其第一代個體極值，然后在個體極值中尋找最大的作為全局極值，在循環迭代過程中，算子按照一定概率與個體極值和全局極值進行交叉運算。

圖3 改進遺傳算法的求解流程圖

3 仿真分析

以表2中的實例數據為實驗對象，使用Matlab7.0編寫服務資源豐富和受限兩種情況下的仿真驗證程序。用戶在云制造系統中提交制造任務時，需同時給出服務質量約束條件和服務質量重要度評分，評分結果經處理后可得到各服務質量權重，其結果如表3所示。針對算例，設定遺傳算法的初始種群規模為50，交叉概率為0.8，迭代次數為200代，資源豐富和受限兩種情況下的仿真結果分別如圖4和圖5所示。

表3 各制造任務約束條件和服務質量權重

通過仿真結果發現，在服務資源豐富情況下，所有制造任務在無需等待下都得到了完成，總執行時間為13天；在服務資源受限的情況下，總運行時間為18天，部分制造服務以連續運用的方式進行服務組合以滿足所有任務請求，例如CS1、CS3和CS7等運用2次。

圖4 資源豐富下的制造云服務組合優化結果

4 結束語

針對時序約束下面向混合任務的制造云服務組合HTO-MCSC問題，論文在描述其流程的基礎上建立了多目標優化數學模型，并使用改進遺傳算法進行求解，特別是提出一個擴展的基于子任務排序的雙層編碼方式，并通過仿真實例驗證了優化模型和算法的可行性和有效性，這對云制造系統的運行具有一定的實際指導意義。

本文在一定程度上解決了云制造服務組合的靜態優化問題，但是，在實際組合過程中，系統將面臨各種不確定因素的干擾。下一步將對各種不確定因素進行詳細分析，構建制造云服務組合的動態優化機制，以提高服務組合的魯棒性和自適應性。

[1] TAO F, ZHAO D M, HU Y F, 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.

[2] 賀東京，宋曉，王琪，等. 基于云服務的復雜產品協同設計方法[J]. 計算機集成制造系統，2011，17(3)：533-539.

[3] 李伯虎，張霖，王時龍，等. 云制造——面向服務的網絡化制造新模式[J]. 計算機集成制造系統，2010，16(1)：1-8.

[4] 李伯虎，張霖，任磊，等. 云制造——面向服務的網絡化制造新模式[J]. 計算機集成制造系統，2010，16(1)：1-16.

[5] 劉衛寧，劉波，孫棣華. 面向多任務的制造云服務組合研究[J]. 計算機集成制造系統，2013，19(3)：199 -209.

[6] 陶飛，張霖，郭華，等. 云制造特征及云服務組合關鍵問題研究[J]. 計算機集成制造系統, 2011, 17(3): 477-486.

[7] 楊晨. 基于QoS的多目標服務組合算法[J]. 計算機工程與設計，2011，32(4)：1322-1325.

[8] ZENG L, BENATALLAH B, NGU A HH, et al. QoS-aware middleware for Web Services Composition[J]. IEEE Transactions on Software Engineering, 2004, 30(5): 311-327.

[9] ZHANG L Z, GUO H, TAO F, et al. Flexible management of resource service composition in cloud manufacturing[C]// IEEE International Conference on Industrial Engineering and Engineering Management. Washington, D.C.,USA: IEEE Computer Society, 2010: 2278-2282.

[10] 張超勇，饒運清，劉向軍，等. 基于POX交叉的遺傳算法求解Job Shop調度問題[J]. 中國機械工程，2004，15(24)：2149-2153.

(編輯 趙蓉)

Hybrid-task Oriented Manufacturing Cloud Service Composition Optimization with Time-sequence Constraint

LIU Zhi, GONG Ben-gang, TANG Juan，GUI Yun-miao

(School of Management Engineering, Anhui Polytechnic University, Wuhu Anhui 241000, China)

Aiming at the Hybrid-task oriented manufacturing cloud service composition (HTO-MCSC) problem, an optimization model and a solution algorithm are established and proposed. Initially, the procedure of this problem is described, which includes hybrid task decomposition, manufacturing cloud service recommendation and cloud service composition optimization. Secondly, the optimization model is established by aimed at the optimal integrated quality of service. According to the characteristics of the problem, the improved genetic algorithm is used to solve it and meanwhile the double coding and Precedence Operation Crossover (POX) operator, which are based on the extension the sub-task sorting, are adopted in this algorithm. At last, two simulation examples verified the feasibility and effectiveness of the optimization model and algorithm both under resources abundant and limited circumstances.

cloud manufacturing; service composition; quality of service; time-sequence constraint; hybrid task

1001-2265(2014)06-0138-05

10.13462/j.cnki.mmtamt.2014.06.038

2013-10-14；

2013-11-18

國家自然科學基金資助項目(71171002，71371012); 教育部人文社會科學研究項目(13YJA630021); 安徽高校省級自然科學研究項目(KJ2013B033); 安徽高校省級人文社會科學研究項目(SK2013B066)

劉志(1985—)，男，安徽肥西人，安徽工程大學講師，主要從事CIMS、制造過程優化與控制、生產系統建模與仿真等研究，(E-mail)liuzhi0551@126.com。

TH166；TG65

A