協(xié)同設計中基于混合Petri網(wǎng)的云工作流表示模型

焦合軍， 張 璟， 李軍懷， 施進發(fā)， 李 建

1.西安理工大學計算機科學與工程學院，西安710048

2.鄭州航空工業(yè)管理學院管理科學與工程學院，鄭州450015

3.河南工程學院計算機學院，鄭州451191

4.西安理工大學機械與精密儀器工程學院，西安710048

工作流是多個參與者利用預定義的規(guī)則實現(xiàn)預期業(yè)務目標的過程.從云計算服務提供者的角度看，工作流提供了任務的自動調(diào)度、資源的優(yōu)化和管理，從而優(yōu)化云計算的運行服務.云工作流是工作流管理系統(tǒng)(workf low management system,WfMS)在云環(huán)境下的一種新的應用模式，就用戶而言，云工作流能提供對復雜應用的抽象定義、靈活配置和自動化運行；就云服務提供商而言，云工作流能提供任務的自動調(diào)度、資源的管理和優(yōu)化.云工作流的研究與應用正是在這種供求雙方的雙重推動下產(chǎn)生并發(fā)展起來的.

Petri網(wǎng)模型是一個基于圖的數(shù)學形式化描述模型，可以描述并發(fā)系統(tǒng).Petri網(wǎng)可以動態(tài)地表現(xiàn)一個系統(tǒng)，對活動的即時監(jiān)控以及沖突和同步現(xiàn)象的描述非常有效，特別是在圖形表達的直觀性和易于編程方面優(yōu)勢明顯，適合云工作流的建模需求.目前關(guān)于協(xié)同設計的工作流研究很多，文獻[1]以專家系統(tǒng)的推論引擎作為工作流程管理系統(tǒng)的推進機制，提出了一種支持協(xié)同產(chǎn)品設計的以規(guī)則為基礎的工作流管理系統(tǒng)模型架構(gòu)；文獻[2]對云制造環(huán)境下協(xié)同工作流采用狀態(tài)機建模，構(gòu)造一種基于分層有限狀態(tài)自動機(hierarchical f inite state machine,HFSM)的協(xié)同工作流控制模型；文獻[3]提出了一種基于代理的云工作流執(zhí)行方案，定義了規(guī)范的模擬云資源部署的方法.雖然上述研究都注意到模型的復雜性,在某個方面對工作流程進行分解，但并不能充分表達產(chǎn)品協(xié)同設計工作流模型的特點.本文在前人的研究成果基礎上，基于有色Petri網(wǎng)并結(jié)合定時約束和組合性，建立了一種在空間上三維分布的協(xié)同設計工作流模型，然后進行定量分析、評估以及優(yōu)化，使創(chuàng)建的云工作流規(guī)范化、常態(tài)化.

1 產(chǎn)品協(xié)同設計云工作流建模分析

產(chǎn)品協(xié)同設計在業(yè)務邏輯關(guān)系和數(shù)據(jù)結(jié)構(gòu)上體現(xiàn)出了自身的復雜性，目前協(xié)同設計不再局限于車間和組織內(nèi)，更多的是跨地域、跨行業(yè)和跨組織的，這又體現(xiàn)出了執(zhí)行環(huán)境的復雜性.云工作流技術(shù)是實現(xiàn)協(xié)同設計流程建模、流程管理以及流程自動化的核心技術(shù)，如果要高效地執(zhí)行這些協(xié)同設計流程，就需要工作流技術(shù)的支持.

從建模的角度來看，設計人員必須相互協(xié)作和支持，減少摩擦和沖突，利用異構(gòu)資源和分布式技術(shù)完成工作流.在云計算環(huán)境下，傳統(tǒng)模式的工作流不能很好地滿足云計算模式需求[4]，具體表現(xiàn)如下：

1)多用戶并發(fā)性：在CSCW中云工作流的執(zhí)行涉及多個用戶，其任務單元可以在一定約束條件下并發(fā)運行，此時要充分利用協(xié)同機制來避免資源爭用和死鎖的發(fā)生.

2)可伸縮性：云工作流可實現(xiàn)底層計算資源自配置，即根據(jù)執(zhí)行情況增加或減少可用節(jié)點數(shù)目，在保證任務調(diào)度的前提下控制成本.服務的底層資源可以根據(jù)業(yè)務需求實時伸縮，達到資源的有效利用.

