孟廣學(xué)

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

0 引言

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

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

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

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

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

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

圖1 工作流四種基本模型

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

對(duì)于一個(gè)復(fù)雜的基于Petri網(wǎng)工作流模型直接進(jìn)行等價(jià)服務(wù)時(shí)間的分析較為困難，必須依據(jù)基本的模型進(jìn)行簡(jiǎ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)品銷(xiāo)售過(guò)程為例來(lái)具體說(shuō)明基于Petri網(wǎng)的工作流建模及性能分析過(guò)程。

2 模型的建立

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

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

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

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

圖2 產(chǎn)品銷(xiāo)售過(guò)程流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

性能等價(jià)計(jì)算的原則是:首先由里到外，通過(guò)性能的等價(jià)變化將復(fù)雜的結(jié)構(gòu)化簡(jiǎn)到最簡(jiǎn)單，在簡(jiǎn)化模型的過(guò)程中，要依據(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)過(guò)串、并和選擇的化簡(jiǎn)，得到如圖4所示的模型:

圖4 產(chǎn)品銷(xiāo)售過(guò)程最終模型簡(jiǎ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)的編程工具語(yǔ)言，用來(lái)實(shí)現(xiàn)自動(dòng)和交互式任務(wù)進(jìn)行通信，而無(wú)需人的干預(yù)。

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

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

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

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

圖6 check_order的仿真模型圖

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

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

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

在仿真軟件ExSpect中通過(guò)屬性的設(shè)置可以得到平均時(shí)延的近似值。本節(jié)的仿真過(guò)程中使用和上一節(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表示對(duì)訂單進(jìn)行處理的平均時(shí)延，也就是我們?cè)谛阅艿葍r(jià)時(shí)間中計(jì)算出來(lái)的系統(tǒng)總的性能等價(jià)時(shí)間;xvariance表示平均時(shí)延的可靠性。根據(jù)上圖我們得出的平均時(shí)延的近似值約為3037.644。與上節(jié)中計(jì)算的等價(jià)時(shí)間3043.277之間的誤差小于1%，符合時(shí)間精度的要求。

5 結(jié)論

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

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

［2］ 龍鵬飛，鄭凱，林勇.基于A(yíng)gent技術(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］ 陳曦，周彥，樂(lè)曉波.匡迎春.Petri網(wǎng)化簡(jiǎn)新技術(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