郝穎,封雪，于世東

（營口理工學(xué)院電氣工程系，營口115000）

基于Petri網(wǎng)的網(wǎng)上購書流程建模

郝穎,封雪，于世東

（營口理工學(xué)院電氣工程系，營口115000）

Petri網(wǎng)是一種系統(tǒng)模擬和分析的有力工具，工作流網(wǎng)是基于Petri網(wǎng)對業(yè)務(wù)流程的形式化描述。首先介紹Petri網(wǎng)和工作流網(wǎng)的基本概念，接著介紹基于Petri網(wǎng)的工作流建模技術(shù)，然后給出網(wǎng)上購書流程的Petri網(wǎng)模型，最后使用工作流網(wǎng)分析工具WoPeD對建立的Petri網(wǎng)工作流模型的正確性進(jìn)行分析。

0 引言

工作流通常與業(yè)務(wù)流程重組相關(guān)，它涉及到工作流的建模、評估、合理性分析、執(zhí)行等相關(guān)的研究[1]。工作流管理聯(lián)盟給出的工作流定義是：工作流是一類能夠完全或者部分自動(dòng)執(zhí)行的經(jīng)營過程，它根據(jù)一系列過程規(guī)則，文檔、信息或任務(wù)能夠在不同的執(zhí)行者之間進(jìn)行傳遞與執(zhí)行[2]。

工作流建模就是將業(yè)務(wù)流程及各流程之間的業(yè)務(wù)規(guī)則抽象出來，并用一種形式化的、計(jì)算機(jī)可處理的方式來表示，這種形式化的結(jié)果就稱為工作流模型。工作流模型必須包含執(zhí)行工作流過程時(shí)所需要的全部信息，包括工作流的所有活動(dòng)間執(zhí)行的依賴關(guān)系，順序、循環(huán)、判斷條件，以及資源約束條件[3]。

目前，對工作流模型描述和分析方法的研究正日益受到人們的重視。工作流建模方法主要有以下三種類型（1）基于通信的方法；（2）基于活動(dòng)的方法；（3）基于Petri網(wǎng)的方法[4]。其中,基于Petri網(wǎng)的方法對工作流建模被廣泛接受，主要有以下原因[5-9]：（1）Petri網(wǎng)具有很強(qiáng)的表達(dá)能力，能夠描述工作流建模過程中涉及到的各種語義。Petri網(wǎng)能夠以圖形化的方式描述工作流過程。（2）Petri網(wǎng)建模方法是基于狀態(tài)的，它能描述一個(gè)任務(wù)是處于何種狀態(tài)（enabling、execution）。（3）高級Petri網(wǎng)可以進(jìn)行層次化的建模，有利于對各層次模型獨(dú)立的進(jìn)行正確性驗(yàn)證。（4）Petri網(wǎng)具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，可以有效地分析模型的各種特性：有界性、活性、安全性、不變量等。

本文首先介紹了Petri網(wǎng)和工作流網(wǎng)的基本概念，描述了基于Petri網(wǎng)建立工作流模型的方法，并使用Petri網(wǎng)建立網(wǎng)上購書流程的模型。最后，使用工作流網(wǎng)的建模、模擬和分析工具WoPeD（Workflow Petri Net Designer）對網(wǎng)上購書業(yè)務(wù)流程的Petri網(wǎng)模型進(jìn)行正確性分析。

1 Petri網(wǎng)的基本概念

1962年德國學(xué)者C.A.Petri在他的博士論文《用自動(dòng)機(jī)通信》中首次使用網(wǎng)狀結(jié)構(gòu)模擬通信系統(tǒng)，系統(tǒng)模型就是Petri網(wǎng)的雛形。經(jīng)過多年的發(fā)展，Petri網(wǎng)已經(jīng)成為計(jì)算機(jī)異步成分之間進(jìn)行通信的理論基礎(chǔ)，是描述具有分布、并發(fā)、異步特征系統(tǒng)的有效工具[10]。

