高德平, 周國祥

(合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院,安徽 合肥 230009)

工作流技術(shù)起源于20世紀(jì)70年代的“辦公自動化”和“任務(wù)批處理”思想,但受當(dāng)時計算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)發(fā)展水平的制約,一直未有較大的發(fā)展[1,2]。直至90年代,隨著計算機(jī)技術(shù)的迅速發(fā)展,制約工作流技術(shù)發(fā)展的技術(shù)枷鎖逐漸被打破,同時伴隨著經(jīng)濟(jì)的發(fā)展,原有的信息管理系統(tǒng)已經(jīng)不能滿足企業(yè)的需要,人們迫切需要開發(fā)出的系統(tǒng)能夠迅速地反應(yīng)需求的變化,這也直接促進(jìn)了工作流管理系統(tǒng)(WfMS)的發(fā)展,目前已經(jīng)有許 多 WfMS,如 Action Workflow、Visual Workflo和 Flow Mark等。工作流管理的主要目標(biāo)是:通過調(diào)用有關(guān)的信息資源與人力資源來協(xié)調(diào)業(yè)務(wù)過程中的各個環(huán)節(jié),使之按照一定的順序依次執(zhí)行,從而實(shí)現(xiàn)業(yè)務(wù)過程的自動化[1,3]。

1993年成立的工作流管理聯(lián)盟(Workflow Management Coalition,簡稱WfMC)給出了工作流和工作流管理系統(tǒng)的定義:①工作流是一個業(yè)務(wù)過程全部或部分地用計算機(jī)自動執(zhí)行。②工作流管理系統(tǒng)是一個完全定義、管理和執(zhí)行工作流的系統(tǒng),它通過計算機(jī)表示的工作流邏輯來驅(qū)動軟件的有序執(zhí)行。

1 工作流建模技術(shù)

1.1 工作流技術(shù)簡述

目前,工作流建模技術(shù)方面還處于百家爭鳴時代,并沒有統(tǒng)一的標(biāo)準(zhǔn)。比較流行的幾種建模方法為:基于描述語言、基于圖和網(wǎng)的方法(如有向圖和 Petri-Nets)以及基于規(guī)則的方法等形式[2,3]。

在眾多的工作流建模方法中,Petri網(wǎng)是一種比較有應(yīng)用前景的技術(shù)。經(jīng)典Petri網(wǎng)是在20世紀(jì)60年代由德國學(xué)者C.A.Petri提出,它是一種由庫所(Place)和變遷(Transition)2種元素構(gòu)成的有向圖。它具有圖形化表達(dá)的形式化語義、基于狀態(tài)的流程描述方式和豐富的模型分析方法等優(yōu)點(diǎn),同時它可以方便地通過計算機(jī)表示,在工作流建模中有著先天的優(yōu)勢[4,5]。此外,Petri網(wǎng)具有很多擴(kuò)展的高級Petri網(wǎng)(如時間Petri網(wǎng)、著色Petri網(wǎng)和層次Petri網(wǎng)等),它們非常適合用于描述和分析復(fù)雜的過程,是當(dāng)前工作流建模技術(shù)研究的熱點(diǎn)。

1.2 工作流網(wǎng)的結(jié)構(gòu)

通過對企業(yè)流程的分析,總結(jié)出企業(yè)的流程可以歸納為4類,分別為:串行、并行、選擇和循環(huán)。工作流網(wǎng)絡(luò)應(yīng)該能準(zhǔn)確描述這4類流程,即工作流網(wǎng)的路由結(jié)構(gòu)主要有:串行結(jié)構(gòu)、并行結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)[6],如圖1所示。

圖1 工作流網(wǎng)的4種路由結(jié)構(gòu)

(1)串行結(jié)構(gòu)。各個變遷按照順序串行執(zhí)行的流程,如圖1a所示。

(2)并行結(jié)構(gòu)。變遷B、C可以同時執(zhí)行,且執(zhí)行的順序不受限制的流程,如圖1b所示。

