工作流網(wǎng)合理性驗證的矩陣實現(xiàn)

劉 川，陳金玉

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

工作流技術(shù)［1］是隨著生產(chǎn)和辦公自動化等領(lǐng)域?qū)τ嬎銠C(jī)技術(shù)的引入而逐漸提出和發(fā)展的。在工作流應(yīng)用系統(tǒng)［2］的開發(fā)過程中，一般需要經(jīng)過業(yè)務(wù)流程的分析和建模、流程定義、流程發(fā)布、投入運行等過程。但如果等到投入實際運行后才發(fā)現(xiàn)流程模型不合理，則可能導(dǎo)致不可挽回的巨大損失。

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

本研究在工作流管理系統(tǒng)及業(yè)務(wù)流程建模技術(shù)的基礎(chǔ)之上，通過對現(xiàn)有Petri網(wǎng)［4］相關(guān)建模及驗證技術(shù)的分析，對文獻(xiàn)［5］提出的工作流網(wǎng)模型的合理性驗證算法進(jìn)行了改進(jìn)，把對應(yīng)的Petri網(wǎng)形式的工作流網(wǎng)模型表示為2個矩陣及向量形式，并通過矩陣及向量運算來進(jìn)行工作流模型的合理性驗證。

1 工作流網(wǎng)模型

工作流網(wǎng)是以Petri網(wǎng)為基礎(chǔ)的一種網(wǎng)結(jié)構(gòu)?；镜腜etri網(wǎng)是一種有向二部圖，一般包含4個基本元素:庫所(place)、變遷(transition)、有向弧(arc)和表示描述系統(tǒng)動態(tài)變化的資源標(biāo)記(token)。

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

2 工作流網(wǎng)合理性驗證的矩陣實現(xiàn)

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

合理性是一個工作流網(wǎng)應(yīng)該滿足的最基本要求，即應(yīng)該滿足任何執(zhí)行的案例過程都能結(jié)束，不存在死任務(wù)，且結(jié)束的時候只有終結(jié)庫所有一個標(biāo)志，其他庫所均為空。雖然合理性是一個最低的要求，不涉及其他可維護(hù)性問題，但合理性要涉及工作流的動態(tài)特性，并不是很容易驗證。

2.1 算法基本思路

文獻(xiàn)［5］的合理性驗證方法主要是基于可達(dá)圖，采用向量表示來逐步驗證可能的狀態(tài)，根據(jù)最終的結(jié)果來檢驗合理性。

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

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

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

3)如果結(jié)束庫所有標(biāo)志出現(xiàn)，則判斷是否為不合理情況。若為合理情況則繼續(xù)執(zhí)行步驟4);否則算法結(jié)束，工作流網(wǎng)模型是不合理的。

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

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

2.2 相關(guān)矩陣向量描述

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

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

矩陣A－稱為Petri網(wǎng)PN的輸入矩陣:

矩陣A+稱為Petri網(wǎng)PN的輸出矩陣:

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

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

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

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

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

設(shè)M0為工作流網(wǎng)的初始狀態(tài)即{1，0，…，0}，同時用一個集合H來存放發(fā)生過的狀態(tài)，最初時令H={M0}。

用集合 N來存放產(chǎn)生的新狀態(tài)，最初也令N=?。

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

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

2.3 具體實現(xiàn)步驟

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

2)設(shè)立初始狀態(tài) Ts=(0，0，…，0)，PS={1，0，…，0}，M0={1，0，…，0}，歷史狀態(tài)集合H={M0}，產(chǎn)生的新狀態(tài)集初始為N=?，設(shè)置當(dāng)前狀態(tài)向量M=M0，還可以設(shè)置狀態(tài)使能標(biāo)記fire來判斷在某個狀態(tài)下是否有變遷能發(fā)生。fire為false表示沒有變遷能發(fā)生，如果為true則表示有變遷能發(fā)生。令fire=false，以便于程序?qū)崿F(xiàn)。

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

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

