模糊情況下帶時序約束服務(wù)流程的構(gòu)建與優(yōu)化

梁合蘭，杜彥華，李蘇劍

（北京科技大學(xué) 機械工程學(xué)院，北京 100083）

0 引言

隨著面向服務(wù)的體系架構(gòu)及云計算的迅速發(fā)展，Web服務(wù)（簡稱服務(wù)）已經(jīng)成為企業(yè)信息系統(tǒng)的重要組成元素。如何在海量的候選服務(wù)中快速靈活地選擇并構(gòu)建出滿足用戶需求的最優(yōu)服務(wù)流程，已經(jīng)成為當前學(xué)術(shù)界和工業(yè)界關(guān)注的熱點問題［1-3］。

由于企業(yè)業(yè)務(wù)策略、法律法規(guī)設(shè)定等原因，服務(wù)流程中常常存在時序約束［2-3］。如果時序約束存在錯誤或者不一致，將會對企業(yè)造成不必要的損失甚至災(zāi)難性的后果。而測量不精確、信息不完備、描述信息模糊及信息包含噪聲等原因，往往導(dǎo)致時序約束具有不確定性［2］。因此，在服務(wù)流程構(gòu)建過程中必須考慮模糊不確定情況下的時序一致性問題，以保證服務(wù)流程的正常執(zhí)行。

針對基于服務(wù)質(zhì)量（Quality of Service，QoS）的服務(wù)優(yōu)選或組合問題，國內(nèi)外從服務(wù)組合［4-7］、云制造［8-12］和服務(wù)流程優(yōu)化［2-3，13-20］三個領(lǐng)域分別開展了相關(guān)研究。但是，上述研究少有考慮不確定情況下的QoS全局優(yōu)化問題，特別是少有考慮帶模糊不確定性的服務(wù)時序約束問題。在求解方面，上述研究方法多用于求解確定性服務(wù)組合模型，不能直接套用到模糊問題求解上，且求解效率有待提高。

針對上述研究［2-20］的不足，本文提出一種新的服務(wù)流程構(gòu)建與優(yōu)化方法。首先，建立了模糊情況下帶時序約束的服務(wù)流程優(yōu)化模型，該模型不但能有效表達QoS屬性及時序約束的模糊化內(nèi)涵，而且具有較好的普適性；然后，基于模糊機會約束理論及模糊滿意度法，將多目標模糊約束模型進行等價轉(zhuǎn)化，采用基于信息素的混合遺傳算法實現(xiàn)模型求解。該算法借鑒蟻群算法中的信息素思想，不僅利用親代染色體和服務(wù)自身攜帶的局部優(yōu)化信息，還利用信息素記錄的全局優(yōu)化信息指導(dǎo)染色體的交叉，從而提高算法效率。

與上述已有方法［2-20］相比，本文的主要創(chuàng)新點如下：①構(gòu)建了模糊情況下帶時序約束的服務(wù)流程優(yōu)化模型，彌補了現(xiàn)有研究缺乏描述QoS屬性及時序約束模糊不確定性的不足；②設(shè)計了高效的求解方法。首先，基于模糊機會約束和滿意度法的模型等價轉(zhuǎn)化，既保留了模糊信息量，也滿足了啟發(fā)式算法求解模糊服務(wù)流程優(yōu)化問題的需求；然后，通過基于信息素的混合遺傳算法來實現(xiàn)更好的執(zhí)行時間和求解精度。

1 相關(guān)工作

目前，針對服務(wù)優(yōu)選或組合問題，國內(nèi)外學(xué)者從服務(wù)組合、云制造和服務(wù)流程優(yōu)化三個領(lǐng)域分別開展了相關(guān)研究，下面分別進行詳細述評。

1.1 服務(wù)組合方面

這方面與本問題相關(guān)的具體研究內(nèi)容包括基于QoS計算的服務(wù)組合［4-5］、基于語義的QoS 服務(wù)組合［6-7］等。具體來說，文獻［4］針對基于中間件平臺的QoS 感知的確定性服務(wù)組合問題，建立了整數(shù)規(guī)劃模型并進行求解；文獻［5］設(shè)計了改進變異算子求解確定性服務(wù)組合問題，該模型考慮了服務(wù)組合和原子服務(wù)的時間約束；文獻［6-7］設(shè)計了基于語義的QoS全局優(yōu)化模型，并通過重心法實現(xiàn)了QoS屬性去模糊化。

上述研究［4-7］側(cè)重于封裝的服務(wù)組合和原子服務(wù)的時間要求，少有考慮具有模糊不確定性的服務(wù)時序約束。且針對不確定情況下QoS全局優(yōu)化的研究［6-7］，采用去模糊化處理，存在不能反映決策者風險偏好等業(yè)務(wù)因素的不足。

1.2 制造網(wǎng)格與云制造方面

制造網(wǎng)格基于網(wǎng)格技術(shù)將分散資源進行封裝和集成，以透明的方式為用戶提供各類制造服務(wù)，從而實現(xiàn)資源的集成和優(yōu)化運行［8］。針對確定性網(wǎng)格服務(wù)組合問題，文獻［8］提出了基于粒子群優(yōu)化算法的制造網(wǎng)格資源服務(wù)組合優(yōu)選方法；針對資源服務(wù)優(yōu)選問題沒有考慮用戶感受及QoS評估的語義差異性等不足，文獻［9］提出基于了直覺模糊集的服務(wù)匹配算法。

云制造是一種利用網(wǎng)絡(luò)和云制造服務(wù)平臺，按用戶需求組織網(wǎng)上制造資源，為用戶提供各類按需制造服務(wù)的一種網(wǎng)絡(luò)化制造新模式［10］。針對制造云服務(wù)組合問題，文獻［11］建立了基于QoS的多任務(wù)云服務(wù)組合問題模型，并提出基于矩陣實數(shù)編碼的改進遺傳算法求解；文獻［12］在語義服務(wù)和模糊集理論的基礎(chǔ)上，提出一種語義服務(wù)模糊匹配方法。

上述研究［8-12］多針對確定性服務(wù)優(yōu)選問題的建模及求解。對于不確定情況下的服務(wù)優(yōu)選問題［9，12］，采用模糊匹配方法只能滿足單個服務(wù)的最優(yōu)選擇，不能保證服務(wù)組合的全局最優(yōu)。目前缺乏不確定情況下QoS全局優(yōu)化的建模及求解方法。

1.3 服務(wù)流程

相關(guān)研究工作主要集中于服務(wù)QoS 的不確定性表征及基于QoS的服務(wù)流程優(yōu)化兩個方面。

（1）QoS的不確定性表征 主要有基于概率分布理論［2-3］、基于區(qū)間數(shù)理論［13-14］、基于模糊數(shù) 理論［15-16］三類方法。其中，基于概率分布的方法將QoS屬性定義成服從一定分布的隨機量，但由于統(tǒng)計量不足或隨機因素規(guī)律性不強，將導(dǎo)致分布規(guī)律產(chǎn)生偏差或無法得到分布函數(shù)；基于區(qū)間數(shù)的方法通過區(qū)間數(shù)描述屬性值的變化，但屬性值在區(qū)間上遵循均勻分布，不能反映服務(wù)的偏好性；基于模糊數(shù)的方法通過模糊數(shù)描述QoS屬性，較好地反映了服務(wù)的不確定性及偏好性。

