面向過程的資源組合排斥沖突檢測方法

孟慶豐 李海波

面向過程的資源組合排斥沖突檢測方法

孟慶豐 李海波

(華僑大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 福建 廈門 361021)

由于云制造環(huán)境下服務(wù)于業(yè)務(wù)過程的資源集中可能存在相互排斥的資源，在運行階段可能會產(chǎn)生資源沖突。針對這種情況，提出了面向業(yè)務(wù)過程的資源組合排斥沖突檢測方法。以工作流模型為基礎(chǔ)，提出資源服務(wù)鏈模型(RSCM)并分析在資源服務(wù)鏈模型中可能出現(xiàn)排斥沖突的情況；提出有效子圖的概念。最后基于資源服務(wù)鏈模型和有效子圖，提出面向過程的資源組合沖突檢測算法。實驗結(jié)果表明，該算法能有效地檢測出面向過程的資源組合過程中因資源排斥關(guān)系而產(chǎn)生的資源沖突。

云制造 業(yè)務(wù)過程 資源組合 沖突檢測

0 引 言

云制造是一種利用網(wǎng)絡(luò)和云制造服務(wù)平臺，按用戶需求組織網(wǎng)上制造資源(制造云)，為用戶提供各類按需制造服務(wù)的一種網(wǎng)絡(luò)化制造新模式[1]。資源組合是指將云制造環(huán)境下能夠完成特定制造任務(wù)所需的各類制造資源聚集在一起，為資源虛擬化提供支持，從而提高云制造中資源的利用率，實現(xiàn)資源增值[2]。云制造環(huán)境下，制造資源因具有多樣性、異構(gòu)性、分散性、協(xié)同性和專業(yè)性等特點[3-5]，資源之間存在著排斥關(guān)系、依賴關(guān)系、可替換關(guān)系等關(guān)系[6]。其中，資源排斥關(guān)系可能會導(dǎo)致業(yè)務(wù)過程執(zhí)行失?。阂环矫?，在建模階段，如果將相互排斥的資源組合在一起，在運行階段，業(yè)務(wù)過程就可能會產(chǎn)生資源沖突(稱為排斥沖突)；另外一方面，在云制造環(huán)境下，資源組合往往比較復(fù)雜，建模人員很難兼顧到所有資源之間的排斥關(guān)系。所以需要給出一種沖突檢測方法，在資源組合的模型階段對其進(jìn)行檢測，提前測出可能存在的排斥沖突，使得模型能夠及時被修改，從而減少業(yè)務(wù)過程執(zhí)行失敗的幾率。

針對這種減少制造任務(wù)執(zhí)行失敗的幾率的問題，當(dāng)前主要的研究有：利用形式化的方法(Petri網(wǎng)、進(jìn)程代數(shù)和有限自動機(jī)等)，通過驗證服務(wù)狀態(tài)的可達(dá)性、死鎖和活鎖等來驗證服務(wù)組合的正確性[7-9]；對工作流語義失敗的處理可以事先在模型中描述出來，如WAMO模型[10]；還有一種給資源枷鎖的方法，試圖避免工作流之間的資源沖突[11]；通過分析約束在工作流模型和運行層次所起的不同作用，識別出無效路徑[12]。然而，關(guān)于云制造面向過程資源組合中的排斥沖突檢測問題，目前的研究較少。

鑒于此，本文展開了對面向過程資源組合的排斥沖突檢測問題的探索：首先，給出資源排斥關(guān)系和資源服務(wù)鏈模型的定義，并分析面向過程的資源組合模型階段排斥沖突；然后，引入有效子圖的概念，并基于此給出面向過程的資源組合排斥沖突的檢測方法。利用本方法，可以在模型階段提前檢測出資源組合中可能存在的排斥沖突，從而降低制造任務(wù)執(zhí)行出錯的幾率。

1 面向過程的資源組合排斥沖突分析

1.1 資源排斥關(guān)系

云制造環(huán)境下，服務(wù)于業(yè)務(wù)過程資源集中，可能存在相互沖突的資源。相互沖突的資源不能共同服務(wù)于同一個業(yè)務(wù)過程。由此，下面給出資源排斥關(guān)系的定義：

