基于Petri網(wǎng)的工作流過程建模和時(shí)間性能分析

肖作斌,孫　鵬,張智慧,李小春

(1.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院,陜西 西安　710077;2.北京信息職業(yè)技術(shù)學(xué)院 電子工程系,北京　100015)

?

基于Petri網(wǎng)的工作流過程建模和時(shí)間性能分析

肖作斌1,孫鵬1,張智慧2,李小春1

(1.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院,陜西 西安710077;2.北京信息職業(yè)技術(shù)學(xué)院 電子工程系,北京100015)

摘要介紹了基于Petri網(wǎng)的工作流建模技術(shù),并針對(duì)一個(gè)復(fù)雜的企業(yè)生產(chǎn)經(jīng)營(yíng)活動(dòng)的流程構(gòu)建了一個(gè)簡(jiǎn)化靈活的模型,利用隨機(jī)Petri網(wǎng)的性能分析方法對(duì)建立的模型進(jìn)行了時(shí)間性能分析。結(jié)果表明,文中的性能分析方法可對(duì)復(fù)雜的模型進(jìn)行有效地簡(jiǎn)化分析。

關(guān)鍵詞工作流;Petri網(wǎng);工作流網(wǎng);時(shí)間性能

工作流是現(xiàn)實(shí)世界的業(yè)務(wù)過程全部或部分在計(jì)算機(jī)應(yīng)用環(huán)境下自動(dòng)執(zhí)行的表示形式,其使得多個(gè)參與者之間按照預(yù)先定義的規(guī)則自動(dòng)地傳遞文檔、信息或任務(wù),從而促使總體業(yè)務(wù)目標(biāo)得以實(shí)現(xiàn)。而工作流模型的建立是工作流執(zhí)行的前提和基礎(chǔ),工作流建模的目的就是將業(yè)務(wù)流程形式化,便于其在計(jì)算機(jī)上進(jìn)行分析和處理。

目前國(guó)內(nèi)外學(xué)者提出了各種各樣的工作流建模方法[1],其中基于Petri網(wǎng)的建模技術(shù)具有直觀的圖形表示、形式化的語義、狀態(tài)和事件的顯示表示以及豐富的數(shù)學(xué)分析技術(shù)等特點(diǎn),能夠滿足工作流模型的建模需求,現(xiàn)有的基于Petri網(wǎng)工作流建模方法有很多,如時(shí)間、著色、分層等[2-4]方法。在此基礎(chǔ)上,研究人員針對(duì)工作流模型的性能評(píng)價(jià)技術(shù)也開展了相關(guān)研究,如采用擴(kuò)展的時(shí)間Petri網(wǎng)模型來進(jìn)行工作流模型的時(shí)間性能計(jì)算和分析[5];通過線性推理來估計(jì)時(shí)間性能的上下界[6];運(yùn)用遍歷網(wǎng)中所有路徑的方法來計(jì)算時(shí)間性能[7]等。

本文介紹了Petri網(wǎng)和工作流網(wǎng)的基本概念以及從Petri網(wǎng)到工作流網(wǎng)的執(zhí)行映射。為降低時(shí)間性能分析的復(fù)雜度,本文采用了隨機(jī)Petri網(wǎng)的性能分析方法對(duì)建立的模型進(jìn)行簡(jiǎn)化分析。經(jīng)實(shí)例分析,可證明該分析方法對(duì)于復(fù)雜工作流模型的時(shí)間性能分析是簡(jiǎn)便有效的。

1基于Petri網(wǎng)的工作流網(wǎng)

1.1　定義

Petri網(wǎng)最早在20世紀(jì)60年代由Carl Adam Petri提出。因其有著堅(jiān)實(shí)嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)基礎(chǔ)、完全形式化的語義、強(qiáng)大的表達(dá)能力、直觀的圖形表示等特點(diǎn),Petri網(wǎng)成為工作流建模和分析的主要工具。Petri 網(wǎng)的定義如下[8]