（2）基于QoS的服務(wù)流程優(yōu)化 主要可分為兩類方法：①精確求解方法，如整數(shù)規(guī)劃、分支定界［13，17］；②啟發(fā)式優(yōu)化算法［18-20］，如蟻群算法、遺傳算法。精確算法在求解大規(guī)模服務(wù)優(yōu)化問題上存在計算時間較長的弊端；啟發(fā)式優(yōu)化算法在執(zhí)行時間上具有更好的優(yōu)勢，但此類算法多用于求解確定性服務(wù)流程優(yōu)化模型，不能直接套用到模糊問題求解上，而且其進化過程多單一地依靠局部或全局優(yōu)化信息，求解效率有待提高。此外，目前在建模方面也缺乏帶模糊時序約束的服務(wù)流程優(yōu)化模型。

2 問題描述及形式化模型

為構(gòu)建優(yōu)化的服務(wù)流程，首先需要根據(jù)業(yè)務(wù)需求進行抽象服務(wù)流程定義。本文首先介紹基于Petri網(wǎng)的抽象服務(wù)流程模型，并在服務(wù)流程不確定因素分析的基礎(chǔ)上，建立本文問題的形式化模型。

2.1 服務(wù)流程的抽象模型

Petri網(wǎng)作為一種具有直觀圖形表示的形式化模型，在模型的邏輯、時間和性能的分析方面得到了廣泛應(yīng)用，因此本文使用Petri網(wǎng)定義抽象服務(wù)流程。

定義1 Petri網(wǎng)PN［21］。PN=（P，T，F(xiàn)），其中：P表示庫所集合；T表示任務(wù)集合；F?（P×T）∪（T×P）表示連庫所和變遷的有向弧集合。

定義2 工作流網(wǎng)WF-Net［21］。一個Petri網(wǎng)只有當滿足以下條件時可以稱為工作流網(wǎng)：①包含2個特殊的庫所ε和θ，其中：ε是初始庫所，即·ε=?；θ是結(jié)束庫所，即θ·=?。②如果添加一個變遷來連接庫所θ和ε，即·t=｛θ｝，t·=｛ε｝，則Petri網(wǎng)被連接起來。

2.2 服務(wù)流程的不確定因素分析

服務(wù)流程的不確定因素主要包括以下兩方面：①由于測量不精確、信息不完備等原因，部分QoS屬性度量具有模糊不確定性；②時間屬性及客戶對服務(wù)時序要求的模糊性，將導(dǎo)致模糊時序約束的產(chǎn)生。

（1）模糊QoS屬性

流程由服務(wù)組合而成，為構(gòu)建QoS優(yōu)化的服務(wù)流程，必須定義候選服務(wù)的質(zhì)量屬性。根據(jù)國際標準ISO 8402和ITU E.800對QoS的定義，本文考慮其中時間、成本和可靠性（為表述一致，后文中均按此順序描述）3個最具代表性的QoS屬性。

因為任意模糊數(shù)都可以利用一個梯形模糊數(shù)逼近［22］，所以本文采用梯形模糊數(shù)反映QoS 屬性的模糊性，如圖1所示。

圖1顯示了服務(wù)的第k個質(zhì)量屬性xk2，xk3，xk4］，k=1，2，3。式中：xk1和xk4分別為梯形模糊數(shù)的上界和下界，［xk2，xk3］為隸屬度為1的點集。例如，某服務(wù)的時間屬性～A1=［4，5，7，9］表示該服務(wù)最理想的處理時間為［5，7］個單位時間；隨著所要求的處理時間的減少或增加，服務(wù)在相應(yīng)時間內(nèi)完成的可能性減少，當服務(wù)時間在［0，4）或（9，+∞）時，其完成可能性為0。

（2）模糊時序約束

作為流程中常見的時間信息，時序約束通常表示活動之間的時序關(guān)系、某個活動執(zhí)行期限以及活動與某個日期集綁定等。實際服務(wù)流程中往往存在時序約束，但是傳統(tǒng)的確定性時間窗不能反映時序約束的不確定性和偏好性，因此本文用梯形模糊時間窗代替?zhèn)鹘y(tǒng)時間窗的定義。梯形模糊時間窗表示為關(guān)于時間π的梯形模糊數(shù)，時間不確定性或偏好性由該模糊數(shù)的隸屬度函數(shù)μ（～π）表示。

為了表達一致，采用相對時序約束形式［2］表達所有約束。例如，抽象服務(wù)流程中存在相對時序約束DR（i，j）≤［0，0，7，9］，表示客戶最希望任務(wù)j能在任務(wù)i開始后7個時間單位內(nèi)完成，其滿意度為1；否則，隨著處理時間的增加，顧客滿意度減少，應(yīng)盡量避免；當任務(wù)j的結(jié)束時間離任務(wù)i開始時間大于9個時間單位時，客戶滿意度為0，即顧客不能接受。

此外，時間屬性的模糊性將導(dǎo)致服務(wù)流程的處理時間DR（i，j）存在模糊性。根據(jù)其取值區(qū)間，模糊時序約束滿足程度可分為完全滿足、部分滿足和完全違反三大類（如圖2），但該分類原則僅簡單判定了模糊約束是否滿足一致性，而在實際業(yè)務(wù)環(huán)境中，決策者更關(guān)注模糊時序約束的滿足程度是否達到特定服務(wù)水平，且針對不同的服務(wù)流程，可能存在不同的服務(wù)水平要求。

為了量化判定服務(wù)流程是否滿足模糊時序約束，本文定義模糊時序約束滿足性如下：

定義3 模糊時序約束滿足性［23］。設(shè)抽象服務(wù)流程中存在模糊時序約束Pos｛DR（i，j）≤～B｝≥α，且～B=［y1，y2，y3，y4］，α∈［0，1］及DR（i，j）的模糊處理時間為=［x1，x2，x3，x4］。定義時序約束的滿足程度為Pos｛DR（i，j）≤～B｝=Area｛［E，F(xiàn)］∩μ其 中：［E，F(xiàn)］表示邊及圍成的區(qū)域表示的隸屬度函數(shù)，Area｛·｝表示面積計算。若Pos｛DR（i，j）≤｝≥α成立，則模糊時序約束滿足。

以時序約束Pos｛DR（i，j）≤［0，0，7，9］｝≥0.9為例，現(xiàn)已知任務(wù)i開始到任務(wù)j結(jié)束的模糊時間窗DR（i，j）=［4，5，7-10］。根據(jù)定義3，可計算出2=4，即4=0.875。因為0.875＜0.9，所以可判斷時序約束Pos｛DR（i，j）≤［0，0，7，9］｝≥0.9不滿足。

