基于Petri網(wǎng)的工作流模型的研究與仿真①

孟廣學(xué)

(華北科技學(xué)院計(jì)算機(jī)學(xué)院，北京 東燕郊 101601)

0 引言

Petri網(wǎng)主要是通過對工作流任務(wù)之間的屬性關(guān)系進(jìn)行描述建立模型的一種工具，它的優(yōu)點(diǎn)是能夠充分對并發(fā)的、離散的事件進(jìn)行動(dòng)態(tài)方面的屬性描述，通過對屬性的描述利用圖形化的工具進(jìn)行模型的建立，再結(jié)合數(shù)學(xué)的理論和定義，進(jìn)行模型算法方面的分析和評價(jià)，典型的Petri網(wǎng)具備以下特點(diǎn):首先它是一種圖形化的建模工具，具有直觀、易用的優(yōu)點(diǎn)，在資源緊張時(shí)或有沖突造成資源并發(fā)時(shí)能夠形象化地描述和化解;其次，它又具有數(shù)學(xué)化的建模描述能力，結(jié)合信息論和隨機(jī)過程論對系統(tǒng)的不確定性或隨機(jī)性進(jìn)行分析。

活動(dòng)在執(zhí)行的過程中，依據(jù)不同的執(zhí)行順序，定義四種執(zhí)行過程的基本模型［1］:

1)順序執(zhí)行也稱為串行執(zhí)行:如圖1(a)所示，多個(gè)任務(wù)分先后次序依次執(zhí)行。如有任務(wù)A和B兩個(gè)任務(wù)要執(zhí)行，A任務(wù)執(zhí)行完了再執(zhí)行B任務(wù)。

2)選擇執(zhí)行也稱為有條件的分支執(zhí)行順序:如圖1(c)所示，首先對執(zhí)行的條件進(jìn)行判斷，判斷哪個(gè)任務(wù)執(zhí)行的條件成立就執(zhí)行哪個(gè)任務(wù)，按照條件的優(yōu)先權(quán)的高低有選擇的執(zhí)行。

3)并行執(zhí)行也可稱為同時(shí)執(zhí)行順序:如圖1(b)所示，兩個(gè)任務(wù)同時(shí)執(zhí)行或以任意的順序進(jìn)行，如任務(wù)C和任務(wù)B就是并行地執(zhí)行。

4)重復(fù)執(zhí)行也可稱為循環(huán)執(zhí)行順序:如圖1(d)所示，每個(gè)任務(wù)只要條件成立，可以循環(huán)的多次執(zhí)行。

圖1 工作流四種基本模型

1 工作流模型服務(wù)時(shí)間的等價(jià)分析方法

對于一個(gè)復(fù)雜的基于Petri網(wǎng)工作流模型直接進(jìn)行等價(jià)服務(wù)時(shí)間的分析較為困難，必須依據(jù)基本的模型進(jìn)行簡化的處理，分別計(jì)算每種連接方式的等價(jià)服務(wù)時(shí)間，最后在計(jì)算整體模型的性能參數(shù)。

1.1 并聯(lián)模型的服務(wù)時(shí)間的等價(jià)分析方法［4］

性能等價(jià)服務(wù)時(shí)間的期望值為:

1.2 選擇模型的服務(wù)時(shí)間的等價(jià)分析方法［4］

1.3 串聯(lián)模型等價(jià)服務(wù)時(shí)間的分析方法［4］

下面以產(chǎn)品銷售過程為例來具體說明基于Petri網(wǎng)的工作流建模及性能分析過程。

2 模型的建立

首先這里涉及到的產(chǎn)品銷售過程的用戶需求，主要包括:

1)用戶向公司發(fā)出訂單，指出需要的計(jì)算機(jī)配置和數(shù)量，公司接收到用戶的訂單后根據(jù)用戶提出的配置要求檢查庫存及價(jià)位等信息進(jìn)行決策。

2)要對以上訂單情況進(jìn)行檢查和審核，通過審核可以接受，則執(zhí)行下一步，否則向用戶發(fā)出通知或信函，告知結(jié)果或提出修改意見，修改訂單，接著交給辦事員發(fā)出反饋意見。