3)可協(xié)同性：云工作流執(zhí)行時，每個用戶必須保持協(xié)同，這樣才能保證各個項目分解的任務能有序執(zhí)行，通過既相互獨立又相互配合的多個設計團隊或組織可以協(xié)同實現(xiàn).一般的工作流雖然可以滿足項目管理的部分特性，但是任務的定時約束不能很好地描述出來.定時約束描述序列任務之間的時間約束關(guān)系，一個項目由多個任務[s1,s2,···,sn]構(gòu)成，每個任務si都由事件A界定，如任務的開始事件和完成事件，結(jié)束一個任務所需要的時間有兩部分：執(zhí)行時間e和等待時間w.任務間的約束是指某一任務的事件AS對另一個子任務的事件AT的時間約束，它來源于任務的時序控制，分別有時間上限約束u(AS,AT)和時間下限約束l(AS,AT).如果事件AS的結(jié)束事件發(fā)生在t0時刻，那么事件AT的開始事件發(fā)生在[t0+l,t0+u].

4)動態(tài)性：考慮到負載均衡，工作流的組成單元和行為控制可以在運行時動態(tài)調(diào)整.

5)組合性：云計算環(huán)境下的產(chǎn)品設計過程由概念設計、方案設計、技術(shù)設計構(gòu)成.由于產(chǎn)品設計比較復雜，單一的組織或團隊不能完成，這就需要分工完成，讓不同的組織或團隊承擔不同的設計任務，體現(xiàn)了云工作流的組合性.

綜合以上云工作流建模分析可以看出，云工作流不僅僅是傳統(tǒng)工作流技術(shù)在云計算環(huán)境中的應用，作為新型的先進設計模式，它必須具有并發(fā)、敏捷、組合和全方位的典型特征，要求有更靈活、更高效以及多層次的云工作流模型，以實現(xiàn)云環(huán)境下的協(xié)同工作流管理.

2 某系列汽車傳動系協(xié)同設計云工作流建模

2.1 混合Petri網(wǎng)

傳統(tǒng)的Petri網(wǎng)是一個雙重有向圖，可以描述異步且并發(fā)的計算機系統(tǒng)模型，具有模擬性、流動性和同步并發(fā)性.基于傳統(tǒng)Petri網(wǎng)的模型在過程描述中應用廣泛，但大多數(shù)側(cè)重模擬控制流，對于可伸縮性、協(xié)同性的云工作流描述能力有限，無法表示數(shù)據(jù)的傳遞方式以及類型，對于角色和數(shù)據(jù)的表達也很缺乏.

由于傳統(tǒng)Petri網(wǎng)的局限性，本文提出了將顏色、定時約束、組合進行擴展的混合Petri網(wǎng)(hybrid Petri nets)作為云工作流建模和分析的有效工具.顏色說明事物的屬性以區(qū)分不同的令牌(token)，為了描述數(shù)據(jù)流和任務，將各類數(shù)據(jù)和任務映射為令牌類型.令牌類型的多樣性使云工作流受關(guān)注的不僅僅是令牌的數(shù)目，連接庫所和變遷的有向弧也可以進行相應的擴展.令牌的值需要設置前置條件，變遷只能在其輸入庫所中至少有一個標記而且滿足前置條件時才能就緒.這樣在描述非常復雜的協(xié)同設計過程時,建模會產(chǎn)生一個無所不包的大網(wǎng).因此，考慮將基本Petri網(wǎng)的五元組在面向云工作流的數(shù)據(jù)和任務方面進行相應擴充.

混合Petri網(wǎng)中的令牌可以帶有數(shù)據(jù)值的含義，即顏色類.該數(shù)據(jù)值可以是任意復雜類型的數(shù)據(jù)，對于某一個特定的令牌來說，它包含的所有顏色被稱為庫所的顏色集.一個庫所上可能包含兩個或兩個以上不同數(shù)據(jù)值的令牌，即為多重集.變遷用來描述任務或動作，其輸入弧表示變遷將從相應的庫所移走令牌，輸出弧表示變遷將增加令牌到相應的庫所，即?t∈T，?pin∈Pin，變遷h的執(zhí)行需要輸入pin，當且僅當pin?·t；?t∈T，pout∈Pout，變遷t的執(zhí)行產(chǎn)生輸出pout當且僅當pout?t·.

2.2 基于HPN的云工作流建模

HPSim仿真軟件具有方便的圖形用戶界面，可以對HPN網(wǎng)模型進行單步或連續(xù)的模擬運行.本文采用HPSim對某系列汽車底盤傳動系云工作流模型進行建模仿真.

2.2.1 傳動系云工作流模型