定義1 資源排斥關(guān)系。設(shè)R為服務(wù)于某業(yè)務(wù)過程的資源集合，?ri,rj∈R，如果ri和rj之間存在沖突，則稱ri與rj在該業(yè)務(wù)過程中相互排斥，記作Xor(ri,rj)=TRUE。

1.2 資源服務(wù)鏈模型

資源服務(wù)鏈模型RSCM(Resources Service Chain Model)，是指面向過程的資源組合在模型階段建立的模型。該模型為工作流模型中各個活動定義所需的資源集。首先,借鑒文獻(xiàn)[13]，給出工作流模型的定義：

定義3 資源服務(wù)鏈模型。設(shè)資源服務(wù)鏈模型為RSCM= (id,wfm,RS,F)，其中id是RSCM的唯一標(biāo)識；wfm是對應(yīng)的工作流模型；RS={R1,R2,… ,Rn}，n≥1，其中Ri∈RS表示服務(wù)于wfm中某個活動的資源集；F表示由RS到wfm中活動集合A的映射，?R∈RS,F(R)∈A。

圖1描述的是某齒輪制造過程的資源服務(wù)鏈模型，其中wfm表示資源服務(wù)鏈模型中定義的工作流模型，RS表示模型中服務(wù)于對應(yīng)工作流的資源集的集合，RS中的資源集與wfm中的活動一一對應(yīng)。

圖1 某齒輪制造過程的資源服務(wù)鏈模型

1.3 面向過程的資源組合排斥沖突

面向過程的資源組合排斥沖突，是指在模型階段，RSCM中定義了相互排斥的資源，并且這些相互排斥的資源能夠服務(wù)于同一個過程實例，使得在運行階段某個過程實例產(chǎn)生的資源沖突。因此，面向過程的資源組合中排斥沖突有以下兩個特點：

(1) RSCM中定義了相互排斥的資源。根據(jù)定義3，如果RSCM中相互排斥的資源，其在RSCM中可能的分布情況有：分布于在同一個資源集中；在不同的資源集中。如圖2所示，資源r1和r4位于同一個資源集R1中；r31和r34位于不同的資源集R13和R14中。

圖2 相互排斥的資源的分布情況

(2) 相互排斥的資源可能服務(wù)于同一個過程實例。顯然，如果相互排斥的資源位于同一個資源集中，則必然服務(wù)于同一個過程實例；如果相互排斥的資源位于不同的資源集中，根據(jù)定義2和定義3，在工作流模型控制結(jié)構(gòu)的控制下，服務(wù)處于XOR不同分支的活動的資源集，不能共同服務(wù)于同一過程實例。如圖1所示，資源集R13和R14分別處于一個XOR類型控制塊的不同分支上，不能服務(wù)于同一過程實例。

2 面向過程的資源組合沖突檢測方法

綜上所述，對面向過程的資源組合沖突檢測，即檢測對應(yīng)的RSCM的各個資源集中是否可能服務(wù)于同一個過程實例并且存在相互排斥的資源。首先，要判斷RSCM中任意兩個資源集是能夠服務(wù)于同一個過程實例。為此，引入有效子圖的概念。

2.1 有效子圖

定義4 有效子圖。設(shè)G=(V,E)是工作流模型wfm的時序關(guān)系圖，其中V=A,E=S,G′=(V′,E′)為wfm的一個實例的時序關(guān)系圖，容易證明G′是G的子圖，稱G′為G的一個有效子圖。圖3中描述的是某齒輪制造過程的時序關(guān)系圖G和有效子圖ESG。

圖3 某齒輪制造過程的時序關(guān)系圖與有效子圖

顯然，在wfm的控制下，有效子圖G′有如下性質(zhì)：

(1)as∈V′,ae∈V′。

(2) ?ai∈V′,aj∈V′，使得∈V′，即G′是連通的，記作Connected(G′) =TRUE。