3)接受訂單后一方面要通知用戶付款，另一方面要發(fā)出生產(chǎn)通知。這兩個(gè)過程是并行的過程。發(fā)出生產(chǎn)通知后要進(jìn)行裝配計(jì)算機(jī)然后發(fā)貨此時(shí)流程結(jié)束。按照需求進(jìn)行分析得出整個(gè)銷售過程的流程圖如圖2所示。

圖2 產(chǎn)品銷售過程流程圖

4)整個(gè)流程通過以下活動(dòng)完成銷售業(yè)務(wù)過程。

(1)用戶向公司發(fā)出訂單，指出需要的產(chǎn)品配置和數(shù)量，在Petri模型中用變遷t0表示。

(2)公司接收用戶訂單，在模型中用變遷t1表示。

(3)公司對用戶訂單進(jìn)行檢查，即指以下3個(gè)活動(dòng)的并發(fā)過程，可用一個(gè)瞬時(shí)變遷表示:計(jì)算價(jià)格，在模型中用變遷t2表示;檢查零部件庫存是否滿足需求，在模型中用變遷t3表示;進(jìn)行配置檢查，確認(rèn)用戶的訂單技術(shù)上是否可行，在模型中用變遷t4表示。

(4)進(jìn)行決策，在模型中用變遷t5表示。如果通過檢查，則繼續(xù)執(zhí)行;如果未通過檢查，則向用戶發(fā)出信函，解釋為什么訂單不能完成，并提出修改意見，修改訂單，在模型中用變遷t10表示，接著交給辦事員發(fā)出反饋意見，在模型中用變遷t11表示。

(5)準(zhǔn)備接收訂單的確認(rèn)通知，它就是指一方面通知用戶付款，另一方面發(fā)出生產(chǎn)通知的兩個(gè)并行過程，它本身可用一個(gè)瞬時(shí)變遷表示。通知用戶付款，在模型中用變遷t8表示。

(6)用戶接到通知，進(jìn)行付款，在模型中用變遷t9表示。

(7)發(fā)出生產(chǎn)通知，在模型中用變遷t6表示。

(8)裝配計(jì)算機(jī)，在模型中用變遷t7表示。

(9)發(fā)貨，在模型中用變遷t12表示。

針對上面實(shí)例的系統(tǒng)流程圖，在定義Petri網(wǎng)模型時(shí)，各個(gè)任務(wù)之間的先后關(guān)系用庫所節(jié)點(diǎn)p(O)來表示;用變遷節(jié)點(diǎn)t矩形(□)表示系統(tǒng)中的任務(wù);任務(wù)和工作流邏輯關(guān)聯(lián)形式用弧(⌒)表示;圓圈中帶有黑點(diǎn)(⊙)標(biāo)記的表示執(zhí)行狀態(tài)。由此對工作流進(jìn)行建模的實(shí)施過程中用到的變遷的含義定義如表1所示。

表1 產(chǎn)品銷售過程工作流Petri網(wǎng)模型中變遷的含義

在分析系統(tǒng)流程圖2的基礎(chǔ)上，結(jié)合表1的定義建立系統(tǒng)工作流的Petri網(wǎng)模型如圖3所示。其中假設(shè)接受訂單的概率為a，修改訂單的概率為1－a;當(dāng)有用戶向公司提交訂單時(shí)，首先要接受公司的審核和檢查，檢查和審核的過程設(shè)為并發(fā)的活動(dòng)，利用Petri網(wǎng)模型進(jìn)行描述時(shí)，使用一個(gè)瞬時(shí)的變遷來表示;公司對提交的訂單檢查通過后準(zhǔn)備接受訂單時(shí)也可以用一個(gè)瞬時(shí)變遷，并發(fā)處理發(fā)出生產(chǎn)通知和通知用戶付款這兩個(gè)過程。

圖3 產(chǎn)品銷售過程工作流網(wǎng)模型圖

3 模型的性能等價(jià)分析

3.1 petri網(wǎng)模型的變遷的平均延遲時(shí)間

本文研究過程中假設(shè)變遷 t0，t1，t2，t3，t4，t5，t6，t7，t8，t9，t10，t11，t12的平均延遲時(shí)間分別為:

其中延遲時(shí)間的單位為分鐘。另外，對t5的分支選擇處設(shè)接收訂單的概率α1=0.91。

3.2 性能等價(jià)計(jì)算

性能等價(jià)計(jì)算的原則是:首先由里到外，通過性能的等價(jià)變化將復(fù)雜的結(jié)構(gòu)化簡到最簡單，在簡化模型的過程中，要依據(jù)基本的四種模型進(jìn)行，首先分析模型的串聯(lián)、并聯(lián)、選擇和循環(huán)關(guān)系的基本構(gòu)成，然后根據(jù)相應(yīng)的等價(jià)公式計(jì)算出整個(gè)系統(tǒng)相關(guān)的性能參數(shù)。經(jīng)過串、并和選擇的化簡，得到如圖4所示的模型:

圖4 產(chǎn)品銷售過程最終模型簡化圖

3)最后由串聯(lián)公式(3)求出總的性能等價(jià)時(shí)間

計(jì)算出模型的性能等價(jià)時(shí)間以后，可以根據(jù)相應(yīng)的公式計(jì)算系統(tǒng)的吞吐率和平均處理的任務(wù)數(shù)等性能參數(shù)。實(shí)例系統(tǒng)的模型中只存在一個(gè)標(biāo)記，所以吞吐率是等價(jià)時(shí)間的倒數(shù)，即λ123456789101112=3.29 ×10－4(任務(wù)/每分鐘)，一天內(nèi)的平均處理任務(wù)數(shù)為24×60×3.29×10－4=0.474(個(gè))。

4 仿真分析

基于Petri網(wǎng)的工作流模型可以使用多種方法進(jìn)行仿真分析，其中ExSpect是一種比較完善的仿真工具，Expect是一個(gè)免費(fèi)的編程工具語言，用來實(shí)現(xiàn)自動(dòng)和交互式任務(wù)進(jìn)行通信，而無需人的干預(yù)。

隨著Expect的不斷發(fā)展，其功能越來越強(qiáng)大，已經(jīng)成為系統(tǒng)管理員的的一個(gè)強(qiáng)大助手。Expect需要Tcl編程語言的支持，使用ExSpect工具結(jié)合ExSpect語言能夠有效地監(jiān)控和分析業(yè)務(wù)流程。本節(jié)利用ExSpect工具及語言對上節(jié)的產(chǎn)品銷售實(shí)例系統(tǒng)進(jìn)行仿真設(shè)計(jì)及相應(yīng)的性能分析。

下面針對以上所建立的產(chǎn)品銷售過程的實(shí)例模型進(jìn)行仿真研究;在ExSpect中建立系統(tǒng)的主模型main，如圖5所示:

圖5 主程序main的仿真模型圖

上圖中system節(jié)點(diǎn)設(shè)置為generator，check_order表示對用戶訂單進(jìn)行檢查的部分，這部分包括檢查配置，檢查庫存數(shù)量和計(jì)算價(jià)格三個(gè)部分。handel_order表示對訂單進(jìn)行處理的部分，主要包括訂單存在問題時(shí)修改訂單和訂單要求能夠滿足而接受訂單需要交款發(fā)貨兩種情況。在仿真的過程中check_order和handel_order需要分別建立的模型。其中check_order檢驗(yàn)訂單的仿真模型如圖6所示。

圖6 check_order的仿真模型圖

在圖6中的處理框check中的代碼是xmsg＜－order_arrived，其含義是指將order_arrived中的標(biāo)志交給xmsg，仿真過程中對配置的檢查，庫存數(shù)量的檢查和價(jià)格的計(jì)算三個(gè)部分主要體現(xiàn)其信息的走向，如果配置不合格或者庫存不足，則給出需要修改訂單的結(jié)論;如果合格，則要返回相應(yīng)的信息，還要計(jì)算出價(jià)格，做出接受訂單的決定。仿真結(jié)果圖7給出了信息傳遞的方向和過程。

圖7 check_order的仿真結(jié)果圖

