（计算机软件与理论专业论文）petri网的价格建模研究.pdf

中山大学博士学位论文p e t r i 网的价格建模研究 论文题目：p e t r i 网的价格建模研究 专业：计算机软件与理论 博士生：刘显明 指导教师：李师贤教授 摘要 时间和价格是大多数应用系统模型的两项主要参数，因此如何将时间和价格 信息有效地在建模工具中表示出来并加以应用成为一个有意义的问题。目前各种 扩展了时间信息的p e t r i 网可以有效地建模系统的时间参数，但是对价格参数却 无能为力，所以为p e t r i 网扩展价格信息是一个需要解决的问题，最近已经出现 了面向网格应用模型的价格时问p e t r i 网，但是该工作的重点在于应用级q o s 建 模。另外，在自动机研究领域已经出现了价格时间自动机和权重时间自动机等工 具。这些工作为p e t r i 网的价格建模研究提供了有价值的参考。 本文首先简单介绍和归纳了p e t r i 网的基础知识以及p e t r i 网的各种扩展，以 此作为全文工作的基础。接下来重点讨论了在p e t r i 网中扩展时间信息的方式和 各种扩展了时间信息的p e t r i 网，以此作为后面讨论p e t r i 网价格建模的基础，这 是因为价格信息和时间信息有很多相似和相关之处。 本文的主要贡献与创新是：为经典p e t r i 网和时间p e t r i 网扩展了价格信息， 并且讨论了相应的语义和最小成本的可判定问题。在研究p e t r i 网时间建模的过 程中，我们发现目前的p e t r i 网扩展几乎没有考虑价格因素，所以本文尝试为经 典p e t r i 网扩展了固定价格和随机价格参数。进一步研究了经典p e t r i 网和p e t r i 网的价格扩展之间的关系，并讨论了相应的状态空间计算方法、最小成本的可判 中t 1 i 大学博士学位论文p e t r i 网的价格建模研究 定性问题和模型的简化方法。然后从应用的角度讨论了基于价格p e t r i 网的成本 模型和基于随机价格p e t r i 网的决策模型。 在分别研究了p e t r i 网的时间建模和价格建模以后，本文提出一种扩展了价 格信息的时间p e t r i 网一价格时间p e t r i 网，这样可以将时间和价格信息统一地体 现在一个模型中。证明了时间p e t r i 网是价格时间p e t r i 网的子类，并提出了两种 不同的状态空间计算方法，其中：计价状态娄方法为传统状态类扩充了累积成本， 价格时间状态类方法则讨论了从价格时间p e t r i 网到价格时间自动机的转换。然 后从应用的角度讨论了基于价格时问p e t r i 网的成本时间模型。 众所周知，经典p e t r i 网和时间p e t r i 网中只有标识和时间约束能够影响变迁 的实施。所以在( 随机) 价格p e t r i 网和价格时间p e t r i 网的讨论中我们也没有改 变这一原则。但是我们在研究基于价格p e t r i 网的应用模型过程中，发现让利润 约束来影响变迁的实施比较符合应用的环境。所以提出一种带利润约束的价格 p e t r i 网，并探讨了相应的分析技术和应用例子。 最后总结全文，并讨论和归纳了p e t r i 网中时间建模和价格建模的异同，以 及p e t r i 网的各种价格扩展之间的关系。 关键词：p e t r i 网，价格建模，时间建模，形式语义，状态空问计算，价格时间 自动机 中山大学博士学位论文 p e t t i 网的价格建模研究 t i t l e ：r e s e a r c ho nm o d e l i n gp r i c ei np e t r in e t s m a j o r ：c o m p u t e rs o t t w a r ea n d t h e o r y n a m e ：l i ux i a n m i n g s u p e r v i s o r ：p m f e s s o r l is h i x i a n a bs t r a c t t i m ea n dc o s ta r et h et w om a j o rp a r a m e t r e sf o rm o s ta p p l i c a t i o ns y s t e mm o d e l s ，s o i ti sam e a n i n g f u lt h i n gt ot a k et i m ea n dc o s ti n f o r m a t i o ni n t ot h ec o n s i d e r a t i o no f s y s t e mm o d e l i n g a tp r e s e n tt h e p e t r in e t se x t e n d e dw i t ht i m ei n f o r m a t i o na r e e f f e c t i v et o o l sf o rm o d e l i n gt h et i m ep a r a m e t r e ，b u tu n f o r t u n a t e l yn o tf o rm o d e l i n g t h ep r i c ep a r a m e t r e s oi ti si n t e r e s t i n gw o r kt oe x t e n dp e t r in e tw i t hp r i c ei n f o r m a t i o n r e c e n t l yak i n do fp r i c et i m e dp e t r in e ti sp r o p o s e df o rg r i da p p l i c a t i o ns y s t e m s ，b u t t h i sw o r kf o c u s e so nm o d e l i n gq o sr e q u i r e m e n ta tt h ea p p l i c a t i o nl e v e l a d d i t i o n a l l y t h e r ee m e r g e ss o m er e l a t e dw o r ki nt h ea r e ao ft i m e da u t o m a t a ( e g t h ep r i c e dt i m e d a u t o m a t aa n dt h ew e i g h t e dt i m e da u t o m a t a ) t h ew o r km e n t i o n e da b o v ed o e sp r o v i d e o u rr e s e a r c hw i t hv a l u a b l ea d v i c e so nm o d e l i n gp r i c ei n f o r m a t i o ni np e t r in e t s w ef i r s ti n t r o d u c es o m ec l a s s i c a lp e t r in e tc o n c e p t s ，a n ds u m m a r i z et h ec u r r e n t w o r ki ne x t e n s i o no fp e l r in e t sa st h eb a s i so ft h i sd i s s e r t a t i o n t h e nt h ee m p h a s i si s l a i do nd i s c u s s i n gt h ev a r i o u sw a y so fm o d e l i n gt i m ea n dt h ee x e n t s i o no fp e t r in e t s w i t ht i m ei n f o r m a t i o na st h eg r e a tr e f e r e n c ef o rp r i c em o d e l i n g ，b e c a u s et h e r ea r e i m p o r t a n ts i m i l a r i t i e sa n dr e l a t i o n s h i pb e t w e e nt h ep r i c ea n d t i m ei n f o r m a t i o n 中山大学博： 学位论文 p e t r i 网的价格建模研究 t h em a i nc o n t r i b u t i o no ft h i sd i s s e r t a t i o ni st oa d dp r i c ei n f o r m a t i o ni n t oc l a s s i c a l p e t r in e ta n dt i m ep e t r in e t t od i s c u s st h es e m a n t i c so ft h e s ep e t r in e t sa n dt h e m i n i m u m c o s tr e a c h a b i l i t yp r o b l e m d u r i n gt h er e s e a r c ho nm o d e l i n gt i m ei np e t r i n e t s ，w ef i n dt h a tt h e r ei s1 i t t l ew o r ki ne x t e n s i o no f p e t r in e t sw i t hp r i c ei n f o r m a t i o n t h u s ，t h i sd i s s e r t a t i o nt r i e st oa d dp r i c ei n f o r m a t i o ni nc l a s s i c a lp e t r in e t w ef i r s t d i s c u s st h er e l a t i o n s h i pb e t w e e nc l a s s i c a lp e t r in e ta n dt h ee x t e n s i o no fp e t r in e tw i t h p r i c ei n f o r m a t i o n t h e nw es u g g e s tt h ew a yt oc o m p u t es t a t es p a c ea n dt os o l v et h e m i n i m u m - c o s tr e a c h a b i l i t yp r o b l e m ，t o g e t h e rw i t ham e t h o dt os i m p l i f yt h em o d e l a n dt h ec o s tm o d e la n dt h eo n ef o rb u s i n e s sd e c i s i o na r ee s t a b l i s h e db a s e do np r i c e d p e t r in e ta n ds t o c h a s t i cp r i c e dp e t r in e tr e s p e c t i v e l y a f t e rt h et i m ea n dp r i c em o d e l i n go fp e t r in e t sh a v i n gb e e ns t u d i e ds e p a r a t e l y , t h i s d i s s e r t a t i o np r o p o s e sat i m ep e t r in e te x t e n d e dw i t hp r i c ei n f o r m a t i o n ，n a m e dp r i c e t i m ep e t r in e t ，w i t hw h i c ht i m ea n dp r i c ep a r a m e t r e sa l ea b l et ob em o d e l e di na n u n i f o r mf r a m w o r kw h a t sm o r e ，i ti sp r o v e dt h a tt i m ep e t x in e ti st h es u b c l a s so f p r i c et i m ep e t r in e t m o r e o v e r , w ep r o p o s et w om e t h o d st oc o m p u t es t a t es p a c e ：t h e i d e ao fp r i c e ds t a t ec l a s si st oa d da c c u m u l a t e dc o s tt os t a t ec l a s s ；t h ei d e ao fp r i c e d t i m e ds t a t ec l a s si st oc o m p u t et h es t a t es p a c eo f p r i c et i m ep e t r in e ta sa p r i c e dt i m e d a u t o m a t a a n dt h ec o s t t i m em o d e lf o rab u s i n e s sp r o c e s si se s t a b l i s h e db a s e do nt h e p r i c et i m ep e t r in e t a sw ek n o w n ，t h ef i r i n gr u l eo fc l a s s i c a lp e t r in e ta n de x t e n s i o no fp e t r in e t sw i t h t i m ei n f o r m a t i o nj u s td e p e n d so nt h em a r k i n ga n dt i m ec o n s t r a i n t s ，a sf lr e s u l to f w h i c ht h ef i r i n gm l eo f p r i c ep e t r in e ta n dp r i c et i m ep e t r in e ts t i l lw o r kw i t h o u tt h e p r i c ei n f o r m a t i o n d u r i n gt h es 如d yo f t h ea p p l i c a t i o nm o d e lb a s e do np r i c e dp e t r in e t i ti sf o u n dt h a tp r o f i tc o n s t r a i n t ss h o u l da f f e c tt h ef k f i n go fp r i c e dp e t r in e t s ow e p r o p o s ean e w k i n do fp r i c e dp e t r in e tw h o s ef i r i n gm l ei sm o d i f i e dt oc o n s i d e rt h e p r o f i tc o n s t r a i n t s t h e nw ed i s c u s st h ea n a l y s i sm e t h o da n dp o s s i b l ea p p l i c a t i o n d o m a i n sf o rt h i sp e t r in e t 中山大学博士学位论文 p e t f i 网的价格建模研究 f i n a l l yt h i s d i s s e r t a t i o ni sc o n c l u d e dw i t ht h e d i s c u s s i o no nt h ec o m p a r i s o n b e t w e e nt i m em o d e l i n ga n dp r i c em o d e l i n g ，a sw e l la st h er e l a t i o n s h i pa m o n gt h e s e p e t r in e t sp r o p o s e dw i t h i nt h i sd i s s e r t a t i o n k e yw o r d s ：p e t r in e t ，p r i c em o d e l i n g ，t i m em o d e l i n g ，f o r m a ls e m a n t i c s ，s t a t e s p a c ec o m p u t a t i o n ，p r i c e dt i m e d a u t o m a t a 中山大学博士学位论文 p e t r i 网的价格建模研究 第1 章引言 p e t r i 网( p e t r in e t ，简称p n ) 是一个经典的并发模型，由德国学者c a r la d a mp e t r i 博士在1 9 6 2 年提出【”。最初p e t r i 博士使用这种模型来建模通信系统，随后引起了学 术界和工业界的极大关注，后来人们就把这种模型命名为p e t r i 网。p e t r i 网以研究模 型系统的结构和动态行为为目标，着眼于系统各种状态及状态变化之间的关系。经 过研究人员的不断努力，p e t r i 网作为一种图形化和数学化的建模工具广泛用于系统 建模、分析和验 2 j 。因为p e t r i 网有图形化的特点，所以具有直观和易学易用的特 点；同样地，p e t r i 网还有数学化的特点，所以可以用形式化方法来严格地定义和分 析模型。 在p e t r i 网研究与发展的过程中，研究人员对经典p e t r i 网模型进行了各种扩展， 主要包括：时延p e t r i 网( t i m e dp e t r in e t ) 3 1 ，时n p e t r i l n ( t i m ep e t r in e t ) 1 4 1 ，随 机p e t r i l 网( s t o c h a s t i cp e t r in e t ) 5 1 ，时序p e t r i l n ( t e m p o r a lp e t r in e t ) 【6 】抑制弧p e t r i 网( i n h i b i t o ra r c sp e t r in e t ) 【7 】，着色p e t r i 网( c o l o r e dp e t r in e t ) s l ，对象p e 仃i 网 ( o b j e c tp e t r in e t ) 9 1 ，模糊p e t r i n ( f u z z yp e u in e t ) 【1 们，混合p e t r i 网( h y b r i dp e t r i n e t ) 1 1 1 等等。 这些有益的扩展使得p e t r i n l ) c j 分析和描述能力不断增强，应用领域不断增加佗 。 早期的p e t r i 网主要应用于计算机科学本身，例如文献【4 将p e t r i 网用于协议分析验证， 文献【5 】将p e t r i n 用于系统性能分析。后来经过长期的发展，随着许多具有其他学科 背景的研究人员对p e t r i 网产生了研究兴趣，p e 仃i 网的应用范围已经远远超过了计算 机科学本身。例如，目前p e t r i l n 已经在制造系统i l l 】、系统生物掣13 1 、电子商务【1 4 等 领域得到成功应用。另外，p 咖i 网在管理科学与工程、电力与电子、交通等领域也 已经引起了研究人员的注意。 中山大学博士学位论文 p e t r i 网的价格建模研究 1 1 研究背景 从p e t r i 网的发展历史我们可以看到：1 9 7 4 年美国马萨诸塞理工学院的 c r a m c h a n d a n i 在其博士论文使用时延p e t r i 网分析异步并发系统中将时间概念引 入p e t r i 网j ；随后越来越多的研究人员根据p e t r i 网本身的特点和时问信息的特点提 出了各种扩展时间信息的p e t r i 网和相应的分析方法；进一步地，研究人员开始将这 些扩展了时间信息的p e t r i 网用于许多实际系统的建模、分析和效率的检验。从过去 的那些成功例子可以知道：为p e t r i 网扩展时间信息大大增强t p e t r i 网的实用性。 但是随着p e t r i 网应用领域的不断拓展，研究人员发现有许多应用模型不仅仅需 要将时间特性在模型中体现出来，还需要将价格特性也体现在模型中。目前在工作 流建模方面，研究人员已经显示出了对价格建模的兴趣。例如，文献 1 5 】、 1 6 1 乖1 1 7 】 提出了包括时间( t i m e ) 和价格( p r i c e ) 等指标的o o s 模型。具体到基于p e t r i 网的工 作流建模方面，荷兰学者w m ev a i ld e r a a l s t 和h a r e i j e r s 等人则指出：他们已经将 扩展了时间信息的p e t r i 网成功地用于工作流建模主要目的之一的“模拟和分析” 18 1 1 ”，而对另一个主要目的“成本和预算分析并没有做深入研究，这是因为目前 的p e t r i 网还不能很方便地建模和价格信息有关的应用系统呻l 。 非常值得注意的是，在本文作者致力于p e t r i 网价格建模研究的同时口o 】【2 i 】，国 内清华大学计算机科学系的学者刘卫东、宋佳兴和林闯教授等人于2 0 0 5 年提出了一 种价格时间p e 衄网( p r i c et i m e dp e t r in e t ) 【2 2 】。虽然该文的核心工作在于讨论基于 这种价格时间p e t r i 网的网格计算应用模型，但是他们的工作说明p e t r i 的价格扩展 已经引起了国内学术界的注意。另外，在实际应用系统中研究人员也已经开始考虑 价格参数。例如，i b m 的苏黎世实验室在网格资源商业化方而做了许多工作，澳大 利亚m o n a s h 大学的学者r b u y y a 提出了面向服务的网格计算经济体系结构，国内的 一些研究人员在网格资源调度中也引入了价格参数【2 j 1 1 2 4 l 。所以我们自然会有这样的 想法产生：如果能够将价格信息有效地在p e t r i 网中表示出来，那么这种p e t r i 网将会 成为对应用模型进行成本分析的一种可能工具：进一步来讲，如果能够将时间和价 格信息同时在p e t r i 网中体现出来，则可以建立基于p e t r i 网的成本时间模型。 中山大学博士学位论文 p e t r i 网的价格建模研究 众所周知，在经典p e t r i 网中，变迁的实施条件只和位置中的托肯数量有关：而 在时间p e t r i 网中，则在变迁的实施条件中增加了时间约束条件。相应地，对于扩展 了价格信息的p e t r i 网来说，是否需要在变迁的实施条件中增加利润约束条件是一个 有意义的问题。可以这样认为：对用来作一般成本分析的p e t r i 网来说，并不需要增 加利润约束条件；但是对于那些以利润为导向的系统来说，增加利润约束条件则非 常有必要。而这种增加了利润约束条件的p e t r i 网或许在更为广泛的领域有潜在的应 用价值，就像国内外许多致力于经济控制论研究的研究人员已经将控制论成功地应 用于经济学领域一样。 ；在为p e t r i 网扩展价格信息的过程中，我们注意到在自动机2 5 1 1 2 6 l 研究领域也有相 关的工作。观察自动机研究领域的发展轨迹，可以发现其中有一个十分有意思的发 展分支：一般的自动机_ 扩展了时间信息的自动机专扩展了时间和价格( 权重) 信息的自动机。1 9 9 4 年印度裔美国学者r a l u r 和d l d i l l 提出了用于实时系统建模的 时间自动机”，2 0 0 1 年r a l u r 等人提出权重时间自动机( w e i g h t e d t i m e d a u t o m a t a ) 1 2 7 1 ，同时丹麦学者g b e h r m a n n 和k l a r s e n 等也提出价格时间自动机( p r i c e dt i m e d a u t o m a t a ) 2 8 1 1 2 9 m o 。他们的工作是为位置和边分别联系一个c o s t 或p r i c e 参数。这里 c o s t 或p r i c e 表示的主要是能量或者货币，例如使用价格时间自动机建立一个低功耗 系统的时间和能量模型。显然也可以考虑将p r i c e 用来表示一般意义上的价格概念， 这些自动机领域的研究工作从另一个方面说明了为p e t r i 网扩展价格信息的必要性和 可能性。 许多研究人员致力于研究扩展了时间信息的p e t r i 网和自动机之间的关系。例 如，法国学者e c a s s e z 和o r o u x 在文献 3 1 中讨论了时间自动机和时间p e l r i 网的 关系，丹麦学者j s r b a 则在文献 3 2 中研究了时问自动机网络( n e t w o r k so ft i m e d a u t o m a t a ) 和时间弧p e t r i 网( t i m e d a r cp e t r in e t s ) 。那么当我们为( 时间) p e t r i 网扩展了价格信息之后，也应当去研究这些扩展了价格信息的( 时间) p e t r i 网和相 应的( 时间) 自动机之间的关系。 中山大学博士学位论文p e t r i 网的价格建模研究 1 2 研究目标 因为在经典p e t r i 网和p e t r i 网的时间扩展方面已经有了许多成熟的工作，所以 本文将瞄准p e t r i 网的价格扩展来进行努力。相应地，本文的主要研究目标包括下面 三个： 1 为p e t r i 网扩展价格信息，并讨论网的语义和最小成本可达问题 2 研究p e t r i 网的时间建模和价格建模有何异同，以及p e t r i 网的各种价格扩 展之间的关系； 3 研究扩展了价格信息的p e t r i 网和相应的自动机之间的关系。 1 3 主要工作 基于前面进行的讨论，本文的主要工作包括三部分 1 研究经典p e t r i 网和p e t r i 网的各种时间扩展。 本文首先会介绍经典p e t r i 网的定义和分析方法，进步介绍为p e t r i 网扩展时 间的各种方式。然后将讨论的重点放在p e t r i 网的各种时间扩展上，以此作为后面讨 论p e t r i 网价格建模的基础，这是因为价格信息和时间信息有很多相似和相关之处。 只有对p e t r i 网的时间建模技术进行了充分而深入的研究之后，才能提出合适的价格 建模技术。也只有对现有的p e t r i 网应用领域进行广泛了解之后，才能发现应用中存 在的问题和不足，确定p e t r i 网价格建模的目标。 2 在不修改p e t r i 网实施条件的基础上，提出p e t r i 网的三种价格扩展以及相应 的应用模型。 4 中山大学博士学位论文p e t r i 网的价格建模研究 ( 1 ) 首先提出一种价格p e t r i 网( p r i c e d p e t r in e t ) ，核心思想是为p e t r i 网的变迁 引入固定价格参数。使用价格变迁系统( p r i c e dt r a n s i t i o ns y s t e m ) 给出价格p e t r i n 的语义并证明了经典p e t r i 网是价格p e t r i 网的子类，对价格p e t r i 网进行了可达性分析 并证明了最小成本可达问题是可判定的幽1 。进而使用价格p e t r i 网建立一个业务流程 的成本模型。 ( 2 ) 然后提出一种随机价格p e t r i 网( s t o c h a s t i cp r i c e dp e t r in e t ) ，并采用结构 化的分析方法进行分析。 2 0 和【2 1 】是我们将价格参数引入p e 仃i 网的初步尝试。进 一步使用随机价格p e t r i 网建立一个业务流程的决策模型，探讨扩展了价格信息的 p e 仃i 网应用于业务流程管理领域的可行性。 ( 3 ) 最后提出一种扩展了价格信息的时间p e t r i 网。这里也是为时间变迁扩展 价格参数，相应地给出了一种价格时间p e t r i 网( p r i c et i m ep e t r in e t ) 。首先使用价 格时间变迁系统( p r i c e dt i m e dt r a n s i t i o ns y s t e m ) 给出了价格时间p e t r i 网的语义并 证明了经典时间p e t r i 网是价格时间p e t r i 网的子类。然后分别给出了两种状态空间计 算方法：( a ) 提出计价状态类( p r i c e ds t a t ec l a s s ) 的概念，并证明为状态类扩展 累积成本的合理性和完备性，进而证明出有界价格时间p e 伍网的最小成本可达问题 是可判定的【3 3 ；( b ) 将价格时间p e t r i 网的状态空间构造为一个价格时间自动机 ( p r i c e dt i m e da u t o m a t a ) ，并证明了构造出的价格时间自动机和初始的价格时间 p e t r i 网是双相似的，进而用现有的价格时间自动机分析工具来分析价格时间p e t r i 网 3 4 1 。最后使用价格时间p e t r i 网建立并分析了一个业务流程的成本时间模型。 3 重新定义p e m 网的实施条件，提出一种带利润约束的价格p e t r i 两j 1 3 ”。这里同 样在p e t r i e 中引入了价格变迁，核心思想是让利润约束来影响变迁的实施。首先为 托肯联系了利润参数，提出计价状态的概念来描述这种价格p e t r i 网的动态特性。进 一步定义了这种价格p e 砸网的语义，并根据p 不变量、t 不变量、关联矩阵等结构特 性分析出平均循环利润。最后将带利润约束的价格p e t r i 网应用于一个实际问题的建 中山大学博士学位论文 p e t r i 网的价格建模研究 模和分析。 1 4 主要贡献与创新 本文的主要贡献与创新包括以下三点 1 为经典p e t r i 网扩展了价格信息，并讨论了最小成本可达问题 2 提出一种价格时间p e t r i 网，讨论了相应的语义以及状态空问计算方法 3 讨论了价格时间p e t r i 网与价格时间自动机的关系。 1 5 论文的组织 本文余下的内容按如下方式组织。第二章是对经典p e t r i 网以及各种p e t r i 网扩 展的介绍。第三章介绍了p e t r i 网的各种时间扩展方式，并讨论各种扩展了时间信息 的p e t r i 网。第四章在研究了经典p e t r i 网的价格扩展以后，以业务流程模型为应用 领域，讨论了基于价格p e t r i 网的成本模型和基于随机价格p e t r i 网的决策模型。第 五章提出了一种价格时间p e t r i 网，可以将时间和价格统一体现在p e t r i 网模型中， 并讨论了两种不同的分析方法和相应的成本时间模型。第六章研究了以利润约束影 响变迁实施的利润约束p e t r i 网，并探讨了利润约束p e t r i 网的应用前景。最后的结 束语总结了p e t r i 网的时间建模和价格建模有何异同，以及p e t r i 网的各种价格扩展 之间的关系。 6 中山大学博士学位论文p e t r i 网的价格建模研究 第2 章p e t r i 网基础 在c a r l a d a mp e t r i 博士的( ( s t a t u s r e p o r to n n e t t h e o r y ) ) 一书的序言中提到：网 论一开始就以物理为基础“。通过一些简单的圆圈、长方形、弧线和小圆点，p e t r i 网就能够描述系统活动问的复杂关系。或许这就是p e t r i 网的魅力之所在。当然，我 们要记住“图形符号和游戏规则并不是网论”【3 6 】，“事实上，网论是以计算机科学 的语言提出来的一种物理理论研“i 。本章的主要目标就在于讨论这些定义和分析p e t r i 网的计算机语言。这里会介绍一些p e t r i 网的基础知识作为全文工作的基础。首先介 绍经典p e t r i 网的基本概念、分析方法和基本原理，然后介绍了p e t r i 网的各种扩展以 及相应的应用领域。 2 1 经典p e t r i 网 众所周知，常用的p e t d 网有基本网系统和位置废迁系统。首先简单讨论一下基 本网系统。基本网系统以事件问的基本关系为主，介绍网的动态行为【3 6 】。一个基本 网定义为三元组( b ，e ；f ) ，其中b 条件集，e 为事件集，f 为变迁关系p “。因为在实 际应用中较少使用基本网系统，所以这里不再做更加深入的讨论，有兴趣的读者可 查阅北京大学袁崇义教授的专著p e t r i 网原理与应用。 而位置变迁系统则相对来说更适合于实际应用，所以本文中的的经典p e t r i 网 特指位置变迁系统。 2 1 1p e t r i 网的基本概念 首先给出经典p e t r i 网的定义。请注意，本部分使用的概念在风格上与文献【1 9 、 3 6 1 ；f f l 3 7 1 相同。 7 叶1t l l 大学博士学位论文p e t r i 网的价格建模研究 定义2 1 一个p e t r i 网是一个五元组p n - ( p ，l 口，f m o ) ，其中 ( 1 ) p = p 1 枕，# h 是有穷、非空的位置集： ( 2 ) 7 = 确，匕，哪是有穷、非空的变迁集，且尸n 产o ； ( 3 ) b jp t 斗n 是向后关联函数； ( 4 ) 只t p _ 是向前关联函数； ( 5 ) 蛳：p _ _ 是初始标识。 这里“”表示迪卡尔积，是自然数集合。请注意，在本文中使用r 表示变 迁r 的输出位置集合，使用r 表示变迁r 的输入位置集合，使用p 表示位置p 的 输入变迁集合，使用p 表示位置p 的输出变迁集合。 例如，图1 1 是一个简单的p e t r i 网模型。其中使用圆圈表示位置，使用长方形 框表示变迁，使用有箭头的弧线表示位置和变迁的关系，使用小圆点表示托肯。 定义2 2 个p e t r i 网的标识是一个映射m p 斗。一个标识由向量 ( 朋p 1 ) ，m 扭) ， 4 p ，) ) 表示。其中的第i 个元素表示位置肼中的托肯数。 一个p e t r i 网的动态状态由标识来表示，这里标识是自然数集上的一个m 元组。 例如，图ll 中的状态可以由标识 p 。2 乒2 1 , p s l ) 来表示，这说明：位置p l 中有两个托 肯，位置p z 和位置p 5 中分别有一个托肯，其它位置中没有托肯。为简单起见，可以 将标识( p 1 2 , p z l 乒5 1 ) 记为( 0 2 l 0 0 1 ) 。 t 3 p 4 t 4 p 5 f i g 11 a s i m p l ec l a s s i cp e t r in e t 图1 1 一个简单的经典p e t r i 网 中山大学博士学位论文p e t r i 网的价格建模研究 定义2 3 如果埘0 ) 书，0 ，则称变迁t et 在标识m 下是使f l 洲j ( e n a b l e d ) ，用 t e e n a b l e ( m ) 表示。 例如，图1 1 所示状态下有三个变迁，l 、t 2 ；f u t 3 都是使能的。 定义2 4 如果f 在标识吖下是使能的，那么f 可以实施( f i r i n g ) 并产生一个新的 后继标识m ， r 可由下面方程给出： v p e p , 埘铆= 热p 垂tc r d p g t o 氧i j ) 一b 江如 # p e tc n r l p g t 心功+ 地mf p 曲t o r d p e t o 4 ( 动一嗽，) + 她办i f p e ta , f f p e t 用m ，) m 表示从标识m 实施变迁t 到达标识a ，。从实施规则可知，p e t r i 网模 型的状态变化是局部的，它仅涉及通过输入输出弧连接的位置的状态变化。 例如，如果图1 1 中的变迁 实施，那么将会到达下一个状态，由标识( 0 1 2 0 0 0 表示。 为了简化形式化表达，在后面章节中都会将叫p ) - b ( p ，疗写作脚) = b ( r ) 。因 为这里的p 是确定的。对于只印) 也做同样的处理。 定义2 5 如果在标识肘下变迁 的实施使得变迁“成为新的使能变迁，记为： t k e n e w l y _ e n ( m , r f ) 。 这里n e w l y _ e n 中的变迁满足两个条件：( 1 ) 在标识m 下是不使能的， ( 2 ) 在后继标识”下是使能的。可以形式化地记为：n e w l ye n ( m , t ) = e n a b l e ( m 7 ) 一 e n a b l e ( m ) 例如，如果图1 1 中的变迁t 3 实施，那么将会到达下一个状态，由标识( 0 1 1 0 1 1 ) 表示。此时变迁t 4 成为新的使能变迁。此时的状态如图1 2 所示。 9 中i i l 大学时士学位论文 p e l r i 网的价格建模研究 o p o hm“ f i g 12 t h ep e t r in e ta f t e rt 3 sf i r i n g 图1 2 变迁b 实施以后的模型 o p 3 o p 5 定义2 6 对于标识m ，如果存在两个变迁，le e n a b 如( m ) 、t 2 e n a b l e ( m ) ，且r l 和f 2 中任意一个实施都会导致另一个不可实施，称这两个变迁在标识m 下冲突。 月。 例如，图1 2 中变迁l 和b 在标识( 0 1 1 0 1 1 ) 下是冲突的，因为位置p l 中只有一个托 袁崇义教授指出：网论认为，需要从系统的环境中输入一位信息来决定冲突的 双方谁发生。就系统本身而言，谁有优先权是不确定的。所以冲突也是系统的决策 之处 3 6 】。 上面我们已经讨论t p e t r i n 的基本定义和动态行为【3 6 】，接下来讨论p e 仃i 网的动态 性质。“。网的动态性质可从网的可达图或覆盖树获得，它依赖于初始标识m 。 定义2 7 如果存在r n 使得m 【f ) m ，则称m 从塘接可达。如果存在变迁实 施序列= t l ，2 ，r n ，使得m i i 】) 尬【f 2 ) ， 埘0 ) 瞄h ，则称 “l 从m 可达。 用r e a c h s e t ( m ) 表示从标识m 可达的所有标识的集合。 例如，对于图1 1 中的模型来说，标识( 0 1 2 0 0 1 ) j - t l 标$ r ( 0 1 1 0 1 1 ) 都属于 r e a c h s e “0 2 1 0 0 1 ) 。 1 0 中山大学博士学位论文 p e t d 网的价格建模研究 定义2 8 对所有从初始标识m o 可以到达的标识m ，如果存在k e n , 使得v p e p m ( p 1 k ，则称这个p e t r i n 是有界的( b o u n d e d ) 。 定义2 9 对所有的t e t 和所有的m e r e a c h s e t ( m o ) ，如果存在一个 m e r e a c h s e t ( m ) ，使得t e e n a b & ( m 7 1 ，则称这个p e t r i 网是活的( 1 i v e ) 。 最后还要讨论一下网的结构性质阅。网的结构性质可从关联矩阵和网的结构图 获得，与初始标识无关。 定义2 1 0 对于一个有m 个位置和n 个变迁的p e t r i 网，可以用一个m x n 维的关联 矩阵来描述p e t r i 网的静态结构。关联矩阵c = c 胡，其中勺= c 产c f 一。 如果从变迁。有一条弧到它的输出位置只，则有c ，= l ：如果从变迁0 有一条弧到 它的输入位置肼，则有。d i 。 很容易看出c 广、勺一、c f 分别表示当变迁实篪以后，位置阳中被移入、移出和改 变的托肯数量。 定义2 1 1 一个尸不变量是满足方程工= 0 的向量置p _ m 其中c 是网的关 联矩阵。一个环变量是满足方程c y = 0 的向量y z m 其中c 是网的关联矩阵。 限于篇幅，这里就不再对图1 1 中的模型计算它的关联矩阵和p 、t 不变量，感 兴趣的读者可参阅文献 3 6 。 定义2 1 2 对于一个p e t r i 网，所有可能的变迁实施序列组成的集合是p e k i n 能够 接受的语言。1 3 7 1 在人们对p e c r i 网语言的研究过程中，得出一个很有意义的结论