資源描述:
《基于petri網(wǎng)工作流模型的分析》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、基于Petri網(wǎng)工作流模型的分析晉 蓓,馮衛(wèi)兵(1.西北大學(xué) 計(jì)算機(jī)科學(xué)系,陜西西安 710069;2.西安科技大學(xué) 基礎(chǔ)部,陜西西安 710054)摘要:通過(guò)模型分析發(fā)現(xiàn)所描述的過(guò)程定義中的設(shè)計(jì)錯(cuò)誤,以便對(duì)業(yè)務(wù)過(guò)程重構(gòu)提供正確的指導(dǎo)和科學(xué)的依據(jù)。首先將信牌驅(qū)動(dòng)模型轉(zhuǎn)化為Petri網(wǎng),接著將Petri網(wǎng)進(jìn)行必要化簡(jiǎn),最后對(duì)化簡(jiǎn)后的Petri網(wǎng)進(jìn)行死鎖等分析。關(guān) 鍵 詞:工作流模型;Petri網(wǎng);死鎖中圖分類號(hào):TP911.7文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1000-274X(2004)0068-07工作
2、流模型的分析是指采用各種方法(包括理論模型、模擬、測(cè)量方法),對(duì)工作流模型的內(nèi)部行為進(jìn)行分析計(jì)算,使得工作流模型在理論上是正確和有效的。雖然現(xiàn)在絕大部分的工作流產(chǎn)品都提供模型性能分析的仿真功能,但由于復(fù)雜性等原因,很難找到一種有效的算法對(duì)模型進(jìn)行分析與驗(yàn)證。本文在總結(jié)模型分析研究成果現(xiàn)狀的基礎(chǔ)上,針對(duì)目前模型驗(yàn)證方法存在的不足,總結(jié)了Petri網(wǎng)模型分析中的一些圖形化簡(jiǎn)規(guī)則,針對(duì)企業(yè)經(jīng)營(yíng)過(guò)程模型的特點(diǎn)并利用文中提出的模型正確性標(biāo)準(zhǔn),提出了一種具有完備性和高效率的工作流模型的模型驗(yàn)證方法分析。1
3、相關(guān)概念定義1 信牌驅(qū)動(dòng)模型的靜態(tài)結(jié)構(gòu):多元式稱為信牌驅(qū)動(dòng)模型的靜態(tài)結(jié)構(gòu)(以下簡(jiǎn)稱信牌驅(qū)動(dòng)模型),其中:1)表示擴(kuò)展的信牌驅(qū)動(dòng)模型所涉及的所有數(shù)據(jù),其值域用表示;2)表示活動(dòng)集合,和分別稱為功能函數(shù)和后繼函數(shù)。被定義為根據(jù)出函數(shù)定義,參見下邊的定義;3)表示信牌箱集合;4),稱為的流關(guān)系,其中和分別稱為入關(guān)系和出關(guān)系。對(duì)出關(guān)系定義一個(gè)出函數(shù):表示與相關(guān)的出函數(shù),被稱為的后繼函數(shù)。5)?是惟一的活動(dòng),稱為開始活動(dòng),;6)是一個(gè)活動(dòng)的集合,稱為結(jié)束活動(dòng),;7)?稱為轉(zhuǎn)移的權(quán)重;8)是(注意:中不包含
4、)的一種劃分即8是的另一種劃分,即規(guī)定。若,則;若,則;如果,則被稱為簡(jiǎn)單元素。一個(gè)信牌驅(qū)動(dòng)的工作流模型,開始活動(dòng)只能是一個(gè),但是結(jié)束活動(dòng)可以是多個(gè)。為了描述問(wèn)題方便,有時(shí)我們也將信牌驅(qū)動(dòng)的模型簡(jiǎn)寫成。定義2 真假信牌,設(shè)。1)上的一個(gè)多重集是一個(gè)映射(自然數(shù)集合),令表示上所有多重集的集合;2)表示多重集且表示多重集且表示多重集且。定義3 活動(dòng)的SPLIT,設(shè)為信牌驅(qū)動(dòng)模型,令,稱集合為出弧的集合。表示出弧的個(gè)數(shù)。與所聯(lián)系的信牌箱稱為的后信牌箱?;蛘呋蛘吆头Q為的SPLIT類型,記為。定義4 活
5、動(dòng)的JOIN:設(shè)為信牌驅(qū)動(dòng)模型,令,稱集合為入弧的集合。表示入弧的個(gè)數(shù)。與聯(lián)系的信牌箱稱為的前信牌箱?;蛘呋蛘呋蛘呋蛘撸头Q為的類型,記為。定義5 確定的Petri網(wǎng)[1]。本文的討論均在有限網(wǎng)的基礎(chǔ)上進(jìn)行,以下不再說(shuō)明。定義6 非確定Petri網(wǎng)系統(tǒng)。參見文獻(xiàn)[1]。定義7 非確定變遷的發(fā)生結(jié)果。參見文獻(xiàn)[1]。2 將信牌驅(qū)動(dòng)模型轉(zhuǎn)化為Petri網(wǎng)Petri網(wǎng)有很強(qiáng)的表達(dá)能力,其描述能力與Turing機(jī)等價(jià),因此所有典型的流程都可用Petri網(wǎng)予以描述。本節(jié)探討將工作流模型中的各種基本控制結(jié)構(gòu)
6、自動(dòng)地轉(zhuǎn)化為Petri網(wǎng)的規(guī)則。由于工作流模型是由這些基本的控制結(jié)構(gòu)組合而成的復(fù)雜網(wǎng)絡(luò),所以工作流模型就可轉(zhuǎn)化為一個(gè)Petri網(wǎng)模型[2]。下面研究典型流程到Petri網(wǎng)結(jié)構(gòu)轉(zhuǎn)換的對(duì)應(yīng)規(guī)則(為討論方便,在沒有特別說(shuō)明的情況下,在轉(zhuǎn)換過(guò)程中對(duì)應(yīng)的信牌箱與位子的容量相同,對(duì)應(yīng)連線的權(quán)值相同)轉(zhuǎn)化原則:轉(zhuǎn)化最重要的是要遵守原系統(tǒng)的原有邏輯順序,把對(duì)象的操作映射為Petri網(wǎng)模型中的位子;工作流中的活動(dòng)即Petri中的轉(zhuǎn)移;工作流中的開始活動(dòng)即Petri網(wǎng)中的無(wú)輸入轉(zhuǎn)移和該轉(zhuǎn)移的輸出位子,它受外界因素的
7、控制,自動(dòng)產(chǎn)生激活整個(gè)Petri網(wǎng);工作流中的結(jié)束標(biāo)記即Petri中的無(wú)輸出庫(kù)所得變遷和單變遷的輸入庫(kù)所;工作流中的同步節(jié)點(diǎn)即Petri中的多輸人、單輸出變遷及該變遷的庫(kù)所[3]。81)開始流程:結(jié)束流程的轉(zhuǎn)化如圖1(a)所示。2)結(jié)束流程:結(jié)束流程的轉(zhuǎn)化如圖1(b)所示?! 。╝)(b)圖1信牌驅(qū)動(dòng)模型向Petri網(wǎng)的轉(zhuǎn)化Fig.1ThetransformfromtheXinpai-drivenmodeltoPetrinet3)順序流程:在信牌驅(qū)動(dòng)模型中,將其中的活動(dòng)和信牌箱分別對(duì)應(yīng)為變遷和
8、位子,就可構(gòu)造一個(gè)與之等價(jià)的Petri網(wǎng)結(jié)構(gòu)。4)競(jìng)爭(zhēng)流程:在擴(kuò)展的信牌驅(qū)動(dòng)模型中,競(jìng)爭(zhēng)流程可表示為。其中:;。將其中的活動(dòng)和信牌箱分別對(duì)應(yīng)為變遷和位子,就可構(gòu)造一個(gè)與之等價(jià)的Petri網(wǎng)結(jié)構(gòu),其中,是與對(duì)應(yīng)的元素},。5)無(wú)條件分支:它是一種并發(fā)執(zhí)行的結(jié)構(gòu)。在信牌驅(qū)動(dòng)模型中,并行流程可表示為,其中:
9、。將其中的活動(dòng)和信牌箱分別對(duì)應(yīng)為變遷和位子,就可構(gòu)造一個(gè)與之等價(jià)的Petri網(wǎng)結(jié)構(gòu)。其中:是與對(duì)應(yīng)的變遷},是與對(duì)應(yīng)的位子}(見圖2)?!D2信牌驅(qū)動(dòng)模型向Petri網(wǎng)的轉(zhuǎn)化Fig.2Thetra