根據(jù)模糊時序約束滿足性定義，變量α反映了模糊時序約束滿足程度的最低要求。因此，流程決策者應(yīng)根據(jù)模糊時序約束的重要程度對α進行設(shè)置。以網(wǎng)上購物流程為例，該流程中存在多個時序約束，其中部分約束是由于法律法規(guī)、業(yè)務(wù)安全性等原因設(shè)置的，如“客戶必須在60s內(nèi)完成支付平臺驗證碼輸入”，針對這類嚴格不能違反的約束，可將其α設(shè)置為1；部分約束是為提高客戶服務(wù)水平、便于業(yè)務(wù)操作等原因設(shè)定的，如“顧客網(wǎng)上下單到代理商發(fā)貨的時間控制在24h內(nèi)”，該類約束非嚴格不能違反，但也需保證達到預(yù)期的服務(wù)水平下限要求。因此，企業(yè)可綜合考慮企業(yè)戰(zhàn)略目標、客戶等級、產(chǎn)品特點等因素設(shè)置相應(yīng)的α值。

2.3 本文問題的形式化模型

圖3描述了一個模糊情況下帶時序約束的抽象服務(wù)流程模型。該模型由兩條并行抽象服務(wù)流程WF-Net1和WF-Net2組成。模糊時序約束1～3分別用于描述WF-Net1內(nèi)及WF-Net1和WF-Net2任務(wù)間的時序要求。針對流程中的每一個任務(wù)，均存在一個可實現(xiàn)該任務(wù)功能的候選服務(wù)集合。

為了執(zhí)行該抽象服務(wù)流程，定義服務(wù)流程的執(zhí)行計劃如下：

定義4 執(zhí)行計劃EP［20］。設(shè)存在抽象服務(wù)流程WF-Net=（P，T，F(xiàn)），其任務(wù)集合T=｛t1，t2，…，tn｝，任一任務(wù)ti均存在一個候選服務(wù)集合Si=｛si1，si2，…，simi｝，則抽象服務(wù)流程的執(zhí)行計劃可定義為一個任務(wù)與候選服務(wù)的匹配序列EP=｛〈t1，s1i〉，〈t2，s2j〉，…，〈tn，snk〉｝。其中，序列中包含了抽象服務(wù)流程的所有任務(wù)，且任一任務(wù)有且僅有一個候選服務(wù)與之匹配。

由于各候選服務(wù)集合中往往存在大量質(zhì)量不同的服務(wù)，這些服務(wù)將組合出大量具有不同QoS特征的執(zhí)行計劃。因此，必須在海量的候選服務(wù)中快速靈活地編制出最佳的執(zhí)行計劃，以保證在滿足時序約束條件下的服務(wù)流程QoS最大化。具體就本文所考慮的三類QoS屬性而言，即希望所編制的執(zhí)行計劃在時間、成本和可靠性這三方面達到最佳配置。

綜上分析，本文問題的形式化模型可描述如下：

目標函數(shù)（1）和目標函數(shù)（2）表示所選擇的服務(wù)流程應(yīng)使完成服務(wù)流程的時間和成本盡可能小，且可靠性盡可能大。約束（3）表示任一任務(wù)的開始時間應(yīng)不小于流程中緊前任務(wù)的完成時間；約束（4）表示服務(wù)流程中各時序約束的滿足程度應(yīng)不小于該約束的最小滿足度。需要強調(diào)的是，為了簡化，若一個事務(wù)由多條并行抽象服務(wù)流程組成，則假設(shè)多服務(wù)流程同時開始。如果已知某服務(wù)流程開始時間較晚，則在其他流程的起始點增加一個虛任務(wù)，且其處理時間為相應(yīng)的開始時間差，從而保持各服務(wù)流程的開始時間一致。

從模型定義可以看出，本文模型具有以下優(yōu)點：

（1）通過多模糊目標的定義，有效描述了模糊情況下基于QoS最優(yōu)的服務(wù)流程選擇標準。與基于QoS屬性線性加權(quán)的單目標模型［19-20］相比，多模糊目標能使服務(wù)流程中各QoS屬性均趨向較優(yōu)狀態(tài)，避免了整體QoS加權(quán)值最優(yōu)而部分QoS 屬性取值過低的缺陷；此外，由于函數(shù)中不需要設(shè)置各目標的權(quán)重值，避免了結(jié)果對權(quán)重向量敏感的不足。

（2）通過模糊時序約束滿足性的量化判定，有效描述了服務(wù)流程中的模糊時序約束。決策者可根據(jù)模糊時序約束的重要程度，設(shè)定不同的滿足度閾值α，從而實現(xiàn)服務(wù)流程中時序約束的柔性配置。

（3）該模型能有效反映不確定環(huán)境下QoS屬性的模糊不確定性，且由于確定性或區(qū)間型數(shù)據(jù)均可處理成梯形模糊數(shù)，針對存在確定性或區(qū)間型數(shù)據(jù)的QoS屬性或時序約束，本文模型仍可適用，即該模型具有較好的普適性。

3 模型求解

針對上述問題模型，本文提出模糊情況下帶時序約束的服務(wù)流程優(yōu)化方法，如圖4所示。

（1）求解階段1 多目標模糊約束模型轉(zhuǎn)化?；谀：龣C會約束規(guī)劃和模糊滿意度法，將模糊規(guī)劃問題轉(zhuǎn)化為以QoS滿意度最大化為目標的清晰等價模型。

（2）求解階段2 針對清晰等價模型的求解，提出改進的混合遺傳算法。該算法借鑒蟻群算法中的信息素思想，在遺傳交叉中綜合考慮了局部優(yōu)化信息和信息素記錄的全局優(yōu)化信息，從而加快了求解效率。

3.1 多目標模糊約束模型的轉(zhuǎn)化

文獻［6-7］基于重心法實現(xiàn)QoS 屬性去模糊化，但該方法將在較大程度上損失模糊屬性的語義，不能反映服務(wù)流程執(zhí)行的可靠性、決策者的風險偏好等業(yè)務(wù)因素。為保留模糊信息量，本文首先基于模糊機會約束及其清晰等價轉(zhuǎn)化理論，將3.3節(jié)的模糊約束模型轉(zhuǎn)化成多目標機會約束的清晰等價模型?？紤]到模型中的不同優(yōu)化目標難以直接比較，進一步基于模糊滿意度法，將多目標模糊約束模型轉(zhuǎn)化成以QoS 滿意度最大化為目標的清晰等價模型。

（1）模糊問題的清晰等價轉(zhuǎn)化

首先，按照模糊隨機規(guī)劃理論，將帶模糊數(shù)的目標函數(shù)（1）和目標函數(shù)（2）轉(zhuǎn)化成目標機會約束函數(shù)。根據(jù)屬性的不同性質(zhì)，“時間”、“成本”應(yīng)為成本型屬性，其轉(zhuǎn)化公式為式（5）和式（6）；而“可靠性”為效益型屬性，轉(zhuǎn)化公式為式（7）和式（8）。