(3)選擇結(jié)構(gòu)。在某個流程中,變遷B、C執(zhí)行一個即可,如圖1c所示。

(4)循環(huán)結(jié)構(gòu)。某些變遷B、C需要反復(fù)執(zhí)行多次的流程,如圖1d所示。

2 基于著色Petri網(wǎng)的工作流網(wǎng)模型

在基于Petri網(wǎng)的工作流建模中,常存在著托肯語義的不確定性和網(wǎng)絡(luò)沖突等問題,著色Petri網(wǎng)能夠較好地克服這些問題,本文將對Petri網(wǎng)進(jìn)行顏色擴(kuò)展,并在著色Petri網(wǎng)的基礎(chǔ)上設(shè)計著色工作流網(wǎng)(CWF-nets)模型。

2.1 著色Petri網(wǎng)的定義

經(jīng)典Petri網(wǎng)在工作流建模領(lǐng)域中有著巨大的優(yōu)勢,它可以用計算機(jī)進(jìn)行形式化表示,同時又具有豐富的數(shù)學(xué)基礎(chǔ)和模型分析方法,這使其在工作流模型的分析設(shè)計中有著廣泛的應(yīng)用。

著色Petri網(wǎng)對經(jīng)典Petri網(wǎng)的擴(kuò)展主要體現(xiàn)在增加了托肯顏色、弧表達(dá)式函數(shù)和守衛(wèi)函數(shù)3個方面。它對托肯進(jìn)行著色以達(dá)到客服經(jīng)典Petri網(wǎng)的二義性問題,具體是利用著色托肯來解決不同托肯案例的不同處理,而弧表達(dá)式函數(shù)和守衛(wèi)函數(shù)則控制著色托肯在工作流網(wǎng)中的路由。其定義如下:

定義1 著色Petri網(wǎng)(CPN)是一個多元組CPN=(Σ,P,T,A,C,G,E,I),其中Σ為顏色集;P為庫所;T為變遷;A是有向弧集合;C為著色函數(shù);G為守衛(wèi)函數(shù);E為弧表達(dá)式函數(shù);I是初始化函數(shù),具體定義見文獻(xiàn)[7]。

2.2 CWF-nets的定義

著色工作流網(wǎng) CWF-nets是一個 8元組:CWF-nets=(Σ,P,T,F,G,B,K,W),其詳細(xì)定義見參考文獻(xiàn)[8,9]。CWF-nets是以CPN為基礎(chǔ)來建立工作流網(wǎng)模型,通過CPN對Petri網(wǎng)的擴(kuò)展來加強(qiáng)模型的描述能力,主要體現(xiàn)在顏色擴(kuò)展、增加弧表達(dá)式函數(shù)和守衛(wèi)函數(shù)3個方面。對庫所中的資源進(jìn)行著色,使不同顏色的托肯得到不同的處理,解決了普通工作流網(wǎng)中的路由沖突問題;利用增加的弧表達(dá)式函數(shù)和守衛(wèi)函數(shù)來精確控制著色托肯的流向。

CWF-nets使得模型的描述能力和對數(shù)據(jù)流的控制能力得到了較大的提高,適合于描述較為復(fù)雜的系統(tǒng),本文將通過實(shí)例介紹CWF-nets。

2.3 正確性分析

定理 正確的CWF-nets應(yīng)該保證起點(diǎn)庫所中的每一個案例托肯經(jīng)過傳遞能夠流動到一個終點(diǎn)庫所,而且與沖突消解方式無關(guān)[8]。