Petri網(wǎng)定義為四元組PN=（P，T，F(xiàn)，M0），其中：P是庫所的有限集合，T是變遷的有限集合，F(xiàn)是有向弧的集合，M0是初始標(biāo)識。其充分必要條件是（1）P∩T=Φ；（2）P∪T≠Φ；（3）F?（P×T）∪（T×P）[5]。

Petri網(wǎng)=（P,T,F,M0）稱作工作流網(wǎng)，當(dāng)且僅當(dāng)（1）PN有一個(gè)起始庫所i∈P，使得i=Φ；（2）PN有一個(gè)終止庫所o∈P，使得o·=Φ；（3）如果給PN增加一個(gè)變遷t*，該變遷連接起始庫所i和終止庫所o，其中o作為變遷t*的輸入，i作為變遷t*的輸出（即t*={o}并且t*={i}），則Petri網(wǎng)結(jié)構(gòu)是強(qiáng)連通的。工作流網(wǎng)描述的是一個(gè)過程實(shí)例的生命周期，必須具有一個(gè)起始庫所i和一個(gè)終止庫所o。進(jìn)入起始庫所i的標(biāo)記代表著一個(gè)過程實(shí)例的開始，而進(jìn)入終止庫所o的標(biāo)記則意味著一個(gè)過程實(shí)例的結(jié)束[11-13]。

2 基于Petri網(wǎng)的工作流建模方法

工作流是對業(yè)務(wù)過程的形式化描述，使用Petri對工作流建模比較直觀。工作流過程是任務(wù)的偏序集合，工作流中的任務(wù)用Petri網(wǎng)中的變遷表示，優(yōu)先關(guān)系用庫所表示，工作流實(shí)例用token表示，token的流動(dòng)表示工作流的執(zhí)行。

工作流管理聯(lián)盟定義了四種基本的工作流路由結(jié)構(gòu)[5]：

（1）順序路由。表示兩個(gè)或多個(gè)任務(wù)之間按先后順序執(zhí)行。如圖1所示，先執(zhí)行t1，后執(zhí)行t2。

（2）并行路由。表示并行的兩個(gè)或多個(gè)任務(wù)之間可以按任意順序執(zhí)行。如圖2所示，t1執(zhí)行后，按任意順序執(zhí)行t2，t3或同時(shí)執(zhí)行t2，t3。

（3）選擇路由。表示在流程的某一點(diǎn)，依執(zhí)行結(jié)果判斷選擇哪一條路徑繼續(xù)執(zhí)行。如圖3所示，t1執(zhí)行后，執(zhí)行t2或t3其中之一。

（4）循環(huán)路由。表示某一個(gè)或多個(gè)任務(wù)可能需要重復(fù)執(zhí)行多次。如圖4所示，t1,t2可能會(huì)重復(fù)執(zhí)行多次。

圖1 順序路由

圖2 并行路由

圖3 選擇路由

圖4 循環(huán)路由

3 網(wǎng)上購書流程的Petri網(wǎng)模型

網(wǎng)上購書流程描述如下：用戶登錄購書網(wǎng)站，填寫購書信息，查詢該書的剩余數(shù)量。系統(tǒng)檢查庫存中是否有此書，用戶根據(jù)系統(tǒng)的提示是否有書信息來選擇提交訂單或取消購書操作。用戶提交訂單后，系統(tǒng)會(huì)提示用戶確認(rèn)訂單及地址等信息，如果用戶核查無誤則進(jìn)入付款操作，系統(tǒng)收到返回支付信息，用戶購書成功。

圖5是網(wǎng)上購書流程的Petri網(wǎng)模型，其中變遷的含義如下：t1：用戶登錄；t2：系統(tǒng)驗(yàn)證用戶的身份是否正確；t3：通過驗(yàn)證，用戶填寫購書信息；t4：未通過驗(yàn)證，用戶選擇重新登錄或結(jié)束購書操作；t5：請求查詢書的剩余數(shù)量；t6：核查是否有此書；t7：調(diào)用此書訂單；t8：庫存中無此書操作結(jié)束；t9：用戶填寫訂單表；t10：系統(tǒng)核對訂單表信息；t11：信息正確，用戶付費(fèi)；t12：信息錯(cuò)誤，重填訂單；t13是否付費(fèi)；t14：已付費(fèi)，購書成功；t15：未付費(fèi)，結(jié)束操作或重新要求用戶付費(fèi)。