定義1一個(gè)四元組PN=(P,T,F,M0)是Petri網(wǎng),當(dāng)且僅當(dāng)

(1)P∩T=?

(2)P∪T≠?

(3)F?P×T∪T×P

(4)dom(F)∪cod(F)=P∪T

工作流過程的網(wǎng)模型中含有兩個(gè)特殊的庫(kù)所,其中一個(gè)表示過程的開始,另外一個(gè)表示過程的結(jié)束,在此分別稱其為開始庫(kù)所和結(jié)束庫(kù)所,用i和o表示。針對(duì)工作流網(wǎng)模型的這一特點(diǎn)對(duì)Petri網(wǎng)進(jìn)行相應(yīng)的限制就得到了工作流網(wǎng),由此工作流狀態(tài)的變化便能用工作流網(wǎng)清晰的描述出來。在Petri網(wǎng)的基礎(chǔ)上,工作流網(wǎng)的定義如下:

定義2Petri網(wǎng)系統(tǒng)PN=(P,T,F,M0)是一個(gè)工作流網(wǎng)(WF_net)[9]的充分必要條件是:

(1)存在一個(gè)源庫(kù)所i∈P,使得i=?。

(2)存在一個(gè)終止庫(kù)所o∈P,使得o=?。

(3)對(duì)于每個(gè)結(jié)點(diǎn)x∈P∪T,x都在從i到o的一條路徑上。

滿足上述條件的Petri網(wǎng)稱為一個(gè)工作流網(wǎng),記為WFN(WorkFlow Net)。

定義3一個(gè)連續(xù)時(shí)間隨機(jī)Petri網(wǎng)(SPN)是個(gè)六元組(P,T,F,W,M0,λ),其中P={p1,p2,…,pm}是庫(kù)所的非空有限集合,T={t1,t2,…,tm}是變遷的非空有限集合,W∶F→{0,1,2,…}是有向弧函數(shù),M0∶P→{0,1,2,…}是初始標(biāo)志,λ={λ1,λ2,…,λm}是變遷平均實(shí)施速率集合。

1.2　Petri網(wǎng)到工作流網(wǎng)的映射

工作流管理聯(lián)盟(WFMC)在工作流模型中定義了4種基本路由結(jié)構(gòu):順序路由、并行路由、選擇路由和循環(huán)路由,復(fù)雜的工作流模型均由這4種基本的流控制結(jié)構(gòu)復(fù)合而成。因此,在利用Petri網(wǎng)理論對(duì)工作流模型進(jìn)行建模時(shí),首先,4種基本結(jié)構(gòu)進(jìn)行Petri網(wǎng)建模,然后對(duì)復(fù)雜工作流模型的基本結(jié)構(gòu)進(jìn)行分析,最終建立基于Petri網(wǎng)的工作流模型。

在每一種路由結(jié)構(gòu)進(jìn)行建模前,首先引入4種構(gòu)造模塊,分別是:并行發(fā)散(AND_split)、同步聚合(AND_join)、選擇發(fā)散(OR_split)和選擇聚合(OR_join),其在工作流網(wǎng)基本組件中經(jīng)常出現(xiàn),因此用統(tǒng)一的符號(hào)分別表示這4種構(gòu)造模塊,如圖1所示。

圖1　工作流網(wǎng)基本組件中的構(gòu)造模塊

將4種構(gòu)造模塊應(yīng)用到路由結(jié)構(gòu)的建模中,得到工作流網(wǎng)的4種基本組件[10]:順序組件、并行組件、選擇組件以及循環(huán)組件,如圖2所示。在此,用變遷表示活動(dòng),用庫(kù)所表示狀態(tài),“○·”表示啟動(dòng)庫(kù)所,其中的“·”表示托肯。

圖2　工作流網(wǎng)的基本組件

