工作流網合理性驗證的矩陣實現

劉 川，陳金玉

(重慶大學自動化學院，重慶 400044)

工作流技術［1］是隨著生產和辦公自動化等領域對計算機技術的引入而逐漸提出和發展的。在工作流應用系統［2］的開發過程中，一般需要經過業務流程的分析和建模、流程定義、流程發布、投入運行等過程。但如果等到投入實際運行后才發現流程模型不合理，則可能導致不可挽回的巨大損失。

一般工作流應用開發系統都提供了建模工具，但一些系統卻缺少建模后對模型結構進行合理性驗證的工具，比如較出名的開源工作流系統jBPM4［3］系列及以前的版本，在沒有驗證工具的情況下需要設計人員來把握業務流程的合理性。顯然隨著模型的日益復雜，對模型合理性的正確把握也相應更困難。

本研究在工作流管理系統及業務流程建模技術的基礎之上，通過對現有Petri網［4］相關建模及驗證技術的分析，對文獻［5］提出的工作流網模型的合理性驗證算法進行了改進，把對應的Petri網形式的工作流網模型表示為2個矩陣及向量形式，并通過矩陣及向量運算來進行工作流模型的合理性驗證。

1 工作流網模型

工作流網是以Petri網為基礎的一種網結構。基本的Petri網是一種有向二部圖，一般包含4個基本元素:庫所(place)、變遷(transition)、有向弧(arc)和表示描述系統動態變化的資源標記(token)。

在圖形上用圓形表示庫所，用小黑點表示標記，用矩形表示變遷，用有向弧連接庫所到變遷或連接變遷到庫所。庫所與庫所以及變遷與變遷是不允許直接連接的。限于篇幅，本文用到基本定義如基本Petri的定義、Petri網的前集和后集、Petri網的變遷發生規則等請參考文獻［6］。

2 工作流網合理性驗證的矩陣實現

工作流網(WF-ne)的概念是Alast提出的，是以Petri網為基礎的，其定義和合理性條件請參考文獻［7］。

合理性是一個工作流網應該滿足的最基本要求，即應該滿足任何執行的案例過程都能結束，不存在死任務，且結束的時候只有終結庫所有一個標志，其他庫所均為空。雖然合理性是一個最低的要求，不涉及其他可維護性問題，但合理性要涉及工作流的動態特性，并不是很容易驗證。

2.1 算法基本思路

文獻［5］的合理性驗證方法主要是基于可達圖，采用向量表示來逐步驗證可能的狀態，根據最終的結果來檢驗合理性。

考慮到在不合理網中可能出現不僅結束庫所有標志，并且其他庫所都還有標志的這種不合理情況，為了能減少狀態空間的數量，在算法中加入這種情況的判斷。工作流網的合理性定義參考文獻［5］。本研究的算法思路描述:

1)采用廣度優先算法，記錄工作流網的輸入輸出矩陣［8］，并從初始狀態集合S={M0}開始。

2)根據建立的矩陣判斷S中的狀態能否實施變遷，滿足則實施變遷得到新狀態集合S'，已經出現過的狀態不在S'中，同時通過向量來記錄觸發過的變遷、經歷過的庫所。

3)如果結束庫所有標志出現，則判斷是否為不合理情況。若為合理情況則繼續執行步驟4);否則算法結束，工作流網模型是不合理的。

4)把S'的值賦給S，重復步驟 2)，直到 S中的元素都沒有變遷能發生。

5)如果S中的元素都是形如{0，0，…，1}的終止態，且所有的變遷都發生過，所有的庫所都經歷過，則該網是合理的;否則存在錯誤。

2.2 相關矩陣向量描述

根據上面的思路，采用矩陣及向量的簡單運算來驗證前面轉換的模型的合理性。

定義1 PN=(P，T;F)為一個Petri網。將Petri網中的庫所標記為 P={P1，P2，…，Pm}，變遷標記為 T={T1，T2，…，Tn}。

矩陣A－稱為Petri網PN的輸入矩陣:

矩陣A+稱為Petri網PN的輸出矩陣:

矩陣A=A+－A－，稱為Petri網PN的關聯矩陣(incidence matrix)，用Ai*、A+i*、A－i*分別表示矩陣A、A+、A－的第i行形成的行向量。