當(dāng)用戶的訂單被檢查過以后，需要根據(jù)訂單的檢查結(jié)果選擇是接受訂單還是修改訂單，修改訂單需要發(fā)出反饋意見，而接受訂單一方面要發(fā)出付款的通知，另一方面還要發(fā)出生產(chǎn)或者裝配的通知。仿真過程中簡化模型，建立模型時(shí)考慮收到款后才進(jìn)行裝配產(chǎn)品的情況，從而建立handel_order處理訂單的仿真模型如圖8所示。

在仿真軟件ExSpect中通過屬性的設(shè)置可以得到平均時(shí)延的近似值。本節(jié)的仿真過程中使用和上一節(jié)性能等價(jià)計(jì)算中一致的假設(shè)條件。從而得出如圖9的仿真結(jié)果。

圖8 handel_order的仿真模型圖

圖9 handel_order的仿真結(jié)果圖

在圖9中，subrun表示仿真實(shí)驗(yàn)的次數(shù);xarrivals表示一次實(shí)驗(yàn)中到達(dá)的標(biāo)志數(shù)量，在我們的實(shí)例中表示處理的訂單數(shù)量;xaverage表示對訂單進(jìn)行處理的平均時(shí)延，也就是我們在性能等價(jià)時(shí)間中計(jì)算出來的系統(tǒng)總的性能等價(jià)時(shí)間;xvariance表示平均時(shí)延的可靠性。根據(jù)上圖我們得出的平均時(shí)延的近似值約為3037.644。與上節(jié)中計(jì)算的等價(jià)時(shí)間3043.277之間的誤差小于1%，符合時(shí)間精度的要求。

5 結(jié)論

對復(fù)雜工作流模型進(jìn)行性能方面的分析非常必要，依據(jù)實(shí)際的銷售流程建立的模型非常復(fù)雜而且規(guī)模巨大，對性能的分析比較困難，必須對復(fù)雜的工作流模型依據(jù)四種基本模型進(jìn)行等價(jià)的簡化，根據(jù)基本模型的計(jì)算方法進(jìn)行定量分析，為改進(jìn)和完善模型提供合理依據(jù)。

［1］ 何建佳，徐福緣，張燕，王玉璽，何勝學(xué).基于角色的供需網(wǎng)工作流建模與分析［J］.計(jì)算機(jī)應(yīng)用研究，2010，(10):3813 －3815

［2］ 龍鵬飛，鄭凱，林勇.基于Agent技術(shù)的工作流模型的研究與設(shè)計(jì)［J］.計(jì)算機(jī)工程與科學(xué)，2009，(01):99 －100，112

［3］ Andrews M，Anta A F，Zhang L，Zhao Wenbo.Routing forenergy minimization in the speed scaling model.Proceedings of the 29th IEEE Conference on Computer Communications(INFOCOM’10).2010，339 －345

［4］ 范玉順.工作流管理技術(shù)基礎(chǔ)〔M」，北京:清華大學(xué)出版社，2001

［5］ Pang Shanchen，Li Yin，He Hua，Lin Chuang.A model fordynamic business processes and process changes.Chinese Journal of Electronics，2011，20(4):632－636

［6］ 孔劼，蔡皖東.網(wǎng)絡(luò)的聯(lián)合污染模型［J］.計(jì)算機(jī)應(yīng)用，2011，31(8)

［7］ W.M.P.vanderAalst.Three Good reasons for Usinga Petri－net－based Workflow management System ［J ］， In: NavatheS， WakayamaT，eds.Proeeedings of the intermational Working Conferenee on Infonnation and Proeess Integrtion in Enterprises(IPIC’96)，Camebridge，Massachusetts:Kluwer Aeademic Publishers，1996:179－201

［8］ WFMC.Wbrkflow Management Coalition temunology＆ glossary(WFMC1000)［M］，1994

［9］ WFMC.The workfiow reference model(WFMC1003)［M］，1995

［10］ 陳曦，周彥，樂曉波.匡迎春.Petri網(wǎng)化簡新技術(shù)研究［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(5)

［11］ GeorgakoPolous D，HomickM，Sheth A.An Overview of Workflow Management:From Proeess-Modeling to Wbrkflow Automation Infrastr Ueture［J］，Distributed and Parallel Database，2010，3(2):119－152

［12］ Leylnann F，Altenhuber W.Managing Business Proeesses as an Information Resouree［J］，IBM System Joumal，2009，33(2):326 －348