從模糊約束規(guī)劃的建模思想可知，γ反映了目標函數(shù)在不確定環(huán)境下的實現(xiàn)機會。根據(jù)其定義，γ越小、約束條件成立的可能性越小，即所選擇的服務(wù)流程不滿足滿意值的風險越大。因此，決策者應(yīng)綜合考慮服務(wù)流程的特點、自身風險偏好等因素進行γ的設(shè)置和調(diào)整。例如，對于金融、高價值制造等服務(wù)流程來說，γ的取值更側(cè)重于不確定情況下服務(wù)流程QoS的魯棒性。因此，針對該類流程應(yīng)設(shè)置γ＞0.5，從而規(guī)避不確定情況下QoS的不穩(wěn)定性。與之相對的普通制造、服務(wù)類等服務(wù)流程具有市場競爭激烈、服務(wù)流程靈活等特點，對服務(wù)流程的QoS優(yōu)劣更為敏感。因此，適當調(diào)低γ的水平，如設(shè)置γ≤0.5，將更有利于選擇出不確定情況下存在高QoS可能性的服務(wù)流程。

針對模糊屬性值計算，根據(jù)服務(wù)聚合計算公式［20］和模糊數(shù)運算原則，可得計算公式如表1所示。

表1 模糊屬性的聚合計算公式

根據(jù)表1并結(jié)合抽象服務(wù)流程模型實例，可計算出該服務(wù)流程實例的第i個模糊質(zhì)量屬性值（X）=［Qi1（X），Qi2（X），Qi3（X），Qi4（X）］，其中i=1，2，3。由于上述計算僅涉及梯形模糊數(shù)的加法及乘以常量運算，根據(jù)模糊數(shù)運算法則，所得的仍為梯形模糊數(shù)。因此，機會約束式（6）和式（8）可執(zhí)行清晰等價轉(zhuǎn)化［24］。

（2）基于滿意度的多目標轉(zhuǎn)化

經(jīng)上述處理后，2.3 節(jié)的模糊約束模型即轉(zhuǎn)化成多目標機會約束的清晰等價模型。在多目標處理上，考慮到各QoS的屬性量綱不一，在進行QoS綜合評價時，不同結(jié)果難以直接進行比較。因此，本文基于最大模糊滿意度法［25］，將多目標模型轉(zhuǎn)化為QoS最優(yōu)且不確定性程度最小的QoS滿意度最大化模型。

綜上，可得轉(zhuǎn)化后的模型如下：

式中：目標函數(shù)定義為所有滿意度中最小的一個；λi為第i個屬性的滿意度；Qmaxi和Qmini分別表示服務(wù)流程中第i個屬性的理想解上界和理想解下界。式（12）和式（13）分別為式（6）和式（8）對應(yīng)的清晰等價形式。

當然，服務(wù)流程中可能存在某些屬性（如可用性），該類屬性的聚合計算涉及模糊數(shù)的乘法運算。根據(jù)模糊數(shù)運算法則，梯形模糊數(shù)乘積后將不再是梯形模糊數(shù)，因此無法轉(zhuǎn)化為清晰等價形式。針對該類屬性，可基于模糊模擬技術(shù)產(chǎn)生輸入及輸出數(shù)據(jù)，利用神經(jīng)元網(wǎng)絡(luò)對產(chǎn)生數(shù)據(jù)進行訓(xùn)練，從而逼近不確定函數(shù)［25］。

3.2 基于信息素的混合遺傳算法

通過3.1節(jié)轉(zhuǎn)化后的模型可歸結(jié)為組合優(yōu)化問題。針對組合優(yōu)化問題的求解，遺傳算法、蟻群算法等啟發(fā)式優(yōu)化算法具有較好的執(zhí)行時間優(yōu)勢。其中，遺傳算法借鑒自然界中生物遺傳和進化的規(guī)律，主要通過選擇、交叉和變異算子實現(xiàn)種群的并行全局搜索，并通過評價函數(shù)執(zhí)行種群的優(yōu)勝劣汰，該算法具有大規(guī)模搜索、隨機性、魯棒性、并行性及問題域無關(guān)等特性［26］。因此，與其他智能優(yōu)化算法相比，遺傳算法更適合于處理維數(shù)很高、規(guī)模較大的無數(shù)值概念類［27］優(yōu)化問題。

標準遺傳算法主要依靠隨機搜索策略，容易陷入未成熟收斂和搜索效率較低［5］。雖然文獻［19-20］對標準遺傳算法進行了改進，但在構(gòu)造子個體時仍只利用了父代攜帶的局部信息。針對文獻［19-20］的缺陷，本文設(shè)計了基于信息素的混合遺傳求解算法。該算法參考文獻［28］的算法思想，然而文獻［28］針對的是旅行商問題（Traveling Salesman Problem，TSP），與本文問題有較大區(qū)別，因此本算法結(jié)合問題的特點做了以下調(diào)整：①設(shè)計了多抽象服務(wù)流程優(yōu)化問題的編碼規(guī)則，并提出帶獎勵—懲罰的適應(yīng)度函數(shù)；②設(shè)計了適用于本問題的交叉算子，并重新定義了能見度參數(shù)，用于度量不確定情況下服務(wù)質(zhì)量的優(yōu)劣程度；③與文獻［28］的排序選擇、變異算法不同，本文采用基于錦標賽選擇方法與最優(yōu)保留相結(jié)合的選擇策略，降低了算法的時間復(fù)雜度，通過非均衡的變異概率函數(shù)，實現(xiàn)了變異操作的動態(tài)調(diào)整。

下面描述具體算法設(shè)計。

3.2.1 染色體及適應(yīng)度函數(shù)定義

本文的染色體定義為｛x1，x2，…，xn｝，xi∈［1，mi］。其中：n表示服務(wù)流程中任務(wù)的個數(shù)，mi表示第i個任務(wù)的候選服務(wù)數(shù)量。若一個事務(wù)由多條并行抽象服務(wù)流程組成，則對抽象服務(wù)流程進行排序，并依次對流程中的任務(wù)進行編碼。

以4.1 節(jié)的并行抽象服務(wù)流程WF-Net1和WF-Net2為例。首先將流程中的任務(wù)排序為［t11，t12，t14，t15，t16，t18，t19，t21，t22，t23，t24，t25，t26］；然后依次從各候選服務(wù)集合中選擇一個服務(wù)作為該基因位的值，即可生成一個染色體編碼方案。例如，染色體｛3，2，1，2，3，1，2，1，2，1，1，3，2｝表示任務(wù)t11選擇第3個候選服務(wù)，t12選擇第2個候選服務(wù)。

為了使目標函數(shù)值越高的可行個體具有較高適應(yīng)度，從而有更大的機會遺傳給下一代，本文設(shè)計了帶獎勵—懲罰的適應(yīng)度函數(shù)

式中：Fitness（X）為X的適應(yīng)度，取值范圍為［0，3］；F（X）為按式（9）計算的目標函數(shù)值，取值范圍為［0，1］；V（X）為X的時序約束違反個數(shù)；Vnum為時序約束數(shù)量；P為X的獎勵值，當X為可行染色體時P=1，否則P=0。

3.2.2 基于信息素的交叉算子

在交叉時，針對每個任務(wù)，首先判斷親代染色體是否均選擇了同一個候選服務(wù)，是則將該候選服務(wù)保留到子代中；否則，算子按照式（16），以pp（0≤pp≤1）的概率選擇最合適的服務(wù)（QoS較優(yōu)且信息素值較高），而以1-pp的概率按照式（17）進行輪盤選擇。

