（计算机应用技术专业论文）基于赋时分层着色petri网的工作流建模与性能评价.pdf

摘要 随着企业市场竞争的日趋激烈和业务环境的不断变化，对业务流程管理的要求也变 得越来越高，在多流程多实例并行执行的工作流管理系统中，存在各种各样的约束条件 和资源竞争，一个多流程多实例执行的任务以最优的方案利用资源完成任务，是工作流 调度优化要研究解决的课题，它对企业的资源配置和生产效率有非常重要的现实意义。 工作流技术是实现企业业务过程建模、仿真分析、优化管理的核心技术。它将业务 过程逻辑从应用系统中分离出来，达到了对过程建模、重组和重用的目的。随着工作流 技术的发展，用户对工作流管理系统的可靠性和正确性要求越来越关注。工作流管理系 统的最重要功能之一就是工作流建模。一个好的工作流模型是实现一个具有高度灵活 性、可靠性、可用性、可伸缩性和互操作性的工作流管理系统的关键和基础。工作流建 模主要是研究如何清晰、准确地表示实际应用中的业务过程，特别是研究如何以形式化 的方法表示工作流模型。 随着工作流技术的发展，工作流模型越来越具有并发、动态、复杂和时序关系强的 特点，这给传统的工作流建模方法带来了很大的挑战，比如说u m l 建模和p e t r i 网建模 等。传统的建模方法在解决这类问题时存在着复杂、僵化、柔韧性差、没有时间概念等 缺点。时间是工作流中的重要属性，由于工作流的活动和资源具有动态特性，工作流中 的时间是非确定性的，难以被精确描述，同时考虑到本文描述的是多流程多实例的工作 流调度优化，对着色工作流网( c p w f n e t ) 进行时间、分层扩展，得到赋时分层着色 工作流网( h t c p w f - n e t ) 来描述流程信息。赋时分层着色p e t r i 网( h t c p n e t ) 由于赋 时和分层技术的引入以及相应功能强大的建模软件c p n t o o l s 的支持，使其在工作流建 模领域有了广泛的应用。 本文以典型的工作流管理系统保险索赔的工作流管理系统作为参照实例，基于 h t c p n e t 进行建模，并且对建立的工作流模型进行了正确性验证和性能分析，同时针 对模型的瓶颈提出了优化方案，通过对性能评价结果分析可以证明我们建立的模型和优 化方案是可行和有效的。 关键词：赋时分层着色p e t r i 网，工作流建模，模型验证，性能评价 m o d e l i n ga n de v a l u a t i n go fw o r k f l o wb a s e d o nh i e r a r c h i c a lt i m e d c o l o r e dp e t r in e t z h a n gl e w e i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rz h u l i a n z h a n g a b s t r a c t m a n a g e m e n to fw o r k f l o wi sm o r ea n dm o r ee m p h a s i z ea sm a r k e tc o p e t i t i o ng r o w sa n d b u s i n e s se n v i r o n m e n tc h a n g e s i nt h em u l t i - p o r e e s sa n dm u l t i - i n s t a n c ew o r k f l o ws y s t e m ， t h e r ea r ea l lk i n d so fc o n s t r a i n sa n dr e s o u r c ec o n f l i c t s ot h ew o r kf l o w s c h e d u l i n g o p t i m i z a t i o nf o c u so nt h er e s e a r c ho fa l l o c a t i n gr e s o u r c e st ob e t t e rs c h e d u l em u l t i - p r o c e s s a n dm u l t i i n s t a n c et a s k s t h i sr e s e a r c hi s r e a l l ys i g n i f i c a n tt ot h er e s o u r c ea l l o c a t i o na n d i m p r o v e m e n to fp r o d u c t i v i t ye n t e r p r i s e s w o r k f l o wt e c h n o l o g yi sac o r et e c h n o l o g yt h a ta s s i s t se n t e r p r i s eb u s i n e s sp r o c e s s e st o r e a l i z em o d e l i n g ，s i m u l a t i o n ，a n a l y s i s ，o p t i m i z a t i o nm a n a g e m e n t t h ew o r k f l o wm a n a g e m e n t t e c h n i q u es e p a r a t e st h ep r o c e s sl o g i cf r o mt h ea p p l i c a t i o n s ，a n da c h i e v e st h ep u r p o s eo f p r o c e s sm o d e l i n g ，r e c o m p o s ea n dr e u s e w i t ht h ed e v e l o p m e n to fw o r k f l o w , m o r ea n dm o r e r e s e a r c h e r sa r ec o n c e r n e dw i mt h er e l i a b i l i t ya n dc o r r e c t n e s so fw f m s t h em o s ti m p o r t a n t f u n c t i o no fw o r k f l o wm a n a g e m e n ts y s t e mi sm o d e l i n g ag o o dw o r k f l o wm o d e li st h ek e y a n df o u n d a t i o nf o rf e x i b l e ，c r e d i b l e ，u s e f u l a n dm u t u a l l yo p e r a b l ew o r k f l o wm a n a g e m e n t s y s t e m w h a tt h ew o r k f l o ws y s t e mr e s e a r c h e so ni sh o wt oe x a c t l ye x p r e s st h eo p e r a t i o n p r o c e s so f t h ea c t u a la p p l i c a t i o n ，e s p e c i a l l yh o wt od e s c r i b et h ew o r k f l o wm o d e l f o r m a l l y w i t ht h ei n c r e a s i n go ft h ew o r k f l o wt e c h n o l o g y , w o r k f l o wm o d e ln e e d st or e p r e s e n t s o m ec h a r a c t e r i s t i c ss u c ha sc o n c u r r e n t ，d y n a m i cb e h a v i o r s ，a n dr e a l - t i m ee v e n t se t c ，w h i c h g i v eg r e a tc h a l l e n g et ot h et r a d i t i o n a lm o d e l i n gm e t h o d ss u c ha su m l ，p e t r in e t se t c t r a d i t i o n a lm o d e l i n gm e t h o dh a ss o m ed e f e c t s ，s u c ha st o oc o m p l e x ，r i g i d i t y , i n f l e x i b i l i t y , n o t i m ec o n c e p t t i m ei n f o r m a t i o ni sa ni m p o r t a n ta t t r i b u t ei nw o r k _ f l o w b e c a u s eo ft h ed y n a m i c c h a r a c t e r i s t i c so fr e s o u r c e sa n da c t i v i t i e si nw o r k f l o w , m u c ht i m ei n f o r m a t i o ni su n c e r t a i n a n dc a n tb ed e s c r i b e d p r e c i s e l y , a tt h es a m et i m e ，t h em o d e lt h i sp a p e rd e s c r i b ei s m u l t i - p o r c e s sa n dm u l t i - i n s t a n c e s ot h i sa u t h o rm o d e l sw o r k f l o wp r o c e s s e s 、析t l lh i e r a r c h i c a l t i m e dc o l o r e dp e t r in e t s ( h t c p - n e t ) w h i c hi sb a s e do nc p w f n e t h i e r a r c h i c a lt i m e d c o l o r e dp e t r in e t s ( h t c p n e t ) ，h o w e v e r ，f o ri t sf l e x i b i l i t y , g r e a ta b i l i t yt or e p r e s e n tt h e s e c h a r a c t e r sa n de a s ys i m u l a t i o ni nc p n - t o o l ss o f t w a r e ，i sw i d e l yu s e di nt h i sf i e l d t h i sp a p e rh a ss y s t e m a t i c a l l ys t u d i e do nm o d e lv a l i d a t i o na n dp e r f o r m a n c ee v a l u a t i o n o fw o r k f l o ws y s t e mb a s e do nh t c p n e t ，a n dc h o o s i n ga t y p i c a lw o r k f l o ws y s t e m - - i n s u r a n c e c l a i m ss y s t e ma sa ne x a m p l e w ed os o m er e a c ho nw o r k f l o wv e r i f i c a t i o na n dp e r f o r m a n c e e v a l u a t i o n , i na d d i t i o n ，t h i sp a p e rp u t sf o r w a r do p t i m i z a t i o nm e a n sb a s e do nt h er e s u l t so f e v a l u a t i o n ；i tc a nb es e e nf r o mt h ep e r f o r m a n c ea n a l y s i st h a tt h em o d e l i n gt e c h n i q u ea n d o p t i m i z a t i o nm e t h o d sa r ea c c u r a t ea n de f f e c t i v e k e yw o r d s ：h i e r a r c h i c a lt i m e dc o l o r e dp e t r in e t ，w o r k f l o wm o d e l i n g ，m o d e l v a l i d a t i o n ，p e r f o r m a n c ee v a l u a t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：张蚕) 律 日期：少矽年乎月多e l 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门 ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被 查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用 影印、缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：茎量! 堑：! 垒 指导教师签名：么l 迸扯 日期：z 们哆年乡月多e t 日期：纱，i 年尹月6 e t 中国石油大学( 华东) 硕士学位论文 第一章绪论 1 1 课题的背景和意义 工作流技术起源于二十世纪8 0 年代初的办公自动化运动，到了二十世纪9 0 年代，随 着计算机技术、网络技术、通信技术和分布式数据库等辅助信息技术的迅速发展和成熟， 现代企业信息系统的分布性、异构性和自治性的特征越来越显著。在这种技术背景下， 工作流管理系统成为简化企业复杂信息环境、实现业务流程自动执行的必要工具，这样 一个转变，把工作流技术带入了一个崭新的发展阶段，使得人们从更深的层次、更广的 领域对工作流展开了研究。 性能评价能对工作流的一些性能指标如平均吞吐量、平均等待处理的工作项个数、 资源占有率等进行计算，并以此为依据去设计、预测和改进原有系统。性能评价的方法 有模型分析和模拟两种方法，目前有些工作流管理系统提供了工作流模拟的工具，通过 模拟业务过程的运行来观察工作流执行的正确性和效率。 工作流模型是一种对于工作流的抽象表示，而工作流建模就是对实际的工作流进行 抽象的过程，所以对工作流建模工具的研究首先要做的是对工作流建模的研究。建模的 意思是根据实际存在的内容抽取一个模型用来体现要解决的问题。工作流建模是指把工 作流从实际的工作流程之中抽取出来，抽象成为一个执行过程，然后我们所要做的工作 只要针对这个执行过程进行，比如说可以进行一些宏观的操作：对这个执行过程加以判 断是否能够由某个点达到某个点? 效率问题估算、验证有无死循环? 仿真运行观察流 程、进行管理控制以及过程重新规划等等，然后根据这个基础，制作出相应的建模工具 以体现这个模型，描述问题和解决问题。所以，工作流建模工具的研究目的是为了提供 一个具有严谨的数学基础和充足的表达能力的建模方法，并形成工具以供使用。在工作 流管理领域，流程的抽取即把实际的流程变为抽象的流程这一步骤由建模工具承担。工 作流建模工具涉及到工作流程的抽取、图形化表示、以及流程验证等环节，是实施工作 流管理系统的第一个环节，成为工作流技术领域研究的热点问题之一。 赋时分层着色p e t r i 网( h i e r a r c h i c a lt i m e dc o l o r e dp e t r in e t ，以下简称h t c p n e t ) 在 普通p e t r i 网的基础上，扩展了模型的颜色和活动的执行时间，此外还能层次化地建模业 务流程。相对于复杂系统的普通p e t r i 网模型的杂乱和庞大。h t c p n e t 的层次模型结构更 复合人类的层次化思维，且服务对象建模能力也使模型的内涵更丰富，同时时间戳的引 入也更能解决有时序关系的业务流程。 第一章绪论 1 2 国内外研究及现状 工作流管理技术的发展，对业务流程自动化带来了不少帮助，但其效果仍然不能令 人满意，其不足主要表现在：建模工具对用户建立的模型缺乏验证支持，这使得工作流 管理系统在运行时可能发生致命性的错误，从而导致系统崩溃，损失巨大。建模工具对 建立的模型缺乏性能评价方法的支持。此外，时间约束及管理的问题逐渐成为工作流技 术发展的瓶颈，时间在过程生命周期中扮演着重要的角色，几乎所有的业务过程都存在 于时序环境中，且都是有时间限制的。目前的工作流管理系统大多数没有提供完善的时 间管理功能，一般功能仅局限在给活动赋予执行时间和截止期限，进行一些简单的仿真， 当活动执行时间超过截止期限时能够触发异常，进行一些简单处理等。 另一方面，基于工作流建模技术还远没有成熟，当前国内外对工作流建模方法的研 究有： ( 1 ) 基于面向对象建模方法【l 】。j o e r i s 通过对象来对工作活动、工作步骤、角色、 资源等进行建模。面向对象的技术使得工作流模型具有更大的灵活性，从而易于实现工 作流进化、动态流程等高级工作模式。使得面向对象进行建模具有灵活、全面、易于理 解和易于重用的特性。但是面向对象的建模方法只能对系统进行动态建模，难以对系统 的性能进行评价，同时也没有一套相应的建模工具支持，很难对复杂实时的业务流程进 行建模和性能评价。 ( 2 ) 基于对话的工作流建模 2 1 。g e o r g 在语言对于为理论基础上提出了一种工作流 模型，这种工作流模型是从客户方与服务方这两个角色之间的语言行为交互上对工作流 过程进行定义的。其基本思想是通过语言来协调各协同对象之间的合作关系。基于对话 的工作流模型注重协同对象的自主性和交互性，而不是像传统过程模型一样仅仅注重活 动及其之间的依赖关系。但是这种建模方法仅仅只描述了“活动与活动之间的连接关 系 ，很难从模型角度就看清楚活动之间所影响的状态及变更关系。 ( 3 ) 基于u m l 语割3 】的方法。g r a d yb o o t h 和j i mr u m b a u g h 首先将b o o t h9 3 和 o m t 2 统一起来，并于1 9 9 5 年1 0 月发布了第一个公开版本，称之为统一方法u m0 8 ( u n i t i e dm e t h o d ) 。u m l 建模优点是定义良好，易于表达，功能强大且普遍使用的建 模语言为复杂软件系统的设计提供了有效的手段。同时u m l 也存在自身的不足，它只能 作为一种静态的系统建模，对系统的动态行为进行静态描述，不能对系统进行动态的仿 真，同时作为半形式化语言，也不能对系统进行性能的分析与评价。 2 中国石油大学( 华东) 硕士学位论文 ( 4 ) 基于p e t r i 网的建模方法【4 】。p e t r i 网是有c ap e t r i 教授首先提出的一种建模语言， 被广泛用于描述动态系统，具有良好的形式定义以及直观的表达方式。p e t r i 网具有直观 的图形表示、明确的语义、坚固的理论基础、丰富的分析技术和适合于描述离散并行系 统的特点。但是p e t r i 网也存在很多不足，比如没有层次结构，没有时序概念，同时也容 易导致“状态空间爆炸 。 、 ( 5 ) 基于赋时分层着色p e t r i 网( h t c p n e t ) 【5 1 的建模方法。h t c p n e t 建模方法是 对经典p e t r i 网建模方法的一种扩展，通过引入颜色集解决了“状态空间爆炸”的问题； 通过引入分层技术解决了模型结构过于复杂的问题；通过引入时间戳解决了时序关系的 问题。此外，h t c p - n e t 丰富的分析技术和m o n i t o r 仿真机制也有利于对模型进行性能分 析和评价，基于h t c p n e t 的建模方法十分适合描述模型关系复杂和有时序关系的工作流 业务模型。 一些学者和研究人员也取得了重大的研究成果，e d e r 6 】基于赋时活动图，建立包含 活动时间属性的工作流模型，如活动执行延迟、截止期限、固定日期以及时间距离约束， 并将所有的时间约束换算为活动执行结束的时间点。h o f s t e d e 与n i e u w l a n d 7 1 提出了任务 结构的概念，在工作流管理系统中，任务结构可以被看作一种很好的模型描述与控制语 言。荷兰e i n d h o v e n 大学的w m p v a i ld e ra a l s t 8 1 提出了基于经典p e t r i 网的工作流网概念， 这使得p e t r i 网的众多分析技术与工具可以在工作流管理系统中得以应用，因此工作流网 的概念己被众多研究人员所认同。王亚南【9 1 在工作流图建模方法的基础上，提出了将工 作流图映射为e b f 图、e b s 图、e w f 图和e w s 图，定义了相应图上的关键路径，利用这四个 关键路径对工作流进行了较详细的动态验证。李红臣【1 0 】考虑了活动之间的资源共享情 况，给出了并发工作流时序约束动态验证的方法。s c h o s m i n g 、宫世豪等基于着色p e t r i 网建立了业务流程模型【1 1 】，这种模型有较强的表达能力，但和工作流网的标准有一定差 距，不能运用与工作流网有关的某些性能分析方法。 1 3 研究内容和研究成果 1 3 1 研究内容 ( 1 ) h t c p n e t 建模研究 通过工作流网和h t c p n e t 之间的映射关系建立基于h t c p n e t 的工作流网。 ( 2 ) h t c p n e t 仿真研究 通过研究变迁( t r a n s i t i o n ) 的使能机制和库所( p l a c e ) 的状态，合理控制模拟仿真 3 第一章绪论 的过程，并且通过分析状态空间报告、消息序列图表得到模拟仿真过程的反馈结果，对 模型的合理性做进一步的研究。 ( 3 ) h t c p n e t 性能分析研究 通过研究状态空间报告及其序列图对模型做出初步性能分析，然后有针对性的使用 数据监视器( m o n i t o r ) ，以c m l 语言为基础书写相应的函数，在仿真过程中得到相应 评价指标的结果，并且从评价指标中分析出系统的可行性和瓶颈，并进一步指出优化方 案，对模型进行进一步的优化。 e 4 ) h t c p n e t 性能评价结果展示 综合运用c p nt o o l s 、g n u p l o t 和b r i t n e ys u i t e ( b a s i cr e a l - t i m ei n t e r a c t i v et o o lf o r n e t - b a s e da n i m a t i o n ) 等工具以数据表格、图形和消息序列图表( m s c ) 等多种形式来 把易于理解的性能评价结果展示给用户。 1 3 2 研究成果 本文对工作流建模过程中的理论和实践中所涉及的一系列的关键技术进行了研究， 根据这些技术的研究和运用，提出了基于h t c p n e t 的建模方法，并且基于h t c p n e t 设计 和实现了一个保险索赔工作流模型，用c p n t o o l s 进行了建模和模拟实践，并且对模型 进行了正确性验证和合理性分析，同时对模型的性能进行了评价，通过对性能评价结果 分析找出了模型的瓶颈，提出了优化方案，通过对优化前后模型性能的对比，可以证明 优化方案是可行和有效的。本文的主要贡献主要在于以下几个方面： ( 1 ) 对传统的p e t r i 网理论、工作流网、h t c p n e t 进行了研究，将工作流模型的基 本结构和工作流网的组件对应起来，使得h t c p n e t 能够很好的应用于工作流建模过程， 并对h t c p n e t 网的验证和模拟进行了研究。 ( 2 ) 扩展了w f n e t 工作流网，在w f n e t 的基础上结合h t c p n e t 理论提出了一种赋 时分层着色工作流网( h t c p w f n e t ) 。给出了h t c p w f n e t 的严格定义使能条件和触发 规则，并详细分析了h t c p w f n e t 给工作流建模带来的新特性。基于h t c p n e t 建立工作 流模型可以简化系统模型，易于表达复杂的业务逻辑，提高系统的柔性。 ( 3 ) 建立了工作流的四种基本结构( 顺序、并行、选择、循环) ，给出了由工作 流元模型到h t c p n e t 的映射方法。以工作流的四种基本流程构造结构为出发点，建立了 从业务流程到工作流网模型的完整映像关系，对每一种基本结构均给出了相应的转化规 则。 4 中国石油大学( 华东) 硕士学位论文 ( 4 ) 给出了工作流的触发机制。 ( 5 ) 根据工作流管理联盟关于工作流模型的策略机制，提出一种用资源管理器统 一管理的方法。 ( 6 ) 对系统的性能进行了全方位的分析和评价，通过对所建立的保险索赔工作流 模型的响应时间、延迟时间、平均等待时间、完成时间、等待队列、资源利用率的分析 找出了系统的“瓶颈，针对瓶颈提出了优化方案，通过对实验数据的分析可以证明优 化方案是可行和有效的。 1 4 论文的结构 全文共分为六章，具体内容组织如下： 第一章主要对工作流技术和工作流管理系统的基本概念、产生背景、发展历史及性 能分析的研究现状做了简明扼要的说明，同时对h t c p n e t 做了简要的介绍和说明，并对 本文的组织结构和研究内容与研究成果进行了介绍。 第二章主要针对p e t r i 网及h t c p n e t 的基础知识和基本理论进行详细阐述和分析，对 工具软件c p nt o o l s 做简要说明。 第三章研究了软件性能评价方法，并对其优缺点进行了分析，着重研究了h t c p - n e t 的两种性能评价方法。 第四章对工作流的基础知识以及工作流网的基本结构进行了介绍，本章详细地介绍 了赋时分层着色工作流网的概念、触发机制、特性、映射规则，本章最后介绍了工作流 网资源管理器的定义、分析、设计。 第五章基于h t c p n e t 建立了保险索赔工作流模型，给出了模型的变量声明以及顶层 结构和子页结构，最后给出了几个文章所涉及到的m o n i t o r 函数。 第六章对所建立的模型进行了性能的评价，分析了索赔案例的响应时间、完成时间、 延迟时间、平均等待时间、等待队列、资源利用率等性能，通过对性能分析找到了系统 的瓶颈并提出了优化方案，通过对优化前后性能的对比可以证明优化方案是可行有效 的。 最后部分为全文的总结，以及今后的工作展望。 5 第二章赋时分层着色p e t d 网基础知识与理论 第二章赋时分层着色p e t r i 网基础知识与理论 2 1 基本p e t r i 网相关知识 2 1 1p e t r i 网的产生与发展 p e t r i 网 1 2 - 1 5 是c a p e t r i 博士于1 9 6 0 年提出的，p e t r i 网以研究系统的组织结构和动态 行为为目标，着眼于系统中可能发生的各种变化及变化之间的关系，它只关心变化所需 条件和变化对系统状态的影响。 但在实际应用中，p e t r i 网出现了两个严重不足：一是无数据概念；二是无层次概念。 这些限制使之只能进行小系统的建模。8 0 年代后期高级p e t r i 网的开发解决了这两个致命 的问题，即对经典p e t r i 网进行颜色、时间、层次扩展，h t c p - n e t 就是在此基础上产生的 一种高级p e t r i 网，是少有的能同时用于验证系统功能逻辑的正确性和评估系统性能的建 模语言。此外，它还能自动的或交互的进行仿真，同时也能对系统进行性能分析和评价。 2 1 2p e t r i 网描述及定义 p e t r i l 网的结构元素【2 0 1 包括库所( p l a c e ) 、变迁( t r a n s i t i o n ) 和弧( a r c ) 。库所用 于描述可能的系统局部状态条件或状况，变迁用于描述修改系统状态的事件，弧规定了 局部状态和事件之间的关系。每一条弧有一个对应的权值，称为弧权( w e i g h t ) 。在p e t r i 网模型中，标记( t o k e n ) 包含在库所中，随着事件的发生，标记可以按照弧的方向流 动到不同的位置，从而动态地描述了系统的不同状态。 一个p e t r i 网模型的动态行为是由它的实施规则( f i r i n gr u l e ) 规定的。如果一个变迁 所有的输入位置至少包含一个标记，那么这个变迁可能实施( 相联系的事件可能发生) ， 对这种情况这个变迁称为可实施。一个可实施变迁的实施导致从它所有输入位置中都清 除一个标记，在它的每一个输出位置中产生一个标记。当使用大于1 的弧权时，在变迁 每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可实施，这个变迁的实 施，要根据相连接的弧权在它每一个输出位置中产生相应标记个数。由于变迁的实施使 标记在库所中流动，因此不同时刻，标记在各个库所中的分布不同，这种不同的分布称 为标识( m a r k i n g ) ，标识就相当于系统所处的状态( s t a t e ) 。 对基本p e t r i 网的定义有两种，分别从静态和动态角度进行定义【1 6 】： 定义2 1 当且仅当满足以下条件时，三元组n ( p ，t ，f ) 被成为有向网( d i r e c t e dn e t ) ， 简称网( n e t ) ： f1 ) pf i t = f 2 j 6 中国石油大学( 华东) 硕士学位论文 ( 2 ) p u t a ： ( 3 ) f c p x t u t x p ； ( 4 ) d o m ( f ) o c o d ( f ) = p o t 。 其中，d o m ( f ) = x ij y ：( x ，y ) f ，c o d ( f ) = ylx t x ：( x ，y ) f ) 分别为f 的定义域和值 域；p = p - ，p 2 , - - , p 。) 是n 的有穷库所集合，每个库所代表一种资源；t = t - ，t 2 ，t n 是 n 的有穷变迁集合；p 和t 称为p e t r i 网的库所集( p l a c es e t ) 和变迁集( t r a n s i t i o ns e t ) ；库 所和变迁分别成为p 元素和t 元素，或p 元和t 元；x = pu t 成为p e 仃i 网的元素集；f 是由n 中的一个p 元素和一个t 元素组成的有序偶的集合，被称为流关系( f l o wr e l a t i o n ) 。 p n t = o 表示p 元素与t 元素是两类没有交集的元素，p u t 彩表示网中至少要有一 个元素。 为了方便表述，还需要定义库所或变迁的前集和后集，定义如下： 定义2 2 设x po t ，事x = y l ( y ，x ) ef ；x = y i ( x ，y ) f ) ，那么，k 被称为x 的 前集( t g 称输入集) ，x 成为x 的后集( 也称输出集) 。 有向网通常用来描述静态p e t r i 网，静态p e t r i 网的一个典型事例如图2 1 ： 图2 - lp e t r i 网不例图 r i g z q t h ee x a m p l eo fp e t r in e t s 附注1 ：t l 用粗线表示，代表瞬时变迁；t 2 用矩形表示，代表时间变迁。 定义2 3 一个六元组= ( p ，t ；f ，k ，w ，m o ) 是一个p t 系统，当且仅当： ( 1 ) ( p ，t ；f ) 是一个网，p 中元素代表位置，t 中元素代表变迁，f 为弧元素； ( 2 ) k ：p 哼n + u o o 是位置容量函数； ( 3 ) w ：f j n + 为弧权函数； ( 4 ) m 。：p n 是初始标识，且满足：v p e p ：m o ( p ) s k ( 例，当k ( p ) = 0 0 时，通常 省略k ( p ) 的标注。 7 第二章赋时分层着色p e t r i 网基础知识与理论 2 2 高级p e t r i 网 经典p e t r i 网对托肯的表达涵义以及变迁的发生条件规定的非常简单，在应用到具体 实例中时会受到各个方面的限制【1 7 1 ，为了丰富模型的表达能力，人们对经典p e t r i 网进行 颜色、时间、层次的扩展。 2 2 1 着色p e t r i 网 着色p e t r i 网也成为有色网，就是在经典p e t r i 网的基础上引入颜色的概念，对驻留在 库所中的t o k e n 个体赋予颜色【2 】。着色主要针对t o k e n 和库所而言。通过对托肯( t o k e n ) 着色，能够对托肯加以区分，从而在基于着色p e t r i 建立的模型中表现出不同的资源( 如 不同的消息类型、不同类型的处理对象等) 。对库所的着色实际上是赋给库所一个颜色 集，该颜色集限定了该库所中托肯所能取的颜色范围。一个变迁则表示一个复合条件， 变迁能够被激发就要求与进入变迁的有向弧相连的源库所中含有要求的t o k e n ，从不同库 所进入的t o k e n 在变迁中拟合，如果满足变迁表示的符合条件，变迁激发，产生的新的 t o k e n 送至u 变迁的目标库所中。着色p e t r i 网特别适合对通信协议、分布式系统、自动生成 系统、工作流程进行分析和建模【2 】。着色p e t r i 网提供了一种高度抽象性的建模方法，并 提高了普通p e t r i 网图形化描述系统的能力f 1 8 1 。 着色p e t r i 网比普通p e t r i 网多了一个要素：声明( d e c l a r a t i o n ) 。声明可以用任何脚本 语言实现，在本文中声明用c p n 标记语言( c o l o r e dp e t r in e tm a r k i n gl a n g u a g e s ，简称 c p nm l ) 来描述，在声明中定义了颜色集( 类型) 、函数、运算和变量。声明中定义 的函数可以用来对不同颜色的托肯进行不同的业务流程处理。与程序设计语言相比较， 可以发现颜色集相当于变量的取值。所以，有些情况下也把颜色集称之为类型。 定义2 4 着色p e t r i 网( c p n ) 着色p e t r i 网可以定义为一个九元组【1 9 1 ，c p n = ( ，p ，t ，a ，n ，c ，g ，e ，) ，其中： ( 1 ) ：一个类型的有限非空集合，也称为颜色集； ( 2 ) p ：库所( p l a c e s ) 的有限集合，p = p l ，p 2 ，p m ) ； ( 3 ) t ：变迁( t r a n s i t i o n s ) 的有限集合，t = t l ，t 2 ，t n ； ( 4 ) a ：弧( a r c s ) 的有限集合，满足pn t = pna = tna = ； ( 5 ) n - 节点( n o d e ) 函数，是定义a 到p tk j t p 的函数； ( 6 ) c - p _ 的颜色( c o l o r ) 函数，即每个库所必须属于某个颜色集； 8 中国石油大学( 华东) 硕士学位论文 ( 7 ) g ：自t 至表达式的守卫( g u a r d ) 函数，且满足以下关系： v t e t ：【t y p e ( g ( t ) = b n t y p e ( v a r ( g ( t ) ) ) 】，其中b 是布尔函数； ( 8 ) e ：自a 至表达式的弧表达式( a r ce x p r e s s i o n ) 函数，且满足以下关系： v a e a ：【t y p e ( e ( a ) = c ( p ) mat y p e ( v a r ( e ( a ) ) ) c _ e ，其中p 是节点函数n ( a ) 中的库所， c ( p ) m s 返回库所p 上的多集类型； ( 9 ) i ：自p 到一个终结表达式( 不含任何变量的表达式) 的初始化( i n i t i a l i z a t i o n ) 函数，其中v p p ：【t y p e ( i ( p ) = c ( p ) m s 】。 以下为定义的说明： ( 1 ) 颜色集的集合决定了可用于着色p e t r i 网声明中的类型、运算和函数； ( 2 ) 、( 3 ) 、( 4 ) 表示库所、变迁和弧的三个集合p 、t 和a ，它们都是有限集合， 且两两不相交； ( 5 ) 节点函数把每条弧映射到一个二元组，第一个为源节点，第二个为目标节点， 且这两个节点必须属于不同的类型，即为( 变迁，库所) 或( 库所，变迁) ； ( 6 ) 颜色函数c 把每个库所函数p 都映射到一个颜色集c ，也就是说p 中的每 个t o k e n 都属于颜色类型c ( p ) ( 7 ) 守卫函数g 把每个变迁t 都映射到同一个布尔表达式b ，并且g ( t ) q 6 所有变 量的类型必须包含于颜色集集合中； ( 8 ) 弧表达式函数e 把每条弧a 都映射到一个具有类型c ( p ( a ) ) m 。的表达式。这表 示e ( a ) 的每次求值都生成一个依赖于相邻库所颜色集的多重集合； ( 9 ) 初始化函数i 把每个库所p 映射为不包含变量的表达式，其类型c ( p ) m 和前 面类似，初始化表达式的类型也能为c ( p ) 或取空。 在定义了着色p e t r i 网的概念之后，现在我们来考虑其性质，先引入一下概念： 其中v a t ( t ) 称为，的变量集，e ( x 。，x ：) 称为( ，石：) 的表达式： v t t ： v a r ( t ) = 1 ，iv v a r ( g ( t ) ) v3 a 4 ( f ) ：，哳( e ( 口) ) ) 】， v ( x i ，工2 ) ( p tu t x 尸) ：【e ( x l ，x 2 ) = e ( 口) 】 4 e 彳( 卸z z ) o 定义2 5 多重集： 9 第二章赋时分层着色p e t r i 网基础知识与理论 设s 为非空集合，1 n 。是非负整数集，贝, j s ks 到i n 。的函数叫做s 上的多重集( b a g 或m u l t i s e t ) 。多重集和集合的区别在于前者允许同一个元素出现多次。例如： a ，a ，b 是集合 岛b ) 上的多重集，其中a 出现了两次。用上述定义的语言来说， 如如b ) 对应的 是函数f 钆b _ i n 。，其中f i a ) - 2 ，f ( b ) = l ，本文所涉及到的多重集是指在s 的有限多 个元素上值不为0 的函数。通常用s 表示集合s 上的所有多重集所组成的集合。设 m es 墙为s 上的任一多重集，由定义对任何s e s ，m ( s ) ei n o ，从而m 由s 中元素的一 次式m ( s ) s 唯一确定。 s e s 多重集的运算规则如下： 设m ，m l ，m 2 s 船，n ei n o 为非负整数，则 m l + m 2 = ( m l ( s ) + m 2 ( s ) ) s s e s n m = ( n m ( s ) ) s s e s m l5 m 2 ，v s s ：m 1 ( s ) m 2 ( s ) 若m i s m 2 ，则m l - q m 2 之差为m l - m 2 = ( m l ( s ) - - m 2 ( s ) ) s s e s 在给出着色p e t r i 网的定义前，先对使用的符号做出以下规定： ( 1 ) 类型t y p e 的所有元素，记为t ； ( 2 ) 变量v 的类型，记为t y p e ( v ) ： ( 3 ) 表达式e x p r 的类型，记为t y p e ( e x p 0 ； ( 4 ) 表达式e x p r 中变量的集合，记为v a r ( e x p o ； ( 5 ) 变量集合v 的一个绑定是指对于任一变量v e v ，有一元素b ( v ) t y p e ( v ) 与此 相关； ( 6 ) 表达式e x p r 在绑定b 时的值，记为e x p r ( b ) ，满足v a r ( e x p r ) 为b 中变量的子集， 表达式的取值是将每一个v ev a r ( e x p r ) 用绑定的值来代替。 定义2 6c p n 的标识： c p n 的一个标识是一定义在p 上的矢量函