基于帶權(quán)時間Petri網(wǎng)的工作流建模研究及應用

周望平,黎湖廣

(長沙航空職業(yè)技術(shù)學院,湖南 長沙 410124)

目前，工作流技術(shù)已經(jīng)日益普及應用，它具有流程集中實現(xiàn)、開發(fā)簡單快速、風險低等特點。工作流的建模方式有很多種，如基于活動網(wǎng)絡(luò)、基于形式化表示、基于狀態(tài)與活動圖、基于事務(wù)模型的建模方式等[1]。工作流系統(tǒng)本質(zhì)上大部分基于Petri網(wǎng)構(gòu)建。Petri網(wǎng)的圖形化表示方式使得模型具有良好的直觀能力，因此Petri網(wǎng)非常適合用于對工作流技術(shù)進行建模和分析。

2000年，W.M.P.Van der Aalst提出了基于Petri網(wǎng)的建模技術(shù)[2]。Khodakaram 等人在此基礎(chǔ)上提出了如何利用基于Petri網(wǎng)的工作流對建模過程中的文件進行審查和分類[3]。Mor Peleg等人利用Petri網(wǎng)建模技術(shù)，結(jié)合生物學，開發(fā)出了生物過程的圖形化知識模型的定性推理方法，給出了一個生物概念模型TAMBIS，并將其映射到工作流模型[4]。

但是傳統(tǒng)Petri網(wǎng)不能反映時間等方面的內(nèi)容，無法對大型復雜的結(jié)構(gòu)提供模型支持等，因此，近些年研究人員對Petri網(wǎng)進行了擴充，應用得最廣泛的方案有三種：基于時間、基于顏色和基于層次的擴展。Injun Choi等人提出了一種基于有色Petri網(wǎng)的事務(wù)工作流模型，給出了對該工作流模型的一個實現(xiàn)，對該實現(xiàn)進行了仿真[5]。Berthomieu B.等人提出了一種基于時間Petri網(wǎng)的工作流模型，該模型支持時間變化的通信系統(tǒng)，并采用枚舉法對該時間Petri網(wǎng)進行了驗證，證明了該模型是可靠的[6]。Rainer Fehling則根據(jù)實際工作經(jīng)驗，提出了一種層次化的Petri網(wǎng)工作流模型，作者給出了Petri網(wǎng)分層結(jié)構(gòu)的接口，并將該思想用于編輯器的層次化界面設(shè)計中[7]。

基于時間對Petri網(wǎng)進行擴充是目前較為主流的工作流實現(xiàn)方法。但時間屬性對工作流模型中的資源、案例和過程具有不同的重要性，因此引入加權(quán)的思想，構(gòu)建基于帶權(quán)時間的工作流模型，并以此模型開發(fā)了某企業(yè)的物資管理系統(tǒng)，實際運行情況表明該工作流模型效果良好。

1 Petri網(wǎng)

1.1 Petri網(wǎng)簡介

Petri網(wǎng)于1962年由Carl Adam Petri博士提出，作為一種圖形化描述過程的工具，Petri網(wǎng)被廣泛用于建模與分析上。既擁有嚴格的數(shù)學定義又能形式化表示的Petri網(wǎng)被認為是所有流程定義語言之母。Carl Adam Petri為Petri網(wǎng)給出了一些基本的術(shù)語，簡單分析如下[8]。

(1)資源(resource)：系統(tǒng)發(fā)生變化包括的人員、工具、設(shè)備、數(shù)據(jù)等與系統(tǒng)狀態(tài)有關(guān)的因素。

(2)庫所(place，又稱P元素)：每一類資源存放的地方，既表示存放資源的場所又表示該類資源。庫所是一個抽象概念，將資源按其在系統(tǒng)中的作用進行分類。

(3)變遷(translation，又稱為T元素)：自動化過程會使用和消耗資源，從而可能引發(fā)庫所變化。

(4)連接弧(directed arc)：連接庫所和變遷，表示庫所與變遷之間可能存在的邏輯關(guān)系。

(5)托肯(token)：表示系統(tǒng)的動態(tài)特性。在Petri網(wǎng)中，托肯位于庫所之中，用黑色的小圓點表示，其在庫所中的動態(tài)變化過程代表系統(tǒng)的狀態(tài)改變(又叫標記、標識)。

在上述定義中，庫所、變遷和有向弧為Petri網(wǎng)的必須結(jié)構(gòu)，表示系統(tǒng)的靜態(tài)功能，托肯的動態(tài)變化表示系統(tǒng)的動態(tài)功能。

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