②根據(jù)引理2計算變遷Ti發(fā)生后的狀態(tài)M'=M+Ai*，判斷是否達(dá)到結(jié)束庫所，即［m］是否為1。若為 0則繼續(xù)步驟③。若為 1，則判斷M'［1］到 M'［m －1］是否均為 0，若是則繼續(xù)步驟③;否則結(jié)束算法，說明結(jié)構(gòu)不合理。

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

④ 將M'加入新狀態(tài)集合 N，N=N∪{M'}，M加入出現(xiàn)的歷史狀態(tài)集H，H=H∪{M}，變遷Ti已發(fā)生，故設(shè)置發(fā)生標(biāo)志Ts［i］=1，設(shè)置已經(jīng)歷過的庫所 PS=PS∪M'。

4)判斷fire是否為false，如果為true轉(zhuǎn)步驟5)。如果為false則表示在狀態(tài)M下沒有變遷可以發(fā)生，應(yīng)該為最終結(jié)果，則判斷M是否為{0，0，…，1}，如果不是則網(wǎng)結(jié)構(gòu)不合理，結(jié)束算法，如果是轉(zhuǎn)5)。

5)如果N為空，表示沒有新狀態(tài)，則轉(zhuǎn)步驟6);否則，設(shè)置狀態(tài)標(biāo)識fire=false，從集合N中取出一個元素 Ni，則 N=N －{Ni}，令 M=Ni，轉(zhuǎn)步驟3)。

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

3 實例驗證

下面給出一個保險索賠的工作流網(wǎng)模型實例，根據(jù)上面的實現(xiàn)步驟，進(jìn)行實例驗證。保險索賠的工作流網(wǎng)模型如圖1所示。對其進(jìn)行廣度優(yōu)先，以及對庫所和變遷編號后的模型如圖2所示。

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

圖2 廣度優(yōu)先編號后的模型

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

根據(jù)本文描述的算法步驟，有:

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

2)在狀態(tài)M0下只有T1能發(fā)生，得到狀態(tài)M1=(0，1，0，0，0，0，0，0，0)，經(jīng)過判斷 M1為新狀態(tài)，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狀態(tài)下只有T2能發(fā)生，得到狀態(tài) M2=(0，0，1，1，0，0，0，0，0)，經(jīng)過判斷M1為新狀態(tài)，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狀態(tài)下T3～T6都能發(fā)生，則分別得到狀態(tài) 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)，經(jīng)過判斷均為新狀態(tài)，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狀態(tài)下T3、T4、T7都能發(fā)生，則分別得到狀態(tài) 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)，當(dāng)產(chǎn)生狀態(tài) M9為結(jié)束庫所出現(xiàn)了標(biāo)志，經(jīng)過判斷M9為不合理的情況，算法結(jié)束。

4 算法及實現(xiàn)分析

本文算法理論上可以對任意工作流網(wǎng)模型進(jìn)行合理性驗證。對比較復(fù)雜的工作流網(wǎng)而言，狀態(tài)數(shù)可能呈指數(shù)級增長，但通過矩陣和向量的比較運算來判斷變遷發(fā)生及記錄變遷發(fā)生后的狀態(tài)，使算法步驟更簡潔，相對更利于計算機(jī)程序?qū)崿F(xiàn)。

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

5 結(jié)束語

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

隨著工作流模型和規(guī)模的擴(kuò)大，驗證狀態(tài)也呈指數(shù)級別增長，還需要對模型進(jìn)行化簡等優(yōu)化操作來減少驗證的狀態(tài)，同時，對于不合理的情況，該算法本身也不能定位具體是哪些結(jié)構(gòu)導(dǎo)致了結(jié)構(gòu)的不合理性，這都需要進(jìn)一步研究。

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

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

［3］胡奇.jBPM4工作流應(yīng)用開發(fā)指南［M］.北京:電子工業(yè)出版社，2010.

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

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

［6］吳哲輝.Petri網(wǎng)導(dǎo)論［M］.北京:機(jī)械工業(yè)出版社，2006.

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

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