（計算機應用技術(shù)專業(yè)論文）有色時間petri網(wǎng)與隨機petri網(wǎng)應用研究.pdf

有色時間p e t r i 網(wǎng)與隨機p e t r i 網(wǎng)應用研究摘要p e t r i 網(wǎng)是一種適合于描述異步并發(fā)現(xiàn)象的系統(tǒng)模型，是離散事件系統(tǒng)建模的一種強有力工具，但是在使用基本p e t r i 網(wǎng)來為復雜系統(tǒng)建模時會出現(xiàn)“節(jié)點爆炸 問題，有色時間p e t r i 網(wǎng)( c t p n ) 是克服該問題的有效途徑之一。多范式建模通過耦合和轉(zhuǎn)換以整合不同方法建立的模型來綜合利用多種形式化方法，可以全面準確地描述建模對象，可以大大的減輕仿真建模的工作量、提高整個仿真過程的效率。依據(jù)多范式建模理論，本文提出了基于規(guī)則化描述方法的c t p n 建模方法，同時發(fā)揮兩種建模方法的優(yōu)勢，有利于全面準確地反映系統(tǒng)的設(shè)計內(nèi)容，并以汽車車身控制系統(tǒng)為例為其建立模型，為復雜系統(tǒng)建模和模擬驗證提供一定的借鑒。工作流管理技術(shù)是9 0 年代初興起的軟件技術(shù)，工作流是一個業(yè)務(wù)過程的全部或部分自動執(zhí)行，為了實現(xiàn)工作流管理功能，我們必須將業(yè)務(wù)過程從現(xiàn)實世界中抽象出來，并用一種形式化方法對其進行描述，其結(jié)果稱為是工作流模型。p e t r i 網(wǎng)作為一種圖形化的數(shù)學建模工具，適合于工作流領(lǐng)域的建模需求，提出了基于廣義隨機p e t r i 網(wǎng)( g s p n ) 的工作流建模方法，將工作流模型映射為廣義隨機工作流網(wǎng)模型，并運用可達圖法對工作流正確性和可靠性進行檢查；利用g s p n 與馬爾可夫鏈的同構(gòu)關(guān)系，采用g s p n 和馬爾可夫鏈相結(jié)合的工作流性能分析方法，為工作流性能的有效評估提供理論依據(jù)：并通過實例驗證該方法的有效性。關(guān)鍵詞：有色時間p e t r i 網(wǎng)；規(guī)則化描述方法；多范式建模；工作流模型；廣義隨機p e t r i 網(wǎng)r e s e a r c ho nt h eu s eo fc o l o r e dt i m e dp e t r in e ta n ds t o c h a s t i cp e t r in e ta bs t r a c tp e t r in e ti saf o r m a l ，g r a p h i c a l ，e x e e u t a b l et e c h n i q u ef o rt h es p e c i f i c a t i o na n da n a l y s i so fc o n c u r r e n t ，d i s c r e t e e v e n td y n a m i cs y s t e m s h o w e v e r , w h e nm o d e l i n gc o m p l i c a t e dc o n t r o ls y s t e m s ，b a s i cp e t r in e tm a yl e a dt ot h ep r o b l e mo fn o d en u m b e re x p l o s i o n c o l o r e dt i m e dp e t r in e t ( c t p n ) i saw a yt os o l v et h i sp r o b l e m m u l t i p a r a d i g mm o d e l i n g ，c o n c e r n e dw i t ht h ec o u p l i n go fa n dt r a n s f o r m a t i o nb e t w e e nm o d e l sd e s c r i b e di nd i f f e r e n tf o r m a l i s m s ，c a ng i v ear e p r e s e n t a t i o no fm o d e l si nd i v e r s ef o r m a l i s m s ，a td i f f e r e n tl e v e l so fa b s t r a c t i o n ，a n dt h eb e h a v i o r c o n s e r v i n gt r a n s f o r m a t i o nb e t w e e nt h ef o r m a l i s m si sd e m o n s t r a t e d s om o d e l i n go fc t p nd e r i v e df r o mr u l ed e s c r i p t i o nm e t h o d 。w h i c ht a k e sa d v a n t a g e so ft w om o d e l i n gm e t h o d s ，i sp r e s e n t e d a n da l s ot h em e t h o di si l l u s t r a t e dt h r o u g hm o d e l i n gp r o c e s so fa u t o b o d yc o n t r o ls y s t e m ，w h i c hw i l lh e l pt om o d e l ，a n a l y z ea n ds i m u l a t ef o rc o m p l i c a t e ds y s t e m s w o r k f l o wm a n a g e m e n tt e c h n i q u e sw e r ed e v e l o p e di ne a r l y19 9 0 s w o r k f l o wi st h ea u t o m a t i o no fab u s i n e s sp r o c e s si nw h o l eo rp a r t t oa c h i e v et h ef u n c t i o no fw o r k f l o wm a n a g e m e n t ，t h eb u s i n e s sp r o c e s sm u s tb ea b s t r a c t e df r o mt h er e a lw o r l da n dd e s c r i b e db yak i n do ff o r m a lm e t h o d t h er e s u l ti sw o r k f l o wm o d e l a sak i n do fg r a p h i c a la n dm a t h e m a t i c a lm o d e l i n gt o o l s ，p e t r in e ti sa p p l i c a b l et ot h em o d e l i n gr e q u i r e m e n to fw o r k f l o w am e t h o do fm o d e l i n gf o rw o r k f l o wb a s e do ng e n e r a l i z e ds t o c h a s t i cp e t r in e t ( g s p n ) i sp r o p o s e d t h ew o r k f l o wd e f i n i t i o no fw o r k f l o wm a n a g e m e n tc o a l i t i o ni sm a p p e dt og e n e r a l i z e ds t o c h a s t i cw o r k f l o wn e t t h ev a l i d i t ya n dr e l i a b i l i t yi sc h e c k e du s i n gr e a c h a b l eg r a p hm e t h o d b yu t i l i z i n gt h ee q u i v a l e n c er e l a t i o nb e t w e e ng s p na n dm a r k o vc h a i n ，am e t h o do fc o m b i n i n gg s p na n dm a r k o vc h a i ni su s e dt oa n a l y z et h ep e r f o r m a n c eo fw o r k f l o w t h ee f f e c t i v e n e s so ft h i sm e t h o di sv e r i f i e db ya na p p l i c a t i o nc a s e k e y w o r d s ：c o l o r e dt i m e dp e t r in e t ；r u l ed e s c r i p t i o nm e t h o d ；m u l t i - p a r a d i g mm o d e l i n g ；w o r k f l o wm o d e l ；g e n e r a l i z e ds t o c h a s t i cp e t r in e t插圖目錄圖2 1p e t r i 網(wǎng)的圖形表示9圖2 2 有界p e t r i 網(wǎng)一11圖2 3 有界p e t r i 網(wǎng)的可達標識圖r g ( z ) 1 2圖2 4 數(shù)據(jù)處理的p e t r i 網(wǎng)模型1 3圖2 5 數(shù)據(jù)處理功能子網(wǎng)1 4圖3 1 車身控制系統(tǒng)軟件框架圖2 1圖3 2 樹狀層次模型2 2圖3 3 規(guī)則化描述方法的規(guī)則處理過程2 6圖3 4 基于規(guī)則化描述方法的p e t r i 網(wǎng)建模思路一2 7圖3 5 夜行燈、前照燈行為關(guān)系的p e t r i 網(wǎng)模型2 8圖3 - 6 前雨刮器行為關(guān)系的p e t r i 網(wǎng)模型3 0圖3 7 電動玻璃窗行為關(guān)系的p e t r i 網(wǎng)模型3 1圖4 1 工作流管理系統(tǒng)特性3 7圖4 2 廣義隨機p e t r i 工作流網(wǎng)的4 種路由結(jié)構(gòu)4 l圖4 3 某印刷包裝企業(yè)生產(chǎn)流程圖4 4圖4 4 圖4 3 映射得到的廣義隨機工作流網(wǎng)4 4圖4 5 圖4 4 同構(gòu)的馬爾可夫鏈4 4表格目錄表3 1 規(guī)則化描述方法和p e t r i 網(wǎng)建模的比較2 7表3 2 圖3 5 模型中元素含義2 8表3 3 圖3 - 6 模型中元素含義3 0表3 4 圖3 7 模型中元素含義3 2i v獨創(chuàng)性聲明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以標注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得金魍王些盔堂或其他教育機構(gòu)的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意。、一，學位論文作者簽名：j簽字日期：a 一7 事；習3ln學位論文版權(quán)使用授權(quán)書本學位論文作者完全了解金目墾王些太堂有關(guān)保留、使用學位論文的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復印件和磁盤，允許論文被查閱和借閱。本人授權(quán)盒壁至絲太堂可以將學位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存、匯編學位論文。( 保密的學位論文在解密后適用本授權(quán)書)、_ ，學位論文作者簽名：j簽字日期：函時 葛學位論文作者畢業(yè)后去向：工作單位：通訊地址：導師簽名：簽字日期：電話：郵編：1 ) 耖硼t ，夕；3致謝本文是在導師陸陽教授的嚴格要求和悉心指導下完成的。在兩年半的研究生學習期間，陸老師對我的學習和生活均關(guān)心備至，傾注了大量的心血，使我在各方面均有長足的進步。陸老師活躍的學術(shù)思想，淵博的知識，堅韌的毅力，忘我的工作態(tài)度，嚴謹?shù)墓ぷ髯黠L，對事物敏銳的觀察力都令我欽佩不已，給我留下了深刻的印象。陸老師對我的鼓勵和幫助，將使我終生受益。值此論文完成之際，謹向?qū)熤乱灾孕牡母兄x。感謝d e c s j x 組的所有成員，小組討論時大家的發(fā)言給了我啟發(fā)和靈感；感謝我的同學楊晴晴、郭智奇以及其他實驗室成員，他們在生活和學習上都給了我很大的幫助與鼓勵。感謝其他老師和同學在我攻讀碩士學位期間給予我無私的幫助和友情。同時，我要感謝父母和其他家人對我的支持和關(guān)愛，是他們在背后默默的支持使我能順利的完成碩士研究生的學業(yè)。最后，真誠地感謝有關(guān)專家和學者對本文的評閱和指導。作者：丁峰2 0 0 9 年0 3 月1 1 課題研究背景及目的第一章緒論p e t r i 網(wǎng)是最近十幾年來發(fā)展較為迅速的一種離散事件系統(tǒng)( d e s ：d i s c r e t ee v e n ts y s t e m ) 形式化建模方法，具有很強的描述能力。首先，作為一種圖形化數(shù)學工具，它能對d e s 中的異步、并發(fā)、沖突等重要特征進行直觀描述，并進行分析和研究；其次，作為一種邏輯層次的建模工具，p e t r i 網(wǎng)具有很強的綜合能力，適用于研究邏輯層次上的系統(tǒng)控制和控制作用下的系統(tǒng)行為問題。近年來，為了滿足科學研究和實際應用的需要，p e t r i 網(wǎng)得到了較快的發(fā)展，并出現(xiàn)了有色p e t r i 網(wǎng)、時間p e t r i 網(wǎng)、隨機p e t r i 網(wǎng)等新的子類，p e t r i 網(wǎng)的應用也愈加廣泛。然而，p e t r i 網(wǎng)在為復雜系統(tǒng)建模時會出現(xiàn)“節(jié)點爆炸 問題?；緋 e t r i 網(wǎng)中托肯只計個數(shù)不計個性，對個體變化細節(jié)描述過多，導致模型中庫所節(jié)點過多，缺乏描述組合效果的能力，也限制了基本p e t r i 網(wǎng)的抽象能力和直接模擬復雜過程的能力。有色p e t r i 網(wǎng)通過對托肯著色使其有了個性，是解決復雜系統(tǒng)p e t r i網(wǎng)模型節(jié)點過多問題的有效途徑之一。復雜系統(tǒng)往往有多個異構(gòu)系統(tǒng)組成，在分析和設(shè)計的各個階段也需要不同的形式化方法來描述系統(tǒng)，每一種建模方法都有自身的優(yōu)點和缺點、描述現(xiàn)實世界的不同角度。多范式建模( m u l t i p a r a d i g mm o d e l i n g ) 通過耦合和轉(zhuǎn)換以整合不同方法建立的模型綜合利用多種形式化方法，建模可以在不同抽象級別從不同角度描述現(xiàn)實世界，充分發(fā)揮每種描述方法的優(yōu)勢，更全面、準確地對現(xiàn)實世界建模弘j 。規(guī)則化描述方法( r d m ：r u l ed e s c r i p t i o nm e t h o d ) 【3j 參考智能控制分層模塊化思想，結(jié)合離散事件控制系統(tǒng)的特點，提出一種更直觀、更貼近系統(tǒng)本原的基于對象的分層模型。它是通過構(gòu)建一條一條的邏輯規(guī)則表達式描述各對象之間的行為邏輯關(guān)系。但是規(guī)則庫本身是靜態(tài)的知識描述，模擬執(zhí)行需要額外的控制策略，驗證比較困難。p e t r i 網(wǎng)能夠動態(tài)運行有利于模型的模擬執(zhí)行和分析，具備一套嚴密的數(shù)學理論，各種技術(shù)有利于驗證和分析。鑒于此，本文提出了基于規(guī)則化描述的有色時間p e t r i 網(wǎng)建模方法，同時發(fā)揮兩種建模方法的優(yōu)勢，有利于全面準確地反映系統(tǒng)的設(shè)計內(nèi)容。汽車車身控制系統(tǒng)用于對車身上諸如車燈、雨刮器、電動玻璃窗等各種器件進行方便靈活的控制，是一種典型的d e s 。傳統(tǒng)上依靠復雜的線束來連接眾多電器，成為汽車主要故障源之一，近年來在中高檔汽車上正逐漸被由現(xiàn)場總線連接的車身控制模塊所取代。其方法是把各種器件連接到分布于車身中的多個智能控制節(jié)點上，每個智能控制節(jié)點都是擁有一定計算和存儲資源的嵌入式處理單元。智能控制節(jié)點通過總線連接在一起，通過智能控制節(jié)點中的軟件來實現(xiàn)對各種器件的綜合控制，也即用軟件邏輯取代傳統(tǒng)車身控制系統(tǒng)中的硬件邏輯，具有更好的靈活性和易維護性1 4 。如何對車身控制系統(tǒng)進行建模和仿真是其研究的重要內(nèi)容，采用形式化方法建模和分析這類復雜實時系統(tǒng)可以減少設(shè)計和開發(fā)過程中的錯誤，提高系統(tǒng)運行的可靠性和安全性。但是由于沒有哪一種建模方法可以說是最好的或者適合任何情況和需求的，依據(jù)多范式建模思想，以車身控制系統(tǒng)為例，闡述了基于規(guī)則化描述方法的c t p n 建模的優(yōu)勢。工作流技術(shù)是2 0 世紀9 0 年代初隨業(yè)務(wù)流程重組( b p r ：b u s i n e s sp r o c e s sr e e n g i n e e r i n g ) 而興起的，該技術(shù)可以被廣泛地應用于企業(yè)的過程建模，是實現(xiàn)流程執(zhí)行和控制管理的一條有效途徑。國際工作流管理聯(lián)盟( w f m c ：w o r k f l o wm a n a g e m e n tc o a l i t i o n ) 對工作流的定義：工作流是指整個或部分經(jīng)營過程在計算機支持下的全自動或半自動化。工作流管理系統(tǒng)指的是一個能定義、創(chuàng)建和管理工作流的軟件系統(tǒng)。工作流建模是工作流管理系統(tǒng)具有的基本功能，其主要完成對目標系統(tǒng)業(yè)務(wù)過程的抽象表示 5 6 】。許多工作流管理系統(tǒng)缺乏直觀性，且不具備仿真功能，不能對工作流性能進行有效的分析。這些問題都需要有一種有效的數(shù)學化建模方法。研究人員提出過各種工作流的建模方法，如基于活動網(wǎng)絡(luò)的工作流模型，基于語言行為理論的工作流模型，基于p e t r i 網(wǎng)的工作流模型等。當考慮的工作流過程較為復雜，如存在并發(fā)、沖突等情況時，采用高層次的形式描述模型p e t r i網(wǎng)更為實用。p e t r i 網(wǎng)是一種圖形化的數(shù)學建模工具。一方面它可以用圖形化方式來描述工作流，另一方面它的形式化分析技術(shù)可用于檢查工作流的正確性和可靠性，甚至進行性能分析【7 s 】。本文的又一目的在于將隨機p e t r i 網(wǎng)技術(shù)引入到工作流的建模當中，并利用隨機p e t r i 網(wǎng)理論及其與馬爾可夫鏈的同構(gòu)關(guān)系來分析工作流，為工作流性能的有效評估提供理論依據(jù)，并通過實例驗證該方法的有效性。印刷包裝企業(yè)的生產(chǎn)工藝流程復雜，有膠印、凹印、絲印、柔印、凹凸、燙金和模切等多道工藝；每一道工藝都有很多不同型號的設(shè)備，設(shè)備的局限性比較大、通用性很差；包裝產(chǎn)品的品種、規(guī)格、技術(shù)要求等變化都很大。所以包裝印刷生產(chǎn)過程涉及許多不同的作業(yè)，不同的作業(yè)按照一定的工藝順序交替進行。包裝印刷生產(chǎn)系統(tǒng)是一個典型的動態(tài)離散事件系統(tǒng)，它具有d e s 特征，是事件驅(qū)動，在空間和時間上是離散的，并且是異步不確定的。本文以某印刷包裝企業(yè)的生產(chǎn)流程為例，建立其工作流程的廣義隨機p e t r i工作流網(wǎng)模型，利用g s p n 與馬爾可夫鏈的同構(gòu)關(guān)系，得到其對應的馬爾可夫鏈，基于馬爾可夫鏈的穩(wěn)定狀態(tài)概率進行所要求的系統(tǒng)性能分析，得到工作流模型的時間性能和變遷利用率等指標，可以規(guī)范企業(yè)的業(yè)務(wù)流程，發(fā)現(xiàn)其中的不合理環(huán)節(jié)，進而對企業(yè)的業(yè)務(wù)過程進行優(yōu)化重組，所建立的業(yè)務(wù)過程模型本身就2是企業(yè)非常需要的知識庫和規(guī)則庫。1 2 國內(nèi)外研究概況p e t r i 網(wǎng)的概念最早是在1 9 6 2 年c a r la d a mp e t r i 的博士論文中提出來的。從l9 8 0 年召開第一次p e t r i 網(wǎng)理論和應用的國際研討會以來，每年一次的國際研討會連續(xù)不斷，p e t r i 網(wǎng)理論和應用在不斷的充實和完善。它的縱向發(fā)展表現(xiàn)為：從基本的條件事件網(wǎng)，經(jīng)過位置變遷網(wǎng)，發(fā)展到高級網(wǎng)( h l p n ：h i g h l e v e lp e t r in e t s ) 。它的橫向發(fā)展表現(xiàn)為：從沒有參數(shù)的網(wǎng)發(fā)展到時間p e t r i 網(wǎng)和隨機p e t r i網(wǎng)；從一般有向弧發(fā)展到禁止弧和可變弧；從自然數(shù)標記個數(shù)到概率標記個數(shù)；從原子變遷發(fā)展到謂詞變遷和子網(wǎng)變遷；另外還有引入控制策略的受控p e t r i 網(wǎng)、引入知識表示的模糊p e t r i 網(wǎng)等p e t r i 網(wǎng)變形模型。p e t r i 網(wǎng)具有動態(tài)、并發(fā)和圖形直觀性等良好特性。因此，p e t r i 網(wǎng)作為系統(tǒng)模擬與分析的有效工具已在眾多領(lǐng)域得到廣泛應用。但是在建模復雜系統(tǒng)時出現(xiàn)的節(jié)點爆炸問題卻使工程人員望而卻步。高級p e t r i 網(wǎng)通過引入更高層次的觀念來解決這個問題。更高層次的觀念包括利用復雜數(shù)據(jù)結(jié)構(gòu)的托肯、利用代數(shù)表達式來代表網(wǎng)元素等【9 1 。高級p e t r i 網(wǎng)通過對網(wǎng)系統(tǒng)中的標志進行分類和解析，使網(wǎng)系統(tǒng)的基本元素減少，從而達到縮小網(wǎng)系統(tǒng)規(guī)模的目的。比較成熟的高級p e t r i 網(wǎng)主要有兩種：有色p e t r i 網(wǎng)和謂詞變遷p e t r i 網(wǎng)。高級p e t r i 網(wǎng)并不比原型p e t r i網(wǎng)有更強的模擬能力，但是它可以使網(wǎng)模型更加簡單、清晰一些【l0 1 。多范式建模的關(guān)鍵問題在于如何整合不同的模型，使數(shù)據(jù)和信息能夠在在不同模型間自由地流動 1 1 】，其解決方法主要有兩種：其一是使用一種一般標準語言作為接口語言；其二是使用元模型為建模方法建立統(tǒng)一的模型。b p z e i g l e r 于1 9 7 6 年在t h e o r yo f m o d e l i n ga n ds i m u l a t i o n ) ) 中提出了d e v s( d i s c r e t ee v e n ts y s t e ms p e c i f i c a t i o n ) 理論，以規(guī)范d e s 的各種形式化建模方法，并提供各種形式化方法建模和仿真的框架【l2 1 ，使離散事件系統(tǒng)的模型可以與連續(xù)系統(tǒng)的微分方程模型一樣進行數(shù)學化操作 1 3 1 。由于d e v s 支持連續(xù)的時間基、能夠很好地實現(xiàn)分層模塊化以及面向?qū)ο蟮乃枷?，所以在離散事件系統(tǒng)建模領(lǐng)域很受關(guān)注。目前研究d e v s 比較活躍的團體主要有美國亞利桑那州州立大學建模仿真綜合中心( a c i m s ：a r i z o n ac e n t e rf o ri n t e g r a t i v em o d e l i n ga n ds i m u l a t i o n ) 、麥吉爾大學建模、仿真和設(shè)計實驗室( m s d l m o d e l i n g ，s i m u l a t i o na n dd e s i g nl a b ) 以及韓國先進科學技術(shù)學院( k a i s t ：k o r e aa d v a n c e di n s t i t u t eo fs c i e n c ea n dt e c h n o l o g y ) 等。d e v s 優(yōu)勢在于對系統(tǒng)組成結(jié)構(gòu)、通信機制、時間概念的支持；劣勢是它一種貧語義的系統(tǒng)描述、缺乏系統(tǒng)行為的描述【l 引。正因為如此，將自動機、p e t r i 網(wǎng)等在描述系統(tǒng)行為方面有優(yōu)勢的形式化方法嵌入d e v s 也是必要的。工作流技術(shù)是2 0 世紀9 0 年代興起的，被廣泛的應用于企業(yè)的過程建模。1 9 9 33年國際工作流管理聯(lián)盟成立，在工作流管理系統(tǒng)的相關(guān)術(shù)語、體系結(jié)構(gòu)及應用編程接口等方面制定了一系列標準，并給出了工作流定義，標志著工作流的研究進入相對成熟的階段。在國外的研究成果中，比較著名的有i b m 公司a l m a d e n 研究中心研究開發(fā)的基于持久消息隊列的分布式工作流管理系統(tǒng)一e x o t i c a f m q m 【f l o wm a r k o nm e s s a g eq u e u em a n a g e r ) 、佐治亞大學計算機系研究開發(fā)的具有自適應能力的工作流管理系統(tǒng)一m e t e o r ( m a n a g i n ge n d 2 t 0 2 e n do p e r a t i o n s ) 、基于分布式主動數(shù)據(jù)庫技術(shù)的工作流管理系統(tǒng)一w i d e ( w o r k f l o wo ni n t e l l i g e n ta n dd i s t r i b u t e dd a t a b a s ee n v i r o n m e n t ) 以及基于狀態(tài)與活動圖的工作流管理系統(tǒng)一m e n t o r( m i d d l e w a r ef o re n t e r p r i s e 2 w i d ew o r k f l o wm a n a g e m e n t ) 。相對于國外工作流技術(shù)的研究和發(fā)展，我國對工作流技術(shù)的研究還處于起步階段，自主開發(fā)的工作流產(chǎn)品還是一個空白，在國外的工作流產(chǎn)品的引進和消化方面的工作也十分欠缺。目前在國內(nèi)一些大學，如清華大學、西北大學、浙江大學、上海交通大學都己開展了對工作流技術(shù)的研究工作。其中，清華大學范玉順教授設(shè)計、開發(fā)了c i m f l o w 工作流管理系統(tǒng)，提出了c i m f i o w 工作流模型；史美林教授帶領(lǐng)的課題組提出了一個基于w w w 的通用工作流管理系統(tǒng)：w o w w w w o r k f l o wo nth ew o r l dw i d ew e b ，并將其與傳統(tǒng)的c s c w 技術(shù)結(jié)合起來；浙江大學研制了工作流過程描述語言w p d l ( w o r k f l o wp r o c e s sd e f i n i t i o nl a n g u a g e ) ，實現(xiàn)了編譯制導的工作流建模支撐平臺；西安協(xié)同軟件公司與西北大學合作開發(fā)的s y n c h o f l o w ，作為一個過程管理平臺，其流程的定義方面已經(jīng)達到了業(yè)界領(lǐng)先的水平，基于j 2 e e 的實現(xiàn)，使得系統(tǒng)具有足夠的集成能力這些都取得了良好的研究成果。工作流建模是工作流管理系統(tǒng)具有的基本功能，其主要完成對目標系統(tǒng)業(yè)務(wù)過程的抽象表示。w i n o g r a d 與f l o r e s 在語言行為理論的基礎(chǔ)上提出了一種基于對話的工作流模型【l5 】 16 1 ，這種工作流模型是從客戶方與服務(wù)方這兩個角色之間的語言行為交互上對工作流過程進行定義的。p e t r i 網(wǎng)也被用來建立工作流模型，v a n d e ra a l s t 用有色時間p e t r i 網(wǎng)對活動時間固定的工作流的一些時間特性作了分析【l7 】；李建強將工作流網(wǎng)分解成代表事件的t - 圖，通過t - 圖分析了工作流模型的時間性能、資源利用率等動態(tài)特性【1 8 】；c h i o l a 和m a r s a n 在p e t r i 網(wǎng)理論上給出了廣義隨機p e t r i 網(wǎng)的定義【1 9 1 ；m o l l y 驗證了轉(zhuǎn)移觸發(fā)時間服從指數(shù)分布的隨機p e t r i 網(wǎng)和馬爾可夫鏈具有等價關(guān)系【z o j ；w a n gj i a c u n 將這一論證推廣到廣義隨機p e t r i 網(wǎng)中1 | ，為隨機p e t r i 網(wǎng)應用于模型性能分析鋪平了道路。1 3 課題研究的關(guān)鍵問題及解決方法( 1 ) 依據(jù)多范式建模的思想，結(jié)合規(guī)則化描述方法和p e t r i 網(wǎng)建模各自的特點，提出了如下建模過程：控制策略通過規(guī)則化描述方法抽象描述易得其規(guī)則4式系統(tǒng)，規(guī)則式系統(tǒng)通過編譯實現(xiàn)可以直接生成控制程序。如果控制策略的規(guī)則式系統(tǒng)非常復雜，難于發(fā)現(xiàn)其中的沖突等不安全因素，則可以將規(guī)則式系統(tǒng)轉(zhuǎn)化為p e t r i 網(wǎng)模型來驗證，進而完善規(guī)則式系統(tǒng)。( 2 ) 根據(jù)車身控制系統(tǒng)的特點選擇建模工具。汽車車身控制系統(tǒng)是規(guī)模較大的d e s ，器件的狀態(tài)多樣，器件之間的行為關(guān)系較復雜，規(guī)則式中存在延時因子。有色p e t r i 網(wǎng)由于其庫所和變遷包含復雜的信息，克服了普通p e t r i 網(wǎng)的不足，特別適合于復雜系統(tǒng)的建模。因此選用了有色p e t r i 網(wǎng)作為建模的工具，并根據(jù)系統(tǒng)的特點，引入了時間變遷和類似于受控p e t r i 網(wǎng)中的控制庫所來進行方便、靈活的控制。建模過程遵循常用的步驟：先將復雜系統(tǒng)分解為若干個子系統(tǒng)，對每個子系統(tǒng)單獨構(gòu)建p e t r i 網(wǎng)模型，然后通過p e t r i 網(wǎng)合成運算得到整個系統(tǒng)的模型。( 3 ) 工作流模型到隨機p e t r i 網(wǎng)模型的映射以及系統(tǒng)時間性能和資源利用率的評價。工作流是基于事例的，它的每一部分就是執(zhí)行一個特定的事例，一個工作流包括一組活動，以及它們之間的相互關(guān)系，還包括活動的啟動和終止條件，以及對每個活動的描述。通過用p e t r i 網(wǎng)的變遷表示活動、庫所表示活動觸發(fā)的條件( 活動需要占用一些資源) 、托肯表示事例映射建立工作流的隨機p e t r i網(wǎng)模型。描繪出隨機p e t r i 網(wǎng)模型的可達圖，得出與其同構(gòu)的馬爾科夫鏈，即為系統(tǒng)性能和資源利用率的評價做好了充足的準備。隨機p e t r i 網(wǎng)為系統(tǒng)的性能模型提供良好的描述手段；馬爾可夫鏈為模型的評價提供堅實的數(shù)學基礎(chǔ)。52 1p e t r i 網(wǎng)基本概念第二章p e t r i 網(wǎng)理論基礎(chǔ)2 1 1p e t r i 網(wǎng)的直觀理解p e t r i 網(wǎng)由c a r la d a mp e t r i 于1 9 6 2 年在他的博士論文【2 2 】中提出，是理論計算機科學包括自動機模型和形式語言理論的一個分支。p e t r i 網(wǎng)是一種形式化模型描述方法，它用四個元素為系統(tǒng)建模，分別是：庫所( p l a c e )變遷( t r a n s i t i o n )弧( a r e )托肯( t o k e n ) 。它用庫所、變遷、弧的連接表示系統(tǒng)的靜態(tài)功能和結(jié)構(gòu)，通過變遷點火和托肯的移動描述系統(tǒng)的動態(tài)行為【23 1 。p e t r i 網(wǎng)模型是狀態(tài)變遷模型，可用來描述系統(tǒng)中各異步成分之間的關(guān)系，同時允許同時發(fā)生多個狀態(tài)變遷，也是一個并發(fā)模型。在分析系統(tǒng)的狀態(tài)行為的技術(shù)中，p e t r i 網(wǎng)模型具有自然、直觀、簡單易懂等特點，在并行系統(tǒng)分析、協(xié)議的驗證、自動控制等方面有廣泛的應用【2 4 1 。用p e t r i 網(wǎng)描述的系統(tǒng)有一個共同的特征：系統(tǒng)的動態(tài)行為表現(xiàn)為資源( 物質(zhì)資源和信息資源) 的流動。在給出p e t r i 網(wǎng)( p n ) 形式描述之前，通過分布式系統(tǒng)幾個基本行為模型描述的例子，先對p e t r i 網(wǎng)作一個直觀的說明。庫所用于描述可能的系統(tǒng)局部狀態(tài)，例如：計算機和通信系統(tǒng)的隊列、緩沖、資源等。變遷用于描述修改系統(tǒng)狀態(tài)的事件，例如：計算機和通信系統(tǒng)的信息處理發(fā)送、資源的存取等?；⊥ㄟ^其指向來規(guī)定局部狀態(tài)和事件之間的關(guān)系：它們表述局部狀態(tài)對事件的觸發(fā)以及由事件所引發(fā)的局部狀態(tài)的轉(zhuǎn)換。在p e t r i 網(wǎng)模型中，托肯包含在庫所中，它們在庫所中的動態(tài)的變化表示系統(tǒng)的不同狀態(tài)。如果一個庫所描述一個條件，它能包含或不包含一個托肯，當一個托肯表現(xiàn)在這個庫所中，條件為真；否則為假。如果一個庫所定義一個狀態(tài)，在這個庫所中的托肯個數(shù)用于規(guī)定這個狀態(tài)。例如：在計算機和通信系統(tǒng)中，托肯可以用于表示處理的信息單元、資源單元和顧客、用戶等對象實體。一個p e t r i 網(wǎng)模型的動態(tài)行為是由它的發(fā)生規(guī)則規(guī)定的，當使用等于l 的弧權(quán)時，如果一個變遷的所有輸入庫所( 這些庫所連接到這個變遷，弧的方向是從庫所到變遷) 至少包含一個托肯，那么這個變遷可能發(fā)生( 相關(guān)聯(lián)的事件發(fā)生) 。對這種情況，這個變遷稱為可發(fā)生的。一個可發(fā)生的變遷導致從它所有的輸入庫所中清除一個托肯，在它的每個輸出庫所( 這些庫所連接到這個變遷，弧的方向從標遷到庫所) 中產(chǎn)生一個托肯。當使用大于l 的弧權(quán)時，在變遷的每一個輸入庫所中都要包含至少等于連接弧權(quán)的托肯個數(shù)，它才可以實施：這個變6遷的發(fā)生將清除在該變遷的每一個輸入庫所的相應的托肯個數(shù)，并在變遷的每一個輸出庫所產(chǎn)生相應的托肯個數(shù)。變遷的發(fā)生是一個原子操作，清除輸入庫所的托肯和在輸出庫所產(chǎn)生托肯是一個不可分割的完整操作。2 1 2p e t r i 網(wǎng)的形式化定義定義2 1 ：p e t r i 網(wǎng)( p 舯( 或者簡稱網(wǎng))剛是一個三元組，即剛= ( 只t ，f ) ，其中：1 )p = 0 。，p ：，p 。) 為有限的庫所集，刀= i 叫為庫所個數(shù)：2 ) t = o 。，f 2 ，t 。) 為有限的變遷集，m = i 卅為變遷個數(shù)；3 ) p l qt = g ，即庫所集合p 和變遷集合丁不相交；put 囝，即庫所集合p 和變遷集合丁不同時為空；4 )f ( e x r ) up j p ) 為流關(guān)系，也即弧集合；5 ) a o m ( e ) uc o d ( f ) = p ur，即沒有孤立元素。其中d o m ( f ) = x i 砂：( x ，y ) f ) ，c o a ( r ) = 抄i s x ：( j ，y ) ，) 分別為f 的定義域和值域；6 ) 集合x = p ut 是網(wǎng)元素的集合。定義2 2 ：前置集( p r e s e t ) 、后置集( p o s t s e t )令p n = ( p ，t ，f ) 是一個網(wǎng)，x = p u t 為其元素集合，且x x ，那么x 的前置集，g ) 、后置集o ( x ) 分別為，g ) = i ，工) ，) ，d g ) = dl0 ，y ) f ) 。如果墨ex ，則i ( x t ) = u ，( 工) ，d ( x i ) = uo ( x )定義2 3 - t 函e 數(shù)( c a p a c i t yf u x n e c x u 。o n ) 、標識( m a r k i n g ) 、權(quán)函數(shù)記n o = o ，1 ，2 ， ，n = 1 ，2 ，3 ， ，并以c o 表示無窮：國= 彩+ 1 = c o 1 = 國+ 國，以上定義均對p n = ( p ，t ，f ) 而言。( 1 ) k ：p _ n u 斟稱為庫所容量函數(shù)，容量表示每個庫所存儲資源的最大數(shù)量，但它不是當前的實際資源數(shù)；( 2 ) 對于給定的容量函數(shù)k ，m ：p - - n o 稱為戶的一個標識的條件是：砌p ：m ( p ) k ( p ) ，它表示該庫所的狀態(tài)，所有庫所的狀態(tài)綜合起來反映了系統(tǒng)的狀態(tài)；( 3 ) w ：f n 稱為p 上的權(quán)函數(shù)，定義2 4 ：關(guān)聯(lián)矩陣c 、s 不變量、令p a r = ( p ，t ，f ) 是一個網(wǎng)，令：p o s t = c + 【，f 】- 形g ，p f )p r e = c 一】= ( a ，t j )c = p o s t p r ei = 1 ，2 ，n ；n = l d ；，= 1 , 2 ，m ；m = l 糾。它用來表示資源消耗量或生產(chǎn)量。弘不變量c 腳稱為刖的關(guān)聯(lián)矩陣，其矩陣元素：7c 忉f ，t j = 礦【f ，p fj 一礦p ，t j一個n 元整數(shù)列向量x 稱為p n 的一個s 不變量的充分必要條件：c x x = 0 ；一個攤元整數(shù)列向量y 稱為刪的一個t 不變量的充分必要條件：c rx y = 0 。定義2 5 ：p e t r i 網(wǎng)系統(tǒng)( )六元組= ( p ，t ，f ，k ，w ，眠) 構(gòu)成網(wǎng)系統(tǒng)的條件是：1 )p = ( p ，t ，尸) 構(gòu)成有向網(wǎng)，稱為的基網(wǎng)。2 ) x ，矽，m 。分別為p 上的容量函數(shù)、權(quán)函數(shù)和初始標識( i n i t i a lm a r k i n g ) 。p e t r i 網(wǎng)可用一個有向二元圖表示，其中含有兩類節(jié)點，并用有向弧連接起來。這兩類節(jié)點分別是網(wǎng)的庫所和變遷，弧是庫所和變遷組成的有序偶。p e t r i網(wǎng)的標準圖形表示是用圓圈0 代表庫所，用矩形口來表示變遷( 若變遷是瞬時的，則用i 表示) ，用黑點來表示庫所中含有的托肯，從節(jié)點x 至l j y 的箭頭( 有向弧) 表示有序偶( z ，y ) ( ( x ，y ) f ) 。對于弧廠f ，w ( f ) 1 時，將w ( f ) 標注在弧上。根據(jù)k 函數(shù)的取值可將p e t r i 網(wǎng)分為無界網(wǎng)和有界網(wǎng)。對于無界網(wǎng)，當一個庫所的容量有限時，通常將k ( p ) 寫在庫所的圓圈旁邊；當k ( p ) = 一時，通常省略k ( p ) 的標注。有界p e t r i 網(wǎng)系統(tǒng)的k 函數(shù)為k ：p 寸n ，當k ( p ) = 1 時，省略k ( p ) 的標注。庫所p ，中托肯的數(shù)量膨0 ，) 用黑點的個數(shù)來表示。標識膨是托肯在庫所中的一種分布，用一個行向量m = 瞰幻。) ，m 0 ：) ，m 。) 】來表示。2 1 3p e t r i 網(wǎng)變遷的發(fā)射規(guī)則定義2 6 ：變遷的使能和觸發(fā)( e n a b l i n ga n df i r i n g )= ( p ，t ，f ，k ，w ，m o ) 是一個p e t r i 網(wǎng)系統(tǒng)。1 ) 一個變遷t t 在標識肘下是使能的當且僅當：v p p ，w ( p ，f ) m ( p ) k 0 ) w ( t ，p ) 。2 1 變遷t t 在標識m 下是使能的，在t i c , 發(fā)后產(chǎn)生一個新的后繼標志m 7 ，可由下列方程給出：v pep ：m 7 ( p ) = m ( p ) 一w ( p ，f ) + 矽( f ，p ) = m ( p ) + c ，t ) ，實際上t 的觸發(fā)僅對其前置集z ( x ) 、后置集o ( x ) 中的托肯數(shù)量有影響。也可用如下式表示：m 侈) =m ( p ) 一形0 ，f )m ( p ) + 形( f ，p )m 0 ) 一w b , ，f ) + 矽o ，p )m 0 )p ，( f ) ，p 芒o ( t )p d ( ) ，p 名i ( t )p ei ( t ) f ) o ( t )o t h e r w i s e3 ) 系統(tǒng)標識m 經(jīng)過f 的觸發(fā)得到新的標識m 7 ，可以表示成m t ) m 。定義2 7 ：觸發(fā)序列= ( p , t ，f ，k ，w ，m o ) 是一個p e t r i 網(wǎng)系統(tǒng)。盯= m o t l m l t 2 t m 。是的一個有限觸發(fā)序列當且僅當：v i ：i f 甩：m hk ) m 引叫= ，z 是仃的長度。f t 2 t n 為變遷觸發(fā)序列。p lt tp 2t 2融m 2 - 1 給出的是p e t r i 網(wǎng)= ( p ，t ，f ，k ，w ，m 。) 的圖形表示。其中：p = p 1 p 2 。p 3 。p 4 p s p 6 p 7 1t = t l ，t 2 ，t df 2 ( p 1 t o ( t 1 p 2 ) 。( t h p 4 ) ( p 2 。t 2 ) 。( t 2 p 3 ) ( p 4 t 3 ) ( p 6 t 3 ) ( t 3 p s ) ( t 3 。p 7 ) ( p 5 。t 2 ) i t 0 = pl l l t 2 、= p 2 i t 3 ) = p 4 p do a o = p 2 , p 4 夕o ( t 2 ) = p 3 o ( t 3 ) = p5 p z w ( p t 。t 1 ) = 1 w ( t l ，p 2 ) = 1 w ( p 4 t 3 ) = 2 t f ，110l000 、l 三：二。三二：j2 2p e t r i 網(wǎng)主要性質(zhì)本節(jié)將介紹p e t r i 網(wǎng)的幾個重要性質(zhì)：可達性( r e a c h a b i l i t y ) 、活性( l i v e n e s s )和死鎖( d e a d l o c k ) 、沖突( c o n f l i c t ) 、有界性( b o u n d n e s s ) 和安全性( s a f e n e s s ) 。( 1 ) 可達性l z 糾：任意給定一個標識判定它是否從初始標識出發(fā)可達的問題就是可達性問題，它是p e t r i 網(wǎng)中一個基本的問題，p e t r i 網(wǎng)的其他性質(zhì)都是基于可達性討論的。定義：設(shè)= ( p ，t ，f ，m ) 為一個p e t r i 網(wǎng)。如果存在t t ，使m t ) m ，則稱m 為從m 直接可達。如果存在變遷序列，如和標識序列9m 。，m ：。m 。使得m t 1 ) m 。 f ：) m 2 坂一。 心則稱以為從肘可達的。( 2 ) 活性與死鎖：如果不論標識如何演化，一個變遷總有被激發(fā)的可能，則稱該變遷是活的。如果不論標識如何演化，網(wǎng)內(nèi)都不存在不可激發(fā)的變遷，則稱該p e t r i 網(wǎng)是活的。一個死鎖是一個標識。從該標識不再有任何變遷使能?；钚院退梨i的性質(zhì)，是一種非結(jié)構(gòu)的性質(zhì)，依賴于網(wǎng)的初始。死鎖問題是離散事件動態(tài)系統(tǒng)監(jiān)控理論的一個重要問題，一個死鎖的系統(tǒng)也就失去了研究的意義 2 6 1 。( 3 ) 沖突：沖突反映了系統(tǒng)資源的競爭狀況【2 7 】，一個結(jié)構(gòu)沖突指一個至少有兩個變遷的變遷集合，集合中的變遷具有公共的輸入庫所尸。一個有效沖突指存在一個結(jié)構(gòu)沖突和一個標識，在該標識下，處于結(jié)構(gòu)沖突中的變遷的共同輸入庫所p 的托肯數(shù)少于被該標識使能的p 的輸出變遷的加權(quán)數(shù)。( 4 ) 有界性與安全性【2 8 】：有界性反映的是一個庫所在p e t r i 網(wǎng)運行過程中所能獲得的最大托肯數(shù)，它與p e t r i 網(wǎng)的初始標識有關(guān)。一個庫所p 對一個初始標識而言是有界的，如果存在一個自然數(shù)k ，使得從眠出發(fā)的所有可達標識中，尸的托肯數(shù)不大于k ，稱尸為k 一有界。一個p e t r i 網(wǎng)，若所有的庫所對螈是有界的，則該p e t r i 網(wǎng)對初始標識螈而言是有界的。若p e t r i 網(wǎng)中，所有的庫所是k 一有界，貝j j p e t r i 網(wǎng)是后一有界的。如果正整數(shù)k = 1 ，則稱該p e t r i 網(wǎng)是安全的。2 3p e t r i 網(wǎng)分析方法對于一些簡單的網(wǎng)系統(tǒng)，通過運行( 或者說仿真) 可以觀察出它的一些性質(zhì)。但對于較復雜的系統(tǒng)，用觀察運行的方法來確定其性質(zhì)難免會掛一漏萬。網(wǎng)論為p e t r i 網(wǎng)提出了一些分析方法，如可達標識圖與可覆蓋樹，關(guān)聯(lián)矩陣與狀態(tài)方程，p e t r i 網(wǎng)語言與分析化簡規(guī)則等。這些方法各自有其優(yōu)點和不足之處，本節(jié)介紹常見的可達標識圖與可覆蓋樹，關(guān)聯(lián)矩陣與狀態(tài)方程兩種方法。2 3 1 可達標識圖與可覆蓋樹對于有界p e t r i 網(wǎng)，由于其可達標識集r ( m 。) 是一個有限集，因此可以以r ( m 。) 作為定點集，以標識之間的直接可達關(guān)系為弧集，構(gòu)成一個有向圖。這種有向圖稱為p e t r i 網(wǎng)的可達標識圖。通過一個p e t r i 網(wǎng)的可達標識圖可以分析這個網(wǎng)系統(tǒng)的狀態(tài)變化和變遷發(fā)生序列的情況，從而得知網(wǎng)系統(tǒng)的有關(guān)性質(zhì)。定義2 8 可達標識圖設(shè)= ( s ，t ，f ，眠) 為一個有界p e t r i 網(wǎng)。的可達標識圖定義為一個三元組r g ( z ) = ( 尺( 眠) ，e ，p ) ，其中e = ( m f ，m ，) im i ，m ，r ( m o ) ，3 氣?。簃 f 氣 m ，尸：e r ，尸( m f ，m f ) = t k 當且僅當m ， m ，稱r ( m 。) 為r g ( e ) 的頂點集，e 為r g ( z ) 的弧集；若尸( m ，m ，) = 氣，則稱t l o為弧( m ，m ，) 的旁標。例如圖2 2 所示有界p e t r i 網(wǎng)，按照定義2 8 算法，可以得出其可達標識圖2 3 。當不是有界p e t r i 網(wǎng)時，由于尺( 眠) 是一個無限集，不可能畫出的可達圖。為了用有限形式表達一個有無限狀態(tài)的系統(tǒng)運行情況，需要引入一個表示無界量的符號0 9 。c o 具有這樣的性質(zhì)：1 ) 對于任意正整數(shù)殲：c o n ，t o + n = 緲2 ) 國