時序約束下面向混合任務(wù)的制造云服務(wù)組合優(yōu)化*

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

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

時序約束下面向混合任務(wù)的制造云服務(wù)組合優(yōu)化*

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

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

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

云制造；服務(wù)組合；服務(wù)質(zhì)量；時序約束；混合任務(wù)

0 引言

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

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

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

1 HTO-MCSC問題

1.1 HTO-MCSC問題描述

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

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

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

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

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

1)混合任務(wù)分解

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

2) 云服務(wù)推薦

3) 時序約束下云服務(wù)組合優(yōu)化

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

1.2 HTO-MCSC優(yōu)化數(shù)學(xué)模型

在構(gòu)建HTO-MCSC優(yōu)化數(shù)學(xué)模型之前，首先明確兩個相關(guān)概念及其運算過程。

(1) 服務(wù)質(zhì)量QoS的集成和預(yù)處理

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

(1) 表1 服務(wù)質(zhì)量屬性的集成

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

(2)

(3)

(4)

(5)

(2) 整體服務(wù)質(zhì)量TQoS

(6)

服務(wù)組合優(yōu)化目標為整體服務(wù)質(zhì)量最佳，HTO-MCSC優(yōu)化問題的數(shù)學(xué)模型可構(gòu)建如公式(7)所示。

(7)

2 改進遺傳算法求解HTO-MCSC優(yōu)化問題

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

表2 制造任務(wù)分解及候選服務(wù)QoS

任務(wù)原子任務(wù)候選服務(wù)和服務(wù)質(zhì)量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 編碼與解碼

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

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

圖1 擴展的基于子任務(wù)排序的編碼

2.2 交叉與變異操作

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

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

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

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

圖2 POX交叉操作

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

2.3 適應(yīng)度函數(shù)

(8)

2.4 改進遺傳算法步驟

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

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

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

3 仿真分析

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

表3 各制造任務(wù)約束條件和服務(wù)質(zhì)量權(quán)重

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

圖4 資源豐富下的制造云服務(wù)組合優(yōu)化結(jié)果

4 結(jié)束語

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

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

[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] 賀東京，宋曉，王琪，等. 基于云服務(wù)的復(fù)雜產(chǎn)品協(xié)同設(shè)計方法[J]. 計算機集成制造系統(tǒng)，2011，17(3)：533-539.

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

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

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

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

[7] 楊晨. 基于QoS的多目標服務(wù)組合算法[J]. 計算機工程與設(shè)計，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調(diào)度問題[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

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

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

TH166；TG65

A