（计算机应用技术专业论文）基于着色petri网的工作流建模的研究.pdf

摘要 近几年来，工作流管理技术被业界广泛采用并得到了迅速发展。工作流管理最重要 的功能之一就是工作流建模。这些预定义的过程模型必须能很好的反映实际业务流程， 因此需要找寻灵活的工作流过程形式化表示方法及过程的执行策略。 a a l s t 的工作流网已被众多研究人员所认同，它是基于经典p e t r i 网所建立的。但是， 传统p e t r i 网具有一些固有的缺陷：当系统过于复杂时，由于状态太多，容易引起状态 空间爆炸问题。因此，本文对经典p e t r i 网进行颜色扩展，提出了基于着色p e t r i 网的工 作流网模型，解决了建模过程中的两大问题：资源调用问题及业务处理过程的建模问题。 该模型对业务过程的描述有很强的表达能力，支持对工作流模型的分析与验证。本文对 该模型进行了包括过程模型和资源模型的详细设计。根据c l i e n t s e v e r 思想，将资源从 流程中独立出来，采用统一的资源管理器管理。设计了资源管理器的基本模型，解决了不 确定性活动的建模问题和资源的申请释放问题，以及多个实例时的可能发生的混乱状 况。在a a l s t 的任务结构映射算法的基础上，结合着色p e t r i 网的性质，提出了一种工作 流程模型到着色工作流网的映射算法，采用对链表遍历的方式来映射业务流程。该算法 先给出基本结构的映射规则，然后遍历工作流程模型即有向图，对图中的每一个状态结 点应用相应的映射规则进行着色p e t r i 网映射，再把转化后的着色p e t r i 网模型映射到着 色工作流网，此映射算法能实现着色p e t r i 网建模。 在给出建模方法的同时，本文还论述工作流模型的合理性验证。介绍了仿真分析方 法，并以一系列的实例说明了每种分析方法的具体应用。论文最后给出了一个实际的应 用案例的过程模型。 最后对本文的研究工作进行了总结，针对不足之处提出了改进的措施，并展望要进 一步深入研究的方向，为后续工作奠定了基础。 关键词：工作流，过程定义，着色p e l r i 网，工作流网，资源 r e s e a r c ho nw o r k f l o wm o d e l i n gb a s e do nc o l o r e dp e t r in e t w d x i a o h u i ( c o m p u t e ra p p l i c a t i o nt e c l l i l o l o g y ) d i r e c t e db yz h ul i a n z h a n g a b s t r a c t r e c e n t l y , w o r k f l o wm a n a g e m e n tt e c h n o l o g y , ar a p i d l yd e v e l o p i n gt e c h n o l o g y , h a sb e e na p p l i e dt o m a n yt r a d e s t h em o s ti m p o r t a n tf 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 t h em o d e lm u s t r e f l e c tb u s i n e s sp r o c e s s ，a n di t sn e c e s s a r yt of i n daw a yt oe x p r e s sw o r k _ f l o wp r o c e s s m o r en u m e r o u ss c h o l a r sa n ds p e c i a l i s t sh a v ei d e n t i f i e dw i t hw o r k f l o wn e tb a s e do nc l a s s i c a lp e t r in e t i t , t h e r e f o r e ，c a nd e s c r i b es e q u e n c e ， c o n c u r r e n ta n dc o n f l i c t a n di tm a k e ss y s t e mv i s u a la n d u n d e r s t a n d a b l e t h e r e ，h o w e v e r , a r es o m el i m i t a t i o n s ：i ti sd i 历c u l tt oc o n t r o lf l o wo f b u s i n e s s ，a n dh a st o o m u c hs t a t ew h e ns y s t e mi sv e r yc o m p l i c a t e d s ot h ep a p e re x t e n d sc l a s s i c a lp e t r in e tb yc o l o r t h e ni tp u t s f o r w a r dw o r l f l o wn e tb a s e do nc o l o r e dp e t r in e t t h i sm o d e lc o n s i s t so fp r o c e s sm o d e ld e s c r i b i n g b u s i n e s sp r o c e s sa n dr e s o u r c em o d e ld e s c r i b i n ge n t e r p r i s er e s o u r c e i th a sas t r o n ga b i l i t yt oe x p r e s st h e b u s i n e s sp r o c e s s ，s u p p o r t i n gt h ea n a l y s i sa n dv a l i d a t i o no fw o r k _ f l o wm o d e l t h i st h e s i sp u t sf o r w a r da d e t a i l e dm o d e ld e s i g n , i n c l u d i n gt h ep r o c e s sm o d e ld e s i g na n dt h er e s o u i c em o d e ld e s i g n ar e s o u r m a n a g e ri sm o d e l e d ；t h er e s o u r c em a n a g e ra s s i g n sa n dr e l e a s e sr e s o u r c e t a s k sa n d s u b - p r o c e d u r e si n s i d eap r o c e d u r e ，c o m m u n i c a t ew i t ht h er e s o u r c em a n a g e ra n dt h er e s o u r c e sv i at h eo t h e r c o n n e c t o r s aw a yo fm a p p i n ga r i t h r a e t i cf r o mb u s i n e s sp r o c e s st ow o r k f l o wn e ti sd e s i g n e di nt h i st h e s i s b a s e do nt a s ks t r u c t u r e sw h i c hi sf i r s tc r e a t e db ya a l s t t h et h e s i sd e s i g n st h ea l g o r i t h m i ca n di t s r e a l i z a t i o n t h et h e s i sd e b a t e st w ow o r k f l o wm o d e la n a l y z i n gt e c h n o l o g i e s ：q u a l i t a t i v e ：a n a l y s i sa n dq u a n t i t a t i v e a n a l y s i s i na d d i t i o n , i td e s c r i b e ss i m u l a t i o na n a l y s i sm e t h o da n dc o n c r e t ea p p l i c a t i o nb yas e r i e so f e x a m p l e s i nt h ee n d ，t h et h e s i sr e p r e s e n t sa na p p l i c a t i o nc a s ea n dm o d e l si t sb u s i n e s sp r o c e s s f i n a l l y ，t h et h e s i ss u m m a r i z e st h er e s e a r c hw o r k , p o i n t so u tt h ed i s a d v a n t a g e so ft h i sp a p e ra n dg i v e s s o m ei d e a sf o r t h ef u r t h e rw o r k k e y w o r d s ：w o r k f l o w ，p r o c e s sd e f i n i t i o n ，c o l o r e dp e t r in e t ，w o r k f l o wn e t ，r e s o u r c e 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 日期：三寥年s 月0 2 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：魏蜢 指导教师签名：譬l 兰蔓二 日期：2 8 年占, ga l , 1 9 日期： 9 彦年j l 月歹e l 中国石油大学( 华东) 硕士学位论文 第一章绪论 1 1 研究背景及意义 作为支持过程建模、优化分析、经营过程自动化的有效支持工具，工作流技术成为 近年来业界广泛应用、极力研究和迅速发展的技术。工作流技术的目标是用计算机辅助 实现业务流程，它的主要特点是使处理过程自动化，使用户以及各种应用工具相互之间 协调工作、以共同完成某项工作。 工作流技术起源于二十世纪8 0 年代初的办公自动化运动，到了二十世纪9 0 年代，随 着计算机技术、网络技术、通信技术和分布式数据库等辅助信息技术的迅速发展和成熟， 现代企业信息系统的分布性、异构性和自治性的特征越来越显著。在这种技术背景下， 工作流管理系统成为简化企业复杂信息环境、实现业务流程自动执行的必要工具，这样 一个转变，把工作流技术带入了一个崭新的发展阶段，使得人们从更深的层次、更广的 领域对工作流展开了研究。目前，工作流不仅应用在保险、银行、法律、行政管理等办 公环境，也可以应用于工业和制造等领域，种种迹象表明工作流管理已经对信息系统产 生了重大的影响。 工作流管理是以业务流程的形式化表示为基础，而把实际的业务流程抽象成计算机 可处理的形式化表示正是工作流建模的主要任务。 目前工作流建模技术还远没有成熟，还处于百家争鸣的时代。工作流过程模型描述 方法有形式化描述和非形式化描述，前者通过建模语言描述业务流程，如面向对象技术 中的u m l ，w f m c 定义的工作流描述语言等；后者是通过可视化较强的图形符号来描述 业务流程，这一类过程建模的工具很多，比较成熟的主要有：i d e f 族法、r a d 法、e e p c 法、p e t r i 网法、d f d 法等。由于工作流过程的复杂性，对于过程描述，建立可读性强， 又可以被计算机接受的模型变得尤为重要。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 工作流网，就可以很好地描述工作流模型。在工作流管理领域 取得丰硕成果的荷兰著名学者a a l s t 预言，最终所有的工作流管理系统将会基于p e t r i 网理 论来为过程进行建模。 1 2 国内外研究现状 在工作流技术应用日益得到重视的今天，对工作流模型技术的研究也正在向更深层 次进行。目前工作流模型技术自身的不成熟性【l 】主要表现在：缺乏一种能够支持过程定 义、过程演进以及过程分析的形式化数学模型。工作流模型的核心是对过程的定义，包 括组成过程的基本活动以及活动之间的顺序关系。目前的工作流模型大部分都是从直觉 出发，以图形语言或者文本语言来定义工作流过程。这种定义的方法本质上还停留在用 户层上，即对用户而言是比较理想的方式，但并不利于实际系统的实现，也无法对工作 流的本质特征进行描述。 工作流模型技术研究的课题主要为过程建模理论与建模方法。研究如何清晰准确地 表示实际应用中的过程，特别是研究如何以形式化的方法表示过程模型。这些过程模型 必须能很好的反映实际业务流程，能够对过程定义以及过程实例方便地进行动态修改， 因此需要找寻更为灵活的工作流过程形式化表示方法及过程的执行策略。 p e t r i 网作为一种从过程的角度出发描述和分析复杂系统的模型工具，被广泛地应用 在系统建模中。最早将p e 仃i 网用来建立工作流模型是e l l i s 和n u t t ，他们在p e t r i 网的基础 上提出t i c n ( i n f o r m a t i o nc o n t r o ln e t s ) 模型【2 】，它实际上是高级p “网的一个引申。这里， 2 中国石油大学( 华东) 硕士学位论文 库所表示活动，而变迁则表示活动间的转移。v a nd e ra a l s t 贝j 在p e t r i 网的基础上定义了 w f n e t 3 1 ，即工作流网，并指出用p e t r i 网来描述工作流过程的好处。在工作流网中，变 迁被用来表示活动，而库所则表示活动的使能条件。v a nd e ra a l s t 还把工作流管理联盟 在规范中提出的几种基本的工作流原语映射成相应的p e t r i 网模型，由此建立了工作流网 的基本组件与触发机制。k a m e lb a r k a o u i 等人将a a l s t 的工作推进一步，将等待工作流系 统处理的事务由1 个增加到n 个的情况下提出了多事务工作流的概念【4 】，实例的数量该模 型使得工作流系统处理事务的能力有了定量的表示。 由于基本p e t r i 网的表达能力有限，稍微复杂一些的系统就要使用大量的库所和变迁， 由此引起的“状态爆炸 问题使得p e l 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 嘶网称之为着色p e t r i l 网( c o l o r e dp e t r in e t ， 简称c p n ) 。文献【5 8 】等给出了工作流管理联盟定义的工作流元模型映射为着色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 网模型，该模型在分析工作流服务周期、资源利用率等方面具有明显优势【9 1 。 张鹏程提出了模糊着色p e t r i 网的描述方法，将模糊理论和托肯着色方法用于p e t r i 网中， 并定义映射函数，将模糊信息定量化【l o 】。宫世豪等人基于着色p e t r i 网建立了业务流程模 型，但这种模型和工作流模型有一定差距，不能运用与工作流网有关的一些验证方法【1 1 】。 所以在基于高级p e t f i 网的工作流模型的研究还需要进一步的努力：理论上需要专家和学 者做更为深入地研究和探索，实践中需要对工作流模型和p e t r i 网理论的各个方面进行全 面的再认识和实践，并加紧开发出一种自己的建模仿真工具。 在目前一般的p e t r i 网模型中，都将组织因素在流程中集成起来。但是，根据w f m c 关于工作流模型“参与者_ 扮演角色_ 执行过程 的策略机制，流程应该是三维结构， 即参与者、角色和过程。从流程基于实例的特点来看，把资源作为流程的组成部分不是 很合适。国内外许多软件的开发都采用了客户机朋艮务器的模式，这一点也同样可以运用 ， 在工作流建模当中。目前还没有一套完整的理论和技术方面的支持，今后还需要对工作 第一章绪论 流模型有更多的改进。 1 3 研究内容和成果 1 3 1 研究内容 主要对基于着色p e t d 网的工作流建模、性能分析进行有益的探讨和实践。在工作流 建模工具中用户的输入是非专业的，亦即他们的输入仅仅是表示业务流程的有向图，而 工具的分析应该建立在一定的理论模型之上，如工作流网，所以需要寻找合适的算法将 有向图映射到工作流网，并且有向图中的相应信息必须得以保存。 在工作流模型中，过程模型是执行的核心。在过程模型中，最重要的组件是活动。 具体的活动会涉及到具体的资源以及相关权限。根据这样的要求，本文从资源和过程两 个方面的角度，在工作流模型向工作流网转化做了如下工作： 首先，从资源调用的角度，在基于着色工作流网模型的基础上，根据工作流管理联 盟关于工作流模型的策略机制，提出一种用资源管理器统一管理的方法。其基本思想在 于：用统一的资源管理器来对资源进行管理，这样模型就具有了类似c l i e n t s e v e r 模型的 特性。可以通过统一定义接口，来管理所有不同属性的资源。大大简化了资源调用的复 杂性。 其次，从过程执行的角度，研究了从业务流程到工作流网的转化方法。以工作流的 四种基本流程构造结构为出发点，建立从业务流程到工作流网模型的完整映像关系。并 对每一种基本结构均给出相应的转化规则，对规则的正确性进行证明。在a a l s t 的任务结 构映射算法的基础上，结合着色p e t r i 网的性质，提出了一种基于活动网络的工作流程模 型到着色工作流网的映射算法。此映射算法能实现着色p e t r i 网建模。 1 3 2 研究成果 ( 1 ) 受c l i e n t s e v e r 思想的启示，在工作流程中，考虑将资源从流程中独立出来，用 统一的资源管理器管理。对于模型中的活动的资源获取、使用和释放的过程，设计了它 们与公共接口之间的连接。设计了资源管理器的基本模型，并通过定义正负关联函数解 决了不确定性活动的建模问题和资源申请释放问题，以及多个实例时的可能发生的混乱 状况。 ( 2 ) 在a a l s t 的任务结构映射算法的基础上，结合着色p e t r i 网的性质，提出了一种基 于活动网络的工作流程模型到着色工作流网的映射算法。该算法先给出基本结构的映射 规则，然后遍历工作流程模型即有向图，对图中的每一个状态结点应用相应的映射规则 4 中国石油大学( 华东) 硕士学位论文 进行着色p e t r i 网映射，再把转化后的着色p e t r i 网模型映射到着色工作流网，此映射算 法能实现着色p e t r i 网建模。 ( 3 ) 提出基于c p w f n e t 的工作流模型合理性概念，并总结出判定定理。然后利用p e t r i 网的标准分析技术，主要包括代数分析技术和图分析技术，结合基于着色p e t r i 网的仿 真技术，多方面分析和验证工作流模型的正确性，从而确保工作流模型正确、有效、无 死锁，保证模型能够正确运行。 1 4 论文结构 本文由以下五章和结论以及参考文献组成。 第一章绪论。介绍了论文的研究意义，国内外的研究现状以及论文的主要研究内容 和结构布局。 第二章p e t r i 网理论基础。介绍了经典p e t r i 的基本概念和性质，给出了基本概念的定 义和形式化描述，这些性质在后面描述工作流p c t r i 网的性质都将涉及到。然后指出经典 p e t r i 网在描述系统模型时候的不足，从而引f l 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 网模型。简要介绍工作流的产生和w f m c 对工作流的定义，以 及工作流模型的概念和相关知识。分析了工作流建模的现状。从概念和结构两方面，给 出了工作流向p e t r i 网的映射。首先从概念上介绍了工作流网的形式化定义以及模型中各 元素的定义和解释。然后在结构方面阐述了a a l s t 的任务结构映射方法。分别介绍了任 务结构到经典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 网的工作流过程模型，给出了详细的映射规则。提出了一 种基于活动网络的工作流程模型到着色工作流网的映射算法。最后给出了一个实例验证 规则和算法的正确性。 第五章基于c p n 的工作流模型验证。在给出建模方法的同时，论述工作流模型的合 理性验证。提出基于c p w f n e t 的工作流模型合理性概念，并总结出判定定理。然后利 用p e t r i 网的标准分析技术，主要包括代数分析技术和图分析技术，来分析和验证工作 5 第一章绪论 流模型的正确性，从而保证工作流模型的正确运行。介绍了仿真分析方法，并说明了每 种分析方法的具体应用。这一章还介绍了使用c p n t o o l s 对模型的仿真。通过交互模拟 的方法，仿真验证模型的合法性。最后给出了一个进销存系统这一实际应用案例的过程 模型。并对该模型进行了仿真和基于可达树的合理性验证。 最后对本文的研究工作进行了总结，针对不足之处提出了改进的措施，并展望要进 一步深入研究的方向，为后续工作奠定了基础。 6 中国石油大学( 华东) 硕士学位论文 第二章p e t r i 网理论基础 2 1p e t r i 网概述 p e t r i 网最早由c a p 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 网具有以下特点： 1 ) p e t r i 网具有极强的描述能力，已证明加抑止弧的p e t r i 网，其描述能力与图灵 ( t u r i n gm a c h i n e ) 是等价的。 2 ) p e t d 网又是一种可用图形表示的组合模型。对于系统中的并发、顺序、冲突、 同步、共享等关系能够建立模型并使之形象化。 3 ) p e t r i 网还是一种有严格定义的数学对象，它是建立在代数理论和语言理论等严 格的理论基础之上的一种模型，借助数学方法开发的p e t r i 网分析方法和技术既可用于静 态的结构分析，又可用于动态的行为分析。 但在实际应用中，p e t r i 网出现了两个严重不足：一是无数据概念：二是无层次概念。 这些限制使之只能进行小系统的建模。7 0 年代后期高级网和8 0 年代后期高级p e t d 网的开 发解决了这两个致命的问题。即对经典p e t r i 网进行颜色、时间和层次扩展【1 2 1 ，这种高级 p e t r i 网有机的结合了数据结构和层次分解，是少有的能同时用于验证系统功能逻辑的正 确性和评估系统性能的建模语言。此外，它还能自动的或交互的进行仿真。 有关专家曾指出，p e t r i 网模型不只是在众多模型中一种普通的系统建模工具，它必 为信息论的发展奠定坚实的理论基础。 2 2 经典p e t r i 网 2 2 1 p e t r i 网的定义 p e l r i 网是一种特殊的有向图，有两个基本元素：一是库所集p ，用圆“o ”表示，另一 个是变迁集t ，用短横“一”或竖线“i 表示：有两个表示库所和变迁之间关系的函数，即 输入函数i 和输出函数o 。库所和变迁之间用有向弧连接。 p e t r i 网也可用数学方法表达，这有助于理解其图形结构。 7 第二章p e 一网理论基础 定义2 1 ( p e t r i 网) p e t r i 网的结构是由4 要元描述的一有向图： p n s = ( p ，t ，i ，0 ) 其中： p ：库所的有限集合 p l ，p 2 ，) ，p 0 ； t ：变迁的有限集合纯，f 2 ，) ，t 0 ； i ：p x t 专n 是输入函数，它定义了从p 到t 的有向弧的重复数或权( w e i g h t ) 的集合， 这里n = 0 ，l ， 为非负整数集； o - t p - n 是输出函数，它定义了从t 到p 的有向弧的重复数或权的集合。 在表示p n 结构的有向图中，若从库所p 到变迁t 的输入函数取值为非负整数( i ) ，记为 i ( p ，t ) = ，则用从p 至l j t 的一有向弧并旁注6 0 表示；若从变迁t 到库所p 的输出函数取 值非负整数，记为o ( p ，t ) = ，则用从t 到p 的一有向弧并旁注表示。特别地，若 c a ) = 1 ，则不必标注；若i ( p ，t ) 或o ( p ，t ) = 0 ，则不必画弧。i 与0 均可表示为n 蚓 负 整数矩阵，o 与i 之差c _ 0 一i 称为关联矩阵。 我们用t 表示t 的所以输入库所的集合，f tl 表示t 的输入库所的个数；用t 表 示t 的所有输出库所( 由来自t 的弧连接的库所，即所有o ( p ，t ) o 的p 的集合，lt l 表 示t 的输出库所的个数。此外还用p 与p 分别表示库所的输入与输出变迁，它们的个 数表示为| pi 与ip f 。 定义2 - 2( 标识p e t r i 网) 标识p n 为一5 要元： p n = p n s ，m ) = p ，t ，i ，0 ，m o ) 此处： ( 1 ) p n s = p ，t ，i ，o 为p n 结构，它由定义2 - i 确定； ( 2 ) m ：p n 为标识p n 的标识，它为一列向量，其第i 个元素表示第i 个库所中的托肯数 目。特别的，m 0 为初始标识，表示初始状态。 2 2 2p e t ri 网的运行规则 在p e t r i 网中，变迁t 表示一事件，用变迁的使能( e n a b l i n g ) 表示事件发生因前提条件 得以满足而能够发生。我们用t 的输入库所( 通过指向t 的弧连接的库所) 表示该事件的发生 所需要的前提局部状态，用由输入库所至t 的输入函数定义这些要求局部前天状态实现的 次数，而局部状态的实现情况由库所中所包含的托肯数目来表示。因此，t 的使能不仅与 其输入函数有关，而且与其所有输入库所中的托肯数目有关。为此，引入以下变迁使能 规则： r 中国石油大学( 华东) 硕士学位论文 定义2 - 3 ( 使能规则) 一变迁t t 在标识m 下使能，当且仅当： 砌o t ：m ( p ) x ( p ，r ) 所有前提条件得以满座的事件的发生，将“消耗”这些前提状态，同时改变与该事 件有关的局部状态( 结果状态) ，即使得这些结果状态实现一定的次数。在p n 中，我们用 使能的变迁的激发( f i r e ) 来描述事件的发生。所消耗的前提状态及其次数通过变迁的输 入函数来定义，并以从输入库所中移去相应数量的托肯来表示；所产生的结果状态及其 次数由输出函数确定，并用输出库所中增加的托肯表示。由于输入库所中的托肯的减少 以及输出库所中托肯的增加，使得p n 的标识发生变化。为此，引入以下变迁使能规则： 定义2 - 4 ( 变迁使能规则) 在标识m 下使能的变迁t 的激发将产生新标识m ： v p e p ：m ( p ) = m ( p ) 一i ( p ，t ) + o ( p ，t ) 具体地 v p t - m ( p ) = m ( p ) 一i ( p ，t ) ； vp e t ：m ( p ) = m ( p ) + o ( p ，t ) ； v p t 八p t ( 既是t 的输入又是输出库所) ：v p e p ：m ( p ) = m ( p ) 一i ( p ，t ) + 0 ( p ， t ) ； v p 叠t 八p 诺t ( 既不是t 的输入又不是输出库所) ：v p p ：m ( p ) = m ( p ) 。 我们称标诩是( 通过t 的激发) 直接从m 可达的，记为m t y m 。 2 2 3 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 e 对实际系统进行模拟和分析的时候，系统的性能可由p e t r i 网的性质反映【1 4 l 。下 面给出p e t r i 网的各种性质所代表的系统特性。 1 可达性：( r c a c h a b i l i t y ) 可达性是p e 仃i 网的最基本的动态性质，其余各种性质都要通过可达性来定义。 定义2 5 设= ( s ，t ，i ，o ，m ) 为一个p e 仃i 网，如果存在t t ，使得m 胗m ，则 称m 为从m 直接可达的。如果存在变迁序列t l ，t 2 ，墩和标识序列m 1 ，m 2 ， m k 使得 m t l m 1 t 2 m 2 m k l k - l m k 则称m k 为从m 可达的。从m 可达的一切标识的集合记为啪。约定m e r ( m ) 。 用p e t r i 网模拟一个实际系统时，网( s ，t ，i ，o ) 描述子系统的结构，初始标识m o 9 第二章p e t r i 网理论基础 标识系统的初始状态，而r ( m o ) 给出了系统运行过程中可能出现的全部状态的集合。 定义2 6 设= ( s ，t ，i ，0 ，m 0 ) 为一个p e t r i 网，其中m 0 是的初始标识。的可 达标识集r ( m 0 ) 定义为满足下面两条件的最小集合： 1 ) m 0 r ( m 0 ) 2 ) 若m er ( m 0 ) ，且存在t t 使得m t l m ，则m r ( m 0 ) 图2 - 1 一个p e t r i 网例子p n i f i 9 2 - 1e x a m p l eo fap e t r in e tp n l 如图2 1 所示的p e t r i 网p n l ，其可达标识集r ( m o ) 为： r ( m o ) = 11 0 0 0 t ， 0 0 11 0 t ， 1 0 0 1 0 t ， o o m l t ， 0 11 0 0 t ， 1 0 0 0 1 t 2 有界性和安全性( b o u n d e d n e s sa n ds a f e n e s s ) 定义2 7 设= ( s ，t ，i ，0 ，m 0 ) 为一个p e t f i 网，s es ，若存在正整数b ，使得 v m r ( m o ) ：m ( s ：s b ) ，则称库所s 为有界的，并称满足此条件的最小正整数b h 库所s 的界，记为b ( s ) 。即 b ( s ) = m i n b ivm r ( m o ) ： m ( s ) ：g b ) 当b ( s ) = 1 时，称库所s 为安全的。 定义2 8 设= ( s ，t ，i ，0 ，m o ) 为一个p e t r i 网，如果每个s s 都是有界的，则称 为有界p e t r i 网。称 b ( z ) - - - m a x b ( s ) i s e s 为的界。当b ( ) = 1 时，称为安全的。 此定义是说，对于p e t r i 网，若存在一个整数，使得m o 的任何一个可达标识的每个库 所中的每个标记数都不超过k ，则称p e t r i 网有界；若k = 1 则称此p 嘣网为安全的。这种网 的每个库所或有一个标记，或没有标记。 容易验证图2 1 中的p e t r i 网p n l 是安全的。 l o 中国石油大学( 华东) 硕士学位论文 有界性( 安全性) 反应系统允许过程中对资源容量的需求。在实际系统的设计中，必须 使得网中的每个位置在任何状态下的标识数小于位置的容量，这样才能保证系统的正常 运行，不至于产生溢出现象。 3 活性( 1 i v e n e s s ) 定义2 9 设= ( s ，t ，i ，0 ，m o ) 为一个p e 仃i 网，m o 为初始标识，t t 。如果对任 意m e ；r ( m o ) ，都存在m r ( m ) ，使得m 胗，则称变迁t 为活的。如果任何t t 都是 活的，则称为活的p e t r i 网。 容易验证图2 1 中的p e l r i 网p n l 是活的。 系统的活性表明，无论工作流过程处于哪种状态，任意的实体所具有的功能是否至 少被执行一次。也就是说，系统的活性表明该系统是否存在死锁现象。 2 2 4p 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 仃i 网的几种分析方法【1 4 】： 1 可达标识图( r e a c h a b l em a r k m gg r a p h ) 与可覆盖性树( e o v e r a b i l i t yt r e e ) 对于有界p e t r i 网，由于其可达标识集r ( m 0 ) 是一个有限集，因此可以以r ( m 0 ) 作为 顶点集，以标识之间的直接可达关系为弧集构成一个有向图，这种有向图称为p e t r i 网的 可达标识图。通过一个p e t f i 网的可达标识图可以分析这个网系统的状态变化和变迁发生 序列的情况，从而得知网系统的有关性质。 定义2 1 0 设= ( s ，t ，i ，o ，m ) 为一个有界p 缸网，的可达标识图定义为一个三 元组r g 匹) = ( r ( m 0 ) ，e ，p ) 。其中 e = ( m ，m ，) lm ，m ，r ( m o ，3 t t ：m f i t t m ，) ) 尸：e 专t ，p ( m ，m ，) = 当且仅当m i i t 七 m ， 称r ( m 0 ) 为i 沿匹) 的顶点集，e 为r g ( ) 的弧集，若尸( m ，m ，) = 气，则称气为弧( m ，m ，) 的旁标。 然而当不是有界p e l r i 网是，由于r ( m o ) 是一个无限集，不可能画出的可达标识图， 为了用有限形式表达一个有无限个状态的系统的运行情况，需要引入一个标识无界量的 符合，具有这样的性质 1 ) 对任意正整数n ：o n ，t o + n = c 0 第二章p e t r j 网理论基础 z ) 咖 当库所s j 中的标识树在p e t r i 网的运行中趋向于无限增长是，就把标识向量中的第j 个分量改为，以此覆盖所有这类标识，这样，就可以通过一个有限树来反映这个p e l r i 网的运行情况，称这个有限树为p e t r i 网的可覆盖性树，记为c t 匹) 。 2 关联矩阵( i n c i d e n c em a t r i x ) 与状态方程( s t a t ee q u a t i o n ) 正如p e t r i 网的一个标识可以标识成一个m 维非负整数向量一样，p e t r i 网的结构也可 以用一个矩阵来表示。这样，就可以引入线性代数的方法对p e t f i 的性质进行分析。 定义2 - 1 1 设= ( s ，t ，i ，o ，m ) 为一个p e t r i 网，s = s l ，s 2 ，j 。 ，t = t l , ，2 ，r 。) ， 则p 砌网的结构( s ，t ，i ，o ) 可以用一个n 行m n 矩阵 a = 】咖 来表示。其中： 口 | ，2 口：一口i i l ，2 ，n ) ，j 1 ，2 ，m 口；= f 三当，s f 警面珂1 2 ，”，m ，c ，；7 = = f ：当( j r i ，r ，e ；j 2 7 7e ；警面，z j f e ! 1 2 ，刃曙 称a 为( 或网卜扛( s ，t ，i ，o ) ) 的关联矩阵。 定理2 - l 设= ( s ，t ，i ，o ，m 0 ) 为一个p e t r i 网，其中m 0 为初始标识，a 为的关 联矩阵，若m e r ( m 0 ) ，则存在非负整数n 维向量x 使得 姒= m o + 4 r x 上式称为p e 仃i 网的状态方程，它给出 j p e t d l 网e q a ，m 从眠可达的一个必备条件。 2 2 5 经典p e l r i 网的不足 作为一个直观的图形工具，经典p e l r i 网在一定程度上可以解决描述摸型的功能，但 是现实世界中的各种过程是很复杂的，有很多方面用经典的p e t a l 网不能完全胜任，主要 有以下一些缺陷。 1 p e t r i 网中没有全局时间的概念，即没有统一的全局时间，除非系统很小，可以被 同一只时钟覆盖住，才能使用该时钟的读数作为全局时间。缺少了时间的p