2建模實(shí)例和模型時(shí)間性能分析

2.1　建模實(shí)例

結(jié)合一個(gè)復(fù)雜的企業(yè)生產(chǎn)經(jīng)營(yíng)活動(dòng)流程,利用基于Petri網(wǎng)的建模技術(shù)進(jìn)行建模。圖3給出了企業(yè)生產(chǎn)經(jīng)營(yíng)活動(dòng)的詳細(xì)流程,然后針對(duì)該流程建立了工作流網(wǎng)模型,如圖4所示。對(duì)于圖4中各個(gè)變遷的描述如下:t1為客戶需求,t2為審核訂單,t3為計(jì)算成本,t4為檢查庫(kù)存,t5為修改訂單,t6為確認(rèn)訂單,t7為制訂計(jì)劃,t8為自制,t9為外協(xié),t10為采購(gòu),t11為檢驗(yàn),t12為國(guó)產(chǎn),t13為進(jìn)口,t14為裝配,t15為發(fā)貨。

圖3　企業(yè)生產(chǎn)經(jīng)營(yíng)活動(dòng)流程

圖4　工作流網(wǎng)模型

2.2　模型分析

工作流系統(tǒng)的時(shí)間性能是衡量一個(gè)工作流過程優(yōu)劣的重要指標(biāo),時(shí)間性能將直接影響工作流系統(tǒng)的實(shí)際可行性。由于現(xiàn)實(shí)中多數(shù)工作流系統(tǒng)的模型變遷時(shí)延是服從指數(shù)分布函數(shù)的,所以在這里利用 隨機(jī)Petri網(wǎng)的性能分析方法對(duì)建立的模型進(jìn)行時(shí)間性能分析,其性能等價(jià)公式可對(duì)復(fù)雜的系統(tǒng)進(jìn)行性能等價(jià)化簡(jiǎn),降低分析的復(fù)雜性。下面給出工作流模型的順序、并行、選擇、循環(huán)這4種基本結(jié)構(gòu)的性能等價(jià)公式[11]。

接下來對(duì)圖4中建立的的工作流網(wǎng)模型進(jìn)行時(shí)間性能分析。表l給出了圖3中變遷的延時(shí)時(shí)間和實(shí)施概率,其中延時(shí)時(shí)間的單位為單位時(shí)間。在進(jìn)行性能分析之前先對(duì)建立的模型進(jìn)行改動(dòng)和化簡(jiǎn),由于t8和t9處都要到達(dá)庫(kù)所p9,然后也都將經(jīng)過變遷t11,所以做出改動(dòng)后如圖5所示,通過分析模型對(duì)其進(jìn)行化簡(jiǎn),得到的化簡(jiǎn)模型如圖6所示,其中變遷t2、t3、t4、t6等價(jià)化簡(jiǎn)為tA,變遷t8、t11等價(jià)化簡(jiǎn)為tB,變遷t9、t11等價(jià)化簡(jiǎn)為tC,變遷t10、t12、t13等價(jià)化簡(jiǎn)為tD,變遷t14、t15等價(jià)化簡(jiǎn)為tE。

表1　變遷的延時(shí)時(shí)間和概率分配

圖5　改動(dòng)后的工作流網(wǎng)模型

圖6　化簡(jiǎn)模型

這樣,通過使用4種結(jié)構(gòu)的性能等價(jià)公式,由內(nèi)到外、由繁至簡(jiǎn),不斷地對(duì)模型進(jìn)行等價(jià)化簡(jiǎn),最終求出了整個(gè)系統(tǒng)的性能等價(jià)時(shí)間。

3結(jié)束語