工作流業(yè)務(wù)過程中的案例、任務(wù)、條件、過程、觸發(fā)等可以由Petri網(wǎng)中的構(gòu)成元素如庫所、變遷、托肯、連接弧等進行映射。其中，Petri網(wǎng)中的變遷描述任務(wù)，庫所對應條件，且?guī)焖硎救蝿?wù)的執(zhí)行次序以及案例的狀態(tài)。庫所中的托肯則表示案例的個數(shù)和執(zhí)行狀態(tài)[9]。

(1)過程：工作流的業(yè)務(wù)過程中定義了哪些任務(wù)需要被執(zhí)行，執(zhí)行這些任務(wù)需要哪些條件，以及這些被執(zhí)行的任務(wù)之間的次序關(guān)系，因此，可以采用Petri網(wǎng)來定義工作流中的過程及其子過程。在Petri網(wǎng)中，只有一個入口和一個出口，分別表示過程的進入和過程的結(jié)束，變遷描述任務(wù)，庫所對應條件。變遷描述的任務(wù)為主動元素，庫所描述的條件為被動元素。

(2)路由：可執(zhí)行的任務(wù)是可以選擇的，采用Petri網(wǎng)庫所的轉(zhuǎn)移，確定案例中任務(wù)的執(zhí)行路由，可以確定哪些任務(wù)需要執(zhí)行。

(3)啟動：工作流中的工作項映射為Petri網(wǎng)中一個就緒的變遷，即，只要觸發(fā)條件滿足，則該變遷立即執(zhí)行。當變遷擁有一個額外的輸入庫所時，該輸入庫所中包含的托肯表示任務(wù)的觸發(fā)條件。

2 基于帶權(quán)時間的工作流模型設(shè)計

2.1 帶權(quán)時間工作流概念模型

標準的工作流由三個維度元素組成，包括過程(process)、資源(resource)、案例(case)。引入時間屬性到工作流空間，就可以使工作流的所有組成元素以及元素間的關(guān)聯(lián)關(guān)系具備時間屬性，顯然時間屬性對三個維度的重要性是不同的，因此，在此基礎(chǔ)上，給出帶權(quán)時間工作流的概念。而帶權(quán)時間工作流則是在時間工作流網(wǎng)的基礎(chǔ)上，除關(guān)注過程維外，還關(guān)注資源維以及案例維，如圖1所示。

圖1 工作流的四維模型

2.2 帶權(quán)時間工作流的元模型

所謂元模型，就是關(guān)于模型的模型。工作流的元模型則用來描述工作流中各元素以及元素間關(guān)系的模型。一個擴展的帶權(quán)時間工作流的元模型如圖2所示，圖中，Logic-Rule代表邏輯規(guī)則，表示工作流中的分支(Split)、匯聚(join)結(jié)構(gòu)以及AND、OR、XOR等相關(guān)性約束，Derived Process繼承了過程的定義，為Process的子過程，子過程可以具備自己的屬性，不同的子過程可以進行組合，這樣可以使得不同的邏輯層次上基本任務(wù)粒度可以進行靈活控制。

圖2 元模型靜態(tài)UML圖

在元模型中，任務(wù)task具備角色(role)、工具(tool)以及案例(case)三要素。工具處理相應的數(shù)據(jù)，角色則使用工具。對任務(wù)進行實例化，由資源(發(fā)起者)觸發(fā)后，任務(wù)被激活為活動，執(zhí)行這些活動，形成過程，這些過程會擁有各種各樣的狀態(tài)。事件(event)既可以觸發(fā)控制轉(zhuǎn)移又可以導致狀態(tài)轉(zhuǎn)化。狀態(tài)之間可以相互轉(zhuǎn)化(類似于線程的就緒、掛起、運行等)。任務(wù)狀態(tài)的變化由狀態(tài)轉(zhuǎn)換規(guī)則(state-transfer-rule)決定，任務(wù)轉(zhuǎn)移的方式則由任務(wù)轉(zhuǎn)移規(guī)則(task-transition-rule)決定，狀態(tài)轉(zhuǎn)換規(guī)則和任務(wù)轉(zhuǎn)移規(guī)則統(tǒng)稱為規(guī)則(Rule)。規(guī)則與規(guī)則之間由聯(lián)系(conn)組成，聯(lián)系則引用相關(guān)數(shù)據(jù)以及觸發(fā)相應事件。

