擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流的Ｐｅｔｒｉ網(wǎng)建模
2008-12-31 00:00:00張信芳
電腦知識與技術(shù) 2008年32期
摘要：應(yīng)用Petri網(wǎng)建模與工作流技術(shù)，構(gòu)建了擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流的Petri網(wǎng)模型，并對一個(gè)擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流實(shí)例，給出了基于Petri網(wǎng)化簡分析方法的模型化簡與性質(zhì)驗(yàn)證，表明該模型能夠?qū)?dān)保業(yè)務(wù)管理系統(tǒng)工作流進(jìn)行有效的分析和驗(yàn)證，從而為擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流分析提供了理論基礎(chǔ)。
關(guān)鍵詞：Petri網(wǎng)；工作流；擔(dān)保業(yè)務(wù)
中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)32-1149-03
Petri-net-based Modeling for Surety Business Management System Workflow
ZHANG Xin-fang
(School of Computer Science Technology， Soochow University， Suzhou 215500， China)
Abstract: This thesis has constructed a Petri-net model for Surety Business Management System Workflow， applying technology of Petri-net-based Modeling and Workflow. Model reduction and properties verification based on Petri net reduction are presented for a Surety Business Management system workflow instance. The research result indicates that this model can effectively analyze and verify a Surety Business Management workflow system. Thus it enriches theory on design and workflow analysis in Surety Business Management system integration.
Key words: petri-net; workflow; surety business
1 引言
擔(dān)保行業(yè)是信息和知識應(yīng)用高度密集型行業(yè)，其一系列行為都必須要建立在高質(zhì)量信息平臺的基礎(chǔ)上。擔(dān)保業(yè)務(wù)管理系統(tǒng)為信用擔(dān)保機(jī)構(gòu)提供業(yè)務(wù)工作平臺，為擔(dān)保業(yè)務(wù)各活動提供支持工具，便于決策層對各項(xiàng)業(yè)務(wù)指標(biāo)進(jìn)行全面監(jiān)控，從而控制并降低擔(dān)保風(fēng)險(xiǎn)。
擔(dān)保業(yè)務(wù)流程本身的復(fù)雜性與對正確性的高度要求，需要一種形式化的建模和驗(yàn)證分析技術(shù)作為理論支撐。1962年德國的CA. Petri博士在研究自動機(jī)通信時(shí)，提出了一套形式化的建模方法，在當(dāng)時(shí)引起了學(xué)術(shù)界的廣泛關(guān)注，因此用他的名字命名為Petri網(wǎng)[1]。Petri網(wǎng)是一種系統(tǒng)建模與分析工具，它兼顧了嚴(yán)格語義與圖形語言兩個(gè)方面，是一種基于狀態(tài)的建模方法，具有強(qiáng)有力的分析技術(shù)和手段[2，3]，因而非常適合于工作流建模及其分析。荷蘭學(xué)者W.M.P. van der Aalst定義了基于Petri網(wǎng)的工作流系統(tǒng)的形式化模型——工作流網(wǎng)，并研究了基于工作流網(wǎng)的分析和驗(yàn)證技術(shù)，建立了網(wǎng)性質(zhì)和工作流性質(zhì)之間的對應(yīng)關(guān)系，大大推動了基于Petri網(wǎng)的工作流建模及其分析等方面的工作[4]。
在上述工作的基礎(chǔ)上，本文將工作流網(wǎng)模型應(yīng)用到擔(dān)保業(yè)務(wù)管理系統(tǒng)中，提出了擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流的建模方法，構(gòu)建了擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流的形式化模型。基于該模型，就能對擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流進(jìn)行有效的分析和驗(yàn)證。
2 相關(guān)理論
2.1 Petri網(wǎng)概述
首先，給出本文所需的Petri網(wǎng)的基本概述和定義，有關(guān)Petri網(wǎng)的詳細(xì)資料可參考文獻(xiàn)[5][6]。
經(jīng)典Petri網(wǎng)是由矩形表示的變遷(Transition)和由圓圈表示的庫所(Place)兩種元素構(gòu)成的有向圖，轉(zhuǎn)換和庫所之間通過有向連接弧(Arc)連接。
定義2.1（Petri Net）一個(gè)Petri網(wǎng)是一個(gè)四元組，PN＝{P，T，F(xiàn)，W}，其中：
1) P＝{p1，p2，…，pn}是庫所的有窮集合；
2) T＝{t1，t2，…，tm}是變遷的有窮集合；
3) F?哿(P×T)∪(T×P)是有限連接弧的有窮集合，表示庫所與變遷之間的順序關(guān)系；
4) W:F→{1，2，3，…}是一個(gè)指定連接弧權(quán)重的函數(shù)；
5) P∪T≠Ф且P∩T=Ф。
如果從庫所p到變遷t有一個(gè)連接弧，即
在Petri網(wǎng)中，任何時(shí)刻每個(gè)庫所都擁有零個(gè)或多個(gè)托肯（Token），托肯在各個(gè)庫所間的分布狀況代表著Petri網(wǎng)的狀態(tài)（State，或Marking）。即Petri網(wǎng)的狀態(tài)M∈P->IN，例如3p1＋0p2＋3p3＋1p4代表庫所p1和p3擁有三個(gè)托肯，庫所p4中有一個(gè)托肯，而庫所p2則沒有托肯。另一種表示方法是：3p1＋3p3＋1p4。為比較兩種狀態(tài)，通常會定義狀態(tài)之間的偏序關(guān)系：對于Petri網(wǎng)PN的任意兩個(gè)狀態(tài)M1和M2，M1≤M2當(dāng)且僅當(dāng)對于每個(gè)p∈P有M1(p)≤M2(p)成立。
在Petri網(wǎng)的運(yùn)行過程中，變遷按如下規(guī)則改變托肯在Petri網(wǎng)中分布情況：
1) Enable規(guī)則，一個(gè)變遷t有效（enabled）當(dāng)且僅當(dāng)t的每個(gè)輸入庫所p至少有w(p， t)個(gè)托肯，其中w(p， t)表示從p到t的連接弧的權(quán)重；
2) Fire規(guī)則，有效變遷可以被激發(fā)，變遷t激發(fā)的結(jié)果是從其輸入庫所p中刪除w(p， t)個(gè)托肯，向其輸出庫所p中添加w(t， p)個(gè)托肯，其中w(t， p)表示從t到p的連接弧的權(quán)重。
對于Petri網(wǎng)PN＝｛P，T，F(xiàn)，W｝和狀態(tài)M1，有如下標(biāo)記：
2.2 工作流網(wǎng)
van der Aalst W M P在Petri網(wǎng)的基礎(chǔ)上定義了工作流網(wǎng)(Workflow Net)。在工作流網(wǎng)中，庫所對應(yīng)過程中的條件，變遷對應(yīng)過程中的可執(zhí)行活動。
工作流網(wǎng)還要求有一個(gè)起始庫所和一個(gè)終止庫所，所以需在開始節(jié)點(diǎn)對應(yīng)的變遷ti前增加起始庫所i，并把i與ti通過連接弧連接。在過程模型中增加一個(gè)終止節(jié)點(diǎn)，所有結(jié)束節(jié)點(diǎn)都有一條無條件的路由邊與該終止節(jié)點(diǎn)直接連接。該終止節(jié)點(diǎn)無具體業(yè)務(wù)功能，只是為了限制每個(gè)工作流網(wǎng)只有唯一的出口。每個(gè)結(jié)束節(jié)點(diǎn)執(zhí)行結(jié)束后都會路由到該終止節(jié)點(diǎn)，然后整個(gè)流程終止。同時(shí)在終止節(jié)點(diǎn)to增加終止庫所o，并把to與o通過連接弧連接。由此得到工作流網(wǎng)的定義。
定義2.2 (Workflow Net)一個(gè)Petri網(wǎng)PN=(P，T，F(xiàn)，W)是一個(gè)工作流網(wǎng)WN(Workflow Net)當(dāng)且僅當(dāng)下面三個(gè)條件成立：
1) PN有兩個(gè)特殊的庫所：i和o，其中庫所i被稱為源庫所（source place），且·i＝?覫，庫所o被稱為終止庫所（sink place），且o·＝?覫；
2) 當(dāng)PN增加一個(gè)連接o和i的變遷后t*（即·t*＝｛o｝，t*·＝｛i｝），該P(yáng)etri網(wǎng)是一個(gè)強(qiáng)連通Petri網(wǎng)；
3) 連接弧的權(quán)重都是1，即W：F->{1}。
條件1表示由工作流網(wǎng)WN表示的過程實(shí)例執(zhí)行時(shí)有唯一入口和出口。條件2是為限制在工作流網(wǎng)WN中，不存在執(zhí)行不到的變遷，即每個(gè)變遷對應(yīng)節(jié)點(diǎn)對整個(gè)過程模型的執(zhí)行都是有貢獻(xiàn)的。條件3表示每個(gè)工作流網(wǎng)都是一個(gè)普通（ordinary）Petri網(wǎng)。在本文后續(xù)部分，如果沒有特殊強(qiáng)調(diào)，Petri網(wǎng)中連接弧的權(quán)重都是1，Petri網(wǎng)用三元組（P，T，F(xiàn)）表示。
因?yàn)橐粭l路由邊只會連接一個(gè)源節(jié)點(diǎn)和一個(gè)目的節(jié)點(diǎn)，所以經(jīng)路由邊轉(zhuǎn)化而得的庫所都只有一個(gè)輸入變遷和一個(gè)輸出變遷。而且起始庫所i沒有輸入變遷，唯一輸出變遷是開始節(jié)點(diǎn)對應(yīng)的變遷；終止庫所o沒有輸出變遷，唯一的輸入變遷是終止節(jié)點(diǎn)對應(yīng)的變遷。所以工作流中每個(gè)庫所最多只有一個(gè)輸入變遷和一個(gè)輸出變遷，因此工作流網(wǎng)又是一種加標(biāo)圖（marked graph）。
需要注意工作流網(wǎng)刻畫的是單個(gè)過程實(shí)例的執(zhí)行情況，而且定義5中的三個(gè)條件只是最小約束，這意味著即使?jié)M足這三個(gè)條件的工作流網(wǎng)在實(shí)際執(zhí)行時(shí)仍可能出現(xiàn)死鎖等錯(cuò)誤情況。
每個(gè)工作流網(wǎng)WN有兩個(gè)特殊狀態(tài)：起始狀態(tài)Mi和終止?fàn)顟B(tài)Mo。Mi表示起始庫所i擁有唯一的庫所，而Mo表示終止庫所o擁有唯一的庫所。
3 擔(dān)保業(yè)務(wù)工作流網(wǎng)建模
3.1 擔(dān)保業(yè)務(wù)與Petri網(wǎng)的映射
將擔(dān)保業(yè)務(wù)流程中的角色映射為工作流網(wǎng)中的庫所節(jié)點(diǎn)；角色之間的交互是是通過擔(dān)保事務(wù)進(jìn)行交互的，因此，將擔(dān)保事務(wù)映射為工作流中的變遷節(jié)點(diǎn)；在擔(dān)保事務(wù)中的交互狀態(tài)或信息映射為工作流中的標(biāo)記。擔(dān)保業(yè)務(wù)流程與工作流網(wǎng)的映射關(guān)系如表1所示。
利用表1的映射關(guān)系，就可以用工作流網(wǎng)來刻畫擔(dān)保業(yè)務(wù)流程。
如圖1所示的工作流網(wǎng)模型就是一個(gè)具體的擔(dān)保業(yè)務(wù)流程的過程模型。該流程主要描述了企業(yè)客戶在申請擔(dān)保過程中所涉及的信息處理、交互及存檔等。基于擔(dān)保業(yè)務(wù)流程與工作流網(wǎng)的映射關(guān)系，通過定義庫所、變遷節(jié)點(diǎn)及其關(guān)聯(lián)關(guān)系，模型能夠有效地描述該流程中的業(yè)務(wù)環(huán)節(jié)，并反映它們之間的時(shí)序關(guān)系。
該模型中的庫所節(jié)點(diǎn)對應(yīng)于擔(dān)保業(yè)務(wù)流程的各個(gè)功能單元，其具體的對應(yīng)關(guān)系如表2所示。
表3則給出了工作流模型中的變遷節(jié)點(diǎn)與擔(dān)保業(yè)務(wù)流程中所包含的事務(wù)之間的對應(yīng)關(guān)系。
3.2 模型的化簡分析與驗(yàn)證
Petri網(wǎng)不僅為系統(tǒng)建模提供了形式化的手段和方法，更重要的是，Petri網(wǎng)具有豐富的分析和驗(yàn)證手段，包括基于狀態(tài)方程的代數(shù)分析方法、基于可達(dá)性的圖分析方法以及基于化簡、分解等的歸納分析方法等，能夠?qū)δＰ瓦M(jìn)行有效的分析和驗(yàn)證，從而為實(shí)際系統(tǒng)高效正確運(yùn)行提供保障。具體地，基于本文構(gòu)建的工作流網(wǎng)模型，我們可以對擔(dān)保業(yè)務(wù)管理系統(tǒng)及其工作流進(jìn)行如下的分析和驗(yàn)證工作：
1）模擬和仿真：基于Petri網(wǎng)的可達(dá)圖，我們可以模擬和仿真系統(tǒng)運(yùn)行，求解所有可達(dá)狀態(tài)，從而對系統(tǒng)的動態(tài)特性和運(yùn)行機(jī)理進(jìn)行深入的了解和理解；
2）定性分析：可以測試所設(shè)計(jì)的工作流是否能夠達(dá)到預(yù)期的目標(biāo)或滿足特定的性質(zhì)，包括安全性、可達(dá)性、活性及合理性（soundness）等；
3）定量分析：可以引入隨機(jī)分析等定量分析技術(shù)，對擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流進(jìn)行性能分析，包括平均服務(wù)時(shí)間、資源利用率等，為優(yōu)化、調(diào)度、評價(jià)系統(tǒng)提供依據(jù)。
下面，我們以圖1所示的工作流網(wǎng)為例，利用Petri網(wǎng)的化簡分析技術(shù)，分析該模型的合理性性質(zhì)，以表明模型分析和驗(yàn)證的有效性。事實(shí)上，合理性是工作流的重要性質(zhì)之一，合理性保證了對于任何工作流實(shí)例，在沒有異常的情況下，處理過程都能終止。W.M.P. van der Aalst[7]證明了工作流網(wǎng)滿足合理性的充分必要條件是其擴(kuò)展網(wǎng)（EWN）是活的和有界的，從而將合理性問題轉(zhuǎn)化為Petri網(wǎng)動態(tài)性質(zhì)的分析和驗(yàn)證。但性質(zhì)判定方法可能會受到狀態(tài)空間爆炸的約束，因此，很多學(xué)者研究了基于結(jié)構(gòu)的分析方法，其中化簡技術(shù)是最為常用的一種。在文獻(xiàn)[8]中，就討論了如何基于化簡技術(shù)對工作流網(wǎng)進(jìn)行合理性分析，文中提出了若干保持合理性的化簡規(guī)則，并指出，如果一個(gè)自由選擇擴(kuò)展工作流網(wǎng)基于這些規(guī)則能將其化簡為只包含一個(gè)庫所和一個(gè)變遷的閉環(huán)網(wǎng)，則該工作流網(wǎng)是滿足合理性的。
對于圖1所示的工作流網(wǎng)，很容易驗(yàn)證其擴(kuò)展網(wǎng)是自由選擇網(wǎng)，因此可以利用文獻(xiàn)[8]的化簡方法，需要用到的化簡規(guī)則包括如下的三條：
化簡規(guī)則1：如果自由選擇擴(kuò)展工作流網(wǎng)EWN中輸入輸出弧都唯一的庫所P的輸入變遷ti與輸出變遷to不是同一個(gè)變遷，P的輸出變遷to的輸出庫所不為空且只有唯一的輸入庫所P，則庫所P的輸入輸出變遷可以被融合成同一個(gè)變遷t（從而P被化簡掉），t的輸入輸出庫所分別是ti與t。的輸入庫所與輸出庫所的并，見圖2(a)。
化簡規(guī)則2：如果自由選擇擴(kuò)展工作流EWN網(wǎng)中輸入輸出弧都唯一的變遷t的輸入庫所Pi與輸出庫所Po不是同一個(gè)庫所，t的輸入庫所Pi的輸入變遷不為空且只有唯一的輸出變遷t，則變遷t的輸入輸出庫所可以被融合為同一個(gè)庫所P(從而t被化簡掉)，P的輸入輸出變遷分別是Pi與Po輸入變遷與輸出變遷的并，見圖2(b)。
化簡規(guī)則3：如果自由選擇擴(kuò)展工作流網(wǎng)中變遷t1，t2有相同的輸入輸出庫所，則可以將t1，t2融合成一個(gè)變遷t，見圖2(c)。
為了應(yīng)用上述化簡規(guī)則，首先擴(kuò)展工作流網(wǎng)WN得到其擴(kuò)展網(wǎng)EWN，其中增加的變遷為to，具體的化簡過程如下：
步驟1：連續(xù)應(yīng)用規(guī)則1，逐次消去符合規(guī)則1的庫所，并相應(yīng)的合并符合規(guī)則1的變遷，得到化簡后的工作流網(wǎng)EWN1，見圖3(a)所示；
步驟2：應(yīng)用規(guī)則2，消去變遷t(3)，并合并庫所o與p(2)，得到化簡后的工作流網(wǎng)EWN2，見圖3(b)所示；
步驟3：應(yīng)用規(guī)則1，消去庫所p(1)，合并變遷t(1)與t(2)，得到化簡后的工作流EWN3，再圖3(c)所示；
步驟4：應(yīng)用規(guī)則2，消去變遷t1，合并庫所o與i，最終化簡為只含一個(gè)庫所和一個(gè)變遷的閉環(huán)網(wǎng)EWN4，見圖3(d)所示。
通過上述化簡過程，我們將WN化簡為只含一個(gè)庫所和變遷的EWN4，說明該工作流網(wǎng)是滿足合理性的。
4 結(jié)論
基于工作流網(wǎng)模型，本文給出了擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流的Petri網(wǎng)建模方法，構(gòu)建了相應(yīng)的形式化模型。利用該模型可以對擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流進(jìn)行分析與驗(yàn)證。
本文的工作一方面為擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流定義了形式化模型，提供了理論分析與驗(yàn)證方法，從而為擔(dān)保業(yè)務(wù)管理系統(tǒng)工作流的應(yīng)用提供了理論支持，另一方面，也拓寬了Petri網(wǎng)模型及其理論的應(yīng)用領(lǐng)域，相應(yīng)地，新的領(lǐng)域和應(yīng)用也必將出現(xiàn)新的理論課題和挑戰(zhàn)，這也為Petri網(wǎng)理論的深入研究提出了要求，有助于豐富和發(fā)展Petri網(wǎng)基礎(chǔ)理論。
參考文獻(xiàn)：
[1] 袁崇義.Petri網(wǎng)原理[M].北京:電子工業(yè)出版社，1997.
[2] 吳哲輝.Petri網(wǎng)行為描述、性質(zhì)分析與系統(tǒng)模擬[D].山東科技大學(xué)，2002.
[3] Der Aalst W M P， Hee K. 工作流管理一模型、方法和系統(tǒng)[M].王建民，聞立杰，譯.北京:清華大學(xué)出版社，2004.
[4] 李建強(qiáng)，范玉順.基于Petri網(wǎng)化簡方法的工作流模型驗(yàn)證[J].信息與控制，2001，30(6):492-497.