為在HPSim下對某系列汽車協(xié)同設計工作流模型建立的傳動系模型如圖1所示.在Begin庫所中含有3個令牌，分別定義一個值，例如第2個令牌的值定義包含文檔號、運行環(huán)境、狀態(tài)及內(nèi)容.SF表示設計分解，分解為總體設計ZS和詳細設計XXS.之后ZS和XXS并行進行，在下一個庫所之前如果延遲在時間上限約束tu(XXS/ZY,XCG)和時間下限約束tl(XXS/ZY,XCG)之間，系統(tǒng)運行正常；如果計時在時間上限約束tu(XXS/ZY,XCG)和時間下限約束tl(XXS/ZY,XCG)之外，系統(tǒng)會產(chǎn)生報警信號.XT0和XT表示協(xié)同設計，云工作流Cloud W負責管理和分配虛擬資源，對于詳細設計還需要活動變遷GT和調(diào)度的資源庫所ZY，接著將方案設計信息分別授權(quán)給初始詳細設計XCG和初始總體設計ZCG.評審人員ZJ在此基礎上可進一步進行評估，不合格的通過重新設計變遷T12從頭開始.任務CS1、CS2、CS3分別完成傳動系不同部件的驗收工作，考慮到提高資源的利用效率，建模時采用了并行處理.因為它們是相互獨立的，所以可以并行執(zhí)行，這樣可以在很大程度上縮短完成時間.對于設計結(jié)果需要修改的情況，分別發(fā)送給維修人員組合WHZ1、WHZ2和WHZ3，經(jīng)過驗收和維護WH，得到最終的CAPP結(jié)果，Re為下一次設計變遷，通過它可以進行其他零部件的協(xié)同設計.

圖1 某系列汽車傳動系混合Petri模型Figur e 1 Hybrid Petri model about a certain type of automobile power-transmission system

2.2.2 傳動軸協(xié)同模型

傳動軸是汽車傳動系中傳遞動力的重要部件.本文將設計任務SR分解為軸管設計AeTB、伸縮套設計SJS和萬向節(jié)設計Cp TJ，設計完成后分別發(fā)送給設計校驗JyFF，之后再審核CCSH，經(jīng)過延時完成后，本次的輸入、輸出庫所對應于圖1中的XT替代變遷.具體模型見圖2，SR代表任務開始，RW1、RW2、PRW3為分解的部分任務，JyY1、JyY2、JyY3表示校驗員，P7為審核員，XXS1、XXS2、XXS3為協(xié)同完成的部分結(jié)果.

圖2 傳動軸設計模型Figur e 2 Shaft design model

2.2.3 半軸協(xié)同模型

全浮式半軸的任務相對簡單一些，如圖3所示.繼續(xù)將其分解為半軸AxSH設計和半軸套管ASSL設計，之后經(jīng)過內(nèi)部裝配協(xié)商ICoN和熱處理工藝設計THP，在一定的定時約束完成全浮式半軸的設計.裝配設計和后續(xù)的驗收維護都可以根據(jù)實際的任務和人員分配情況進行建模，從而完成整個傳動系的協(xié)同設計過程模型.其中，SS、SF1、SF3、ZPY1、ZPY2、P5、P6均為下一個活動變遷的執(zhí)行庫所.

圖3 半軸設計模型Figure 3 Half shaft design model

2.3 傳動系性能指標定量描述

為了定量描述系統(tǒng)的性能，可以利用馬爾科夫過程對隨機Petri網(wǎng)進行定量分析，每一個變遷關(guān)聯(lián)一個實施速率，每個實施速率λi服從一定的概率分布，得到的模型就是隨機Petri網(wǎng)[5].一個SPN同構(gòu)于一個連續(xù)時間馬爾科夫鏈(Markov chain,MC)[6]，如圖4所示.λi可以表示成變遷實施延時的倒數(shù).在一個連續(xù)時間隨機Petri網(wǎng)中，變遷的實施存在時間延時，這個延時可以看成是一個服從于負指數(shù)分布的連續(xù)隨機變量.對任意一個隨機Petri網(wǎng)，利用式(1)可以得到轉(zhuǎn)移矩陣Q=[qij]n×n

圖4 同構(gòu)的馬爾科夫鏈Figure 4 Homogeneous Markov chain

設MC中n個狀態(tài)的穩(wěn)定狀態(tài)概率是一個行向量X={x1,x2,···,xn}，則根據(jù)馬爾科夫鏈可得

求解式(2)可以得到每個可達標識穩(wěn)定概率P[Mi]=xi(n≥xi≥1).