在元模型中，Activity(活動)被分解為task(任務(wù))和Logic-Rule(邏輯規(guī)則)。task由WFMS(工作流管理系統(tǒng))分配給資源完成，是為業(yè)務(wù)邏輯任務(wù)。而Logic-Rule則屬于自動化任務(wù)，WFMS在其中充當執(zhí)行者的角色，屬于管理邏輯任務(wù)。從Activity的角度分析，Logic-Rule不但承擔了選路控制的任務(wù)，同時也負責了案例數(shù)據(jù)的選路任務(wù)以及相應的數(shù)據(jù)處理任務(wù)。這種分解使得task中只需要定義狀態(tài)轉(zhuǎn)換規(guī)則，Logic-Rule只需要定義任務(wù)轉(zhuǎn)移規(guī)則，兩者這種低耦合關(guān)系，讓業(yè)務(wù)任務(wù)定義只需要經(jīng)過微小改變就可以重復利用，甚至達到完全復用。

在工作流中，作為任務(wù)的執(zhí)行者，既可以是程序設(shè)備，也可以是人，這兩者在元模型中被統(tǒng)一為角色(Role)。

在元模型中，case(案例)為被過程處理的業(yè)務(wù)對象。case關(guān)心的是數(shù)據(jù)，既包括業(yè)務(wù)對象中抽象出來的相關(guān)數(shù)據(jù)，又包括控制案例流轉(zhuǎn)的控制數(shù)據(jù)。

2.3 帶權(quán)時間工作流的過程模型

工作流過程模型是整個工作流管理系統(tǒng)的基礎(chǔ)，同時也是整個工作流模型最重要的部分，可以說，工作流過程模型是整個工作流模型的核心部分。工作流過程模型是區(qū)分一個工作流模型好壞的關(guān)鍵所在，系統(tǒng)所支持的應用范圍以及系統(tǒng)的靈活性很大程度上取決于模型描述能力的強弱。

過程模型的組成實體有三類：過程、活動和子過程。過程是對現(xiàn)實世界一個業(yè)務(wù)過程結(jié)構(gòu)的抽象描述。過程包含很多屬性，如過程名、時間限制、活動列表、起始活動、各個活動的優(yōu)先級以及限制條件等等。活動則是對業(yè)務(wù)過程中一個具體的執(zhí)行步驟的抽象描述，比如打開打印機，活動可以根絕應用語義分為不同的類型。子過程則類似于數(shù)據(jù)庫中的外鍵，是對另外一個模型的引用，包括輸入輸出、結(jié)束條件、過程名、過程描述等。

過程模型包括五種關(guān)系，分別是先序關(guān)系、繼承關(guān)系、組成關(guān)系、引用關(guān)系和調(diào)用關(guān)系。先序關(guān)系即第二章中提到的WFMC的四種控制結(jié)構(gòu)。每一種結(jié)構(gòu)中前后的元素間存在著先序關(guān)系。繼承關(guān)系，在三種實體中，子過程與過程間便存在著繼承關(guān)系。組成關(guān)系，連接過程和活動，表示一個過程由一個或多個活動組成。引用關(guān)系，在一個過程執(zhí)行中引用其他過程的對象或者實體。調(diào)用關(guān)系，一個過程或者活動執(zhí)行過程中需要調(diào)用其他應用程序來處理本活動中的對象。

根據(jù)1.2節(jié)所述方法將元模型映射到Petri網(wǎng)，通過Petri網(wǎng)形成WF-Net，再將元模型相關(guān)概念映射為Petri網(wǎng)的相應角色，在此基礎(chǔ)上進行適當?shù)臄U展，形成帶權(quán)時間工作流模網(wǎng)(WTPWF-Net)。WTPWF-net引入時間工作流網(wǎng)和基本工作流網(wǎng)的相關(guān)思想，采用帶權(quán)的時間屬性對托肯進行擴充，用擴充后的托肯表示案例數(shù)據(jù)的時間性約束。變遷的屬性則采用資源以及附加其上的時間屬性進行映射。

2.4 工作流概念到模型元素的映射

工作流管理系統(tǒng)中要處理的業(yè)務(wù)對象由案例表示，在基本工作流網(wǎng)以及時間工作流網(wǎng)中，案例映射為Petri網(wǎng)的托肯，表示前一個任務(wù)已經(jīng)完成。Alast在Petri網(wǎng)的擴展方式中提出了一種可能的時間擴展，并為托肯擴展了時間戳屬性，時間戳屬性主要用于處理兩個任務(wù)間的時間延遲，代表擁有該屬性的托肯何時能被引用。在其他情況下，托肯同樣作為一個信號使用，其不具備自身的獨立屬性。