網(wǎng)上購書流程的Petri網(wǎng)模型采用了順序路由，選擇路由，循環(huán)路由三種結(jié)構(gòu)實(shí)現(xiàn)了對購書流程中一些異常情況的處理方法。：（1）用戶身份驗(yàn)證失敗，系統(tǒng)可以結(jié)束操作或提示用戶重新登錄；（2）當(dāng)系統(tǒng)查不到用戶所要購買的書時(shí)，系統(tǒng)結(jié)束操作。（3）用戶填寫訂單出錯(cuò)時(shí)，系統(tǒng)結(jié)束操作或要求用戶重新修改訂單。（4）用戶未付款時(shí)，系統(tǒng)結(jié)束操作或要求用戶付款。在上述各種情況中也可以把變遷加入時(shí)間觸發(fā)機(jī)制。在一定的時(shí)間內(nèi)，用戶未操作，則系統(tǒng)結(jié)束操作。

4 網(wǎng)上購書模型的正確性驗(yàn)證

一個(gè)工作流網(wǎng)是正確的當(dāng)且僅當(dāng)[14]：（1）對起始庫所i可達(dá)的任意狀態(tài)M，都存在一個(gè)觸發(fā)序列可以從狀態(tài)M到終止庫所o。（2）庫所o是唯一的終止庫所，當(dāng)一個(gè)工作流實(shí)例運(yùn)行結(jié)束時(shí)，只有庫所o中有且僅有一個(gè)token，其它庫所均為空。（3）Petri網(wǎng)中沒有死變遷，也就是說任意一個(gè)變遷都可被執(zhí)行，Petri網(wǎng)是活的。正確性表明i到o的所有路徑中，每個(gè)變遷都觸發(fā)過，每個(gè)庫所都經(jīng)歷過，正確性描述的是工作流網(wǎng)的動(dòng)態(tài)特性。

圖5 網(wǎng)上購書流程的Petri網(wǎng)模型

WoPeD[15]是基于Java的開源軟件，由德國卡爾斯魯厄大學(xué)開發(fā)，WoPeD的生成文件是PNML格式的，是一種可以對工作流網(wǎng)描述的過程進(jìn)行建模，模擬和分析的簡單易用的軟件。WoPeD可以執(zhí)行在任何支持Java的系統(tǒng)上。WoPeD[16]提供Petri網(wǎng)和工作流網(wǎng)的圖形化界面，包括交互模擬。WoPeD支持模型驗(yàn)證和屬性的可視化，并且內(nèi)置算法可以檢測模型正確性，過程度量和定量模擬等。

本文使用WoPeD，采用可達(dá)圖的方法對圖5的網(wǎng)上購書流程的Petri網(wǎng)模型進(jìn)行正確性進(jìn)行驗(yàn)證。WoPeD用廣度優(yōu)先算法構(gòu)造可達(dá)圖，如圖6所示。

從圖6中可以觀察到狀態(tài)（0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1）是唯一沒有輸出的狀態(tài)，即該狀態(tài)只有輸入弧，沒有輸出弧，該狀態(tài)為結(jié)束狀態(tài)。圖5的Petri網(wǎng)模型中庫所p16是結(jié)束庫所，由結(jié)束狀態(tài)（0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1）可知除了庫所p16中有token之外，其他庫所中都沒有token，符合工作流網(wǎng)的正確性的定義。

5 結(jié)語

