（计算机应用技术专业论文）基于扩展数据对象petri网的工作流模型的研究.pdf

华中科技大学硕士学位论文 摘要 、近年来，对工作流模型分析和描述方法的研究得到普遍重视。工作流模型是 工作流管理系统的基础，它决定了系统的行为和功能特性。良好的工作流模型应 能严格规范工作流的运行规则，从而使工作流执行程序能在运行时解释工作流模 型，f 确调度和分配任务。对工作流模型的合理性、可用性和正确性的分析和验 证也一直是工作流研究领域内的热点问题。i j 通过对当前工作流模型的研究现状的总结分析，发现针对工作流中的数据信 息的建模，方法还存在局限性。因此，为了建立一种可以合理的同时描述工作流 中的过程信息和数据信息的模型，在过程定义方面，采用p e t r i 网建模方法，建立 工作流过程模型；在数据信息方面，采用面向对象方法，建立分级多粒度的数据 模型。通过结合过程模型和数据对象模型，提出一种扩展数据对象工作流p e z r i 网 模型。 由于模型中扩充了数据信息，所以模型除了具有结构特性、行为特性外，还 具有存在性、可用性和操作匹配性等数据特性。根据出现图、覆盖图等图形分析 法、关联矩阵等线性代数法和针对原子数据对象的模型化简法，对模型的各种特 性可以进行形式化验证和分析。 模型具有形象的描述数据对象和数据操作、保持与传统分析方法的兼容、更 好的p e t rj 网仿真效果和模型修改的灵活性等特点。可以有效的描述和分析工作流 中的过程信息、数据信息及二者之间的依赖关系，为工作流模型的分析验证提供 了种有力的工具。 关键词：工作流；p e t r i 网；面向对象；数据模型 华中科技大学硕士学位论文 a b s t r a c t r e c e n t l y ，r e s e a r c ho na n a l y s i sa n d d e s c r i p t i o nm e t h o d so nw o r k f l o wm o d e lg e t s m o r ea n dm o r ec o n c e r n w o r k f l o wm o d e li st h eb a s i so fw o r k f l o wm a n a g e m e n ts y s t e m a n di td e t e r m i n e st h eb e h a v i o r sa n df u n c t i o n a lc h a r a c t e r i s t i c so ft h es y s t e m a g o o d w o r k f l o wm o d e ls h o u l ds t r i c t l ys t a n d a r d i z et h er u nt i m ef o r m u l a so fw o r k f l o w ，s ot h a t t h ei , v o r k f l o w e x e c u t i n gp r o g r a mc a r lc o m m e n t a t ew o r k f l o wm o d e lw h e ni ti sr u n n i n g ， d i s p a t c ha n da s s i g nt a s k sc o r r e c t l y a n a l y z i n ga n dv a l i d a t i n gt h er a t i o n a l i t y ，u s a b i l i t y a n dv a l i d i t yo ft h ew o r k f l o wm o d e li sa l s oo n eo ft h em a j o rr e s e a r c ht o p i c si nt h ea r e a o fw o r k f l o wf i e l d b a s e do nt h es u m u pa n a l y s i so ft h ec u r r e n tr e s e a r c ho nw o r k f l o wm o d e l s ，i ti s f o u n dt h a tt h e r ei s s o m e t h i n gl i m i t a r y i nt h ec u r r e n tm o d e l i n gm e t h o d s ，a i m i n ga t m o d e l i n go f d a t ai n f o r m a t i o no f w o r k f l o w s oi no r d e rt oc o n s t r u c tam o d e lt h a tc a n d e s c r i b et h ep r o c e s sa n dd a t ai n f o r m a t i o ns i m u l t a n e o u s l y ，o nt h ea s p e c to fp r o c e s s d e f i n i t i o n ，p e t r in e t sm o d e li sa d o p t e dt ob u i l dw o r k f l o wp r o c e s sm o d e l ；a n do dt h e a s p e c t o fo nd a t ai n f o r m a t i o nm o d e l i n g ，0 0m e t h o d si s u s e da n dah i e r a r c h i c a l m u l t i g r a n u l a r i t yd a t am o d e li s c o n s t r u c t e d t h e nc o m b i n i n gp r o c e s sm o d e la n dd a t a o b j e c tm o d e l ，aw o r k f l o w m o d e lb a s e do ne x t e n d e dd a t ao b j e c tp e t r in e ti sp r e s e n t e d s i n c ed a t ai n f o r m a t i o nh a sb e e ne x p a n d e dt ot h em o d e l ，t h em o d e lh a ss t r u c t u r a l p r o p e r t i e s ，b e h a v i o r a lp r o p e r t i e sa n d d a t ap r o p e r t i e s ，s u c ha se x i s t e n c e ，a v a i l a b i l i t ya n d o p e r a t i o nm a t c h a b i l i t y b a s e do ng r a p h i c a la n a l y s i sm e t h o d s ，s u c h a so c c u r r e n c eg r a p h ， c o v e r a b i l i t yg r a p h ，l i n e a ra l g e b r am e t h o d s ，f o re x a m p l ei n c i d e n c em a t r i x ，a n d t h e m e t h o d sa b o u tm o d e lr e d u c e ，t h ef o r m a lv e r i f i c a t i o na n da n a l y s i so nm o d e lp r o p e r t i e si s g i v e n t h em o d e lp o s s e s s e sm a n ym e r i t ss u c ha sv i s u a ld e s c r i p t i o no nd a t ao b j e c ta n d d a t ah a n d l i n g ，k e e p i n gc o n s i s t e n tw i t ht r a d i t i o n a la n a l y s i sm e t h o d s ，ab e t t e rp e t r in e t s i m u l a t i o n e f f e c t ，a n df l e x i b i l i t y o nm o d e lm o d i f i c a t i o n t h em o d e ld e s c r i b e st h e d e p e n d e n c e r e l a t i o nb e t w e e nw o r k f l o w p r o c e s s a n di n f o r m m i o n p e r s p e c t i v e ，a n d i i 华中科技大学硕士学位论文 p r o x i d e sa ne f f e c t i v et o o f o rt h ea n a l y s i sa n d v e r i f i c a t i o no f d a t ao p e r a t i o n k e yw o r d s ：w o r k f l o w ；p e t r in e t s ；o b j e c to r i e n t a t i o n ；d a t am o d e l 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 近年来企业由于面临市场竞争、全球化、减少成本及产品服务推陈出新的压 力，迫切需要新的技术以有效地分配企业资源、缩短处理时间与及提高生产效率， 尤其在大型异构的分布式环境下，需要严密的监控技术协调系统相关工作的有效 执行，这些需求使得工作流技术渐渐成为最佳的选择。 工作流从本质上讲是使在多个参与者之间按照某种预定义的规则传递文档、 信息或任务的过程自动进行，从而实现某个预期的目标，或是促使此目标的实现 1 1 2 1 。各工作项以流程的形式，由发起者发起流程，经过本部门以及其他部门的处 理，最终到达流程的终点。工作流管理系统的目标就是要协调组成工作流的四大 元素，即人员、资源、事件、状态，推动工作流的发生、发展、完成，实现全过 程监控。 一个工作流管理系统在企业应用之后预期会有下述影响： ( 1 ) 将提升企业内外多样企业活动的整合能力，增强了组织内部部门与跨组织 之间的协调与合作工作的进行。 ( 2 1 企业流程知识累积能力的增加，可汇集与加值来自不同部门或单位的知识 与心得，使得企业学习的机制更为增强。 ( 3 ) 跨越了以纸张为基准的管理限制，企业营运的管理将更有弹性与实效。 ( 4 ) 充分运用工具的特性，可以用更具弹性的作业方式满足各层不同客户的不 同需求，有助于改善企业的竞争力。 工作流管理系统巨大的潜在市场和广阔的应用领域吸引了越来越多的科研机 构与软件厂商投入到这方面的研究和开发中，更多更新的技术被集成进来，文件 管理系统、数据库、电子邮件、移动式计算、i n t e m e t , 眼务等都已被容纳到工作流 管理系统之中! 。据不完全统计，目的通用w t m s 及声称具有工作流功能的系统 已经有几百种之多。国内目前也开始出现这方面的研究与开发f 5 】。工作流技术的研 究应用r 益受到学术界与企业界的重视，许多大学和研究机构也致力于工作流技 华中科技大学硕士学位论文 术的进一步发展，开展了一系列研究项目，取得了显著的成果。 各种不同类型的系统各有其不同的特点，尤其体现在作为基础的工作流模型 定义语言方面。然而对于复杂的应用需求，一种w f m s 可能并不能捕足某个复杂的 业务过程中所有环节的需要；同时面临着分布式系统的发展趋势，不同系统之间 的信息传递与交互急需实现。这些应用上的特点要求各种不同类型的w f m s 应该可 以实现互联和互操作1 6 ，以便他们能够被纳入到一个统一的框架之中，在不同的位 置和领域发挥其各自的优势与作用。 工作流管理系统在需要一个共同遵守的标准的基础上，还要求有一种能够支 持过程定义、过程演进以及过程分析的形式化数学模型【7 。目前的工作流模型大部 分都是从直觉出发，以图形语言或者文本语言来定义工作过程，这种定义的方法 本质上还停留在用户层上，即对用户而言是比较理想的方式，但并不利于实际系 统的实现，也无法对工作流的本质特征进行描述，因而也更谈不上对过程的分析 与评价。同时，工作流验证与仿真方面尚处于一种几近空白的状态，大部分的w f m s 不提供或者仅仅提供用户手动的检查方式。 因此，本文的研究目的在于探讨工作流模型和语义的形式化表示方法，提出 种能够清晰准确的描述实际系统的建模理论与建模方法，并且建立模型验证和 仿真方法，从而实现模型的形式化分析论证，从根本上提高工作流系统的j 下确性 和可靠性。 1 2 相关研究 近年来，对工作流模型分析和描述方法的研究得到普遍重视。工作流模型是 工作流管理系统的基本，它决定了系统的行为和功能特性f 8 】a 良好的工作流模型应 能严格规范工作流的运行规则，从而使工作流执行程序能在r u n t i m e 时解释工作 流模型，讵确调度和分配任务。 1 2 1w f m c 参考模型 w f m c 提出了工作流参考模型【”，约定了工作流系统的体系结构、应用接口及 特性，主要目的是为了实现工作流技术的标准化和开放性。w f m c 的全称是 华中科技大学硕士学位论文 w o r k f l o u rm a n a g e m e n tc o a l i t i o n ，成立于1 9 9 3 年8 月，主要职责是负责w t m s 的标准 化工作。19 9 4 年1 1 月2 9 日，w f m c 发布了工作流系统参考模型( w o r f l o wr e f e r e n c e m o d e l ) 。该模型详细描述了工作流系统的有关概念，并在此基础上给出了w t m s 的主要组成部分、各部分的功能及相互间的接口。如图1 1 ，该模型由过程定义工 具、工作流执行服务、客户应用程序、被调应用程序、管理监控工具及相互阳j 的 接口组成。 过程定义工具 千接口1 t w o r k f l o wa p i 及互换格式 | 管理监f 。工作流执行服务 蚓掣僦掷j 芎 i 控工具i 飞n 5 7 i 工作流引擎卜jjii 工作流引擎一 + 接口2接口3 十 l 客户应用| ：! 卜i 被调应用 实廷仃嗣辽样头 图11 w f v l c1 作流管理系统参考模型 同其它标准一样，w f m s 参考模型给出的只是w f m s 的各个功能部分，而没有 给出任何实现的细节。实际构造一个w f m s 时有许多的技术细节需要加以考虑， 以便满足w f m s 向大规模工作流管理方向发展所需的高度的灵活性、可用性、可 。 伸缩性、可靠性以及互操作性等方面的要求。 在系统定义的基础上，w f m c 定义了一种工作流过程描述语言( w o r k f l o w p r o c e s sd e f i n i t i o nl a n g u a g e 【9 】，简称w p d l ) ，它遵从工作流管理联盟所颁布的建模 标准，在此基础上开发的工作流管理系统能够实现与现有的工作流产品相兼容， 具有良好的互操作性。w p d l 语言。主要由三部分构成| 1 0 】：基本数据类型和表达式、 工作流模型表示和语言扩展属性，其中采用关键字( 如w o r j ( f l 0 w 、a c t i v i t y ) 来描述对象、属性和关系，采用变量( 如字符串常量、占位符) 来表示实体的名 华中科技大学硕士学位论文 字和属性值。 基于w p d l 语言的工作流建模，不仅清晰地描述了业务实体对象问的关系，还 能较好地支持实体属性的逐步细化和求精，以完整、灵活和清晰的特性为现实世 界各类业务的建模提供了极大的便利。但是由于w p d l 语言的出发点是作为种标 准化描述语言而出现的，因此它的缺点在于没有提供明确的实现机制，只是一种 类似于标记语言的文本定义，在用户的直观性和系统的进一步分析方面都有所欠 缺。因此，w p d l 语言常常用作底层数据存储或者异构系统之间数据传递的标准格 式【3 4 ，而依靠附加的建模及转换工具实现模型的定义。 1 2 2 工作流模型分类 1 2 2 1 基于任务的工作流模型 在基于任务的工作流模型( t a s kf l o w ) 中任务( t a s k ) 是最基本的组件，在执行 时，工作流根据静态的流程定义格式与动态的系统运作情况以决定执行的顺序。 在图形表示上，基于任务的工作流模型是典型的有向无环图( d i r e c t e da c y c l i c g r a p h ) ，工作任务以节点( n o d e ) 表示，任务之间通过连接弧表示任务的先后次序关 系，选择条件则是通过有向弧上的标注表示的，如图1 2 所示。大部分w f m s 都采 用了这种模形，有w i d e i 1 与i b m 的f l o w m a r k 【1 2 1 。 幽1 2t a s k f l o w 范例 1 2 2 2 基于状态的工作流模型 在系统运行时，状态( s t a t e ) 是指在某个特定的时间一个对象于当时情况的抽象 化表示。由上个状态进入到下个状态则表示有某个特定的事件( e v e n t ) 或活动的发生 而触发了状态问的转移。工作流的行为是以一连串的状态转移表示。扩充后的状 念转换图( s t a t et r a n s i t i o n ) 可以表达层次( h i e r a r c h y ) 、并发( c o n c u r r e n c y ) 与工作之 华中科技大学硕士学位论文 削的通信( c o m m u n i c a t i o n ) 。借助于系统不同程度的抽象化，扩充层次模型实现了流 程模块化；并发的扩充用于描述反馈式系统( r e a c t i v es y s t e m ) 的模式化；工作之间的 通信用于描述工作间的信息交换。 在图形表达上，s t a t e t r a n s i t i o n 也是有向无环图，每一个s t a t e t r a n s i t i o n 模型都 有个开始状态与结束状态，不同于t a s kf l o w 的是，状态是以节点表示，而事件 或活动则是用状态之间的连线上的标注表示的，如图1 3 。这种建模方法中典型的 是s t a t e c h a r t s 13 1 4 ，和u m l 活动图等。 吲1 3s t a t et r a n s i t i o n 范例 1 2 2 3 基于关系的工作流模型 基于关系捕获( r e l a t i o n s h i pc a p t u r i n g ) 的工作流建模方法是根据某种特定的 关系( r e l a t i o n s h i p ) 而找出相关工作任务的集合，这些关系可能是触发或是使能 ( e n a h i i n g ) 或抑目3 t ( d i s a b l i n g ) 相关工作的条件。以触发( t r i g g e r s ) 的建模方法为例， 所谓工作被事件所触发指的是一个事件的发生造成一件工作被执行，而一件工作 是被定义为一连串事件的集合，并且在事件发生时有一人员负责此工作。以触发 为基础的工作流的基本元素是工作任务，工作与工作间的连接弧表示触发关系， 外部的事件引起触发的发生，图1 4 表示触发模式化方法。 i ) - t - 幽1 4 触发( t r i g g e r ) 范例 警 华中科技大学硕士学位论文 1 2 2 4 基于通信的工作流模型 基于通信的工作流模型( c o m m u n i c a t i o nb a s e d ) 主要在于确认各个执行者之 问的通信( c o m m u n i c a t i o n ) 关系，此方法也包含工作任务，不同的是，工作任务的出 现只在执行者通信关系产生时发生。 图1 5 是一个表示c o m m u n i c a t i o n b a s e d 模式化方法的范例，采用这种建模方法 的系统有a c t i o n t e c h 的a c t i o n w o r k f l o w 。在图例中，工作被认为是一个封闭的 循环，首先确定客户( c u s t o m e r ) 与执行者( p e r f o r m e r ) 的关系，客户与执行者之间的 通信主要分为四步：提议( p r o p o s e ) 、同意( a g r e e m e n t ) 、实行( p e r f o r m a n c e ) 与满意 f s a t i s f a c t i o n ) ，工作流依靠其间反复来回的通信完成工作。 r 。一p m l m u m m r 吐 i p e o r m b i p d 供# n n 神- _ j i c u s t o m e r l s - 卿“c l i o | i 括二 图1 5c o m m u n i c a t i o nb a s e d 范例 1 2 2 5 混合模型 由于上述四种建模方法往往在表达大型系统上过于复杂、难懂，以及是从单 方面来研究工作流系统，因而无法提供一个易懂地、一致地与可验证性地表达方 式，所以除以上四种基本模型外，还产生了其他建模方法1 8 。20 1 。主要思路是综合 上述两种或多种建模思想，从而从系统的多个侧面来描述系统行为。其中p e t r i 网建 模方法就是结合任务与状态两个层面来建立工作流模型川。 p e t r i 网最早在1 9 6 2 年由c a r la d a mp e t r i l 2 2 所提出，随后相关的研究与扩充相 继出现，例如t i m ep e t r in e t s1 2 3 1 、c o l o u r e dp e t r in e t s1 2 4 , 2 5 、o b j e c tp e t r in e t s1 2 6 2 ”、 p r e d i c a t e t r a n s i t i o np e t r in e t s 2 8 1 、s t o c h a s t i cp e t r in e t s 2 9 1 等。p e t r i n j 可以作为很多系 统的图形及数学模组工具，它对描述和研究具有并行( p a r a l l e l i s m ) 、并发 华中科技大学硕士学位论文 ( c o n c u r r e n c y ) 、同步( s y n c h r o n i z a t i o n ) 、资源分享( r e s o u r c es h a r i n g ) 等性质 的信息系统，是一种非常适合的工具川。 由于p e t r i 网具有直观的图形表示、形式化的语义、状态和事件的显示表示、丰 富的分析技术等特点，对于从理论上验证工作流程模型结构的合理性十分有效。 目前大部分的工作集中于对工作流过程模型的建立及分析上【3 0 , 3 1 ，如文献 3 2 3 5 提出了过程模型的验证方法，文献 3 6 提出模型继承的思想以实现可适应性的工作 流，文献 3 7 ，3 8 3 研究了不同系统的互操作问题。还有一部分工作集中于资源分配的 p e t r i 网模型，如文献 3 9 4 1 采用资源管理器( r e s o u r c em a n a g e r ) 自, t j 方式协调工作流 中的人力资源。 对于工作流p e t f i i n 中的数据信息的研究，或者采用单独信息视图的方法口”， 或者作为托肯的属性在高级p e m 网过程模型中附带出现 3 1 , 3 2 】，这些表示方法仅仅停 留在描述的阶段，而对于数据操作的并发和死锁问题却往往缺少行之有效的分析 验证的方法。 1 2 3 面向对象 面向对象( o o ) 的思想反映了人类思维的一般特征，即从特殊到一般以及从 一般到特殊。进入9 0 年代以来，基于这一思想而发展起来的各种技术，j 1 o o a 、 o o d 、o o p 等在计算机领域得到了广泛的应用。随着w t m s 研究的不断深入，o o 思想也被引入进来，逐渐形成了面向对象的工作流管理系统( o o w f m s 4 2 1 ) 。 1 2 3 1 面向对象方法 面向对象方法是一种运用对象、类、继承、封装、聚合、消息传递、多态性 等概念来构造系统的软件开发方法1 4 3 1 。 面向对象方法与技术起源于面向对象的编程语言( o o p l ) 。但是，面向对象 不仅是一些具体的软件开发技术与策略，而且是一整套关于如何看待软件系统与 现实世界的关系、以什么观点来研究问题并进行求解、以及如何进行系统构造的 软件方法学。概括地说，面向对象方法的基本思想是，从现实世界中客观存在的 事物( 即对象) 出发来构造软件系统，并在系统构造中尽可能运用人类的自然思 维方式。 华中科技大学硕士学位论文 面向对象方法强调直接以问题域( 现实世界) 中的事物为中心来思考问题、 认识问题，并根据这些事物的本质特征，把它们抽象地表视为系统中的对象，作 为系统的基本构成单位。这可以使系统直接地映射问题域，保持问题域中事物及 其互相关系的本来面貌。 结构化方法采用了许多符合人类思维习惯的原则与策略( 如，自顶向下、逐 步求精) 。面向对象方法则更加强调运用人类在日常的逻辑思维中经常采用的思 想方法与原则，例如，抽象、分类、继承、聚合、封装等等。这使得软件丌发者 能更有效地思考问题，并以其他人也能看得懂的方式把自己的认识表达出来。 具体地讲，面向对象方法有如下一些主要特点： ( 1 ) 从问题域中客观存在的事物出发来构造软件系统，用对象作为这些事物的 抽象表示，并以此作为系统的基本构成单位。 ( 2 ) 事物的静态特征( 即可以用一些数据来表达的特征) 用对象的属性表示， 事物的动态特征( 即事物的行为) 用对象的服务表示。 ( 3 ) 对象的属性与服务结合成一体，成为一个独立的实体，对外屏蔽其内部细 节( 称作封装) 。 ( 4 ) 对事物进行分类。把具有相同属性和相同服务的对象归为一类，类是这些 对象的抽象描述，每个对象是它的类的一个实例。 ( 5 ) 通过在不同程度上运用抽象的原则( 较多或较少地忽略事物之间的差异) ， 可以得到较一般的类和较特殊的类。子类继承超类的属性与服务，面向对象方法 支持对这种继承关系的描述与实现，从而简化系统的构造过程及其文档。 ( 6 ) 复杂的对象可以用简单的对象作为其构成部分( 称作聚合) 。 ( 7 ) 对象之间通过消息进行通信，以实现对象之间的动态联系。 ( 8 ) 通过关联表达对象之间的静态关系。 概括以上几点可以看到，在用面向对象方法开发的系统中，以类的形式进行 描述并通过对类的引用而创建的对象是系统的基本构成单位。这些对象对应着问 题域中的各个事物，他们内部的属性与服务刻画了事物的静态特征和动态特征。 对象类之恻的继承关系、聚合关系、消息和关联如实地表达了问题域中事物之问 实际存在的各种关系。因此，无论系统的构成成分，还是通过这些成分之问的关 华中科技大学硕士学位论文 系而体现的系统结构，都可以直接地映射问题域。 1 2 3 2 面向对象在工作流中的应用 面向对象方法代表了一种贴近自然的思维方式，它强调运用人类在r 常的逻 辑思维中经常采用的思想方法与原则。面向对象方法中的抽象、分类、继承、聚 合、封装等等思维方法和分析手段，能有效地反映客观世界中事物的特点和相互 的关系。而面向对象方法中的继承、多态等特点，可以提高过程模型的灵活性、 可重用性。因此，应用面向对象的方法将降低工作流分析和建模的复杂性，并使 工作流模型具有较好的灵活性，可以较好地反映客观事物。 关于o o w f m s 的研究有两个不同的层面。其一是指w f m s 的实现使用o o p 的方 法，即将w f m s 系统中的各种元素以对象的形式加以描述，并在某种环境下加以实 现，从而实现系统要素的重构与重用。例如，i n c o n c e r t 将各种类型的对象保存在 - - 种r d b m s 中【4 2 】；c o d a l 坝0 是基于o s fd e c 的o o 扩展d c h 而实现的【4 4 】； f l o w m a r k l ) ! l j 以c + + 为编程语言，并将所有的对象保存在一个名为o b j e c t s t o r e 的 o o d b m s 中 4 5 1 。 o o w f m s 研究的另个方面是关于面向对象的工作流过程模型1 4 6 - 4 8 ，即使用 面向对象的方法来完成业务过程的分析建模，并得到相应的对象表示。在文献 4 8 1 中给出了一种可以定义对象之动态关系的扩展对象模型，而由各种动态关系联系 起来的多个对象构成的联盟则可以有效地表示工作流程。这种模型在通用的分布 式对象技术环境下实现起来比较容易。 1 3 本文的研究重点 本文的研究设想是结合建立可以同时描述过程信息和数据信息的工作流模 型，因而在过程模型方面，采用p e t r i 网建模方法；在数据信息方面，采用面向对象 方法。通过组合过程模型和数据对象模型，建立工作流模型，同时借助经典p e t r i 分析方法，对模型进行有效性验证。 课题的主要工作有： ( 1 ) 研究p e t f i 网建模理论： 华中科技大学硕士学位论文 ( 2 ) 借助面向对象方法，建立数据对象模型； ( 3 ) 建立包含数据和过程信息的工作流模型； ( 4 ) 分析模型特性并提出验证方法。 出于p e t r i 网具有强大的建模分析能力和算法，可以预计，通过结合数掘和过程 模型，建立完善的工作流p e t r i i n 模型，可以实现对工作流中过程和数据的双重有效 性验证，从而为工作流管理系统提出一个先进的模型。 华中科技大学硕士学位论文 2 基于p e t r i 网的工作流模型 本章着重探讨应用p e t r i 网理论进行工作流建模的总体技术方案。p e t r i 网 ( p e t r i n e t ，p n ) 是一种很有效的模型描述语言，主要用来对系统设计、分析和模拟。 首先分析普通p e t r i 网和高级p e t r i 网建模分析的原理，研究了p e t r i 网在工作流建 模中的应用，分析其不足之处，并提出改进方向。 2 1p e t ri 网 p e 讲网是一个有向图，由两种节点组成f 2 1 ，即库所( p l a c e ) 和变i z t _ ( t r a n s i t i o n ) 。 有向弧( a r c ) 可以从库所指向变迁，或者从变迁指向库所。若以图形表示，则库所以 圆形表示，变迁以方块或者条形表示。标识( m a r k i n g ) 为每个库所指定了一个非负 的整数，表示该库所内所含托肯( t o k e n ) 的数目，在图形中表现为库所内的黑点的个 数。首先介绍p t 网的概念，这是种标准p e t r i 网，也是后继研究的基础。 2 1 1p t 网 定义2 1 ( p t 网) 一个p t 网是一个三元组n = ( p ，t ，f ) ，其中 p = p l ，p 2 ，p i t i ) 是一组有限的库所集合， r = t l ，t 2 ，t n 是一组有限的变迁集合， f ( p t ) u ( t p ) 是组有向弧集合， 其中p nt = 中且p u t 中 图2 1 是一个简单的p t n j 的图示。p t i n 也被称为正规化p e t r i 网，这是相对于 带有权重的p e t r i 网而言的。为了描述系统的动态特性，定义变迁的激发规则如下。 定义2 2 ( 前集，后集) = ( p ，t ，f ) 是一个p t 网。对于每个n p u t ： n 2 n o p u t ( n 0 ，n ) f ) ( n 的前集) 且 n 2 n o p u ti ( n ，n o ) f ( n 的后集) 华中科技大学硕士学位论文 定义2 3 ( 激发规则) n 2 ( p ，t ，f ) 是一个p t 网，m 是n 的一个标识，并且t t ( 1 ) m 授权t ，当且仅当t m ( 2 ) m i 是m 通过激发t 可以到达的( 表示为m t m 1 ，当且仅当m 授权t 并 且m 1 = m - t t t 图2 】一个简单的p t 网 在利用p e t r i 网模拟系统时，可以利用p e t r i 网对并发系统的诸多性质来进行 分析。系统的特性可以分为两种：种与初始标识相关，称为行为特性；另一种 则是与初始标识无关的，称为结构特性。现在已经发展出很多工具用于计算分析 p t 网的行为特性。 行为特性主要有可达性( r e a c h a b i l i t y ) 、有界性( b o u n d e d n e s s ) 、活性 ( l i v e n e s s ) 、返回性( r e v e r a b j t y ) 、覆盖性( c o v e r a b i t y ) 、肇持性 ( p e t s i s t e n c e ) 、同步距离( s y n c h r o n i c d is l a n c e ) 、有界公平性 ( b o u n d e d f a i r n e s s ，b - f a i r ) 等。详细定义可参见文献 3 3 主要分析方法有出 现序列( o c c u r r e n c es e q u e n c e s ) 、出现图( o c c u r r e n c eg r a p h ) 、覆盖图 ( c o v e r a b i l i t yg r a p h ) 、有限覆盖图( r e s t r i c t e dc g ) 等。 结构特性主要有( 强) 连通性( ( s t r o n g l y ) c o n n e c t e d ) 、良好句柄 ( w e l l h a n d l e d ) 、自由选择( f r e e c h o i c e ) 、s 一可覆盖( ( s - c o v e r a b l e ) ) 等。 主要分析方法有s 一分支( s - c o m p o n e n t ) 、s 一不变量( p l a c e - i n v a r i a n t ) 和t 一不变 量( t r a n s i t i o n i n v a r i a n t ) 等线性代数的计算方法。 2 1 2 高级p e t r i 网 普通p e l ：r ：网导出的模型对于小型系统描述和分析都很有效，但对于大型系 统，由于节点个数过多，对于实际应用带来很大困难。因此扩展出现高级p e t rj 网。 谓词变迁网( p r tn e l s ) 为每个库所定义一个外延可变的谓词，谓词的主 华中科技大学硕士学位论文 体可以是个体，也可以是由个体组成的多元组”。每个变迁都与一个公式相关联， 其中可以包括个体集上有定义的运算以及外延不变的谓词。每条弧都标注有一个 由项的多元组构成的符号和。项由变量名和个体名以及它们组成的多元组构成。 在系统的任何状态下每个个体都恰属于一个谓词的外延。 有色p e t r i 网( c o l o u r e dp e t r in e t s ) 通过为托肯附加颜色( 类型) 而扩展 得到”“。不同颜色的托肯表示不同的数据类型，每个库所和变迁也都定义了所有 可能出现色的集合，有向弧上定义了操作函数，用于精确表示不同的转换规则。 由于有色p e t r i 网方便的表达能力，在实际建模中得到了很多应用，进而扩展出对 象p e t r i 网。 面向对象p e t r i 网( o b j e c to r i e n t e dp e t r in e t s ) 是将有色p e t r i 网和面向 对象技术融合而成”“2 “。根据结合的角度不同，可以分为三类： ( 1 ) 基于有色p e t r i 网的对象模型的形式化描述 目的是用p e t rj 网为对象模型提供一种形式化的分析和验证手段，它把一个类 的属性、消息和方法集映射到一个有色p e t r i 网的库所、变迁和有向弧集合，再采 用p e t r i 网的分析技术完成形式化的验证工作”9 。“。 ( 2 )基于对象思想的有色p e t r i 网建模 p e t r i 网处理复杂问题的办法是对系统建立层次化和模块化的模型，而面向对 象思想可以把各个单元网更好地组织起来，以直观反映系统的结构和功能分布、并 使建模过程符合人们的思维模式。由于p e t r i 网最重要的应用是系统建模以及在模 型基础上对系统进行分析，所以基于对象思想的p e t r i 网建模方法是二者相结合最 为常见的一种方式”1 。”。 ( 3 )基于对象的有色p e t r i 网 直接将面向对象的思想融入到p e t r i 网的定义中去，产生一种具有面向对象特 点的p e t f j 网扩展形式可以将二者更加紧密地结合起来。大多数这类性质的p e t r i 网扩展形式的定义主要注重于表现对象的封装，以达到信息隐藏和高度模块化的 目的j1 。；1 。 华中科技大学硕士学位论文 另外还有分) 罢p e t r i 网( h i e r a r c h i c a lp e t r in e t s ) ，通过变迁细化或者库所 置换的方式实现模型的分层表示“；时i & p e t r i 网( t i m e dp e t r in e t s ) ，为变迁 规定获得发生权后的等待时间或者是发生延续时间”“；随机p e t r i 网( s t o c h a s t ic p e t r in e t s ) ，在变迁上加入随机因素“；连续p e t r i 网( c o n t i n u o u sp e t r in e t s ) 库所中的托肯个数可以是实数；混合p e t r i 网( h y b r i dp e t r in e t s ) 等等。 2 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 网除了提供图性化的表达方式之外，也提供形式化 的语义以数学的方式表示。 ( 3 ) 丰富的分析技术：p e t r i 网具有结构特性和行为特性，并且提供许多方法 以验证模型。 ( 4 ) 符合工作流六个基本要素：p e t r i 网符合工作流管理联盟所制定的工作流 六个基本要素。 ( 5 ) 目前多种支持p e t r i 网的工具可以对工作流提供建模和分析的能力。 由于p e t r i 网具有上述特点，对于从理论上验证工作流程模型结构的合理性十 分有效。表示工作流的p e t r i 网又可称为w fn e t s 3 3 1 。 2 2 1w fn e t s w fn e t 的构造是十分直观的，变迁表示工作任务，库所表示变迁激发的条件， 库所内的托肯表示工作流系统所处于的状态。因此，w fn e t 可以同时从任务和状 态两方面来描述系统。 4 华中科技大学硕士学位论文 定义2 4 ( w fn e t ) 一个p t 网n = ( p ，t ，f ) 是一个工作流网( w fn e t ) 当且仅当 ( 1 1i p 八i = 由 ( 2 )o p a 0 = 中，且 ( 3 )短路p t 网( p ，t u t ) ，f u ( 0 ，t ) ，( t ，i ) ) ) ，表示为n ，是强连通的，其 中t u t w fn e t 要求每个模型仅有一个起始库所i 和一个终止库所0 ，标志着流程的起 点和终点。短路网是指在p t 网中加入个辅助变迁t ，和两条连接弧( 。，t ) ，( t ，i ) ， 从而连接终止库所和起始库所，如图2 2 所示。由于工作流中不允许有死变迁，因 而要求短路网是强连通的，即每个变迁都有可能被激发。 0 图22 一个短路p 厂r 网 w fn e t 提供了四种路由：顺序、并行、选择和循环。 顺序流程是最常见的一种路由，表现了任务之间的诱发关系。 并行流程表示同时授权几个任务( a n d - s p i t ) ，任务之间的执行次序无关紧 要，但这些任务都必须完成后才能接着执行别的任务( a n d j o i n ) 。 选择流程表示对于不同的事件可能会选择一个或多个不同的分支任务。选择 流程又可以分为非确定性选择和确定性选择。在非确定性选择流程中，分支任务 的选择由工作流运行的环境所决定，构造模块采用i m p l i c i zo r s p l i t u i m p l i c i t o r j o i n 配合使用；确定性选择流程中，分支任务的选择由事件的属性来决定，构 造模块采用e x p i c i to r s p i t $ j e x p l i c i to r j o i n 配合使用。 循环流程实际上也是一种选择流程，因此可以用e x p l i c i to r s p l i t 来建模， 构造模块中的变迁同时也起 l j e x p l i c i to