WTPWF-net中，賦予托肯獨立的帶權(quán)時間屬性(Weighted Time Attribute)，該時間屬性包括三個值：案例創(chuàng)建時間(Case Created Time)、案例有效時間(Case Valid Time)、時間權(quán)重(Time Weight)，其中，時間權(quán)重值越大，案例的優(yōu)先級就越高，該案例重要性越大(即可能包含關(guān)鍵數(shù)據(jù)等情況)，這三個值可以完整的表述所有案例的時間信息。

在基本工作流定義中，只要過程不結(jié)束，案例數(shù)據(jù)永遠有效，意味著案例的生命周期為貫穿過程始終，但在實際的工作流管理系統(tǒng)中，這不可能。因此，在WTPWF-Net中，給予托肯的帶權(quán)時間屬性中，CVT為獨立值，代表在業(yè)務(wù)對象中，案例數(shù)據(jù)的有效時間。CVT大，則案例數(shù)據(jù)的有效期長，反之則短。這樣，當用戶需要對案例的處理進行時間性約束時，可以直接修改CVT的值，而不用去修改過程定義中任務(wù)的間隔時間。同樣，當由案例映射成的托肯相對重要時，給予TW一個比較大的值，當案例為一次性或者相對不重要的案例時，給予TW一個相對較輕的值。

在基本工作流定義中，Petri網(wǎng)中的變遷由活動的執(zhí)行映射而來，庫所則由活動執(zhí)行的條件映射而成，只有庫所擁有托肯時，活動執(zhí)行的條件才視為滿足。但在WTPWF-net中，將任務(wù)分為了兩種，分別是管理邏輯任務(wù)和業(yè)務(wù)邏輯任務(wù)，兩者都需要映射，同時，在各種狀態(tài)下以及狀態(tài)的轉(zhuǎn)換間會存在一定的時間延遲。

WTPWF-net中，在加入帶權(quán)的時間因素后，任務(wù)狀態(tài)轉(zhuǎn)換圖如圖3所示(采用操作系統(tǒng)中的時間片分片思想)。

圖3 活動狀態(tài)轉(zhuǎn)化圖

其中，S0為等待狀態(tài)，S1為就緒狀態(tài)，S2為運行狀態(tài)，S3為完成態(tài)，S4為異常態(tài)，S5為終止狀態(tài)，S6為掛起狀態(tài)，終止狀態(tài)與掛起狀態(tài)均為人工干預導致(參考了操作系統(tǒng)中進程模型)。

S3、S4、S5為終止態(tài)，S0為起始態(tài)，S0經(jīng)過調(diào)度到S1，S1經(jīng)過點火到S2，當S1的時間片用完時，跳轉(zhuǎn)到終止態(tài)S4，當S1終止時，跳轉(zhuǎn)到S5，當S1取消執(zhí)行時，跳回到起始態(tài)S0.當S2取消時，回退到S1。當S0時間片用完時，跳到終止態(tài)S4。S0中斷時，跳到S5。

在圖3中，業(yè)務(wù)邏輯任務(wù)的狀態(tài)分為等待、就緒、執(zhí)行三個狀態(tài)，分別由S0，S1和S2表示。當業(yè)務(wù)邏輯任務(wù)處于S0時，WFMS擁有控制權(quán)，當業(yè)務(wù)邏輯任務(wù)分配完成后，業(yè)務(wù)邏輯任務(wù)形成工作項，進入用戶的工作項列表，此時業(yè)務(wù)邏輯任務(wù)處于S1，相應的控制權(quán)也從WFMS上轉(zhuǎn)移到執(zhí)行任務(wù)的資源。

WTPWF-net中，將等待狀態(tài)下的業(yè)務(wù)邏輯任務(wù)映射為庫所，將就緒和執(zhí)行狀態(tài)下的業(yè)務(wù)工作項映射為變遷。同時，業(yè)務(wù)邏輯任務(wù)和業(yè)務(wù)工作項也包含自己的時間屬性，包括任務(wù)分配延遲時間(DDT)、分配有效時間(DVT)、條件觸發(fā)延遲時間(FDT)、條件觸發(fā)有效時間(FVT)、執(zhí)行延遲時間(EDT)、執(zhí)行有效時間(EVT)，映射后，DDT和DVT為庫所的時間屬性，F(xiàn)DT、FVT、EDT、EVT為變遷的時間屬性。

在管理邏輯任務(wù)中，就緒狀態(tài)到執(zhí)行狀態(tài)可以擁有多條可選路徑，執(zhí)行狀態(tài)到就緒狀態(tài)也有多種方式，因此，這是一種不同于普通變遷定義的多入口多出口方式，這里，將之定義為查找變遷。