Petri網(wǎng)自提出以來，已經(jīng)發(fā)展成為一個(gè)龐大的研究領(lǐng)域。利用Petri網(wǎng)建立工作流模型，不僅能夠以圖形化的方式直觀地表現(xiàn)出流程，并且便于用戶使用流程建立工作，本文基于Petri網(wǎng)建立了網(wǎng)上購書流程的模型，并且利用Petri網(wǎng)的可達(dá)性分析技術(shù)，使用WoPeD對網(wǎng)上購書流程模型的正確性進(jìn)行分析和驗(yàn)證。

圖6 網(wǎng)上購書流程的可達(dá)圖

[1]Workflow Management Coalition.The Workflow Reference Model.Technique Report[R].WFMC-TC00-1003.Hampshire:Workflow Management Coalition,1995.

[2]范玉順.工作流管理技術(shù)基礎(chǔ)[M].北京:清華大學(xué)出版社，2001．

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

[4]孫志東.基于Petri網(wǎng)的層次遷移工作流系統(tǒng)模型研究[D].山東大學(xué)，2006.

[5]Van Der Aalst W.M.P.The Application of Petri nets to Workflow Management[J].The Journal of Circuits Systems and Computers,1998,8（1）：21-66.

[6]周福明，吳斌等.基于Petri網(wǎng)的工作流建模與正確性分析[J].計(jì)算機(jī)科學(xué)，2005，2.

[7]谷建鑫，仇建偉.基于Petri網(wǎng)的工作流模型[J].計(jì)算機(jī)工程與設(shè)計(jì)，2005，2.

[8]陳慧靈等.基于Petri網(wǎng)的工作流過程建模[J].計(jì)算機(jī)工程與科學(xué)，2008，5.

[9]張信一，黎燕.基于Petri網(wǎng)的工作流建模[J].微機(jī)發(fā)展，2003，6.

[10]袁崇義.Petri網(wǎng)原理[M].北京：電子工業(yè)出版社，1997.

[11]楊雯，劉厚泉.基于Petri網(wǎng)的工作流模型的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，9.

[12]W.M.P.van der Aalst.Verification of Workflow Nets.In P.Azéma and G.Balbo,Editors,Application and Theory of Petri Nets 1997,Volume 1248 of Lecture Notes in Computer Science,pages 407-426.Springer-Verlag,Berlin,1997.

[13]胡堅(jiān)，宋斌恒.一個(gè)基于AOP技術(shù)的工作流異常處理策略[J].微計(jì)算機(jī)信息，2005.

[14]何路路，方歡.基于Petri網(wǎng)的保險(xiǎn)工作流系統(tǒng)建模及驗(yàn)證[J].牡丹江師范學(xué)院學(xué)報(bào),2016,1.

[15]The WoPeD project homepage.http:///www.woped.org.

[16]Thomas Freytag,Martin Sanger.WoPeD-An Educational Tool for Workflow Nets.In:Proceedings of the BPM Demo Sessions,Eindhoven,September 2014：31-35.

A Workflow Model for Purchase Books Online Based on Petri Net

HAO Ying，F(xiàn)ENG Xue，YU Shi-dong

（Yingkou Institute of Technology,Yingkou 115000）

Petri net is a powerful tool for system simulation and analysis.Workflow is a formal description of the business process based on Petri net.Firstly introduces the basic concept of Petri net and workflow net,then introduces the workflow model technique based on Petri net,takes the Petri net model of online purchase books as an example,uses the workflow Petri net Designer Tool WoPeD to analyze the correctness of the model.

1007-1423（2017）27-0073-04

10.3969/j.issn.1007-1423.2017.27.016

Petri網(wǎng)；工作流；網(wǎng)上購書

郝穎（1984-），女，遼寧鞍山人，碩士，講師，研究方向?yàn)樾问交?yàn)證、軟件工程

封雪（1984-），女，遼寧營口人，碩士，講師，研究方向?yàn)橛?jì)算幾何、機(jī)器人路徑規(guī)劃

于世東（1979-），男，遼寧東港人，碩士，副教授，研究方向?yàn)閿?shù)據(jù)可視化、數(shù)據(jù)分析、.NET開發(fā)

2017-07-18

2017-09-20

Petri net;Workflow;Online Purchase Books