式中：Nk（g）表示第g代第k個任務(wù)選中的服務(wù)；Sk表示第k個任務(wù)的候選服務(wù)集合；τj（g）表示第g代第j個服務(wù)的信息素值；ηj為服務(wù)j的能見度，按式（18）計算；β為調(diào)節(jié)信息素和能見度之間相對重要性的參數(shù)；r為隨機數(shù)。變量R定義如下：

能見度ηj用于反映服務(wù)j的QoS 優(yōu)劣程度。為使整體質(zhì)量較優(yōu)的服務(wù)被選中的概率較高，本文定義ηj如下：

式中：qmaxki和qminki分別為第k個任務(wù)第i個屬性的模糊上限和模糊下限；表示候選服務(wù)j第i個屬性的梯形模糊數(shù)。

從上述過程可以看出，本文設(shè)計的交叉算子在構(gòu)造子個體時，除了繼承親代染色體的服務(wù)選擇信息外，還依靠基于能見度的局部信息及基于信息素的全局優(yōu)化信息指導(dǎo)服務(wù)的選擇，并通過一定概率的隨機選擇保持了種群的多樣性。此外，由于本文設(shè)計的交叉算子是按照染色體中的基因位順序依次對各任務(wù)重新編碼，該方法將不會改變父代染色體中的任務(wù)排列順序，且均適用于單流程或多服務(wù)流程的構(gòu)建優(yōu)化問題。

3.2.3 信息素更新策略

在遺傳算法每代運算后，各服務(wù)的信息素值將按照最大—最小螞蟻系統(tǒng)［29］中的機制進行更新，具體公式如下：

式中：ρ表示信息素的持久度；Fitness（GS）為當前全局最優(yōu)解GS的適應(yīng)度。此外，在每次更新中，令τmax=Fitness（GS）／1-ρ，τmin=τmax／2n。若τi（g+1）＞τmax，則τi（g+1）=τmax；若τi（g+1）＜τmin，則τi（g+1）=τmin。從而保證信息素值被限制在區(qū)間［τmin，τmax］之內(nèi)。

由式（19）和式（20）可知，非全局最優(yōu)解中服務(wù)的信息素將因信息素的“蒸發(fā)”而減少；而包含在全局最優(yōu)解中的服務(wù)信息素將得到加強，且全局最優(yōu)解的適應(yīng)度越高，該解對應(yīng)的各候選服務(wù)的信息素強度增加量越大，從而有利于提高相應(yīng)服務(wù)在交叉操作中被選中的概率。

3.2.4 求解過程

綜上可得基于信息素的混合遺傳算法的求解過程如下：

算法1 基于混合遺傳的服務(wù)流程優(yōu)化算法。

輸入：抽象服務(wù)流程WF-Net=（P，T，F(xiàn)）；模糊時序約束集合ψ=｛…，Pos｛DR（i，j）≤～dk｝≥αk，…｝；候選服務(wù)集合CS=｛s11，…，snmn｝；算法設(shè)置參數(shù)，包括：種群規(guī)模pop＿size，迭代次數(shù)G，基于最大信息素與能見度選擇的概率pp，信息素與能見度的相對比重β，信息素持久度系數(shù)ρ，交叉概率pc，變異概率函數(shù)pm（g）和錦標賽候選規(guī)模tour＿size。

輸出：執(zhí)行計劃X=｛x1，x2，…，xn｝。

步驟1 按抽象服務(wù)流程排序，對各流程中的任務(wù)依次從其候選服務(wù)集合中隨機選取一個服務(wù)作為染色體基因。根據(jù)模糊屬性的聚合計算公式和抽象服務(wù)流程實例，計算染色體的滿意度F（X），并結(jié)合時序約束判定結(jié)果V（X），獲得染色體的適應(yīng)度。重復(fù)本步驟pop＿size次，即生成初始的染色體群體pop，種群大小為pop＿size。

步驟2 按pop中的染色體順序依次生成隨機數(shù)r：若r不大于交叉概率pc，則將第i個染色體標識為候選親代染色體。重復(fù)本步驟pop＿size次，從而確定參與交叉的候選親代染色體集合R。

步驟3 在集合R中按輪盤賭策略選擇兩個染色體作為親代染色體，初始化k=1，并按下列操作生成新個體：

（1）當雙親染色體第k個基因位的值相同，則保留親代的值；否則，按照式（16）確定第k個基因位的值。

（2）k=k+1，重復(fù)步驟（1），直到n個任務(wù)均匹配上服務(wù)。

（3）生成隨機數(shù)r，若r不大于第g代變異概率pm（g），則對新個體執(zhí)行單點變異操作。

步驟4 將新個體放入臨時種群tempop，若tempop中的個體數(shù)量不小于pop＿size／2，則轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟3。

步驟5 對tempop與pop中的染色體，執(zhí)行基于錦標賽選擇方法與最優(yōu)保留相結(jié)合的選擇機制。即每次隨機從tour＿size個染色體中選擇最佳方案，重復(fù)本步驟pop＿size次，從而選出pop＿size個染色體賦給pop。進一步，將適應(yīng)度最高的個體替換pop中適應(yīng)度最低的個體，從而生成下一代初始種群。

步驟6 判斷是否已達到迭代次數(shù)G，是則輸出最終結(jié)果；否則執(zhí)行信息素更新策略，轉(zhuǎn)步驟2。

本文算法綜合了遺傳算法和蟻群算法的特點，并通過以下設(shè)計達到提高算法精度和收斂速度的目的：①在交叉操作方面，既考慮了優(yōu)良親代染色體的局部信息，也考慮了信息素所攜帶的全局優(yōu)化信息（如步驟3（1）～步驟3（2）），從而避免了文獻［19-20］中單純依靠局部信息進行交叉的不足；②在選擇操作方面，與文獻［19-20，28］的排序選擇策略相比，采用基于錦標賽選擇方法與最優(yōu)保留相結(jié)合的選擇策略（如步驟5），有利于降低選擇操作的時間復(fù)雜度；③在變異操作方面，通過設(shè)計變異概率函數(shù)（如步驟3（3）），使變異概率隨著迭代次數(shù)的增加而逐步降低，既有利于保持種群的多樣性，也便于算法快速收斂。

4 算例分析

為驗證本文算法的可行性，通過一個手機生產(chǎn)實例［20］來介紹和應(yīng)用本文方法。

4.1 實例說明

為了簡化模型，假設(shè)一個新手機生產(chǎn)在現(xiàn)實的生產(chǎn)企業(yè)中包含2個流程：電子主板生產(chǎn)流程（WFNet1）和外圍部件生產(chǎn)流程（WF-Net2）。這2個流程的并行情況如圖5所示。

每個任務(wù)均執(zhí)行服務(wù)外包策略，相關(guān)候選服務(wù)信息如表1所示。其中候選服務(wù)的QoS屬性由［時間，成本，可靠性］組成，且上述屬性均為梯形模糊數(shù)。如對任務(wù)t11來說，有三個候選服務(wù)s111～s113可為其提供服務(wù)。其中服務(wù)s111完成該任務(wù)的模糊時間為［4，6，8，10］、成本為［2，3，4，6］、可靠性為［2，4，5，6］。

為了縮短產(chǎn)品投放市場的時間、獲得更大的市場占有率，設(shè)置相關(guān)的時序約束如下：

