（模式识别与智能系统专业论文）基于着色petri网的工作流引擎设计与实现.pdf

摘要 工作流管理是一个广泛应用并迅速发展的新技术，目的是为了让 合适的人或软件在恰当的时间执行正确的工作。它的主要特点是使计 算机上的处理业务流程自动化，使人以及各种应用工具相互之间协 调，以完成某项工作。 通过分析目前的工作流技术和产品，总结了两个问题：( 1 ) 许多工 作流管理系统都提出了他们自己的过程建模语言，用来满足具体用户 的需求，但是这些语言缺乏形式化的方法来确定其性质和合理性；( 2 ) 许多工作流管理系统功能过于庞大，不适合一些中小型应用，而开发 一个新的工作流产品时，有大量的相同功能需要重新设计开发。因此， 抽象出工作流管理系统的核心功能，设计可重用的工作流引擎，是一 个有效的解决途径。 本文从以上两个方面进行了有益的研究和探索，得出了一些理论 和实践的成果： ( 1 ) 建立了基于着色p e t r i 网的工作流过程模型。在工作流网 ( w f n e t ) 的基础上，通过引入了颜色的概念，定义了着色工作流网 ( w o r k f l o wn e tb a s e do i lc o l o r e dp e t r in e t ，w f c n e t ) ，增强了模型的建模 能力。 ( 2 ) 设计了四种基于w f c n e t 的工作流多实例模式，并对设计结果 进行了仿真实验和分析。通过与其他工作流产品的比较，证明了 w f c n e t 具有较强的建模能力。 ( 3 ) 设计并实现了一个可重用的轻量级工作流引擎。该引擎具有以 下特点：将工作流逻辑和应用逻辑剥离，使引擎变得更简单；采用内 存存储技术，使引擎变得更快速；设计了灵活的资源管理，使引擎功 能强大；引入事件通知机制和事务处理机制，增强了系统的可扩展性 可靠性。 本文设计的工作流引擎既可以作为工作流管理系统的一个核心 部分，也可以很方便地和其它应用集成，应用到所有需要工作流技术 的场合。 关键词：工作流管理系统；p e t r i 网；工作流模式：工作流引擎；轻 量级 中南大学硕士学位论文 a b s t r a c t a b s t r a c t w o r k f l o wm a n a g e m e n t ，t h er a p i d l yd e v e l o p i n g t e c h n o l o g y ，i s w i d e l y u s e di n m a n ya p p l i c a t i o n a r e a s t h e g o a l o fw o r k f l o w m a n a g e m e n ti st oa r r a n g es u i t a b l ep e o p l eo rs o f t w a r et op e r f o r mr i g h t t a s k sa tr i g h tt i m e i t sm a i nf e a t u r e sa r ea u t o m a t i n gt h ep r o c e s s i n gf l o w s a n dm a k i n gp e o p l ea n da p p l i c a t i o nt o o l st oc o o r d i n a t ew i t h e a c ho t h e r t h r o u g ha n a l y z i n gc u r r e n tw o r k f l o wt e c h n o l o g ya n dp r o d u c t s ，t w o d e f i c i e n c i e sw e r eg e n e r a l i z e di nt h e m ：( 1 ) m a n yw o r k f l o wm a n a g e m e n t s y s t e m s d e v i s et h e i ro w np r o c e s s m o d e l i n gl a n g u a g e t h a ts e e m s a p p r o p r i a t ef o rs p e c i f i cu s e rn e e d s ，b u ti sn o tb a c k e db ya n yf o r m a l i s m t h a tc a na s c e r t a i ni t s p r o p e r t i e s o r s u i t a b i l i t y ( 2 ) m a n y w o r k f l o w m a n a g e m e n ts y s t e m sw h i c hh a v es ol a r g e ra m o u n to ff u n c t i o n a l i t yt h a t t h e yi sn o ts u i t a b l ef o rm i d s m a l la p p l i c a t i o n s h o w e v e r ，e v e r yt i m ea n e ww o r k f l o ws o l u t i o ni sc o n c e i v e dt h e r ea r eal o to ff u n c t i o n a li t i e st h a t i se v e n t u a l l yr e i n v e n t e da n dr e d e v e l o p e d s oi ti sag o o dw a yt oa b s t r a c t k e m e lo ff u n e t i q n a l i t yf r o mw o r k f l o wm a n a g e m e n t ，t h e nd e v e l o pa r e u s a b l ew o r k f l o we n g i n e i nt h i st h e s i s ，ab e n e f i c i a lr e s e a r c ha n dp r a c t i c ew a sm a d ei nt w o a s p e c t sm e n t i o n e da b o v e ，a n ds o m ee s s e n t i a lt h e o r e t i ca n dp r a c t i c a l r e s u l t sw e r eo b t a i n e da sf o l l o w ： ( 1 ) aw o r k f l o wp r o c e s sm o d e lb a s e do nc o l o r e dp e t r in e tw a s b u i l t t h r o u g ha d d i n gc o l o rc o n c e p t ，w f c n e tw a sd e f i n e db a s e do nw f - n e t t h em o d e l i n ga b i l i t yo fw f c n e ti sm o r ep o w e r f u lt h a nw f - n e t ( 2 ) i n v e n t i o n so ff o u rm u l t i p l e - i n s t a n c ep a t t e r n so fw o r k f l o wb a s e d o nw f c - n e tw e r ep r o v i d e d m o r e o v e r ，s i m u l a t i o na n da n a l y s i sw a sm a d e f o rt h e s ei n v e n t i o n s a f t e rc o m p a r i n gw i t hs o m ew o r k f l o wp r o d u c t s ，i t w a s p r o v e d t h a tw f c n e th a sb e t t e rm o d e l i n ga b i l i t y ( 3 ) ar e u s a b l ea n dl i g h t w e i g h tw o r k f l o we n g i n ew a sd e s i g n e da n d i m p l e m e n t e d t h i se n g i n eh a ss o m ec h a r a c t e r i s t i c sa sf o l l o w ：s e p a r a t i o n b e t w e e nw o r k f l o wl o g i ca n db u s i n e s sl o g i cm a k e st h ee n g i n eb e c o m i n g s i m p l e ；u s i n ge m sm e m o r yt e c h n o l o g yf a s t st h ee n g i n e ；f l e x i b l er e s o u r c e m a n a g e m e n tm a k e st h ee n g i n em o r ep o w e r f u l ；t h ee v e n tn o t i f i c a t i o n m e c h a n i s ma n dt r a n s a c t i o nh a n d l i n gm e c h a n i s mm a k e st h ee n g i n em o r e i i 中南大学硕士学位论文a b s t r a c t e x t e n d a b l ea n dr e l i a b l e t h ew o r k f l o we n g i n ed e s i g n e di nt h i st h e s i sn o to n l yc a nb eu s e da s t h ek e m e l p a r te m b e d d e di nw o r k f l o wm a n a g e m e n ts y s t e m s ，b u ta l s oc a n b ei n t e g r a t e dw i t ho t h e ra p p l i c a t i o n st ob eu s e de v e r y w h e r et h a tn e e d w o r k f l o w k e yw o r d s ：w o r k l o wm a n a g e m e n ts y s t e m ；p e t r in e t ；w o r k f l o wp a u e m ； w o r k f l o we n g i n e ；l i g h t w e i g h t i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：日期：三丛年j 月! 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 日期：丑年1 月上日 中南大学硕士学位论文 第一章绪论 第一章绪论 自2 0 世纪7 0 年代以来，世界市场已经由传统的相对稳定市场逐步演变为动 态多变的市场，企业之间的竞争也由过去的局部竞争变成全球范围的竞争。而在 企业之间的竞争日益白热化的同时，企业面临的社会、经济、制造环境与客户需 求也已经发生了巨大的变化。从先进制造战略、企业经营过程重组、市场环境的 变化、到企业组织结构的变化趋势、以及企业计算机应用的发展历史可以清楚地 看出，面向过程的计算机应用在以后的企业经营业务中将发挥越来越重要的作 用。作为面向过程建模、优化、执行与监控的工作流技术已经表现出其强大的生 命力。可以预计，在今后的几年内，工作流技术将掀起企业计算机应用的新耐1 1 。 1 1 工作流的发展历史 工作流技术发端于1 9 7 0 年代中期办公自动化领域的研究工作，但工作流思 想的出现还应该更早，1 9 6 8 年f i l mn o r d s i e c k 就已经清楚地表达了利用信息技 术实现工作流程自动化的想法。1 9 7 0 年代与工作流有关的研究工作包括：宾夕 法尼亚大学沃顿学院的m i c h a e ld z i s m a n 开发的原型系统s c o o p ，施乐帕洛阿 尔托研究中心的c l a r e n c ea e l l i s 和g a r yj n u t t 等人开发的o f f i c e t a l k 系列试验 系统，还有a n a t o lh o l t 和p a u lc a s h m a n 开发的a r p a n e t 上的“监控软件故障 报告”程序。s c o o p 、o 伍c e m l k 和a n a t o lh o l t 开发的系统都采用p e t r i 网的某 种变体进行流程建模。其中s c o o p 和o f f i c e m l k 系统，不但标志着工作流技术 的开始，而且也是最早的办公自动化系统。 含有工作流特征的商用系统的开发始于1 9 8 3 年至1 9 8 5 年间，f i l e n e t 、 v i e w s t a r 等公司率先开拓了工作流产品市场，早期的商用系统主要来自于图像处 理领域和电子邮件领域。图像处理许多时候需要流转和跟踪图像，工作流恰好迎 合这种需求；增强的电子邮件系统也采用了工作流的思想，把原来点对点的邮件 流转改进为依照某种流程来流转。f i l e n e t 于1 9 8 4 年推出w o r k f l o 商用系统， v i e w s t a r 于19 8 8 年推出v i e w s t a r ，i b m 于19 8 8 年推出i m a g e p l u s 。 进入1 9 9 0 年代以后，相关的技术条件逐渐成熟，工作流系统的开发与研究 进入了一个新的热潮。特别是在i n t e m e t 应用日益普及的情况下，现代企业的信 息系统的分布性、异构性和自治性的特征越来越显著，信息源之间的连接表现出 松散藕合的特点，促进了c s 体系结构和分布式处理技术( w w w 、c o r b a 、j a v a ) 的广泛应用1 2 】。 在企业应用实际中，虽然工作流的概念相对于物料流资金流信息流等概念要 中南大学硕士学位论文第一章绪论 抽象一些，但是工作流从更高的层次上提供了实现了物料流资金流信息流及其涉 及的相关过程与应用的集成机制，从而使得企业能够实现业务过程集成，业务过 程自动化与业务过程的管理 目前，在全球范围内，对工作流的技术研究及相关产品的开发进入了更为繁 荣的阶段：据调查，共有2 0 0 多种软件声称支持工作流管理或者拥有工作流特 征。工作流技术被应用于电讯业、软件工程、制造业、金融业、银行业、科学试 验、卫生保健领域、航运业和办公自动化领域。 1 2 工作流概念及工作流管理系统 1 2 1 工作流概念 工作流是针对工作中具有固定程序的常规活动而提出的一个概念。通过将工 作活动分解成定义良好的任务、角色、规则和过程来进行执行和监控，达到提高 生产组织水平和工作效率的目的。几十年来，不同的研究者对工作流分别提出了 不同的定义。到目前为止，对于工作流仍没有完全统一的定义。不同的机构和组 织分别从不同的角度对工作流概念进行了描述。 ( 1 ) 7 - 作流管理联盟的定义 工作流管理联盟( 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 w f m c ) nt _ 作流提供了一 个标准定义。w f m c 是一个国际组织，组建于1 9 9 3 年，己发展到2 0 0 多个成员( 包 括销售商、用户、生产商、研究所、大专院校等) ，其宗旨是促进工作流的应用， 并制定工作流管理系统的标准。 w f m c 给出的工作流定义是：工作流是一类能够完全或者部分自动执行的业 务流程，根据一系列过程规则，文档、信息或任务能够在不同的执行者之间传递、 执行【3 j 。 ( 2 ) g i g ag r o u p 的定义 工作流是业务流程中可运转的部分，包括任务的顺序以及由谁来执行、支持 任务的信息流、评价与控制任务的跟踪、报告机n t 4 1 。 ( 3 ) i b ma l m a d e l lr e s e a r c hc e n t e r 的定义 工作流是业务流程中的一种计算机化的表示模型。定义了完成整个过程所需 用的各种参数。这些参数包括对过程中每一个单独步骤的定义、步骤间的执行顺 序、条件以及数据流的建立、每一步骤由谁负责以及每个活动所需要的应用程序 【5 】 o “) w m p v a n d e r a a l s t 的定义 工作流是一系列工作的偏序集。工作的序列可以有多种方式，比如工作x 与 2 中南大学硕士学位论文第一章绪论 y 满足x ；在虾是使 1 8 中南大学硕士学位论文第二章基于p e t r i 网的过程模型及合理性验证 能的。变迁t 可以引发，引发后得到后续标识胗，则 i m ( p ) + 1 ，p ，一r m ( p ) = 必( p ) 一1 ，p o t f i m ( p ) ，其他 如图2 1 ( a ) ，m o = ( 1 ，0 ，0 ，0 ，0 ，o ) 库所p l 中含有一个托肯，m ( p 1 ) = l ，此时t 1 被 使能，处于可触发状态，一旦r 。触发，其前集库所p 。中减少一个托肯，其后集库 所见、胁中增加一个托肯，”0 1 ) = o ，m ( p 2 ) = i ，m ( p 4 ) - i ，”= ( 0 ，1 ，0 ，l ，0 ， 0 ) ，如图2 2 ( b ) ，此时t 2 ，t 3 被使能。 2 3 3p e t r i 网基本属性 定义2 5 ( 并发和冲突) ：设p e t r i 网p n = ( p ，乃f ，m o ) ，m o 是州的一个标识， 若，了，f 2 使得m p l m 【f 2 ，则当 ( 1 ) m p l m l _ m l l 2 m 1 2 m 2 一m 2 p l 时称t l ，t 2 在m 下并发； ( 2 ) m 【f 1 1 m 1 一m 1 p 2 m 1 2 m 2 一- 1 m 2 p l 时称 l ，t z 在虾冲突。 定义2 6 ( 可达性) ：设p e t r i 网p n = ( p ，乃f ，m o ) ，若3 m l ，m 2 ，m t ，使 得： v 1 f 七，3 t , t ：m k m i + l ，则称变迁序列6 = f l ，t 2 ，& 在m 下是使 能的，m 到尥是可达的，记作m 。1 6 m 。 定义2 7 ( 可达集合) ：设p e t r i 网p 兰妒，乃f ，m o ) ，令r ( m o ) 为满足下列条件 的最小集合：( 1 ) m o e g ( m o ) ：( 2 ) 若m e r ( m o ) ，且r l 使得u t m ，m e r ( m o ) ： 则称r ( 而) 为p e t f i 网刖的可达标识集合。 定义2 8 ( 活的) ：称p e t r i 网用忙( p ，歹；f ，u o ) 是活的当且仅当vt e et ， v m e r ( m o ) ，3 m e r ( m ) ，使得m p 。也就是说，如果一个p e t r i 网是活的， 则对于任意从初始标识得到的标识m ，必至少存在一个可以触发的变迁t e 乃 并获得后续标识m 。 定义2 9 ( 公平的) ：称p e t r i 网尸= ( p ，死f ，m o ) 是公平的当且仅当v “，红t ， jk o ，对vm r ( m o ) ，v 艿t 都有 m i c r 人群( ，f 8 ) = 0 一拌( f ，8 ) m o 。 即如果一个p e t r i 网是回归的，则对于任意从初始标识蜗得到的标识膨和抬， 标识时可达标识时。 定义2 1 l ( 有界的，安全的) ：称p e t r i 网p n = ( p ，乃f ，m o ) 是有界性( 安全) 的 当且仅当v m e r ( m o ) ，v p p ，3 k o ，使得m 颤拓1 ) 。 或者说，一个p e t r i 网服有界的，当且仅当对于每一个库所p ，存在一个自 1 9 中南大学硕士学位论文 第二章基于p e t r i 网的过程模型及合理性验证 然数以，对于每一个可达的状态，库所p 中的托肯数少于玎；一个p e t r i n p 是安全 的，当且仅当库所中最大的托肯数不超过1 。 定义2 1 2 ( 强连接) ：一个p e t r i 网尸是强连接的，当且仅当对每一对节点( 即 库所和变迁衍吵，存在一条从x 至炒的路径。 2 3 4p e t r i 网基本分析方法 不变量和关联矩阵 定义2 1 3 ( 关联矩阵和不变量) ：令= ( p ，死f ，k ，职m o ) 是一个有限的p 厂r 系统，且p = - p i ，p 2 ，p n ，弘 l ，t 2 ，岛 。 ( 1 ) 矩阵c - 【c 胡( 1 f 门，1g m ) 是的关联矩阵，如果勺= w ( t j ，j f ) 职毋，钐； ( 2 ) 一个n 元整数列向量x 叫做的一个s 不变量，如果ct x x = 0 ，其中ct 为 c 的转置矩阵： ( 3 ) 一个n 元整数列向勤叫做的一个t 不变量，如果c x y = o 。 定义2 1 4 ( 引发数向量) ：令= ( 尸，死f ，k ，) 是一个有限的p t 系统， 若巧t ，3 m r ( m o ) ：m 陋 ，记撑( 焖的为f 在占中出现的个数。令爿( 回， 1 ， 2 ，n ，则称向鼢引发数向量。 状态方程 定义2 1 5 ( 状态方程) ：令= ( 尸，乃f ，k ，职m o ) 是一个有限的p t 系统， 若m 【6 m ，mm r ( 蚴，艿t ，则称m 刊r + 嘞p e t r i 网的状态方程。 通过引发数向量，关联矩阵和一个状态的标识，就可以很好地计算出任意状 态的标识，同样可以计算出从一个标识到另外一个标识所需要的步骤。 还以图2 1 为例，我们用状态方程和关联矩阵来分析： c = 一lo l一1 o1 1o oo o0 0o 00 1o 一1 0 11 0l 初始状态朋沪【1 ，0 ，0 ，0 ，0 ，0 】，变迁t l 、t 2 、t 3 触发各一次的引发数向 量为疑【l ，l ，1 ，0 ，0 ，0 】 2 0 中南大学硕士学位论文第二章基于p e t r i 网的过程模型及合理性验证 m = + c 壮 1 ，0 ，0 ，0 ，0 ，o 】+ 【0 ，0 ，0 ，1 ，1 ，0 】 2 4 工作流网 2 。4 1 工作流网定义 一l0 l一1 01 l0 00 00 00 o0 一l0 10 1一l 0l 【1 ，1 ，1 ，0 ，0 ，o 】= a a l s t 对工作流技术的研究和推广做出了很大的贡献，他将p e t r i 网应用于工 作流，提出了基于p e t r i 网的工作流网( w f n e t ) 4 6 , 4 7 , 4 8 1 。许多学者都是在此基础上 进行研究和改进。 定义2 1 6 47 ，1 1 ( 工作流网) ：一个p e t r i 网p n = ( p ，t ；d 被称为工作流网，当且 仅当它满足下面的两个条件： ( 1 ) 脯两个特殊的库所：f 和o 。库所f 是一个起始库所，即i = o ，库所0 是 一个终止库所，即d = 0 。 ( 2 ) 如果在p n j j i a , - - 个新的变迁f ，使t 连接库所。与，即，- o ) ， = f ) ， 这时所得到的雕强连通的。 从以上两个对p e t r i 网的约束条件可以看出：条件( 1 ) 是使工作流网必须具有一 个起始点和一个终止点，进入起始库所的托肯代表着一个过程实例的开始，而进 入终止库所的托肯则意味着一个过程实例的结束；条件( 2 ) 使得工作流网中不存 在处于孤立的活动和条件( 所谓孤立状态，是指经过该变迁或者库所不存在由f 到。 的道路) ，所有的活动与条件都位于由起始点到终止点的道路上。 在工作流网中，库所对应着过程中的条件，即活动发生的因果关系，变迁对 应着过程中的可执行活动，库所中的托肯代表一个过程实例的状态。一个变迁有 一定数量的输入库所和输出库所，分别代表事件的前置条件和后置条件。当某事 件的前置条件成立时，则该事件( 变迁) 发生，并将托肯转移至后置库所中。在分 析工作流网的性质中，经常会用到扩展工作流网的概念，其定义如下： 定义2 1 7 4 刀( 扩展工作流网) ：扩展工作流网删通过在工作流网舭添加变 迁，获得，产连接o 和f 。尸= ( p ，t ；f ) 满足条件：p = p ，t = t u 矿 ，f = f u ( d ， 产) ，( 产，o ) 。 2 l 中南大学硕士学位论文第二章基于p e t r i 网的过程模型及合理性验证 2 4 2 工作流基本结构到p e t r i 网的映射 工作流管理联盟规定了七种基本的工作流过程结构，( s e q u e n t i a lr o u t i n g ， a n d s p l i t ，a n d j o i n ，o r - s p l i t ，o r j o i n ，i t e r a t i o n ) 可以描述一般的工作流程俐。 1 ) 并行结构 两个或多个活动可以独立并行发生，互相不影响。如图2 2 ( a ) ，活动a 和活 动c 并行执行。 2 ) 顺序结构( s e q u e n t i a ir o u t i n g ) 活动一个接着一个顺序执行。如图2 2 ( b ) 所示，活动b 在活动a 执行完成之后， 并且在活动c 执行之前开始执行。 3 ) 并发结构( a n d s p l i t ) 如图2 2 ( c ) 所示，活动b 和活动c 是并行执行的，这也意味着活动b ，c 可以同 时执行，也可以以任何次序执行，但必须保证在活动a 之后开始。 4 ) 并汇聚结构( a n d j o i n ) 如图2 2 ( d ) ，活动a 和b 是并行执行的，但只有在a 和b 都完成的情况下活动c 开始执行。 5 ) 选择结构( o r s p l i t ) 如图2 2 ( e ) 所示，在活动a 完成后，活动b 或者活动c 被执行，它们中只有一个 可以被选择，活动b ，c 是互斥的，条件结构也可称为选择结构，用于对多选一情 况的建模。 6 ) 或汇聚结构( o r j o i n ) 如图2 2 ( f ) 所示，活动a 和b 并行执行，活动c 在其中任何一个活动的完成都可 开始执行。 7 ) 循环结构( i t e r a t i o n ) 在某些特殊的情况下，有些活动需要多次被执行，如返工的情况。在图2 2 ( g ) 中，活动b 被执行一次或多次。 ( a ) 并行结构( p a r a l l e lr o u t i n g ) 0 3 ) 顺序燃j ( s e q u e n t i a lr o u t i n g ) 器 中南大学硕士学位论文 第二章基于p e t r i 网的过程模型及合理性验证 ( c ) 并蝴( a n d s p l i t ) 0 9 ) 并汇聚锆构( a n d - j o i n ) ( e ) 选择结构( o r - s p l i t )( f ) 或汇聚结构( o r j o i n ) ( g ) 循环结构( i t e r a t i o n ) 图2 2 工作流基本过程结构 根据p e t r i 网语义，用变迁代表活动，可将工作流基本过程结构完全映射如下： p lp 2肋 p sp 6 ( a ) 并行结构的p e t r i 网模型 见d ( b ) 顺序结构的p e t r i 网模型 中南大学硕士学位论文第二章基于p e 倒网的过程模型及合理性验证 p 3 ( c ) 并发结构的p e t r i 网模型 殷 ( d ) 并汇聚结构的p e t r i 网模型 ( e ) 选择结构的p e t r i 网模型 ( f ) 或汇聚结构的p e t r i 网模型 p i见p3 佑1 循环结构的p e t r i 网模型 图2 3 工作流基本过程结构的p e t r i 网模型 2 5 工作流网的合理性验证 过程模型的合理性是业务目标实现的基本保证。工作流模型的合理性验证是 工作流建模环境的一个核心功能，其目的是对己经建立的工作流模型按某种合理 性原则进行验证。这里的合理性包括两方面的含义：一方面是指过程模型的结构 合理性，也就是说过程模型是无结构冲突的，在没有错误发生时工作流是能够正 常终止的；另一方面是指过程模型的语义合理性，也就是说工作流在正常终止时 应该达到所期望的业务目标。过程模型的结构合理性可以通过证明的手段得以验 证，而语义合理性需要研究过程模型的语义，或者仿真工作流执行。通过模拟工 作流的各种执行情况，检查模拟结果与实际业务目标的差异。本节只讨论过程模 型结构的合理性。 中南大学硕士学位论文第二章基于p e t r i 网的过程模型及合理性验证 2 5 1 工作流合理性定义 在进行工作流过程验证之前，我们先要弄清楚什么是合理的工作流过程。 a a l s t 对基于p e t r i 网的工作流网的合理性验证的理论做了深入的研究【4 7 ，5 0 , 5 1 , 5 2 1 ， 给出了工作流网的合理性准则，即： ( 1 ) t 作流网必须具有一个起始库所f 和终止库所o ； ( 2 ) 每一个任务或者条件都处在由起始库所f 到终止库所o 的道路； 以上两个条件是静态的条件，也就是说这两个性质只与p e t r i 网的性质有关。 ( 3 ) 对于每一个工作流实例，程序最终会终止。当它终止的时候，有一个托 肯在结束库所o 里，并且其他的库所是空的； ( 4 ) 在工作流网中没有死的任务，也就是说工作流网中的任意一个任务都是 可以通过执行一系列适当的路由而执行的。 条件3 和条件4 也就是所谓的合理性性质。我们给出一个工作流网合理性的形 式化定义： 定义2 1 8 ( 合理性) ：由工作流网所建立的模型p 是合理的，当且仅当： ( 1 ) 对于每一个可以从状态i n 达的状态此有一个点火顺序( f i r i n gs e q u e n c e ) ， 可以使得状态朋变迁到状态o ，即：v 致f dj ( m 【 d ) 。 ( 2 ) 状态o 是可以从状态f 到达的状态，并且状态o 是唯一满足库所o 中至少有一 个托肯的状态，即：v m ( i 堋a m d ) j ( m 【 d ) 。 ( 3 ) 在州中不存在死变迁，即：v ，t ，j 朋以行纠p m 。 条件( 1 ) 表示过程定义实例在运行时可以终止，条件( 2 ) 保证过程实例能够正 确终止，而用条件( 3 ) 保证过程定义实例中每一个任务都存在执行的可能。基于 上述三个条件，过程定义的正确性和可靠性都能通过对模型的合理属性进行验证 而获得保证。 2 5 2 工作流合理性验证方法 那么如何进行工作流合理性验证呢? 通过上节的分析可以看出来，对工作流 合理性的验证可以从两个方面入手，一是验证工作流网的活性，一是验证工作流 网的有界性。这样验证的正是p e t r i 网的两个基本性质，因此可以利用p e t r i 网的分 析方法和理论成果来验证工作流网的合理性。下面分别讨论基于可达树和基于秩 定理的工作流合理性验证方法。 基于可达树的工作流合理性验证 定理2 1 47 ，l j ：一个工作流网是合理的，当且仅当( 尸，0 是活的和有界的。 按p e t r i 网理论，网系统是否有界，是否存在死变迁的问题等均可归纳为标识 中南大学硕士学位论文第二章基于p e t r i 网的过程模型及合理性验证 覆盖( c o v e r a b i l i t y ) i h - j 题，即给定一个标识m 或组标识 必 ，问是否有某个或某 些可到达标识能覆盖m 或 尬 。 定义2 1 9 ：设m 和 为尸胆( s ，丁；一上的两个标识： ( 1 ) 若v s e s ：般s ) ) ，就说肘被覆盖，记作肘膨； ( 2 ) 若憔 ，目? 脖”，就说m 小于 ，记作m m ； ( 3 ) 若a 认膨，且朋 ”铆，就说a 欠 在库所s e s 成立。 解决p e t r i 网系统的覆盖问题，可以通过构造可达树( r e a c h a b i l i t yt r e e ) 或可达图 ( r e a c h a b i l i t yg r a p h ) 来解决。 定义2 2 0 【4 q ( 可达树) ：设p e t r i 网p n = ( p ，乃f ，m o ) ，可达树r m t ( p n ) = ( 形 毋是一棵树，其中，结点集晦叫( 包含w 和m 维非整数向量集合) ，弧集e 标以 阮素。我们定义一个记号w ：v r l e n ，以咖，n + w - - - - w + w = w 门= w 。 可达树构造过程如下： 步1 ：根v 0 标以m o ，并将v o 进栈s t a c k ； 步2 ：标有m e 虬所的结点v 位于栈顶， ( 1 ) 若v f 丁，jp e p ：p ，d f 一朋p ) 1 ，则1 ，没有后续结点， 将其出栈，转步3 ；否则，步骤( 2 ) ； ( 2 ) 若存在一个未经如下处理的f 兀v p e p ：p ，力n 朋1 ， 则1 ，有后续结点，其中弧( 1 ，) 标以，v 标以下法确定的 ； 否则，将v 出栈，并转步3 ； ( a ) 若树中存在标记m 的结点v ”，满足 3 p e p ，? p ) = 渤p ) + c p ，f ) 若肝圳，v 为一个叶子结点，转步骤( 2 ) ；否则，转步骤( b ) ； ( b ) 若从根v o 至t j v 的路上有标以m 的结点，”，满足 v p e p ： 矿( p ) 坳) + c p ，d 则对所有满足m p ) 朋p ) + c 协，f ) 的p ，令m 仞) - - - w ； 否则，令m 协) 司知) + c p ，f ) ，并将，进栈，转步2 ； 步3 ：当栈s t a c k 为空时，可达树r m t ( p n ) 被确定，结束；否则，转步2 。 定义2 2 1 【4 6 】( 可达图) ：设p e t r i 网p n = ( p ，死f ，m o ) ，可达树r m t 妒a 7 ) = ( 儿 d 是删的可达树，称有向图r m g ( 刚) 是p 的可达图当且仅当从r m t ( p a o 到 r m g ( p n ) 的满射厅：r m t ( p n ) - - , r w g ( 踟，使得： ( 1 ) 结点映射为结点，有向映射为有向弧，且从v ，到吁的弧映射为办( v ，) 到办( 功 的弧： ( 2 ) ( ，沪锄( 功营版j 铷矿，即结点v f 和吩映射为r m g ( p n ) 上同一结点的充分必 要条件是v ，和v ，的标记相同： 中南大学硕士学位论文第二章基于p e t r i 网的过程模型及合理性验证 ( 3 ) r m g ( p n ) 的结点和有向弧由它们在r m t ( p n ) o p 的原像标记。 我们拿图2 1 分析，其可达树和可达图分别为图2 4 、图2 5 ： 0 0 1 1 0 0 i匀 + 0 0 1 0 1 0 i “ 0 1 0 0 1 0 1 l f 2 0 0 1 0 1 0 i“ 0 0 0 0 0 10 0 0 0 0 1 图2 - 4 可达树图2 5 可达图 可达树或者可达图是表示p e t r i 网的状态空间的，基于上述可达树构造算法获 得的可达树，可以直接依据合理性的定义，验证w f - _ n e t 的合理性。验证算法如 下： 步l ：如果工作流网的可达树中存在m ( p ) = o o ，表示库所p 中的托肯数在接下来 的变迁中会一直增大，直至趋向于无穷，因此，该工作流网不是有界的，转步3 ； 步2 ：令三是为可达树的所有叶节点的集合，进行如下判断： ( 1 ) 如果v m ：m ( p ) ：t t - - d 表示系统可以正常终止； l v ，0 ( 2 ) 如果3 m 三： 妖d ) = o 说明系统中存在死锁，死锁发生在库所p ：朋p ) o ； ( 3 ) 如果b m 三：m ( o ) = 1n3 p - - - o a m ( p ) o ，说明系统中存在多余的库所，导 致系统不能正常终止。 步3 ：算法结束。 当工作流网中的节点数目不多时，网系统的状态空间规模还可接受。当节点 数目很多时，网系统的状态空间呈指数规模扩张，使构造可达树的算法过程非常 耗时，基本上是不可接受的。即使是相对简单的自由选择网，构造可达树的算法 复杂度也是指数级的。因此，寻找复杂度相对简单的合理性验证算法，是进行工 作流网过程定义合理性验证的现实需要。 基于秩定理的工作流合理性验证 对于满足某些结构条件的p e l r i 网，判定活性和有界性的算法时间复杂度是多 项式次的。因此，可以利用p e t r i 网的理论成果来研究一种特殊的工作流网一自由 2 7 r 上叭 m 叭 中南大学硕士学位论文第二章基于p e t r i 网的过程模型及合理性验证 选择工作流网( f r e e c h o i c ew f n e t s ) ，其合理性验证算法时间复杂度是多项式次的 【4 l 】 o 定义2 2 2 4 7 1 ( 自由选择网) ：一个p e t r i 网是自由选择网，当且仅当对于每两个 变迁t l ，和t 2 ，t i n t z # 1 2 l ，t l = t 2 。 定理2 2 【5 3 】秩定理，自由选择网是结构活的和结构有界的，当且仅当： ( 1 w 有正的s 不变量； ( 2 ) n - 有 i e 的丁不变量； ( 3 ) i a l = r a n k ( c ) 十1 ( 其中c 是的关联矩阵，彳是的丛的集合) 。 因此，我们可以将该定理应用到工作流网，得到自由选择工作流网合理性定 理。 定理2 3 自由选择工作流网尸= 妒，t ，d 是合理的，当且仅当网系统的扩 展网( p ，d ： ( 1 ) 雨有正的s 不变量； ( 2 ) 州有正的丁不变量； ( 3 ) i a l = r a n k ( c ) 十1 ( 其中c 是p 的关联矩阵，彳是p 的丛的集合) ； ( 4 ) 删的每一个死锁都包含一个被f 标识的陷阱。 其中s 不变量可以通过方程了c 。= 0 求解，获得，丁不变量可以通过方程 c j = - 0 求解镞得，而线性方程组的整数解的问题是多项式时间可解的【5 4 1 ，矩阵的 秩也可以在多项式时间内获得求解【5 5 】，所以我们能够求证条件( 1 ) 、( 2 ) 和( 3 ) 。对 于条件( 4 ) ，如果我们能够证明每个最小死锁都包含一个被f 标识的最大陷阱，根 据死锁的可加性，也可以论证p n 的每一个死锁都包含一个被f 标识的陷阱。因此 求解合理性的关键问题在于获得删的最小死锁，k e m p e r 5 6 1 在引用自由选择网最 小死锁特性定理的基础上，给出了在线性时间获得自由选择网最小死锁的算法。 整个算法的时间复杂度是o ( p 1 刁( 训+ i 矸卜l 同) + 眵1 2 闭) ，是可以在多项式时间里 得到求解的，因此，这是一个有效实用的算法。 2 6 小结 本章首先介绍了工作流过程建模的几种方法，比较了p e 仃i 网用于过程建模的 优势，并给出了p e t r i 网的形式化定义，总结了其基本性质和分析方法。接下来， 介绍了a a l s t 提出的工作流网，工作流网实现了p e t r i 网到工作流基本结构的映射。 本章的重点是对工作流网合理性验证方法的讨论。我们利用p e t r i 网的理论成 果和分析方法来解决工作流网合理性验证的问题，提出了基于可达树的验证方法 和基于秩定理的验证方法。 中南大学硕士学位论文第三章着色工作流网及工作流多实例模式 第三章着色工作流网及工作流多实例模式 利用经典p e t d 网对简单系统进行建模和分析是足够的，但进行复杂的过程建 模时，其表达方法就显得有些不足。此时利用它所建立的模型将非常庞大，系统 结构缺乏柔性，从而给模型的构造和分析带来了很大的困难。为了建模的需要， 将经典p e t r i 网的托肯赋予一定的颜色以代表不同的事物，就形成了着色p e t r i 网 ( c o l o rp e t r in e t ，c p n ) 。着色p e t r i 网具有更强的表达能力，应用更广泛。j e n s e n 深 入研究了着色p e t r i 网的分析方法，开发出了一个着色p e t r i 网的计算机软件，并