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

摘要 工作流是一类能够完全或者部分自动执行的业务流程，根据一系列过程规 则，文档、信息或任务能够在不同的执行者之j 瑚传递、执行。清晰和准确地对业 务流程进行描述需要借助于一定的建模方法和工具。本文主要研究基于p e t r i 网 的工作流模型。 p c 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 网建模在办公自动化系统中的应用。在工作流管理 软件环境l o t u sd o m i n o n o t e s 中，对办公过程应用p e 仃i 网进行建模和分析。具 体的实例应用表明，利用p e t r i 网进行过程建模，不仅可以很好地描述业务流程 中异步性、并发性和资源共享等问题，还可以对模型的正确性进行数学分析和验 证，在工作流引擎执行之前发现设计错误，避免了模型中可能出现的冲突和死锁。 关键词：工作流，p e t r i 网，过程建模和验证，l o t u s 。 a b s t r a c t t h ew o r k f l o wi sak i n do fc o m p u t e rr e a l i z a t i o no ft h eb u s i n e s sp r o c e s s ，w h i c h d e f i n e dw h a ti st h eb u s i n e s sp r o c e s s ，h o wt od oa n ds oo n i ti sv e r yi m p o r t a n tt of i n d am o d e l i n gt o o lt od e s c r i b et h i sk i n do f b u s i n e s sp r o c e s s t h i sp a p e r m a i n l ys t u d i e di n am o d e l i n gt o o l ：p e t r in e t t h ep e t r in e ti st h em a t h e m a t i c a l d e s e r i p t i o no ft h es e p a r a t e ，p a r a l l e l s y s t e m s t h i sp a p e rd e s c r i b e st h ep r o c e s so fw o r k f l o wb a s e do np e t r in e tt h e o r i e s ， i n t r o d u c e sak i n do fw o r k f l o wm o d e l ：w o r k f l o w n e t ，a n a l y z e st h es t r u c t u r a l c o r r e c t n e s so ft h ew o r k f l o wn e t o nt h eb a s i so fa n a l y s i n gw f n e t s s h o r t c o m i n g ， c p w f - n e tc o m b i n i n gc p n ( c o l o r e dp e t r in e t ) w i t hw f - n e ti sp u tf o m , a r d s t r i c t d e f i n i t i o n ，e n a b l ec o n d i t i o na n dt r i g g e rr u l eo fc p w f n e ta r eg i v e n ，a n dt h en e w c h a r a c t e r i s t i c sb r o u g l l ti nw o r k f l o wm o d e l i n ga r ea n a l y s e di nd e t a i l 一 t h ea p p l i c a t i o no fp e t r in e tt h e o r i e si nt h ec r e a t i o no ft h em i s s i v em a n a g e m e n t w o r k f l o wm o d e li sd i s c u s s e d am i s s i v em a n a g e m e n tp e t r in e t sm o d e li sc r e a t e da n d a n a l y z e d t h ea p p l i c a t i o ni n d i c a t e dt h a tt h ep r o c e s sm o d e l i n gb a s e do nt h ep e t r in e t ， n o to n l yc a nd e s c r i b et h eb u s i n e s sp r o c e s s ，b u ta l s oc a na v o i dt h ec o n f l i c ta n dt h e d e a d l o c k k e yw o r d s ：w o r k f l o w ，p e t r in e t ，p r o c e s sm o d e l i n ga n dv e r i f i c a t i o n ，l o t u s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得云洼王些盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 学位论文作者签名：召尹j 孓 签字开期：口缉，月彤同 学位论文版权使用授权书 本学位论文作者完全了解云注兰些太堂有关保留、使用学位论文的规定。 特授权丞洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：砰甘 签字r 期：删年，月肜= | 翩签昏，膨 签字f f 期：御g 年，月，珀 学位论文的主要创新点 一、从理论上对p e t r i 网的结构进行了深入地分析。 二、利用工作流网对办公流程建模。 三、根据工作流网的特性对办公流程模型进行分析验证。 第一章绪论 第一章绪论 本章介绍工作流技术的起源及发展，给出一组与工作流相关的基本概念，分 析了工作流技术的研究现状，最后对论文做了总体安排。 1 1 工作流技术的起源 工作流的概念起源于生产组织和办公自动化领域。它是针对r 常工作中具有 固定程序的活动而提出的一个概念。目的是通过将工作分解成定义良好的任务、 角色，按照一定的规则和过程来执行这些任务并对它们进行监控，达到提高办事 效率、降低生产成本、提高企业生产经营管理水平和企业竞争力f 1 1 。 8 0 年代初期，在p c 机尚未作为信息处理工具出现的时候，纸张是各行各业 中进行日常业务活动所不可替代的载体，包括表单、文件、信函、技术资料等在 内的各类与企业密切相关的文档都是以纸张的形式在各个部门之间进行传递的。 这种古老的载体在信息的处理、组织、存储以及查询检索方面都是低效的。因此， 人们希望出现一种无纸化的、计算机使能的工作环境。一些公司、企业也建立了 自己专用的或者可商品化的表单传递应用系统( f o r m s r o u t i n ga p p l i c a t i o n s ) ，通 常运行在大型机或小型机上，用于实现日常表单处理的电子化与自动化这种系 统可以看成是现代工作流管理系统的一个雏型。 8 0 年代中期，f i l e n e t 和v i e w s t a r 等公司率先开拓了工作流产品市场，成为 最早的批工作流产品供应商。他们把图像扫描、复合文档、结构化路由 ( s t r u c t u r e dr o u t i n g ) 、实例跟踪、关键字索引以及光盘存储等功能结合在一起， 形成了- i 十全过程支持某些业务流程的集成化的软件( 包) 。这便是早期的工作 流管理系统。比较典型的有f i l e n e t 于1 9 8 4 年推出的w o r k f l o wb u s i n e s ss y s t e m ， v i e w s t a r 于19 8 8 年推出的v i e w s t a r 。很显然，这种增值性质的集成化软件系统 为企业简化与重组自己的关键业务流程提供了一种非常合适的方案；而且出此 我们还可以看出，工作流从最初的诞生之同起就是作为一种面向过程的系统集成 技术而出现的，只不过限于当时的计算机发展水平，它所集成的功能较为简单面 已。 进人9 0 年代，随着计算机的普及、网络的延伸，现代企业的信息资源越来 越表现出一种异构、分布、松散耦合的特点，企业的分散性、决策制定的分散性、 对同常业务活动详尽信息的需求以及c l i e n t s e r v e r 体系结构、分布式处理技术 第一章绪论 ( c o r b a ，w w w ，o l e ，j a 、峻) 的同益成熟，都说明了这样一个事实：集中 式信息处理的时代已经过去，实现大规模的异构分布式执行环境，使得相互关联 的任务能够高效运转并接受密切监控已成为一种趋势。在这种不可抗拒的技术背 景下，工作流管理系统也由最初的创建无纸办公环境转而成为同化企业复杂信息 环境、实现业务流程自动执行的必要工具。这样的一个转变，把工作流技术带入 了一个崭新的发展阶段，使得人们从更深的层次、更广的领域上对工作流展丌了 研究。 2 1 工作流技术的标准化组织工作流管理联盟( w o r k f l o wm a n a g e m e n tc o a l i t i o n ) 于1 9 9 3 年成立。它的成立标志着工作流技术在计算机应用研究领域之中被明确 地划分出了自己的一席之地，相应的概念与术语也得到了人们的承认。在全球范 围内，对工作流的技术研究以及相关的产品丌发进入了更为繁荣的阶段，更多、 更新的技术被集成进来，文件管理系统、数据库、电子邮件、移动式计算、i n t e m e t 服务等都已被容纳劐工作流管理系统之中，市场上工作流产品极大丰富。 工作流是从英文单词w o r k f l o w 翻译过来的。w o r k f l o w 是由单词w o r k 和f l o w 组合得到的词。单词w o r k 表示工作或者任务，单词f l o w 表示流动、流程或者流 量等。f l o w 反映了一种变化以及变化的过程，它本身的含义比较抽象，但当它 与某个具体的过程相联系时就有了具体含义，例如电流、水流、气流等。在企业 的经营管理与生产组织中，f l o w 也有相当重要的意义，如表示物料传输过程的物 料流，表示资金流动的资金流，反映信息处理和传递过程的信息流，同样还有价 值流、决策流、控制流等概念。依此类推，用活动及活动之间变化的过程表示的 业务流程就是工作流【1 l 。 1 2 工作流的概念 1 2 1 工作流定义 十几年来，不同的研究者对工作流分别提出了不同的定义。到目前为止，对 于工作流仍没有完全统一的定义。不同的机构和组织分别从不同的角度对工作流 概念进行了描述。 ( 1 ) 工作流管理联盟的定义 工作流是一类能够完全或者部分自动执行的业务流程，根据一系列过程规 则，文档、信息或任务能够在不同的执行者之间传递、执行1 3 】。 ( 2 ) g i g ag r o u p 的定义 工作流是业务流程中可运转的部分，包括任务的顺序以及由谁来执行、支持 任务的信息流、评价与控制任务的跟踪、报告机, n t 4 j 。 第一章绪论 ( 3 ) i b ma l m a d e nr e s e a r c hc e n t e r 的定义 工作流是业务流程中的一种计算机化的表示模型。定义了完成整个过程所需 用的各种参数。这些参数包括对过程中每一个单独步骤的定义、步骤问的执行顺 序、条件以及数据流的建立、每一步骤由谁负责以及每个活动所需要的应用程序 5 1 。 ( 4 ) 、m p v a nd e r a a l s t 的定义 工作流是一系列工作的偏序集。工作的序列可以有多种方式，比如工作x 与y 满足x m 或m o m + ，m 叫做m 的后继 4 第二童基于p e t ri 网的工作流模型建立与分析 标识。 2 2 2p 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 3 】【“1 ： ( 1 ) 经典p e t r i 网。最简单的p e t r i 网系统。规定网系统中每个库所的容 量都为1 。p e t r i 网的库所又叫条件，变迁又叫事件，所以基本p e t r i 网又称条件 事件系统，简称c e 系统。 i i ，v i 玳，i - - - - 中，0 = 由： ( 2 ) 可x p u t 八x 不i n 八x 不o u t ，x 至少在一条从j i n 到0 o u t 的路径上： ( 3 ) 将变迁t 分为五类：自动类，人工类，消息类，时钟类，哑变迁。 用t c 表示t 的分类，则v t e t ： t y p e ( t c ( t ) ) c t t ，其中，t t = f 自动类， 人工类，消息类，时钟类，哑变迁1 。 2 5p e t r i 网模型的结构分析 当工作流管理技术应用领域同趋广泛化和复杂化时，各种实际应用也对工作 流技术也提出了更高的要求，要求工作流管理系统提供有效的手段来检验过程模 型的正确性。用户建立好的一个过程模型很可能会有错误或者不是最优的。这样 的系统一旦实际运行，有时会带来严重的后果。因而过程模型在实际投入运行之 前离线的进行验证分析和优化就显得十分必要。 从所描述的工作流系统的角度解释，p e t r i 网作为数学工具使得我们能够确 第二章基于p e t rj 网的工作流模型建立与分析 认系统的特性是否存在。系统的特性可分为行为( b e h a v i o r a l ) 特性与结构 ( s t r u c t u r a l ) 特性。行为特性是p e t r i 网与切始标识有关的性能，在业务流程真 正用于实践之前，设计者必须测试业务的动态行为，如吞吐量、占用率和制造成 本；而结构特性与仞始标识无关，它取决于p e t r i 网的拓扑结构。这早将从实际 应用的角度介绍一些重要的结构与行为特性，包括可达性( r e a c h a b i l i t y ) 、有界 性( b o u n d n e s s ) 、安全性( s a f e n e s s ) 、守恒性( c o n s e r v a t i v e n e s s ) 、活性( l i v e n e s s ) 和可逆性( r e v e r s i b i l i t y ) 。 使用p e t r i 网的概念构造w f m s 能够利用p e t f i 网的很多分析技术。当w f m s 设计出来之后，就可以参照过程、资源和实例这三个维度来分析【 】，如图2 h 所示。 图2 - 1 1 工作流管理的分析维度 分析的首要目标是引领w f m s 的设计者建造业务流程的正确规范。因而以 下将讨论p e t r i 网的结构分析技术。结构分析涵盖了进程维度。这些结构分析技 术只是针对网中实例的一个特殊标识描述：假设一个实例托肯在库所p 中，即 m = 1 。这就意味着由于c a = 由，可以使用为p t 网开发出来的分析手段。通过 结构分析，可以在工作流引擎执行流程之前发现设计错误。 当证明模型的结构性质时，并没有分析资源。加入资源后使得这项工作很难 解决，这是由于资源违背了为建造单一实例的p e t f i 网而定义的某些规则。资源 的抽象可以稳妥地进行，因为我们假设是人力资源。因此，从死锁状态恢复总是 可能的。1 3 4 】 2 5 1 可达陛 可达性是p e t r i 网的个重要行为特性。给定一个p e t r i 阿，从初始标识m o 可以到达哪些标识，或者给定一个标识，是否可以激发从初始标识到达该标识的 一系列变迁。 第二覃基于p e t ri 网的工作流模型建立与分析 定义2 1 0 若从初始标识m o 开始，激发一个变迁序列，产生标识m 。则称 m ，是从m o 可达( r e a c h a b l e ) 的。若从m o 开始，只要激发1 个变迁即可产生m ， 则称m r 是从m o 立即可达的( m m e d i a t e l y r e a c h a b l e ) 。所有从2 1 。可达标识的集合 称为可达标识集或可达集，记为r ( m o ) 。 一般地，从m o 到m ，所激发的变迁序列表示为s r = ，t j ，这里m ， j ，为1 到m 之间的整数。从m o 激发s r 产生m ，表示为：m o s r m ， 对于每一个激发的变迁序列s r ，都可以关联1 个m l 激发向量m ，该向量 的第i 个元素，对应着变迁t 在s ，中出现的次数n 。一般地，u r = ( n 。，n m ) 1 。 对于定的u ，其对应的激发的变迁序列可能不是唯一的， 可达性用来描述工作流系统这样的2 个问题： ( 1 ) 工作流系统按照一定的轨迹运行，系统能否实现预期状态或者不出现 不期望的状态。典型的问题是工作流是否能够实现预期的要求，即工作流按照一 定的步骤运行，一定的任务是否能够完成。 ( 2 ) 要完成一个特定的任务，如何确定工作流系统的运行轨迹。典型的问 题为任务的调度安排问题。 工作流运行的轨迹就是用激发变迁序列s r 表示事件发生的先后顺序，而系统 的状态表示为p e t r i 网的标识m 。因此，第一个问题可以描述为：给定s ，、初始 标识m o 以及期望达到的标识m ，则有m o i s t e n ：，若m r = m ，则答案是肯定的； 若m r c m ，在答案是否定的。第二个问题可以描述为：给定m o 与m ，寻找s r 使得m o s ， m ，成立。其中s ，可能不是唯一的，通常都在一定的准则下选取优化的 s r ， 2 5 2 有界性 定义2 1 1 给定p n = ( p ，t ，i ，0 ，m o ) 以及其可达集r ( m o ) ，对于库所p p ， 若v m r ( m o ) ：m ( p ) k ，则称p 是k 有界的，此处k 为诈整数；若p e t r i 网的所 有库所都是k 一有界的，则p e t r i 网是k 有界的。 特别地，k = l 时，即当库所或p e t r i 网是1 有界的，我们称该库所或p e t r i 网是安全的。若对于任意初始标识1 1 1 0 ，p e t r i 网都是k 有界的，则p e t r i 网是结构 有界的( s t u c t u r a l l y b o u n d e d ) 。 2 5 3 活性 定义2 1 2 对于一个变迁t t ，在任一标识m r 下，若存在某一变迁序列 s ，该变迁序列的激发使得此变迁t 使能，则称变迁t 是活的( l i v e ) 。若一个p e t r i 网的所有变迁都是活的，则该p e t r i 网是活的。 第二章基于p e t r i 罔的工作流模型建立与分析 死变迁( d e a dt r a n s i t i o n ) 与死锁( d e a d l o c k ) 从反面描述p e t f i 网的活性。 若存在r n r ，不存在从m 开始的激发t 使能的变迁序列，则变迁t 为死变迁。 若存在1 1 3 r 。在此m 下无任何变迁使能，则称p e t r i 网包含一个死锁，该标识 为死标识( d e a dm a r k i n g ) 。 在资源共享系统中，下列4 个情况可能同时满足，从而导致死锁： ( 1 ) 互斥：一个资源不可以为2 个以上过程同时使用，一个过程排斥其它 过程对于该资源的占用。 ( 2 ) 占用且等待：一个过程已被许可占用某一或某些资源，同时又在请求 占用其它资源。 ( 3 ) 无抢占：已分配给某一过程的资源不能从该过程中抢走，除非该过程 使用此资源完毕后释放。 ( 4 ) 循环等待：2 个或更多过程排成一个链，链上每一过程都在等待一个 正在被链上的下一个过程占用的资源。 p e t r i 网活性意味着在任意从初始标识r i l o 可达的标识m 下，总可以通过逐步 激发某变迁序列来激发任意变迁。因此，若p e t r i 网是活的，则其不存在死锁。 2 。6 工作流网的验证 2 6 1 工作流网的正确性 综上所述，工作流模型还应该满足如下两个条件筘i ： ( 1 ) 任何情况下工作流网都能够最后终止，并且终止时只有库所p 。有一个 托肯，其余库所部是空的。( 2 ) 不能存在死变迁。 以上两个掰寸加务件是工作流用的正确性特征。出此得出工作漉网正确性的定 义。 定义2 ，1 3 基于w f n e t 建立的工作流模型是正确的，当且仅当： ( 1 ) 对每个从初始标识m o 的可达标识m ，必然存在一个从m 到m ，的触 发序列，其中m f 表示仅库所p 0 合有一个托肯的终止标识，即 v m ( m o 与m ) j m 与m r ( 2 ) m f 是唯一正常的结束标识。即： 可m ( m 9 。m m m f ) ( m = m f 、) ( 3 ) 不存在死变迁。即： v t e t ，j m ，m + ：m o 与m 与m 从以上定义可以看出，正确性反映了w f - n e t 的结构特性。条件( 1 ) 保证了 工作流网能够最终到达结束状态；条件( 2 ) 说明当终止库所p 。含有个托肯且 第二章基早p a r r i 网的工作流模型建立与分析 其余库所都不含有托肯时，工作流网即结束运行：前两个条件合起来保证了工作 流网的正确终止。第三个条件是要求工作流网不能存在无法使能的变迁。 对于任意一个w f - n e t ，如何判定其正确性昵? 文献f 3 6 l 指出工作流网的f 确 性与活性和有界性密切相关。为了将活性和有界性与正确性相联系，我们需要将 p n = ( p ，t ，f ) 扩展为p n = ( p ，t ，f ) ，p n 即w f n e t 。扩展方法就是添加连接库所p 。 和p 的变迁t + ，使得： p = 只 t = t uf t + ) ， f = f u ( p 。，t + ) ，( t ，p ，) ) 。 图2 一1 2 所示为p n 和p n 之问的关系。 图2 - 4 2p n 的扩展两 o 以一p n 为基础得到如下重要的定理： 定理2 1一个岍n e t 是正确的当且仅当芦雨是活