（计算机软件与理论专业论文）基于有色对象petri网的工作流建模与分析.pdf

河海大学硕士学位论文摘要 摘要 工作流管理系统的最重要功能之一就是工作流建模一个好的工作流模型是实现一个具 有高度灵活性、可靠性、可用性、可伸缩性和互操作性的工作流管理系统的关键和基础工 作流建模主要是研究如何清晰、准确地表示实际应用中的业务过程，特别是研究如何以形式 化的方法表示工作流模型。 一个工作流系统成功的关键在于向其输入的工作流的质量。因此，工作流的建模和分析 就显得特别重要 面向对象p e t r i 网是目前工作流研究的热点之一，其目的是利用面向对象技术提供的抽 象的封装、分类以及继承机制。简化复杂系统的建模 单一的建模技术因其自身特点和局限性，无法很好地完成从系统建模、分析到验证的全 部任务改进和扩展单一的建模技术，将面向对象建模技术与p e t r i 网建模技术结合在一起， 综合两种建模技术的优势，克服彼此存在的主要缺陷，走复合建模技术的道路是解决大规模 复杂系统建模问题的主要途径在建模过程中利用面向对象的概念对系统进行功能划分。将 复杂系统的建模分解成若干子系统的建模，从而使得p e t r i 网建模技术既适用于大型系统的 建模，又有效的解决了状态空间“爆炸”的问题 本文提出的有色对象p e t r i 网模型c o p n ，用子网来描述对象，对象之间的通信用门变 迁来实现。论文给出c o p n 的形式化定义之后，对一个系统进行了c 0 p n 建模，并且基于分层 思想采用可达树方法对模型予以验证，最后，根据前面的分析，设计了一个名为c o p n - f l o w 的工作流建模工具 关键词：面向对象，颜色，p e l r i 网，工作流，建模 河海大学硕士学位论文 a b s t r a c t o n eo ft h em o s ti m p o r t a n tf u n c t i o n so faw 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 l i n g ag o o d w o r k f l o wm o d e li st h ek e ya n df o u n d a t i o nf o ran e ) 【i b i c 。c r e d i b l e 。u s e f u la n dm u t u a l l yo p e r a b l e w o r k f l o wm a n a g e m e n ts 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 s t h eo p e r a t i o np r o c e s so ft 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 t h es u c c e s s f u lk e yo f t h ew o r k f l o ws y s t e mi st h eq u a l i t yo f t h ew o r k f l o wm o d e l t h e r e f o r e ，t h e m o d e l i n ga n da n a l y z i n go f t h ew o r l l 【f l o wi sv e r yi m p o r t a n t o b j e c t - o r i e n t e dp e t r in e ti st h eh o tp o i n to fp r e s e mr e s e a r c h i n ga r e a , w h o s ec h a r a c t e r i s t i ci s s i m p l i f y i n gc o m p l i c a t e ds y s t e mm o d e l i n gb ye n c a p s u l a t i o n , c l a s s i f i c a t i o na n di n h e r i t i n gs u p p l i e d b yo b j e c t - o r i e n t e dt e c h n o l o g y as i n g l em o d e l i n gt e c h n o l o g yc a n td ow e l li ns y s t e mm o d e l i n g , a n a l y z i n ga n dv a l i d a t i n g b e c a u s eo fi t so w l d i s a d v a n t a g ea n dl o c a l i z a t i o n t os o l v et h i sq u e s t i o n , p u t t i n go b j e c t - o r i e n t e d m o d e l i n gt e c h n o l o g ya n dp e t r in e tm o d e l i n gt e c h n o l o g yt o g e t h e ri sa v i a b l ew a y t h i sm e t h o d ， w h i c hm a k e su s eo f t h ea d v a n t a g e so f t h et w om e t h o d sa n do v e r c o m e st h em a i nd e f e c t se x i s t i n gi n e a c ho t h e r , i sap r h n a r yw a yt om o d e l i n gt h ec o m p l i c a t e ds y s t e m a n a l y z i n gt h es y s t e mu s i n gt h e c o n c e p t si no b j e c t - o r i e n t o dt e c h n o l o g y , b r e a k i n gt h ec o m p l e xs y s t e mi n t os o m es u bs y s t e m , m a k e si tp o s s i b l ef o rp e t r in e tt om o d e l i n gal a r g es y s t e ma n di ts o l v e st h es t a t es p a c e ”e x p l o s i o n ” p r o b l e m t h i sp a p e rp r o p o s e sac o b r o do b j e c t - o r i e n t e dp e t r in e tm o d e l - c o p n , w h i c hd e s c r i b e so b j e c t b ys u bn e t e a c ho b j e c tc o m m u n i c a t e sw i t he a c ho t h e rb yg a t et r a n s i t i o n t h e n ，t h i sp a p e rg i v e s c o p n sf o r m a ld e f i n i t i o n , a n dam e t h o dt om o d e l i n gas y s t e mu s i n gc o p na n dv a l i d a t et h e e x i s t i n gm o d e l i nt h ee n d ，t h ep a p e rd e s i g n sa c o p n m o d e l i n gt o o ln a m e dc o p n - f l o w k e y w o r d s ：o b j e c t - o r i e n t e d , c o l o r , p e t r in e t , w o r k f l o w , m o d e l i n g 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 型叠乎 卯年必月0 2 日 ( 注：手写亲笔签名) 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：至2 叠生0 7 # 口4 月口2 日 ( 注：手写亲笔签名) 河海大学硕士学位论文第一章绪论 1 1 研究背景 第一章绪论 工作流技术是计算机应用领域的一个新的研究热点。 工作流概念产生于2 0 世纪7 0 年代末办公自动化领域的研究“1 ，由于当时各 项技术的不成熟，这项新技术并没有太大的发展。到了8 0 年代，随着社会经济 的发展，企业的规模日益庞大，需要处理的信息资源也飞速增长，企业的经营业 务过程也越来越复杂，人# h i 常希望出现一种无纸化的、计算机协同的工作环境。 些公司和企业为此建立了自己专用的或者可商品化的表单传递应用系统 ( f o r m s - r o u t i n ga p p l i c a t i o n ) ，用来实现对日常表单的电子化或自动化处理。 这些可以看成是工作流管理系统的雏形。 1 9 9 3 年，工作流管理联盟( 肋r k f l o wm a n a g e m e n tc o l i a t i o n ，1 f m c ) 的 成立标志工作流技术开始进入相对成熟的阶段。 目前，在全球范围内，对工作流的技术研究以及相关产品的开发已经进入 了更为繁荣的阶段，更多更新的技术被集成进来，文件管理系统，数据库，电子 邮件，移动计算，i n t e r n e t 服务等都已经被容纳到工作流管理系统中。工作流 产品的市场也以每年两位数字的速度迅速增长圆 w f m c 给出的工作流的定义是0 1 ：工作流是一类能够完全或部分自动执行的经 营过程，在这个过程中，文档、信息或任务能够根据一系列过程规则在不同的执 行者之间进行传递与执行。为了使工作流的概念和接口标准化，并实现不同工 作流产品之间的互操作，胃f m c 在工作流管理系统的相关术语、体系结构及应用 编程接口( w a p i ) 等方面制定了一系列标准，它制定了工作流管理系统组织结构 的参考模型，并给出了五大接口标准，其中接口l 是过程定义数据，以及过程定 义数据的转换规范接口，它也是工作流建模主要研究的接口。 工作流建模，也称流程建模或过程建模，是使用一定的分析、建模和定义 技术，将现实世界中的业务流程翻译成可用计算机处理的流程模型。流程定义是 整个工作流管理系统的核心之一，w f m c 在2 0 0 2 年发布的基于x m l 的流程定义语 言x p d l 旧标准实现了流程定义在不同工作流管理系统之间的互操作性。 目前工作流的技术还不够成熟，市场上不同厂商提供的工作流产品都具有 独立的一套工作流模型、工作流定义语言以及a p i 函数。因为不同的系统之间缺 乏互操作的接口，一旦用户选定一种产品之后，很难再过渡到其他同类产品上。 目前在工作流建模方面还没有形成一套比较成熟的理论和方法，特别是模型验证 方面，严格的理论上的分析还几乎处于空白”。 河海大学硕士学位论文 第一章绪论 图卜l 给出了w f m c 提出的工作流参考模型的示意图，它总共有五个接口， 能够满足工作流管理系统和产品所应该具有的主要功能特征，为实现工作流产品 之间互操作提供了公共的基础m 。 圈卜l 工作流参考模型 本文的工作主要是对工作流建模的研究，因此只与接口l 有关，即过程定义 接口，接口l 为工作流过程定义信息的交换提供了标准的互换格式”。工作流过 程定义工具主要是用来分析、建模、描述并记录经营过程，它输出一个能被工作 流引擎动态解释的过程定义。 使用标准的过程定义格式有下列好处： i 把建模阶段和运行环境进行了分离，建模工具和工作流运行工具可以不是 同一个产品，这样使所建模型更具有灵活性。 2 可以为几个工作流引擎输出过程定义，通过这几个工作流引擎的合作来构 成分布式的工作流执行服务器。 1 2 工作流模型 工作流模型就是对工作流的抽象表示，也是对业务过程的抽象表示。工作流 模型是整个工作流管理系统的基础，模型描述能力的强弱决定了系统所支持的应 用范围以及系统的灵活程度。根据w f m c 的规定，工作流模型的功能是将显示的 业务过程模型转换成计算机化的形式，并在此基础上完成工作流的运行和管理。 工作流建模方法学研究的主要内容是提供一套完整有效的描述业务流程的 建模语言。对流程的描述需要提供对逻辑控制结构( 如顺序、分支、汇合、条件、 循环、并行等) 的描述。即至少要满足w f l c 提出的六种活动类型。使用者可 河海大学硕士学位论文 第一章绪论 以通过这一套语言来建立企业业务流程的形式描述。它主要体现为如何根据过程 目标和系统约束条件，将系统的活动组织为适当的业务流程。 工作流管理联盟为工作流建模做了以下两个方面的工作： 1 建立一个元模型。它用于描述一个过程模型内各个对象，以及它们之间的 关系和属性，这有利于多个工作流产品之间交换模型信息。工作流过程元模型如 图1 - 2 所示。 2 定义一套可以在工作流管理系统之间及在管理系统与建模工具之间交互 过程模型定义的s p i 接口。 圊l - 2 工作流过程元模型 过程定义的元模型中定义了基本的对象类型集，来满足简单的过程定义相互 转换。过程元模型的组成核心是活动。一个工作流模型由若干活动组成，而模型 通过转换条件推进过程实例的运行，实例在运行的过程中可能需要参与者的控制 或者使用相关的数据，并且可能激活相关的应用程序。 对于流程模型的评价，文献 9 提出了理想的工作流模型的条件： 1 表达能力丰富：模型提供丰富的建模概念，使得由大量约束集合而成的元 素能够在模型中被直接表达出来； 2 ，容易理解：不论是领域专家还是普通用户，都能够比较容易地理解模型含 义： 3 最小化：模型中的概念不重叠，每一个基本概念都有它特定的意义； 4 形式化：模型定义能够作为现实对象的精确的形式化描述，支持对模型的 分析验证。 1 3 研究现状 虽然工作流技术发展迅速，但是其技术和产品都没有到成熟时期。因此，以 w f m c 提供的规范标准为参考，对工作流建模理论和方法的研究工作在不断地进 行着，主要有流程图、状态图、活动网络图“”、t d e f 系列、e c a a ( 事件一条件一 动作规则) 、并发事务逻辑“”、p e t r 网以及扩展事务模型的建模方法。 综合来看，基于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 网的工作流建模中采用的主要有信息控制网 ( i n f o r m a t i o nc o n t r o ln e t ，i 蜊) ，时态约束p e t r i 网( t e m p o r a lc o n s t r a i n t p e t r i n e t ，t c p n ) ，着色p e t r i 网( c o l o r e dp e t r i n e t ，c p n ) 等扩展p e t r i 网。 w m p v a nd e rh a l s t 等提出基于高级p e t r i 网的框架结构“”，该结构用于建模 和分析经营过程，并利用“w h a t ，h o w ，b yw h o m ”的方法引导模型框架的应用。在 p e t r i 网基础上，飘m p v a nd e ra a l s t 提出了工作流网( w f - n e t ) 的概念，将时 间约束函数引入n f - n e t ，即t w f - n e t 。杜栓柱通过分析t 1 i | r f n e t 模型不足之处， 建立了扩展的时间p e t r i 网工作流模型( x t w f - n e t ) ，用于处理过程描述中的模 糊信息描述问题“”。张鹏程提出了模糊着色p e t r i 网的描述方法，将模糊理论和 托肯着色方法用于p e t r i 网中，并定义映射函数，将模糊信息定量化“。 面向对象技术( o o t ) 适合由许多活动实体构成的复杂、大规模系统的建模 和分析，并且能够将建模和分析融为一体。o o t 和其它模型理论，如p e t r i 网结 合起来用在工作流建模中是有待深入研究的内容。将p e t r i 网与面向对象的方法 结合，汲取面向对象方法的模块化、多态、重用性及继承的优点，并保留p e t r i 网的理论化验证基础，有可能成为工作流建模的一个研究方向。曹化工教授提出 了运用对象p e t r i 网( 0 p n ) 和基于o p n 的文本描述语言l o o p n + + 作为工作流过程 定义的表达方式和存储形式，使得工作流过程定义既有严格的形式化描述，又有 直观的图形表示u ”。 1 4 本文工作与组织 1 4 1 研究内容 本文在分析工作流在国内外发展的现状，以及近年来一些学者对工作流建模 方面的研究与成果的基础上，研究了p e t r i 网和面向对象分析思想的优缺点，将 两者的优点结合，产生新的模型，并对模型的正确性进行验证。并且用实例说明 模型建立和验证的方法和步骤。 4 河海大学硕士学位论文第一章绪论 本文的主要研究内容如下： 1 c o p n 模型及有色对象工作流网的形式化定义 把p e t r i 网建模和面向对象分析的方法结合起来，提出一种面向对象的 p e t r i 网模型，并给出该模型的形式化定义。然后，进一步根据a l a s tt 作流网 的原理，把面向对象的p e t r i 网模型提升为面向对象的工作流网。 2 有色对象工作流网向x p d l 的映射规则 为了使生成的模型可以和其他的工作流产品有良好的接口，采用x p d l 标准 定义面向对象p e t r i 网模型的语法。论文给出了面向对象工作流网中的实体到 x p d l 中各个实体的映射规则，分别给出了o p n ，门变迁，各种路由结构以及相关 信息向x p d l 的映射规则。 3 有色对象p e t r i 网( c o p n ) 的建模过程 论文对有色对象p e t r i 网( c o p n ) 给出了建模步骤。并且以国家外汇管理局 的外汇检查程序为例，进行详细分析，用实例展示了使用有色对象p e t r i 网建模 的步骤以及验证模型的可行性。 4 有色对象p e t r i 网( c o p n ) 模型的正确性验证 随着工作流技术的发展，市场上出现了很多基于不同理论的工作流产品，但 这些产品都存在一个很大的问题，即忽略了工作流模型验证。目前，几乎没有任 何工具提供验证支持，这主要是因为工作流的验证是一件复杂的工作“”。但是， 工作流模型的验证有时一件非常重要的事情，没有经过验证的工作流模型可能会 在运行中发生致命的错误，造成很大的损失。 高级p e t r i 网的验证一直是个比较复杂的问题。本文针对c o p n 的特点，提 出了一种基于分层思想的模型验证方法，在两个层次分别采用等价替换和改良的 可达树的方法对c o p n 模型进行验证。首先对对象p e t r i 网( o p n ) 采用等价替换 法进行合理性验证，然后用可达树算法对系统的合理性进行分析。为了降低可达 树算法引入。带来的影响，提出了一种改善的可达树算法，可以通过设定参数 来判断p e t r i 网的有界性。 5 基于c o p n 的建模工具c o p n f 1 明的软件实现 基于本篇论文前面几章对c o p n 的研究与分析，提出了一个面向对象建模工 具( c o p n - f l o w ) 的系统架构，并且讨论了向对象的工作流建模工具( c o p n - f l o w ) 的开发过程。该建模工具的主要功能是通过图形化的界面完成基于有色对象 p e t r i 网的流程建模，流程模型在经过x p d l 语法检查和p e t r i 网合理性分析之 后生成符合x p d l 标准的x m l 流程定义文件。 模型定义及其正确性在整个工作流管理系统中非常重要，因此工作流的建模 和合理性分析都非常重要。本篇论文通过对工作流建模过程和合理性分析两个方 面对c o p n 模型进行描述，能够处理实际业务中较复杂的业务流程的建模和分析， 河海大学硕士学位论文 第一章绪论 避免建模过程中p e t r i 网状态空间爆炸的问题，并且能够避免单纯使用可达树算 法造成的可达树节点过多的缺点。 1 4 2 论文组织 论文共分成六章。 第一章绪论：简要介绍工作流，工作流管理系统的产生，以及工作流模型 的概念和相关知识。这一章还分析了工作流建模的现状，介绍了论文的研究背景， 研究现状以及论文的主要研究内容和布局。 第二章理论基础：介绍了p e t r i 网理论的基本概念，p e t r i 网用于工作流 建模的基本思想以及高级的p e t r i 网和使用p e t r i 网进行工作流模型分析的方 法；接着介绍了x p d l 标准和格式，以及在本论文中为何使用x p d l 标准；最后简 单介绍了a l a s t 提出的工作流网。 第三章面向对象工作流网：这一章首先给出了工作流的概念向p e t r i 网映 射的规则，然后将p e t r i 网技术与面向对象建模思想结合起来，提出了面向对象 工作流网c o w f - n e t 。这一章详细给出了它的形式化定义以及如何用论文提出的 建模方式对系统进行建模。为使建模方式有标准的接口，还给出了c o w f n e t 向 x p d l 映射的标准。最后给出了一个建模实例。 第四章基于分层思想的验证算法：该章首先从结构上对c o w f - n e t 模型进行 分析，根据它的特点，提出了一种基于分层思想的工作流模型验证算法。在o p n 层次上，采用等价替换的方式来验证合理性，在整体层次上，考虑到p e t r i 网的 有界性，提出一种改良的可达树算法验证合理性。最后，给出了该验证算法的实 例。 第五章工作流建模工具的实现：根据前几章的成果，给出了与前几章对应 的建模工具的软件实现。这一章还给出了建模工具的功能介绍和整体构架，以及 各功能模块所要用到的类。 第六章总结与展望：总结全文工作，并给出下一步工作的展望。 6 河海大学硕士学位论文第二章理论基础 2 1p e t r i 网 第二章理论基础 p e t r i 最早由c a r la p e t r i 博士与1 9 6 2 年在他的博士论文中提出“”。论文 中采用p n 网络描述计算机系统事件之间的因果关系。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 网具有两个严重不足：一是无数据概念；二是无 层次概念洲这些限制使之只能进行小系统的建模。7 0 年代后期高级网和8 0 年 代后期高级p e t r i 网的开发解决了这两个致命的问题，即对经典p e t r i 网进行颜 色、时间和层次扩展1 。这种高级p e t r i 网有机的结合了数据结构和层次分解， 是能同时用于验证系统功能逻辑的正确性和评估系统性能的建模语言。此外， 它还能自动或交互地进行仿真。 2 1 1 基本p e t r i 网 定义1 ：三元组p n ( p ，t ：f ) 称为p e t r i 网，当且仅当叫1 ： 1 p n t = o ： 2 p u t 0 ： 3 f _ c p t u t p ： 4 d o r a ( f ) u c o d ( f ) = p u t 河海大学硕士学位论文第二章理论基础 其中，p 叫做p n 的库所( p l a c e ) 集，t 叫做变迁( t r a n s i t i o n ) 集，f 叫做 流关系( f l o vr e l a t i o n ) 。p 中的元素叫库所或p 元素，t 中的元素叫变迁或t 元素。f 是由一个p 元素和一个t 元素组成的有序偶的集合。d o r a ( f ) 是f 所含有 序偶的第一个元素所称的集合，c o d ( f ) 是第二个元素的集合： d o m ( f ) = f x lj y ：( x ，y ) f ， c o d ( f ) = ( y lj x ：( x ，y ) f d o m ( f ) 与c o d ( f ) 分别为f 的定义域和值域。 p n 的标准图形表示是用圆圈代表库所，用方框表示变迁，用从x 到y 的有向 弧( 箭头) 表示有序偶( x ，y ) 。 t 3 田2 1 垂本p e t r i 网 图2 - i 是一个p n 的图例。图中库所p l 中出现的小黑点称为托肯( t o k e n ) ， 又叫标记，它用来描述p e t r i 网中资源的流动，它随着变迁的激发在p e t r i 网模 型中流动。 下面给出p n 元素的前集和后集的定义。 定义2 ：设x e x 为网n = ( p ，t ；f ) 的任一元素，令木x = y l ( y ，x ) f ) ， x g f = - ( y l ( x ，y ) f ，乖x 叫做x 的前集，又叫x 的输入集；x , l qx 的后集，又 叫输出集。 定义3 ( p n 的性质) 1 n t _ ( p ，s ：f ) 叫做网n = ( p ，t ；f ) 的对偶网； 2 n - = ( p ，t ；r 1 ) 叫做网n = ( p ，t ；f ) 的逆网； 3 n = ( p ，t ；f ) 是个简单网的充分必要条件是 v x ，y x ：( _ 噬= 车y n x _ c = y 木) ：孛x = y 简单网要求它的元素都能从前集或后集区分开。 4 如果对所有x x 都有, x n x ，i z = 0 ，就说n 是个单纯p n ，简称纯网。 单纯网要求任何元素不能既是另一元素的输入，又是它的输出。 5 若i x i 无穷大，则n 是有限网。 河海大学硕士学位论文第二章理论基础 2 1 2 高级p e t r i 网 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 网的基础上引入了颜色的概念 2 2 o 给每个p e t r i 网中的托肯( t o k e n ) 都定义一个值，通过它能对托肯进行区分。通过给托肯赋值， 就好比给他们涂上了颜色。有色p e t r i 网的出发点是对于系统中类似的要素合 并，并用同一个p n 模型要素( 库所，变迁，弧) 来表示，用这些模型要素的属 性来区分同一系统中不同的个体。在c p n 中称这些属性为色彩( c o l o r ) 。 在变迁实施时所产生的托肯，取决于实施时被消耗的托肯的值，生产出的托 肯的值也可以依赖于那些被消耗的托肯的值。与传统的p e t r i 网不同，生产的托 肯数目也是变化的，即生产的托肯数目由被消耗的托肯的值决定。 定义一：= ( p , t ；f ，c ，i ，j + ，m o ) 称为一个有色网系统的充分必要条件是 ： ( 1 ) ( p ，t ；f ) 是个网，称为的基网。 ( 2 ) c ；put 一颜色集的幂集合，使得： 对于所有p e p ，c ( p ) 是p 上所有可能的托肯色之集合；对于所有t t ，c ( t ) 是t 上所有可能的出现色之集合。 ( 3 ) i 一和i + 分别是p x t 上的负函数和正函数，使得对所有( p ，t ) p x t ： i - ( p ，t ) c ( t ) 。- - c ( p ) 。 l ，且i 一( p ，t ) = 0 的充分必要条件是( p ，t ) 芒f ： i + ( p ，t ) c ( t ) 。- * c ( p ) 。 l ，且i + ( p ，t ) = o 的充分必要条件是( t ，p ) 蔓f 。 ( 4 ) l i o 称为的初始标识，满足：v p p ：地( p ) e c ( p ) 。，即1 4 0 ( p ) e c ( p ) m 即地( p ) 是p 的托肯色集合上的多重集。 定义二：多重集 设s 是个非空集合，n o 是非负整数集，则从s 到n 0 的函数叫做s 上的多重集。 2 层次扩展一层次p e t r i 网 虽然可以用着色p e t r i 网、时间p e t r i 网描述非常复杂的过程，但是得到的 p e t r i 网可能是一个平铺直叙的“大网”。虽然它正确地反映了业务流程，但却 无法清楚地看清它的结构关系，无法观察至l j p e t r i 网建模的过程层次结构。层次 扩展可以帮助克服以上的那些缺点。 在层次p e t r i 网中，每一个结点不再是一个原子结点，可能其中的某一个结 点代表着一个子网，这个子网也是一个带有库所、变迁、更深层次子网的p e t r i 网。所以可以自底而上或自顶而下层次化地构造p e t r i 网。自底而上的方法是首 先从最底层开始，详细地描述基本组件，这些组件被组合成过程，众多的子过程 9 河海大学硕士学位论文 第二章理论基础 再组合成更大的过程，最终得到过程的详尽描述。自项而下的方法则正好相反， 从最高层次开始，过程不断地被分解为予过程，直到最底层只包括变迁和库所。 反复的分解以得到层次化的描述。 3 时间扩展一时间p e t r i 网 通常当希望对一个过程的预期性能进行判断时，就需要对经典p e t r i 网进行 时间扩展嘲。传统的p e ，t r i 网不允许对“时间”建模，即使进行了颜色扩展，对 过程时间进行建模仍然很困难嘲。 采用时间扩展时通常的做法是：标记将时问戳作为一个值嘲该时间戳指明 标记自何时可用，一个时f 司戳为t 的标记只有在时刻t 之后才能被变迁消耗。变 迁要想就绪，当且仅当每个要被消耗的标记的时间戳早于当前时间。也就是说， 变迁的就绪时刻是它的输入库所包含足够的可用标记的最早时刻。标记的消耗按 照先进先出( f i f o ) 规则。拥有最早时间戳的标记首先被消耗。此外，具有最早 就绪时刻的变迁首先实施。如果一个变迁实施并产生标记，那么每个标记都被赋 予一个不早于实施时刻的时间戳。实施的变迁可以确定产生的标记的延时。产生 的标记的时间戳等于实施时刻加上时延。延时的长短可以依赖于其消耗的标记的 值。延时可能是一个固定值( 如l o s ) 也可能是一个位于某一个区间内的随机 值。根据这种固定值和区间值的划分，时间p e t r i 网又可以分为固定延迟网和不 固定延迟时间网由于不固定延时时间网更具有一般性，所以很多研究都是基于 它之上的本文也是以它为研究对象。下面给出不固定延迟时间p e t r i 网的形式 化定义： = ( p ，t ：f ，i ，0 ，肿，t ) 称为不固定延时网，当且仅当： ( 1 )( p ，t ，i ，0 ，m o ) 为带标识的基本网； ( 2 ) t ：t a p ，其中 p 的元素为递增非负实数对a p = ( a m i n ，a m x ) ， 其中o 鲫i n 锄x 。 在这种时间网中，对每个转移t t ，均有一个a p e a p 与之相对应，即表示 转移t 的启动要考虑延迟时间。假设t 在时钟为u 时有效，则它可在区间 u + a m i n 。u + s m a x 内执行。也就是说，当t 有效时，在输入位置p 中的标记至少 要保留a m i n 秒，直至这些标记由于t 的启动而移出。但t 必须在u + a m a x 内启 动，否则将不再能启动。 2 1 3p e t r i 网的基本性质及分析方法 p e t r i 网的强有力的分析技术和手段是它与其他建模方法相比的一个突出的 优势。p e t r i 网有如下性质： 1 可达性( r e a c h a b i l i t y ) i o 河海大学硕士学位论文第二章理论基础 可达性：对给定初始标识即初始托肯分布地的一个p e t r i 网( n ，) ，可达集 r ( n 。) 定义为此p e t r i 网在初始状态标识地下按照触发规则可达的所有状态标 识的集合 此定义表明，一个p e t r i 网的可达集r ( n 。地) ，既取决于网的结构，也取决 于网的初始状态标识。对给定的一个p e t r i 网n 和其初始状态标识m o ，任意指定 的一个托肯分布地是由初始托肯分布地可达的，当且仅当满足虬r ( n ，) 。 2 有界性( b o u n d e d n e s s ) 有界性：对给定初始标识即初始托肯分布的一个p e t r i 网( n ，m o ) ，称此 p e t r i 网为k 有界的，如果对任一可达状态标识m r ( n ，地) 和任一库所节点p ：， 相应于状态标识m 下的p e t r i 网，库所节点p 。中的托肯数满足m ( p 。) = k ，其 中k 为有限正整数。 3 安全性( s a f e n e s s ) 安全性：对给定初始标识即初始托肯分布地的一个p e t r i 网( n ，地) ，称此 p e t r i 网是安全的，如果对任一可达状态标识m r ( n ，吣和任一库所节点p 相应 于状态标识m 下的p e t r i 网，库所节点p 。中的托肯数满足m ( p 。) = l 。 4 活性( l i v e n e s s ) 变迁节点的活性：对于给定初始标识即初始托肯分布地的一个p e t r i 网( n ， m 0 ) ，称其一个变迁节点t 是活的，如果对由初始托肯分布地可达的任一状态标 识m e r ( n ，m d ) ，都可以找到一个触发序列，在由此导出的新托肯分布m 下可使 此变迁节点t 为使能。 定义p e t r i 网的活性：对给定初始标识即初始托肯分布的一个p e t r i 网( n ， 地) ，称此p e t r i 网为活的，如果其每一个变迁节点都是活的。 5 死锁( d e a d l o c k ) 死锁：对给定初始标识即初始托肯分布地的一个p e t r i 网( n ，虬) ，称其一个 变迁节点t 为死锁，如果对由初始托肯分布可达的任一托肯分布m e r ( n ，地) 下，此变迁节点t 都是不使能，即不具有触发权。如果网中存在t 则网存在死锁。 6 冲突( c o n f l i c t ) 本质上，冲突就是两个或多个事件间的一种竞争现象。 冲突：对给定初始标识即初始托肯分布的一个p e t r i 网( n ，l i o ) ，冲突是指 这样的一种现象，如果p e t r i 网的两个或多个变迁节点同时处于使能即具有触发 权的状况，但由于共享某些输入库所节点，使一个变迁节点的触发导致另一个变 迁节点的不能触发。 7 强连通 一个p e t r i 网是强连通的当且仅当对于该网上的任意两个节点( 位置或是变 迁) x 和y ，总存在一条从x 到y 的路径。 河海大学硕士学位论文 第二章理论基础 在基于p e t r i 网的工作流建模过程中，一般是库所代表条件，变迁则代表事 件。一个变迁有一定数量的输入和输出库所，分别代表事件的前置条件和后置条 件。库所中的托肯代表可以使用的资源或数据 2 2x p d l 标准 过程定义影响安全性与管理，因此过程定义阶段是非常重要的阶段。 过程建模的最终结果是要生成一个能被工作流引擎解释并执行的文件。 p e t r i 网虽然直观，表达能力强，但是不便于归档、传输、解释执行，并且不利 于和其他建模工具产生的模型相兼容。因此需要一个标准来统一各个建模工具产 生的工作流模型。 w f 骶为工作流系统制定五类功能接口乜钉，其中接口1 ( 过程定义输入输出接 口) 包含了一个用于描述工作流过程定义的公共元模型，以及过程定义间进行相 互转换的x 札s c h e m a 灌3 。 我们可以用各种不同的工具来分析、建模、描述业务过程。而使用工作流过 程定义接口所定义的公共交换格式，可以实现两个不同系统间工作流过程定义的 相互转化。 接口1 为开发和运行环境之间提供了形式上的分离，可以用建模工具产生过 程定义，并且这个过程定义可以用于多个工作流产品。由建模工具产生的工作流 过程定义可以被不同的工作流运行系统所解释。基于公共转换格式的过程定义还 可以在这些系统问相互转换，从而实现过程定义的分离存储。 为了提供一个公共的方法来访问和描述工作流定义，霄f m c 制定了一个工作流 过程定义元模型，在元模型中给出了过程定义经常用到的一些实体，并为这些实 体制定了各种不同的属性。以元模型为基础，利用公共转换格式和特定工具可以 对模型进行转换。 x p d l ( ) ( m lp r o c e s sd e f i n i t i o nl a n g u a g e ) 是工作流管理联盟提出的一种 基于x m l 的标准的工作流过程定义语言，目的是为了方便工作流过程定义在不同 工作流产品之间的交换。该模型给出了在过程定义交换中使用到的高级实体集 合。 使用不同的工具对工作流模型进行扩展，是x p d l 的一个关键特性。x p d l 不 可能支持所有工具的附加属性。依靠一系列有限的描述工作流过程定义的实体， x p d l 可以支持一些不同的扩展属性处理方法。 x p d l 是一个通用的框架，这也是x p d l 的一个重要特性，这个框架可以支持 开发者的特殊使用目的，而对外表现形式却相同。工作流建模工具的实现和它的 外部接口可以独立开发，因为不管模型是如何实现的，采用什么图形描述( 状态 河海大学硕士学位论文第二章理论基础 图、活动图、工作流网等) ，只要外部接口符合x p d l 规范，那么就可以保持相同 的表示形式。 2 2 1x p d l 的格式 图2 2 为x p d l 顶级实体元模型图。顶级实体包括工作流过程定义( p r o c e s s d e f i n i t i o n ) 、工作流过程活动( p r o c e s sa c t i v i t y ) ，变迁( t r a n s i t i o n ) 信息、工 作流参与者( p a r t i c i p a n ts p e c i f i c a t i o n ) 、3 - 作流应用声明( a p p l i c a t i o n d e c l a r a t i o n ) 、工作流相关数据( r e l e v a n td a t a ) 、系统和环境数据( s y s t e ma n d e n v i r o n m e n td a t e ) 等。 x p d l 中主要实体元素包含五组属性，第一组是所有元素共有的属性，如i d 、 n a u e 等。第二组是各个元素自身特有的属性，第三组是对其它元素的引用属性， 第四组属性提供工作流执行引擎使用的陈述性信息，而最后一组属性是仿真和过 程优化的相关信息。x p d l 定义了实体的扩展机制，可以在实体元素中通过扩展 属性( e x t e n d e da t t r i b u t e s ) 和扩展参数映射( e x t e d e dp a r a m e t e rm a p p i n g ) 来定制自己所需的属性和参数