(3) 符合wfm中控制結(jié)構(gòu)C的語義，即?c∈C,e∈E′,bi∈B(c),e∈E(c,bi)，如果T(c) =XOR，則bj∈B(c),e′∈E(c,bj)，都有e′∈E′，其中bj≠bi；如果T(c)=AND，則bj∈B(c)，e′∈E(c,bj)，使得e′∈E。記作ValiCtrl(G′,wfm)=TRUE。

由有效子圖的定義和性質(zhì)，給出有效子圖的判定規(guī)則：

有效子圖的判定規(guī)則 設(shè)G是RSCM中wfm所對應(yīng)的時序關(guān)系圖，vs和ve是G的唯一開始節(jié)點和結(jié)束節(jié)點，G′=(V′,E′)是G的子圖，并且vs,ve∈V′，如果Connected(G′) =TRUE并且ValiCtrl(G′,wfm)=TRUE，則G′是G的一個有效子圖。

根據(jù)有效子圖的判定規(guī)則，給出求wfm對應(yīng)的時序關(guān)系圖G中的有效子圖算法：

算法1 GetESGSet(wfm,G)

輸入：工作流模型wfm

輸出：有效子圖集ESGSet={G1,G2,…,Gt}

begin

ESGSet=?;

temp = GetSubG(G,G.vs,G.ve);

for all G′∈temp do

if Connected(G′,wfm)=TRUE and

ValiCtrl(G′,wfm)=TRUE then

end if

end for

return ESGSet;

end GetESGSet

算法GetESGSet實際上通過遍歷圖，調(diào)用GetSubG(G,G.vs,G.ve)找出所包含開始節(jié)點G.vs和結(jié)束節(jié)點G.ve的子圖集合，然后根據(jù)有效子圖的判定規(guī)則進(jìn)行篩選，找出有效子圖集ESGSet。算法的時間復(fù)雜度為O(n×m)，其中n是所求子圖的個數(shù)，m是有效子圖的活動節(jié)點個數(shù)。

2.2 面向過程的資源組合排斥沖突檢測方法

算法GetESGSet求出了有效子圖集ESGSet，根據(jù)定義3和定義4，可以通過驗證有效子圖中是否存對應(yīng)的活動節(jié)點，來判斷對應(yīng)的資源集能否服務(wù)于同一個過程實例。由此，給出算法2，判斷工作流模型中任意兩個活動節(jié)點是否在同一個有效子圖中。

算法2 InSameESG(ESGSet,v1,v2)

輸入：ESGSet和wfm中任意的v1和v2

輸出：布爾值

begin

for all G′∈ESGSet do

if Search(G′,v1) = TRUE and

Search (G′,v2) = TRUE then

return TRUE;

end if

end for

return FALSE;

end InSameESG

在算法InSameESG(ESGSet,v1,v2)中，Search(G′,v1)用于判斷節(jié)點v1是否存在于圖G′中。算法中時序關(guān)系圖G是鄰接表結(jié)構(gòu)，該算法的時間復(fù)雜度最好的情況為O(1)，最壞為O(t×(n+e))，其中n為ESGSet中平均每個有效子圖的活動節(jié)點個數(shù)，e為邊的平均個數(shù)，t為ESGSet中元素的個數(shù)。

根據(jù)給定的資源排斥關(guān)系集合Xor，給出算法3，判斷資源服務(wù)鏈模型中定義的任意兩個資源集是否存在相互排斥的資源。

算法3 ExistXorRes(Xor,Ri,Rj)

輸入：資源集Ri、Rj和排斥關(guān)系集Xor

輸出：布爾值

begin

for all r1∈Ri,r2∈Rj,r1≠r2 do

if ∈Xor then

return TRUE;

end if

end for

return FLASE;

end ExistXorRes

在算法ExistXorRes(Xor,Ri,Rj)中，Xor是當(dāng)前業(yè)務(wù)過程的資源排斥關(guān)系集合。該算法的時間復(fù)雜度為O(m×n)，m與n分別是Ri和Rj中的資源數(shù)量。