本文利用基于Petri網(wǎng)的建模技術(shù)對(duì)復(fù)雜的企業(yè)生產(chǎn)經(jīng)營(yíng)活動(dòng)流程進(jìn)行建模,構(gòu)建出一個(gè)簡(jiǎn)化模型,并應(yīng)用4種基本結(jié)構(gòu)的性能等價(jià)公式對(duì)模型進(jìn)行時(shí)間性能分析。建模與性能分析表明,基于Petri網(wǎng)的建模技術(shù)在為復(fù)雜的業(yè)務(wù)流程進(jìn)行建模時(shí)優(yōu)勢(shì)明顯,同時(shí)本文的性能分析方法在對(duì)復(fù)雜模型進(jìn)行性能分析時(shí)是簡(jiǎn)便可行的。

參考文獻(xiàn)

[1]陳廣智,潘嶸,李磊.工作流建模技術(shù)綜述及其研究趨勢(shì)[J].計(jì)算機(jī)科學(xué),2014,41(S1):11-17.

[2]傅作為,樂曉波,王慧英.加權(quán)的時(shí)間Petri 網(wǎng)工作流模型研究[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(15),55-58.

[3]龔凌玲,鐘勇.基于著色Petri網(wǎng)的工作流模型研究[J].計(jì)算機(jī)應(yīng)用,2008,28(6):291-294.

[4]Jiang Hang,Ding Xiangqian.Modeling of hierarchcal petri net-based workflow[C].Wuhan:Control and Industrial Engineering(CCIE),2011.

[5]姜浩,董逸生.一種基于擴(kuò)展時(shí)間Petri 網(wǎng)的工作流時(shí)間性能評(píng)價(jià)方法[J].計(jì)算機(jī)研究與發(fā)展,2005,42(5):849-855.

[6]劉婷,林闖,劉衛(wèi)東.基于時(shí)間Petri網(wǎng)的工作流系統(tǒng)模型的線性推理[J].電子學(xué)報(bào),2002,30(2):153-156.

[7]李建強(qiáng),范玉順.基于Petri網(wǎng)的工作流模型性能評(píng)價(jià)方法[J].計(jì)算機(jī)應(yīng)用,2001,21(6):4-6.

[8]袁崇義.Petri網(wǎng)原理與應(yīng)用[M].北京:電子工業(yè)出版社,2005.

[9]Vander Aalst W,Van Hee K.Workflow management:model,methods and system[M].Beijing:Tsinghua Press,2004.

[10]Vander Aalst WMP.The application of petri nets to workflow management[J].Journal of Circuits,Systems,and Computers,1998,8(1):22-66.

[11]林闖.隨機(jī)Petri網(wǎng)和系統(tǒng)性能評(píng)價(jià)[M].北京:清華大學(xué)出版社,2005.

Workflow Process Modeling Based on Petri Nets and Its Time Performance Analysis

XIAO Zuobin1,SUN Peng1,ZHANG Zhihui2,LI Xiaochun1

(1.School of Information and Navigation,Air Force Engineering University,Xi’an 710077,China;2.Department of Electronic Engineering,Beijing Information Technology Institute,Beijing 100015,China)

AbstractWorkflow modeling technique has been the basis for the entire business process implementation,so selecting efficient modeling techniques for achieving actual complex business processes is particularly important.The time performance evaluation is also an important aspect in the evaluation of workflow models.Firstly,the workflow modeling techniques based on Petri nets are introduced.And then a complex process of production and operation is combined to construct a simplified and flexible model.The average time performance is analyzed using the stochastic Petri net.The results show that a complex model can be analyzed effectively and simply by the proposed performance analysis method.

Keywordsworkflow;Petri net;workflow net;time performance

中圖分類號(hào)TP317.1

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1007-7820(2015)10-044-05

doi:10.16180/j.cnki.issn1007-7820.2015.10.013

作者簡(jiǎn)介:肖作斌(1990—),男,碩士研究生。研究方向:工作流管理。E-mail:xiaozuobin123@126.com

基金項(xiàng)目:中國(guó)博士后基金資助項(xiàng)目(2014M562585)

收稿日期:2015-06-03