穩(wěn)態(tài)下每個庫所中所包含的標記數(shù)量的概率為標記概率密度，對?s∈S，?i∈N，令P[M(s)=i]表示位置s中包含i個標記的概率，則可從標識的穩(wěn)定概率求得位置s的標記概率密度函數(shù)

式中，Mj∈[M0且Mj=i.

變遷的利用率是使變遷可實施的所有標識的穩(wěn)定概率之和.設U(t)為?h∈T的利用率，使得h為可實施的所有標識的穩(wěn)定狀態(tài)之和

式中，E為使h可實施的所有可達標識集合.

3 模型性能分析

各變遷的時間變量體現(xiàn)的是輸入庫所從可實施到實施的時間延時，該變量服從負指數(shù)分布.本文結(jié)合定時約束，設定給出變遷SF、XT0、GT、XT、JL、T12、BM、CS1、CS2、CS3、WH、Re的平均發(fā)生時延為t1、t2、t3、t4、t5、t6、t7、t8、t9、t10、t11、t12，如表1所示.由此可以得到各個變遷的平均發(fā)生率，即每個平均發(fā)生時延的倒數(shù)，分別表示為λ1、λ2、λ3、λ4、λ5、λ6、λ7、λ8、λ9、λ10、λ11、λ12，根據(jù)方程組可以求出各個狀態(tài)標識的穩(wěn)態(tài)概率，如表2所示.根據(jù)式(3)計算各庫所標記概率密度，從庫所概率密度的數(shù)據(jù)中可以看出，庫所XXS、ZCG及ZS的概率較大，于是可將上述業(yè)務單元作為進一步優(yōu)化的重點.

表1 變遷發(fā)生時延Table 1 Time delay of transitions

表2 各狀態(tài)標識的穩(wěn)態(tài)概率Table 2 Steady-state probability of status identif ication

由式(4)可計算變遷利用率，得到的計算結(jié)果見表3.變遷的標記流速是指單位時間內(nèi)流入該變遷y的后置位置s的平均標記數(shù)，其計算公式為

式中，λ為變遷y的平均實施速率.表4給出了變遷標記流速的計算結(jié)果.

表3 變遷利用率計算結(jié)果Table 3 Transitions utilization

表4 變遷標記流速計算結(jié)果Table 4 Tag velocity of transitions

4 云工作流模型評價及優(yōu)化

在HPSim中根據(jù)初始狀態(tài)對云工作流模型進行仿真，從圖5中可以清楚地看到令牌從初始狀態(tài)順利到達最終狀態(tài)[7-8]，這說明建立的模型是可達的.

根據(jù)第3節(jié)性能分析的結(jié)果可以看出，庫所XXS、ZCG、ZY和ZS的概率密度較大，即協(xié)同設計的詳細設計、總體設計、初始總體設計及云資源庫所等任務的調(diào)度環(huán)節(jié)最容易產(chǎn)生信息的堆積.因此，在實際協(xié)同設計中，可將上述任務單元作為優(yōu)化的重點；從變遷利用率來看，變遷XT0、XT、SF和JL的觸發(fā)情況對于整個協(xié)同設計有著非常重要的影響，會直接影響到專家評估及后面的編碼和驗收任務執(zhí)行概率，直至最終影響整個協(xié)同設計業(yè)務流程的工作效率.該Petri網(wǎng)模型可以進一步從業(yè)務沖突和模型分解兩方面入手進行優(yōu)化[9-11].

在基于定時約束Petri網(wǎng)的產(chǎn)品協(xié)同設計模型中，當兩個或多個業(yè)務產(chǎn)生自由選擇的設計結(jié)果時，其中一個變遷的實施阻止另一個變遷的發(fā)生就會導致沖突.在對某系列汽車傳動系產(chǎn)品協(xié)同設計模型的仿真過程中，在業(yè)務ZJ處有發(fā)生沖突的潛在性，也就是說協(xié)同設計模型需要考慮專家評估情況.從整個過程來看，由于協(xié)同設計是個復雜的工程，錯誤的設計結(jié)果會導致部分業(yè)務的迭代或重復設計，這也是可以理解的.為了避免模型中的沖突，讓每一個業(yè)務都能找到適合自己的路徑到達終點，需要將變遷T12細化到圖5陰影部分的每個變遷中.

圖5 HPSim運行結(jié)果Figure 5 Run results of HPSim

在實際的協(xié)同設計過程中，可以將業(yè)務集中的或相似的劃分為一個子系統(tǒng)，從而使設計過程有條理.在Petri模型中，將圖5的陰影部分作為一個子系統(tǒng)，由平均標記流速計算公式得到，R(SF)=R(SF,XXS)+R(SF,ZS)，這樣流入子系統(tǒng)的平均標記流速為R(SF)，其值在表4中有體現(xiàn).比較所有變遷的標記流速不難發(fā)現(xiàn)，整個協(xié)同設計過程中大部分流速快的變遷都發(fā)生在這個子系統(tǒng)內(nèi)，尤其是GT變遷，這就要求充分調(diào)動總體和詳細設計可調(diào)動的閑置資源，將其放在云平臺中供工作流調(diào)度，從而降低庫所XXS、ZCG、ZY和ZS的概率密度.另外，在變遷XT0和XT之間減少調(diào)度時間，必要時可以通過增減變遷的方法來緩解子系統(tǒng)的擁堵.

5 結(jié)語

本文提出了一種基于定時約束Petri網(wǎng)的協(xié)同設計云工作流建模方法.首先從組合性、并發(fā)性和協(xié)同性等五方面分析產(chǎn)品協(xié)同設計過程的特點；然后建立了一個在空間上以定時約束、有色和組合三維分布的多層次模型.本文通過庫所概率密度、變遷利用率和變遷標記流速，對協(xié)同設計各流程流轉(zhuǎn)、工作效率等進行分析，并從業(yè)務沖突及模型分解等方面驗證模型的可達性，從而進行了優(yōu)化.

[1]王浩，武凌.基于專家系統(tǒng)的協(xié)同設計工作流管理系統(tǒng)研究[J].計算機工程與科學，2012,34(12):183-188.

WANGHao,WU Ling.Research of collaborative design workf low management system based on expert system[J].Computer Engineering&Science,2012,34(12):183-188.(in Chinese)

[2]譚貌，段斌，彭邦倫，張建和.云制造環(huán)境下協(xié)同工作流控制模型研究[J].計算機工程，2012,24(3):21-26.

TANMao,DUANBin,PENGBanglun,ZHANGJianhe.Research on control model of collaborative workf low in cloud manufacturing environment[J].Computer Engineering,2012,24(3):21-26.(in Chinese)

[3]GUTIERREZ-GARCIA J O,MIM K W.Agengt-based cloud workf low execution[J].Integrated Computer-Aided Engineering,2012,(19):39-56.

[4]柴學智，曹健.面向云計算的工作流技術(shù)[J].小型微型計算機系統(tǒng)，2012,33(1):90-95.

CHAI Xuezhi,CAO Jian.Cloud computing oriented workf low technology[J].Journal of Chinese Computer Systems,2012,33(1):90-95.(in Chinese)

[5]潘隆濤，涂海寧.基于隨機Petri網(wǎng)的連續(xù)型制造系統(tǒng)建模與性能分析[J].組合機床與自動化加工技術(shù)，2013,(9):25-27.

PANLongtao,TUHaining.Modeling and analysis on continuous manufacture system based on stochastic Petri net[J].Modular Machine Tool&Automatic Manufacturing Technique,2013(9):25-27.(in Chinese)

[6]林闖．隨機Petri網(wǎng)和系統(tǒng)性能評價[M].第2版.北京：清華大學出版社，2005．

[7]TOLOSANA-CALASANZ R,JOSéáB,CONGDUC P,OMERF R.Enforcing QoSin scientif ic workf low systems enacted over cloud infrastructures[J].Journal of Computer and System Sciences,2012,78(4):1300-1315.

[8]LIU Xiao,YANG Yun,YUAN Dong,ZHANG Gaofeng,LIWenhao,CAODahai.A generic QoSframework for cloud workf low systems[C]//2011 IEEE Ninth International Conference on Dependable,Autonomic and Secure Computing,2011:713-720.

[9]JENS-S?NKE V,GIDEON J,EwA D,MATS R,BERRIMAN G B.Experiences using cloud computing for a scientif ic workf low application[C]//Science Cloud'11 Proceedings of the 2nd international Workshop on Scientif ic Cloud Computing,2011:15-24.

[10]WU Zhangjun,LIU Xiao,NI Zhiwei,YUAN Dong,YANG Yun.A market-oriented hierarchical scheduling strategy in cloud workf low systems[J].Journal of Supercomputing,2013,63(1):256-293.

[11]SOFIANE B,THOMAS W.Cloud transition: integrating cloud calls into workf low petri nets[C]//Proceeding of Petri Nets and Software Engineering,2012:215-216.