（1）Pos｛DR（t23，t25）≤［0，0，17，21］｝≥0.9，表示決策者希望“在外圍部件的技術(shù)文檔撰寫開始之后最好能在17個工作日內(nèi)完成外圍部件的生產(chǎn)，最晚不能超過21個工作日”，且所選擇的服務(wù)流程滿足該模糊時序約束的程度應(yīng)不小于90%。

（2）Pos｛DR（t23，t19）≤［0，0，7，12］｝≥1，表示決策者要求“在外圍部件的技術(shù)文檔撰寫開始之后最好能在7個工作日內(nèi)完成主板的生產(chǎn)，最晚不能超過12個工作日”，且所選擇的服務(wù)流程滿足該模糊時序約束的程度應(yīng)為1。

4.2 模型建立及轉(zhuǎn)化

根據(jù)2.3節(jié)的形式化模型定義，結(jié)合本案例的時序約束，可建立問題模型如下：

表2 各任務(wù)對應(yīng)的候選服務(wù)

按照多目標模糊約束模型的轉(zhuǎn)化式（9）～式（14），代入本實例的參數(shù)并化簡，可建立清晰等價模型如下：

進一步，在式（26）～式（29）的模型中，還需對置信水平γ進行設(shè)置。因為手機加工屬于制造類服務(wù)流程，且市場競爭激烈，所以該流程對QoS的優(yōu)劣比較敏感；但是，由于手機產(chǎn)品價值較高，其對不確定情況下QoS的魯棒性同樣具有較高要求。綜上分析，針對本實例，設(shè)置γi=0.5（i=1，2，3）。此外，還將在4.4節(jié)對比不同置信水平下求解結(jié)果的差異，并就置信水平設(shè)置對優(yōu)化結(jié)果的影響進行詳細分析。

4.3 算法求解

針對上述模型，采用基于信息素的混合遺傳算法進行求解。在算法參數(shù)設(shè)置方面，根據(jù)問題規(guī)模，設(shè)置pop＿size=30，G=50，pc=0.8，tour＿size=5；與信息素相關(guān)的參數(shù)參考文獻［28，29］設(shè)置為：pp=0.9，β=3，ρ=0.95；變異概率函數(shù)參考文獻［30］設(shè)置為：pm（g）=0.15×（1-0.1（1-g／G））。實驗 在2.1GHz的英特爾酷睿2雙核處理器和1GB 內(nèi)存的臺式機上完成。由于算法具有隨機性，以某次求解為例，具體求解過程如下：

按照算法的步驟1所述，首先隨機生成30個染色體，組成初始染色體群體pop。以第1個染色體為例，其編碼為｛3，2，1，2，3，1，2，1，2，1，1，3，2｝，通過計算，其對應(yīng)的三個目標函數(shù)的滿意度分別為｛0.67，0.72，0.51｝，由于不滿足第一個時序約束，適應(yīng)度為1.01。相應(yīng)地，通過計算其他染色體的適用度可以看出，初始解的適應(yīng)度范圍為［0.65，2.43］，可行解個數(shù)為11。

生成初始解后，根據(jù)步驟2，按0.8的交叉概率共選擇出21個染色體組成候選親代染色體集合R。根據(jù)步驟3和步驟4，依次從R中按輪盤賭選擇兩個親代染色體執(zhí)行交叉和變異操作，生成臨時種群tempop。以適應(yīng)度為2.42的染色體｛3，2，1，1，3，1，1，3，1，2，1，2，1｝為例，與適應(yīng)度為2.39的染色體｛3，2，2，1，2，1，2，3，2，2，1，1，2｝的交叉和變異過程如下：親代染色體中有7個基因位相同，將直接繼承到子代中，其他6個基因位根據(jù)式（16）重新選擇服務(wù)，最終生成適應(yīng)度為2.45的新染色體｛3，2，2，1，1，1，1，3，1，2，1，2，1｝。由于所生成的隨機數(shù)r大于第1代變異概率閾值pm=0.15×（1-0.1（1-1／50））=0.134，即新染色體｛3，2，2，1，1，1，1，3，1，2，1，2，1｝不執(zhí)行變異操作。根據(jù)步驟5，對tempop與pop中的染色體，基于錦標賽選擇與最優(yōu)保留方法執(zhí)行選擇操作，并確定第1代的染色體組pop?？梢钥闯銎溥m應(yīng)度的范圍為［0.86，2.46］，與初始解比較可知，適應(yīng)度得到了優(yōu)化。

重復(fù)上述步驟2～步驟5，當?shù)螖?shù)為21時，解收斂為｛2，2，1，2，2，1，1，3，2，2，2，2，1｝，其適應(yīng)度為2.50，對應(yīng)的滿意度分別為｛0.61，0.62，0.50｝?；谒@得的最優(yōu)解，客戶可依次為各任務(wù)匹配相應(yīng)的服務(wù)，從而確定最優(yōu)執(zhí)行計劃。

4.4 結(jié)果分析

目標機會約束的置信水平γ反映了目標函數(shù)在不確定環(huán)境下的實現(xiàn)機會。為觀察不同置信水平對優(yōu)化結(jié)果的影響，改變模糊目標中的置信水平γi（i=1，2，3），并記錄目標函數(shù)的滿意度變化，結(jié)果如表3所示。

表3 改變置信水平對優(yōu)化結(jié)果的影響

從表3可以看出，隨著置信水平γi由0.9 降至0.3，最小滿意度不斷增大。表明在不確定環(huán)境下，當手機決策者趨向于選擇存在高QoS可能的服務(wù)流程時，它可能承擔的服務(wù)流程不能兌現(xiàn)QoS承諾的風險將增加，該結(jié)論與實際相符。同時表3也表明，采用本文的多目標模糊約束模型轉(zhuǎn)化方法能較好地保留模糊信息量，并讓手機決策者直觀觀察到風險與效益的關(guān)系，從而權(quán)衡并做出決策。

5 算法性能的對比分析

為了驗證本文算法在計算效率上的優(yōu)越性，進一步從求解精度和算法執(zhí)行時間兩方面，將本文算法與改進遺傳算法［20］、混合優(yōu)化算法［28］及最大-最小蟻群算法［29］進行對比。

在案例設(shè)計方面，本文設(shè)計了三種不同的實驗，包括不同的任務(wù)數(shù)量、不同的候選服務(wù)數(shù)量和不同的時序約束數(shù)量。參數(shù)設(shè)置為pop＿size=100，G=5000，pc=0.8，tour＿size=10，γi=0.5，β=3，pp=0.9，ρ=0.95，pm（g）=0.15×（1-0.1（1-g／G））。每個候選服務(wù)的QoS 都是隨機產(chǎn)生的。具體對各屬性來說，依次產(chǎn)生4個范圍在［1，10］的隨機數(shù)，并對上述隨機數(shù)按從小到大排序，從而獲得該屬性對應(yīng)的梯形模糊數(shù)。所有的實驗均在2.1GHz的英特爾酷睿2 雙核處理器和1 GB 內(nèi)存的臺式機上完成。考慮到算法的隨機性，每組數(shù)值取20次結(jié)果的平均值。