如果一個CWF-nets是正確的,則無論在任何情況下,案例托肯都能順利地處理完畢,流到結(jié)束庫所,不會在流程中發(fā)生丟失或停滯的情況。當(dāng)一個案例托肯在CWF-nets發(fā)生流轉(zhuǎn)時,它所經(jīng)過的一系列的變遷即為一個變遷序列,若某變遷序列L不是其他變遷序列的前綴,則稱L為極大變遷序列。假設(shè)CWF-nets的初始庫所為MPS,終點(diǎn)庫所為 MPE,若CWF-nets是正確的,則任何一個變遷T都屬于一個極大變遷序列中,并且存在一個極大變遷序列L,使得:MPS[L＞MPE。關(guān)于工作流模型的分析可參考文獻(xiàn)[10,11]。

3 實(shí)例與分析

3.1 實(shí) 例

目前,工作流技術(shù)正在逐步應(yīng)用于企業(yè)的關(guān)鍵業(yè)務(wù)中,如企業(yè)的財務(wù)和人力資源管理等。在此,采用著色Petri網(wǎng),對財務(wù)管理中的項(xiàng)目金額申報流程進(jìn)行抽象并建立著色 Petri網(wǎng)模型,如圖2所示。

該流程描述信息如下:通常企業(yè)內(nèi)部會對不同金額的項(xiàng)目采用不同的處理過程,因此將企業(yè)內(nèi)部項(xiàng)目金額申報處理流程設(shè)計為2類:一般項(xiàng)目和重大項(xiàng)目的申報處理。對一般項(xiàng)目的處理步驟為:調(diào)研項(xiàng)目信息—項(xiàng)目金額申報—部門審核—信息整理;對重大項(xiàng)目的處理步驟為:調(diào)研項(xiàng)目信息—項(xiàng)目金額申報—部門審核—領(lǐng)導(dǎo)審核—信息整理;在建立的著色工作流網(wǎng)模型中,采用庫所來表示狀態(tài)信息,變遷表示處理步驟。

圖2 項(xiàng)目金額申報的著色Petri網(wǎng)模型

對庫所進(jìn)行標(biāo)記,以確定其意義。PS為起始庫所;P1為調(diào)研項(xiàng)目信息完畢;P2為項(xiàng)目金額申報完畢;P3為部門審核完畢;P4為部門審核完畢;P5為領(lǐng)導(dǎo)審核完畢;PE為結(jié)束庫所;R為資源庫所。對變遷進(jìn)行標(biāo)記,以確定其意義。T1為調(diào)研項(xiàng)目信息;T2為項(xiàng)目金額申報;T3為部門審核;T4為領(lǐng)導(dǎo)審核;T5為信息整理。(注:針對一般項(xiàng)目和重大項(xiàng)目,P3和P4為2個不同的狀態(tài))。

圖2中定義了顏色集:Color T=N|I;Color U=E|D|L。其中,T表示項(xiàng)目類型;N為一般項(xiàng)目;I為重大項(xiàng)目;U表示人員;E為普通員工;D為部門負(fù)責(zé)人;L為領(lǐng)導(dǎo)。該模型的初始狀態(tài)為2′E+1′D+1′L 和1′N+1′I,表示此時的“資源”有2名普通員工、1名部門負(fù)責(zé)人和1名領(lǐng)導(dǎo),而“任務(wù)”有一般項(xiàng)目和重大項(xiàng)目各1個。在各庫所附近有顏色集標(biāo)記T或U,即對該庫所進(jìn)行顏色標(biāo)記,表示流經(jīng)該庫所的托肯只能為屬于對應(yīng)的顏色集。

此外,還定義了弧表達(dá)式函數(shù),如有向弧(R,T1),(T3,P4)等,表示對不同顏色的托肯執(zhí)行不同的處理。以(R,T1)為例,case x of:N:1′E,I:2′E,代表如果處理1個一般項(xiàng)目,則只需要啟用1名普通員工,而處理1個重大項(xiàng)目,則需要啟用2名員工。同時,變遷T4附近的[x=I]為守衛(wèi)函數(shù),表示只有守衛(wèi)函數(shù)的值為“True”,變遷才可以執(zhí)行,即T4變遷只處理重大項(xiàng)目。

整個著色工作流網(wǎng)模型描述了一個完整的項(xiàng)目金額申報流程,對不同類型的項(xiàng)目采用不同的處理,且明確了資源的占用情況,為企業(yè)建立財務(wù)相關(guān)的工作流管理系統(tǒng)提供了技術(shù)支持。

3.2 分 析

采用本文所述的方法簡要分析該模型,模型中的極大變遷序列L1:T1→T2→T3→T4→T5和L2:T1→T2→T3→T5。對重大項(xiàng)目,托肯從初始庫所PS經(jīng)過極大變遷序列L1最終到達(dá)終點(diǎn)庫所PE;對一般項(xiàng)目,托肯從初始庫所PS經(jīng)過極大變遷序列L2最終到達(dá)終點(diǎn)庫所PE,該模型中沒有不可達(dá)庫所或者死鎖。

4 結(jié)束語

在眾多工作流建模方法中,基于Petri網(wǎng)的工作流建模是一種有巨大優(yōu)勢的建模方式。Petri網(wǎng)具有嚴(yán)密的數(shù)學(xué)基礎(chǔ)和方便通過計算機(jī)處理等優(yōu)點(diǎn),但其對復(fù)雜模型的描述和處理能力不足則是業(yè)界一直努力克服的問題,基于高級Petri網(wǎng)的工作流建?？梢暂^好地解決這些問題。CPN通過對Petri網(wǎng)進(jìn)行顏色擴(kuò)展,具有以下優(yōu)點(diǎn):它能夠描述負(fù)責(zé)的工作流程,具有很好的實(shí)際處理能力;它以Petri網(wǎng)為基礎(chǔ),繼承了Petri網(wǎng)所具有的優(yōu)點(diǎn)。

本文在介紹CWF-nets的基礎(chǔ)上,建立了一個企業(yè)中應(yīng)用比較多的項(xiàng)目金額申報流程的CWF-nets模型。在該模型中,通過CPN成功地避免了因?yàn)橥锌虾x不確定引起的二義性,通過弧表達(dá)式函數(shù)和守衛(wèi)函數(shù)準(zhǔn)確引導(dǎo)托肯的流向,使整個模型可以安全、正確的運(yùn)行。后期的研究工作主要集中在對CWF-nets的分析以及設(shè)計基于CWF-nets的工作流管理系統(tǒng)。

