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

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