（1）任務(wù)數(shù)量的不同

此組實驗是為了研究任務(wù)數(shù)量增加的、不同算法的求解精度和運行時間的差異。在此實驗中，任務(wù)數(shù)量從10增加到50，增幅定為5；固定每個任務(wù)候選服務(wù)的數(shù)量為20，時序約束的數(shù)量為5。實驗結(jié)果如圖6和圖7所示。

從圖6可以看出，本文的求解精度與混合優(yōu)化算法［28］及最大-最小蟻群算法［29］基本相同，明顯優(yōu)于改進遺傳算法［20］，且隨著任務(wù)數(shù)量的增加，求解優(yōu)化效果越明顯。由圖7可以看出，本文算法的計算時間明顯低于其他三種算法。從時間增長趨勢上看，隨著任務(wù)數(shù)量的增加，本文求解時間的增長率最小，而蟻群算法［29］的增長率明顯高于其他三類算法。

（2）候選服務(wù)數(shù)量的不同

此組實驗是為了研究不同算法的求解精度及計算時間隨候選服務(wù)數(shù)量的變化而變化的情況。在這組實驗中，候選服務(wù)的數(shù)量從10增加到50，增幅為5；任務(wù)和時序約束的個數(shù)分別固定為30 和5。實驗結(jié)果如圖8和圖9所示。

從圖8可以看出，本文的求解精度與混合優(yōu)化算法［28］及最大-最小蟻群算法［29］基本相同，明顯優(yōu)于改進遺傳算法［20］。隨著任務(wù)數(shù)量的增加，上述算法較改進遺傳算法［20］的優(yōu)化程度呈上升趨勢。由圖9可以看出，本文算法的計算時間明顯低于其他三種算法。雖然從增長趨勢上看，隨著候選服務(wù)數(shù)量的增加，本文算法計算時間的增長率高于改進遺傳算法［20］，但是由于單個任務(wù)對應(yīng)的候選服務(wù)數(shù)一般不會超過50個，可以認為本文的計算效率仍較改進遺傳算法［20］具有優(yōu)勢。

（3）時序約束數(shù)量的不同

此組實驗是為了研究時序約束個數(shù)的增加對求解精度和計算時間的影響。在這組實驗中，時序約束數(shù)量從5增加到45，增幅為5；任務(wù)及其候選服務(wù)的數(shù)量分別固定為30和10。實驗結(jié)果如圖10 和圖11所示。

從圖10可以看出，本文的求解精度與混合優(yōu)化算法［28］及最大-最小蟻群算法［29］基本相同，明顯優(yōu)于改進遺傳算法［20］。此外，隨著約束數(shù)量的增加，本文算法的求解精度穩(wěn)定，而改進遺傳算法的求解精度明顯呈下降趨勢。由圖11可以看出，本文算法的計算時間最短，而蟻群算法［29］的計算時間最長。從增長趨勢上看，隨著約束數(shù)量的增加，改進遺傳算法［20］的計算時間增長明顯呈上升趨勢，其他三類算法的計算時間增長率均較小。

綜上分析，通過設(shè)計不同任務(wù)數(shù)量、候選服務(wù)數(shù)量和時序約束數(shù)量的實驗，對比發(fā)現(xiàn)：

（1）針對上述多組實驗，本文算法的求解精度均優(yōu)于改進遺傳算法［20］，計算精度提高了1%～29.6%，特別是隨著問題規(guī)模的增大，求解精度的優(yōu)化效果更明顯。在求解時間上，本文算法均優(yōu)于改進遺傳算法，其計算時間節(jié)約了46.6%～69.2%。但需指出，隨著候選服務(wù)數(shù)量的增加，本文算法的求解時間的增長率高于改進遺傳算法。

（2）針對上述多組實驗，本文算法的求解精度與混合優(yōu)化算法［28］基本相同，計算精度最大差別為1.3%。在求解時間上，本文算法明顯優(yōu)于混合優(yōu)化算法，計算時間節(jié)約了58.1%～68.8%。而從時間增長趨勢上看，隨著問題規(guī)模的增大，兩種算法的求解時間增長率接近。

（3）針對上述多組實驗，本文算法的求解精度與最大-最小蟻群算法［29］基本相同，計算精度最大差別為1%。在求解時間上，本文算法明顯優(yōu)于最大-最小蟻群算法，計算時間節(jié)約了82.6%～96.5%。隨著問題規(guī)模的增大，本文算法在求解時間上的增長率明顯低于最大-最小蟻群算法。

分析其原因，就算法的求解精度來說，因為改進遺傳算法［20］僅利用了雙親染色體指導(dǎo)子代生成，而本文算法及其他兩種算法［28-29］均通過信息素記錄迭代過程中的求解經(jīng)驗，并基于所學(xué)習(xí)到的全局信息指導(dǎo)子代生成，所以更有利于獲得較好的求解結(jié)果。特別是隨著任務(wù)數(shù)、服務(wù)數(shù)量和約束的增加，解空間不斷擴大，通過信息素反映的全局信息在尋優(yōu)過程中發(fā)揮的作用更加明顯。

就算法的求解時間而言，因為最大-最小蟻群算法［29］的運算開銷大量花費在基于信息素概率的子代生成計算上，基于信息素的遺傳算法框架降低了算法的時間復(fù)雜度；且與改進遺傳算法［20］和混合優(yōu)化算法［28］相比，本文算法通過改進的選擇及變異策略也進一步降低了算法的時間復(fù)雜度，所以具有比其他三類算法更好的求解時間優(yōu)勢。但從算法流程可知，隨著候選服務(wù)數(shù)量的增大，信息素更新及基于信息素交叉操作的運算量將增大，而候選服務(wù)數(shù)量的增加對改進遺傳算法［20］的時間復(fù)雜度影響較小，因此在候選服務(wù)數(shù)量增加的情況下，本文算法的求解時間增長率會高于改進遺傳算法［20］。

6 結(jié)束語

本文針對普遍存在的時序約束不確定情況，構(gòu)建了模糊情況下帶時序約束的服務(wù)流程優(yōu)化模型。在求解方面，首先基于模糊機會約束理論和最大模糊滿意度法，將多目標模糊規(guī)劃模型轉(zhuǎn)化成以滿意度最大化為目標的清晰等價模型，提出基于信息素的混合遺傳算法進行求解。該算法不僅利用親代和服務(wù)自身的局部信息，還利用以信息素形式保存的全局信息，因此加快了收斂效率。本文設(shè)計了不同任務(wù)數(shù)量、候選服務(wù)數(shù)量和時序約束數(shù)量的實驗，結(jié)果表明：與已有成果相比，本文算法在執(zhí)行時間和求解精度上具有明顯優(yōu)勢。

在本文基礎(chǔ)上，未來將在如下方面進一步展開工作：①針對流程執(zhí)行過程中出現(xiàn)的時序異常，如何實現(xiàn)服務(wù)流程的動態(tài)調(diào)整，從而保證時序一致性；②對除基本結(jié)構(gòu)之外的工作流復(fù)雜模式進行討論。

［1］CHEN J，YANG Y.Multiple states based temporal consistency for dynamic verification of fixed-time constraints in grid workflow systems［J］.Concurrency and Computation：Practice and Experience，2007，19（7）：965-982.