查找變遷Tr(I,O,W,(i,o,w))，其中，*t=I，t*=O，即I為變遷t的前置集，O為變遷t的后置集。(i,o,w)代表時間屬性(變遷起始時間、變遷結(jié)束時間、變遷執(zhí)行權(quán)重)，在起始時間相同的情況下，w大的變遷首先被觸發(fā)。

查找變遷與普通變遷的區(qū)別為，普通變遷只有一個輸入庫所和輸出庫所，查找變遷不受此限制，而且，查找變遷沒有時延，即DDT、FDT、EDT的值恒為0。

WTPWF-net中，Petri網(wǎng)中的弧由任務(wù)間的依賴關(guān)系映射而成，且弧的權(quán)值為一個常量值1，該數(shù)字不具備任何定量意義，僅僅是表示相鄰任務(wù)間具備時序關(guān)系，這與基本工作流網(wǎng)一致。

WTPWF-net中最后一個是關(guān)于資源的映射，由于資源是任務(wù)的發(fā)起者和執(zhí)行者，是任務(wù)以及活動的組成要素，往往與兩者綁定在一起，因此，將資源及其時間屬性同樣映射為Petri網(wǎng)中變遷的屬性。

3 基于WTPWF-net的物資管理系統(tǒng)實現(xiàn)

應用WTPWF-net對某公司物資管理系統(tǒng)進行流程分析，將物資管理系統(tǒng)的相關(guān)審批流程應用本方法編程開發(fā)實現(xiàn)。首先將物資管理系統(tǒng)中的有關(guān)工作流與Petri網(wǎng)進行相應映射，然后由Petri網(wǎng)與WTPWF-net進行映射。圖4為所涉及物資管理系統(tǒng)的主功能界面圖，圖中，左邊的樹形菜單為物資管理系統(tǒng)中的主要功能，可以點擊每個功能查看該功能的流程圖。

圖4 主功能界面圖

圖5為后臺管理截圖，后臺管理人員可見，管理人員查看諸如訂單等信息后將之傳送給領(lǐng)導，以便領(lǐng)導審閱。

圖5 后臺管理

4 結(jié)論

在分析傳統(tǒng)工作流局限性的基礎(chǔ)上，提出了一種帶權(quán)的時間工作流概念，將過程、資源、案例三維空間擴展到過程、資源、案例、時間四維模型，同時，針對傳統(tǒng)工作流只關(guān)心過程而不關(guān)心資源和案例的情況，提出了時間屬性對三個維度的重要性不一致的概念，并給出了帶權(quán)的時間工作流模型，并對該模型的元模型、過程模型給予了詳細說明。最后將提出的工作流模型實際應用于某公司物資管理系統(tǒng)，良好的實際應用效果驗證了方法的可行性和有效性。

[1] 李煒, 曾廣周, 王曉琳.一種基于時間Petri網(wǎng)的工作流模型[J]．軟件學報，2002,13(9):1666-1672.

[2] 張亮, 姚淑珍.基于Petri網(wǎng)化簡技術(shù)的工作流模型正確性研究[J]．計算機工程, 2007,33(9):60-61.

[3] 陸中，孫有朝，吳海橋．基于著色隨機時間Petri網(wǎng)的維修性建模方法[J]．機械工程學報，2011,47(10): 231-237.

[4] 劉銘，張國印，姚愛紅．基于層次實時有色Petri網(wǎng)的實時系統(tǒng)建模與分析方法研究[J]．電子與信息學報，2011,33(3): 24-32.

[5] 余陽，湯庸．時態(tài)工作流過程模型及其合理性驗證[J]．軟件學報，2010,21(6):1233-1253.

[6] 陳偉，文東戈，王昊．層次顏色工作流Petri網(wǎng)建模與應用[J]．計算機技術(shù)與發(fā)展，2009,1(1): 49-52.

[7] 潘理，丁志軍，郭觀七．混合語義時間Petri網(wǎng)模型[J]．軟件學報，2011,22(6): 221-233.

[8] 周建濤，葉新銘．一種構(gòu)造Petri網(wǎng)可達圖的方法[J]．內(nèi)蒙古大學學報(自然科學版)，1999,30(3):392-395.

[9] 周建濤，葉新銘．Petri網(wǎng)的可達圖與可達樹的比較[J]．內(nèi)蒙古大學學報(自然科學版),2000,31(1):117-120.

[10] 羅海濱，范玉順，吳澄．工作流管理技術(shù)綜述[J]．軟件學報，2000, 11(7): 89-97.