定義2 設 PN=(P，T;F，M)為一個 Petri網，把狀態M表示為一個m維行向量，即M=［M(P1)，M(P2)，…，M(Pm)］，其中 M(Pi)表示庫所Pi在狀態M下的標志數。由定義可知M是一個m維非負向量。如果對于任意的p∈P，都有M1(p)≤(M2(p)，則稱M1被M2覆蓋，或者說M2覆蓋M1。

引理1 設 PN=(P，T;F，M)為一個 Petri網，A為其關聯矩陣，ti∈T，由變遷發生規則及向量的比較立即可得M［ti］＞M1的充分必要條件為M≥Ai－*。

引理2 設 PN=(P，T;F，M)為一個 Petri網，A 為其關聯矩陣，ti∈T，如果 M［ti］＞ M1，則由變遷發生規則及定義1的關聯矩陣有M1=M+Ai*。

定義3 (向量的或運算)已知向量X、A、B，令 X=A∪B，則

設M0為工作流網的初始狀態即{1，0，…，0}，同時用一個集合H來存放發生過的狀態，最初時令H={M0}。

用集合 N來存放產生的新狀態，最初也令N=?。

用一個n維向量Ts［n］來標記各個變遷是否已發生，Ts［i］=1表示第i個變遷已經被觸發過，尚未觸發的用 Ts［i］=0來表示，其中:i=1，…，n;最初 Ts=(0，0，…，0)。

對于每個庫所是否被經歷過的情況，采用一個m維向量Ps來記錄，其中m是庫所數，Ps［i］=1表示第i個庫所已經歷過，Ps［i］=0則表示未經歷，最開始的狀態為 Ps={1，0，…，0}。

2.3 具體實現步驟

1)采用廣度優先的方法，把工作流網模型的庫所依次編號為 P1，P2，…，Pm，變遷依次標記為T1，T2，…，Tn。按定義 1 分別建立輸出矩陣 A+、輸入矩陣A－以及關聯矩陣A。

2)設立初始狀態 Ts=(0，0，…，0)，PS={1，0，…，0}，M0={1，0，…，0}，歷史狀態集合H={M0}，產生的新狀態集初始為N=?，設置當前狀態向量M=M0，還可以設置狀態使能標記fire來判斷在某個狀態下是否有變遷能發生。fire為false表示沒有變遷能發生，如果為true則表示有變遷能發生。令fire=false，以便于程序實現。

3)根據輸入矩陣A－及當前狀態M，由引理1判斷是否有變遷能發生，分別進行處理。對每一個能發生的變遷產生的新狀態如果沒有在歷史狀態集H中出現，則加入新狀態集N中，并且對結束庫所出現標志的情況及時檢查是否是不合理的，而對于沒有變遷能發生的情況則判斷是否有不合理情況出現。這一步驟的具體實施步驟:

①根據引理1，判斷變遷Ti(i表示第i個變遷)能否發生，即如果存在輸入矩陣的第i行滿足，則設置fire=true標記有變遷發生，繼續步驟②，否則對下一個變遷進行判斷。

②根據引理2計算變遷Ti發生后的狀態M'=M+Ai*，判斷是否達到結束庫所，即［m］是否為1。若為 0則繼續步驟③。若為 1，則判斷M'［1］到 M'［m －1］是否均為 0，若是則繼續步驟③;否則結束算法，說明結構不合理。

③對M'進行已有狀態判斷。如果M'對每一個 Mi∈H，都不滿足 Mi≤M'(即沒被 M'覆蓋)，則轉步驟④，否則對下一個變遷，轉步驟①對其進行判斷。

④ 將M'加入新狀態集合 N，N=N∪{M'}，M加入出現的歷史狀態集H，H=H∪{M}，變遷Ti已發生，故設置發生標志Ts［i］=1，設置已經歷過的庫所 PS=PS∪M'。

4)判斷fire是否為false，如果為true轉步驟5)。如果為false則表示在狀態M下沒有變遷可以發生，應該為最終結果，則判斷M是否為{0，0，…，1}，如果不是則網結構不合理，結束算法，如果是轉5)。

5)如果N為空，表示沒有新狀態，則轉步驟6);否則，設置狀態標識fire=false，從集合N中取出一個元素 Ni，則 N=N －{Ni}，令 M=Ni，轉步驟3)。

6)最后，檢查向量 Ts和PS，如果 Ts=(1，1，…，1)，并且 PS={1，1，…，1}，則表示該工作流網所有的變遷都能發生，所有的庫所都經歷過，即不存在死鎖現象，表明工作流網是合理的。

3 實例驗證

下面給出一個保險索賠的工作流網模型實例，根據上面的實現步驟，進行實例驗證。保險索賠的工作流網模型如圖1所示。對其進行廣度優先，以及對庫所和變遷編號后的模型如圖2所示。