［2］DU Yanhua，WANG Xiaofei，YAO Jianshi.Probability based timed compatibility of Web service composition［J］.Practical Applications of Intelligent Systems Advances in Intelligent and Soft Computing，2012，124：31-39.

［3］LIU X，YANG Y，JIANG Y，et al.Preventing temporal violations in scientific workflows：where and how ［J］.IEEE Transactions on Software Engineering，2011，37（6）：805-825.

［4］ZENG L，BENATALLAH，B，DUMAS M，et al.Quality driven Web services composition［C］／／Proceedings of the 12th International Conference World Wide Web.New York，N.Y.，USA：ACM，2003：411-421.

［5］ROSENBERG F，MULLER M，LEITNER P，et al.Metaheuristic optimization of large-scale QoS-aware service compositions［C］／／Proceedings of 2010IEEE International Conference on Services Computing.Washington，D.C.，USA：IEEE，2010：97-104.

［6］YANG F，SU S，LI Z.Hybrid QoS-aware semantic Web service composition strategies［J］.Science in China Series F：Information Sciences，2008，51（11）：1822-1840.

［7］LI Zhen，YANG Fangchun，SU Sen.Fuzzy multi-attribute decision making-based algorithm for semantic Web service composition［J］.Journal of Software，2009，20（3）：583-596（in Chinese）.［李 禎，楊放春，蘇 森.基于模糊多屬性決策理論的語義Web 服務(wù)組合算法［J］.軟件學(xué)報，2009，20（3）：583-596.］

［8］TAO Fei，ZHAO Dongming，HU Yefa，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.

［9］TAO Fei，ZHAO Dongming，ZHANG Lin.Resource service optimal-selection based on intuitionistic fuzzy set and non-functionality QoS in manufacturing grid system ［J］.Knowledge and Information System，2010，25（1）：185-208.

［10］LI Bohu，ZHANG Lin，WANG Shilong，et al.Cloud manufacturing：a new service oriented networked manufacturing model［J］.Computer Integrated Manufacturing Systems，2010，16（1）：1-7，16（in Chinese）.［李伯虎，張 霖，王時龍，等.云制造——面向服務(wù)的網(wǎng)絡(luò)化制造新模式［J］.計算機集成制造系統(tǒng)，2010，16（1）：1-7，16.］

［11］LIU Weining，LI Yiming，LIU Bo.Service composition in cloud manufacturing based on adaptive mutation particle swarm optimization［J］.Journal of Computer Applications，2012，32（10）：2869-2874（in Chinese）.［劉衛(wèi)寧，李一鳴，劉波.基于自適應(yīng)粒子群算法的制造云服務(wù)組合研究［J］.計算機應(yīng)用，2012，32（10）：2869-2874.］

［12］BAI L，LIU M.Fuzzy sets and similarity relations for semantic Web service matching［J］.Computers and Mathematics with Applications，2011，61（8）：2281-2286.

［13］DU Yanhua，LI Hong，AI Lifeng.Dynamic configuration of service based processes in cloud computing using linear programming［C］／／Proceedings of the 9th World Congress on Intelligent Control and Automation.Washington，D.C.，USA：IEEE，2012：3509-3514.

［14］CHEN J，YANG Y.Localizing temporal constraints in scientific workflows［J］.Journal of Computer and System Sciences，2010，76（6）：464-474.

［15］WANG P.QoS-aware web services selection with intuitionistic fuzzy set under consumer's vague perception［J］.Expert Systems with Applications，2009，36（3）：4460-4466.

［16］JESJE C，JULIA S，VALETTE R.Fuzzy continuous resource allocation mechanisms in workflow management systems［C］／／Proceedings of 2009 23rd Brazilian Symposium on Software Engineering.Washington，D.C.，USA：IEEE Computer Society，2009：236-251.

［17］ARDAGNA D，PERNICI B.Adaptive service composition in flexible processes［J］.IEEE Transactions on Software Engi-neering，2007，33（6）：369-384.

［18］YU J，BUYYA R.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms［J］.Scientific Programming，2006，14（3）：217-230.

［19］AI L，TANG M.A penalty-based genetic algorithm for QoSaware web service composition with inter-service dependencies and conflicts［C］／／Proceedings of International Conference on Computational Intelligence for Modeling Control &Automation.Washington，D.C.，USA：IEEE，2008：738-743.

［20］DU Y，WANG X，AI L.Dynamic selection of services under temporal constraints in cloud computing［C］／／Proceedings of 2012International Conference on E-Business Engineering.Washington，D.C.，USA：IEEE，2012：252-259.

［21］DU Y，XIONG P，F(xiàn)AN Y，et al.Dynamic checking and solution to temporal violations in concurrent workflow processes［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part A：Systems and Humans，2011，41（6）：1166-1181.

［22］HU Baoqing.Fuzzy basic theory［M］.Wuhan：Wuhan University Press，2010（in Chinese）.［胡寶清.模糊理論基礎(chǔ)［M］.武漢：武漢大學(xué)出版社，2010.］

［23］ZHOU Y，MURATA T，DEFANTI T.Modeling and performance analysis using extended fuzzy-timing Petri nets for networked virtual environment［J］.IEEE Transactions on System，Man，and Cybernetics—Part B：Cybernetics，2000，30（5）：737-755.

［24］LU M.On crisp equivalents and solutions of fuzzy programming with different chance measures［J］.Information，2003，6（2）：125-134.

［25］LIU Baoding，ZHAO Ruiqing，WANG Gang.Uncertain programming with applications［M］.Beijing：Tsinghua University Press，2003（in Chinese）.［劉寶錠，趙瑞清，王 綱.不確定規(guī)劃及應(yīng)用［M］.北京：清華大學(xué)出版社，2003.］

［26］LIU Weining，LIU Bo，SUN Dihua.Multi-task oriented service composition in cloud manufacturing ［J］.Computer Integrated Manufacturing Systems，2013，19（1）：199-209（in Chinese）.［劉衛(wèi)寧，劉 波，孫棣華.面向多任務(wù)的制造云服務(wù)組合［J］.計算機集成制造系統(tǒng)，2013，19（1）：199-209.］

［27］ZHOU Ming，SUN Shudong.Genetic algorithms：theory and application［M］.Beijing：National Defense Industry Press，1996：11-14（in Chinese）.［周 明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，1996：11-14.］

［28］ZHAO F，LI S，SUN J，et al.Genetic algorithm for the onecommodity pickup-and-delivery traveling salesman problem［J］.Computer &Industry Engineering，2009，56（4）：1642-1648.

［29］STUTZLE T，HOOS H.MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889-898.

［30］WANG Wenbin，SUN Qibo，ZHAO Xinchao，et al.Web services selection approach with QoS global optimal based on discrete particle swarm optimization with non-uniform mutation algorithm［J］.Acta Electronica Sinica，2010，38（12）：2774-2779（in Chinese）.［王文彬，孫其博，趙新超，等.基于非均衡變異離散粒子群算法的QoS全局最優(yōu)Web服務(wù)選擇方法［J］.電子學(xué)報，2010，38（12）：2774-2779.］