[1] 史美林,楊光信,向 勇,等.WfMS:工作流管理系統(tǒng)[J].軟件學(xué)報,1999,22(3):326-332.

[2] 曾 煒,閻保平.工作流模型研究綜述[J].計算機(jī)應(yīng)用研究,2005,(5):11-13.

[3] Nichols J,Demirkan H,Goul M,et al.Autonomic workflow execution in the grid[J].IEEE Trans Syst,M an Cybern C,Appl Rev,2006,36(3):353-364.

[4] 李建強(qiáng),范玉順.一種工作流模型的性能分析方法[J].計算機(jī)學(xué)報,2003,26(5):513-522.

[5] Gubala T,Herezlak D,Bubak M,et al.Semantic composition of scientific workflows based on the Petri nets formalism[C]//Proc of the Second IEEE International Conference on e-Science and G rid Computing(e-Science'06),2006.ftp://ftp.Computer.org/press/outgoing/proceedings/deeber/patrick/,2009-03-10.

[6] 潘啟澍,姜 兵.基于Petri網(wǎng)的工作流建模技術(shù)及應(yīng)用[J].清華大學(xué)學(xué)報(自然科學(xué)版),2000,40(9):86-89.

[7] 劉 峰,張 偉.一種擴(kuò)展了價格信息的著色Petri網(wǎng)及其應(yīng)用[J].計算機(jī)應(yīng)用,2007,20(10):2501-2503.

[8] 姚 昱,陳莘萌,劉金碩.一種基于有色Petri網(wǎng)的工作流網(wǎng)模型[J].武漢理工大學(xué)學(xué)報,2007,29(3):134-137.

[9] 程建軍.基于Petri網(wǎng)的研究生培養(yǎng)工作流模型[J].合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2009,32(1):78-81.

[10] 李 濤,鐘詩勝.基于著色時間Petri網(wǎng)的工作流模型及其性能分析[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2006,18(6):824-830.

[11] 王 遠(yuǎn),范玉順.工作流時序約束模型分析與驗(yàn)證方法[J].軟件學(xué)報,2007,18(9):2153-2161.