綜上，下面給出面向過程的資源組合排斥沖突檢測算法，其核心思想是：遍歷RSCM中的RS，對于能夠服務(wù)于同一個過程實例的資源集，判斷其中是否存在相互排斥的資源，如果存在，則返回存在排斥沖突的兩個資源集。在給出算法之前，首先給出算法中可能出現(xiàn)的基本定義和操作：Xor是某業(yè)務(wù)過程中排斥關(guān)系的集合；根據(jù)資源服務(wù)鏈模型獲取RS—GetRS(RSCM)；獲取資源服務(wù)鏈模型對應(yīng)的工作流模型wfm—GetWfm(RSCM)；獲取工作流模型的時序關(guān)系圖—GetTG(wfm)。

算法4 XorConfDetection(RSCM)

輸入：RSCM和資源排斥關(guān)系集Xor

輸出：存在排斥沖突的位置集合Addr

begin

wfm=GetWfm(RSCM);

G=GetTG(wfm);

ESGSet=GetESGSet(wfm,G);

RS=GetRS(RSCM);

Addr=?;

for all RiRS,RjRS do

if InSameESG(ESGSet,F(Ri),F(Rj))=TRUE

and ExistXor (Xor,Ri,Rj)=TRUE then

Addr←Addr∪{};

end if

end for

return Addr;

end XorConfDetection

3 實例分析

以云制造環(huán)境下面向某種齒輪制造過程的資源組合為例。該齒輪生產(chǎn)加工過程的RSCM如圖1所示，各個業(yè)務(wù)活動和活動所需的資源集如表1所示(對于模型中每個活動所需資源的詳細(xì)信息，參見文獻(xiàn)[15])。下面應(yīng)用本文提出的沖突檢測方法來對該模型進(jìn)行檢測。

表1 活動及其資源集

現(xiàn)已知該業(yè)務(wù)過程的排斥關(guān)系集合Xor={,,,,,,}。設(shè)rscm為該業(yè)務(wù)過程的資源服務(wù)鏈模型，調(diào)用面向過程資源組合的排斥沖突檢測算法XorConfDetection(rscm)，對rscm進(jìn)行排斥沖突檢測，其執(zhí)行步驟如下：

步驟1 由算法GetESGSet求出的有效子圖集ESGSet={G1,G2,G3,G4,G5,G6}，如圖4所示。

圖4 所有的有效子圖

步驟2 遍歷rscm中所有的資源集，由InSameESG和ExistXorRes，求出rscm中所有存在排斥沖突的資源集。所得檢測結(jié)果如表2所示。

表2 檢測結(jié)果

實例分析：

(1) 如表2中所示，在rscm中存在排斥沖突的資源集，應(yīng)該修改rscm，以減少過程執(zhí)行失敗的幾率。

(2) 除了表2中所示的存在相互排斥資源的資源集之外，還有一些資源集中存在相互排斥的資源，如r31和r34。然而，由于這些資源集在運行階段，不會服務(wù)于同一個過程實例，所以不存在排斥沖突。

(3) 沖突集的大小對于該算法的效率有直接影響，對于同一個業(yè)務(wù)過程，給定的沖突集越大算法準(zhǔn)確率越高。

(4) 資源排斥關(guān)系是不是一成不變的，隨著科技的發(fā)展，有些制造資源可能不會相互排斥了，所以需要經(jīng)常維護(hù)排斥集。

(5) 可以通過對大量已經(jīng)執(zhí)行的業(yè)務(wù)過程的挖掘，找出更多的資源排斥關(guān)系，不僅可以對面向過程資源組合的排斥沖突檢測提供決策支持，更能減少業(yè)務(wù)過程執(zhí)行失敗的幾率。

4 結(jié) 語

本文通過引入資源排斥關(guān)系和資源服務(wù)鏈模型的定義，并分析在資源服務(wù)鏈模型中可能存在資源沖突情況，然后引入有效子圖，進(jìn)而給出沖突檢測算法，并通過實例驗證了算法的有效性。本方法可以在面向過程資源組合的建模階段，提前檢測出可能的資源排斥沖突，能夠降低業(yè)務(wù)過程執(zhí)行失敗的幾率。

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

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