圖1 保險索賠的工作流模型

圖2 廣度優先編號后的模型

根據圖2建立輸入矩陣A－、輸出矩陣A+和關聯矩陣A(行為T1～T9，列為P1～P9):

根據本文描述的算法步驟，有:

1)設立初始狀態 Ts=(0，0，…，0)，PS={1，0，…，0}，M0={1，0，…，0}，歷史狀態集合H={M0}，新狀態集初始為N=?，設置當前狀態向量M=M0。

2)在狀態M0下只有T1能發生，得到狀態M1=(0，1，0，0，0，0，0，0，0)，經過判斷 M1為新狀態，N={M1}，Ts=(1，0，0，0，0，0，0，0，0)，PS=(1，1，0，0，0，0，0，0，0)，H={M0}。

3)從N中取出M1，在M1狀態下只有T2能發生，得到狀態 M2=(0，0，1，1，0，0，0，0，0)，經過判斷M1為新狀態，N={M2}，Ts=(1，1，0，0，0，0，0，0，0)，PS=(1，1，1，1，0，0，0，0，0)，H={M0，M1}。

4)從N中取出M2，在M2狀態下T3～T6都能發生，則分別得到狀態 M3=(0，0，0，1，1，0，0，0，0)，M4=(0，0，0，1，0，1，0，0，0)，M5=(0，0，1，0，1，0，0，0，0)，M6=(0，0，1，0，0，0，1，0，0)，經過判斷均為新狀態，N={M3，M4，M5，M6}，Ts=(1，1，1，1，1，1，0，0，0)，PS=(1，1，1，1，1，1，1，0，0)，H={M0，M1}。

5)從N中取出M3，在M3狀態下T3、T4、T7都能發生，則分別得到狀態 M7=(0，0，0，0，2，0，0，0，0)，M8=(0，0，0，0，1，1，0，0，0)，M9=(0，0，1，0，0，0，0，0，1)，當產生狀態 M9為結束庫所出現了標志，經過判斷M9為不合理的情況，算法結束。

4 算法及實現分析

本文算法理論上可以對任意工作流網模型進行合理性驗證。對比較復雜的工作流網而言，狀態數可能呈指數級增長，但通過矩陣和向量的比較運算來判斷變遷發生及記錄變遷發生后的狀態，使算法步驟更簡潔，相對更利于計算機程序實現。

通過上面的實例可以看出，在算法的具體實現中，當結束庫所出現標志時即對不合理情況進行及時判斷，在不合理時避免了后續狀態的驗證，在一定程度上減少了驗證狀態的數量。對于合理情況也是可以判斷的，但相對于原算法，除了用2個矩陣和向量表示以及較簡潔的運算實現以外，并沒有什么算法理論上的效率提升。

5 結束語

把工作流網模型表示為輸入輸出2個矩陣和2個庫所和變遷的向量，通過矩陣的比較和加減運算實現了變遷的判斷和發生狀態記錄，完成了對工作流網模型的合理性驗證，并通過及時判斷結束庫所出現標志的合理性來減少后續狀態的判斷次數，效率有了一定的提升，具有一定的實際意義和參考價值。

隨著工作流模型和規模的擴大，驗證狀態也呈指數級別增長，還需要對模型進行化簡等優化操作來減少驗證的狀態，同時，對于不合理的情況，該算法本身也不能定位具體是哪些結構導致了結構的不合理性，這都需要進一步研究。

［1］付偉.工作流技術綜述［J］.河北北方學院學報，2007，23(2):13－15.

［2］侯志松，馮啟高.工作流管理系統開發實錄［M］.北京:中國鐵道出版社，2010.

［3］胡奇.jBPM4工作流應用開發指南［M］.北京:電子工業出版社，2010.

［4］秦凱，姜浩.一種基于Petri網的工作流模型分解方法［J］.計算機技術與發展，2008，18(1):97 －100.

［5］周福明，吳斌，顧慶，等.基于Petri網的工作流建模與正確性分析［J］.計算機科學，2005，32(2):121 －124.

［6］吳哲輝.Petri網導論［M］.北京:機械工業出版社，2006.

［7］van der Alast W M F，van Hee K.工作流管理—模型、方法和系統［M］.王建民，聞立杰，譯.北京:清華大學出版社，2004.

［8］喻斌，武友新.工作流過程建模中驗證技術的研究［J］.微計算機信息，2008，24(1－3):220 －222.