[3] 張霖,羅永亮,范文慧,等. 云制造及相關(guān)先進(jìn)制造模式分析[J]. 計算機(jī)集成制造系統(tǒng),2011,17(3): 458-468.

[4] 張霖,羅永亮,陶飛,等. 制造云構(gòu)建關(guān)鍵技術(shù)研究[J]. 計算機(jī)集成制造系統(tǒng),2010,16(11): 2510-2520.

[5] 任磊,張霖,張雅彬,等. 云制造資源虛擬化研究[J]. 計算機(jī)集成制造系統(tǒng),2011,17(3): 511-518.

[6] 郟維強(qiáng),馮毅雄,譚建榮,等. 制造資源混合粒度優(yōu)化組合方案求解技術(shù)[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2012,24(3): 281-289.

[7] 陳丁劍,吳健,馬滿福,等. 基于Petri網(wǎng)的Web服務(wù)組合建模[J]. 計算機(jī)科學(xué),2006,33(5): 128-135.

[8] 廖軍,譚浩,劉錦德. 基于Pi-演算的Web服務(wù)組合的描述和驗證[J]. 計算機(jī)學(xué)報,2005,28(4): 635-643.

[9] 雷麗暉,段振華. 一種基于擴(kuò)展有限自動機(jī)驗證組合Web服務(wù)的方法[J].軟件學(xué)報. 2007,18(12): 2980-2990.

[10] Ellis C A,Keddara K,Rozenberg G. Dynamic change within workflow systems[C]//Proceedings of International Conference on Organis Computer System. New York,NY,USA: ACM Press,1995: 10-21.

[11] 胡乃靜,顧寧,施伯樂. 基于語義約束的資源工作流并發(fā)正確性保證[J].計算機(jī)研究與發(fā)展,2003,40(5): 712-719.

[12] 李海波,郭春麗,戰(zhàn)德臣. 基于約束滿足性的工作流執(zhí)行成功率提高方法[J].計算機(jī)集成制造系統(tǒng),2010,16(6): 1300-1306.

[13] 李海波. 工作流模型復(fù)雜控制結(jié)構(gòu)構(gòu)造方[J]. 計算機(jī)科學(xué). 2012,39(11),106-110,136.

[14] Bae J,Caverlee J,Liu Ling, et al. Process mining by measuring process block similarity[C]//Business Process Management Workshops. 2006: 141-252.

[15] 《齒輪制造手冊》編寫委員會. 齒輪制造手冊[M]. 北京: 機(jī)械工業(yè)出版社,1997: 3-11.

PROCESS-ORIENTED COLLISION DETECTION METHOD FOR RESOURCES COMPOSITION EXCLUSION

Meng Qingfeng Li Haibo

(CollegeofComputerScienceandTechnology,HuaqiaoUniversity,Xiamen361021,Fujian,China)

Because of the possible existence of mutually exclusive resources in resource concentration that serving the business process in cloud manufacturing environment,resource collisions may occur in running phase. To cope with this problem,we proposed a business process-oriented collision detection method for resources composition exclusion. Based on workflow model,we proposed the resources service chain model (RSCM) and analysed the situation of collision in exclusion possibly occurring in RSCM; we proposed the concept of effective sub-graph as well. Finally,based on RSCM and effective sub-graph,we proposed the business process-oriented collision detection algorithm for resources composition exclusion. Experimental results showed that the algorithm could effectively detect the resource collision caused due to resource exclusion relations in process-oriented resource composition process.

Cloud manufacturing Business process Resources composition Collision detection

2014-10-16。福建省自然科學(xué)基金項目(2012J012 72);廈門市科技計劃項目(3502z20110013);泉州市科技計劃項目(2011G5);華僑大學(xué)中央高校基本科研業(yè)務(wù)費項目(JB-ZR1147)。孟慶豐，碩士生，主研領(lǐng)域：服務(wù)計算與云計算。李海波，副教授。

TP391

A

10.3969/j.issn.1000-386x.2016.04.006