（计算机软件与理论专业论文）工作流过程建模合理性分析与应用.pdf

河海大学硕士论文 工作流过程建模合理性分析与应用 摘要 上作流过程建模是一个复杂且易错的过程。若过程定义在投入运行之后被发 现有错，则修复错误的代价相当高，这个问题引起了研究界和工业界的高度重视。 因此，在建横阶段进行有效的过程验证是卜分必要的【4 “。特别是最近几年，工作 流技术存业务过程重组中的重要作用吏为突出，对复杂流程的分析和验证研究的 需求也越来越迫切。完善工作流过程建模理论已经成为工作流管理系统的个重 要发展方向。 本文主要研究工作流模型的结构合理性问题。在参考了大量当前工作流系统 研究的基础上，首先按照任务结构，给出了x p d l 到p e t r i 网的映射方法，由于 x p d l 已经成为事实上的工作流过程描述语言，使得映射过程可以独立于不同的 建模方法；接着利用p e t r i 网结构分析理论，给出可达树验证方法，并对其不足 进行分析和改进；然后根据j r 作流网的特点，给出符合自由选择网结构的工作流 刚的合理性验证方法，并和p e t r i 网的验证算法进行详细比较和复杂度分析。该 算法的复杂度比普通p e t r i 网的验证复杂度低，具有实际应用价值。 本文的研究成果不仅适用于业务过程领域，在其他应用软件领域也同样具有 较高的理论参考和指导价值。文中给出了合理性验证技术在软件组装领域的应用 扩展，探讨了基于工作流网的w e bs e r v i c e s 组合合理性验证问题。 关键字：工作流、合理性、p e t r i 网、工作流网、扩展自由选择网、复合w e b 服务 望塑查堂堕主望塞 三堡鎏垫堡堡堡鱼堡堡坌堑皇窒旦 a b s t r a c t w o r k f l o wp r o c e s sm o d e l i n ga n dt h ep r o c e s sv e r i f i c a t i o ni nm o d e l i n gp h a s ea r e h i g h l yn o t e d i nb o t hr e s e a r c ha n d i n d u s t r ya r e a ，b e c a u s et h ec o s tf o rm o d i f y i n g e r r o r s i sv e r yh i 出a f t e ra p r o c e s sd e f i n i t i o nb e c o m e so p e r a t i o n a l h o w e v e r ，t h em o d e l i n g o f aw o r k f l o wp r o c e s si sac o m p l i c a t e da n de i t o l p r o n ep r o c e d u r e ，e s p e c i a l l y , w i t h w o r k f l o w sp l a y sam o r ea n dm o r ei m p o r t a n tr o l ei nb u s i n e s sp r o c e s sr e e n g i n e e r i n g ， t h e r ei sa l lu r g e n td e m a n df o rv e r i f i c a t i o nr e s e a r c ha n da n a l y s i so fc o m p l e xp r o c e s s ， t h e r e f o r e ，t oi m p r o v e t h em o d e lt h e o r yh a sb e c o m ea ni m p o r t a n tr e s e a r c hd i r e c t i o n t h i sd i s s e r t a t i o nt r i e st om a k ec o n t r i b u t i o n so ns t r u c t u r a ls o u n d n e s so fw o k f l o w m o d e l t h ef i r s tp a r to ft h i sd i s s e r t a t i o np r o p o s e sa na l g o r i t h mf o rm a p p i n gx p d lt o p e t r in e t sa c c o r d i n gt oa a l s t t a s ks t r u c t u r e b e c a u s ex p d lh a sb e e nas t a n d a r do f w o r k f l o wp r o c e s sd e s c r i p t i o n ，i ti sm a d et h em a p p i n g p r o c e d u r ec a nb ei n d e p e n d e n t o n m o d e l i n g m e t h o d i nt h es e c o n d p a r t ，w o r k f l o wm o d e l i sa n a l y z e d b ys t u d y i n gt h e p e t r it h e o r yo ns t r u c t u r a la n db e h a v i o r a lp r o p e r t i e s a na l g o r i t h mi sg i v e nt ov a l i d a t e t h es o u n d n e s so ft h ew o r k f l o wm o d e la c c o r d i n gt ot h ec h a r a c t e r i s t i c so fw f n e t t h e c o m p l e x i t yo f t h i sa l g o r i t h mi sl o w e r t h a nt h a to f t h ec l a s s i c p e t r i s ，s oi th a sp r a c t i c a l v a l u e s t h er e s e a r c hr e s u l ti nt h i sp a p e rn o to n l y a d a p tt ob u s i n e s sp r o c e s sm o d e l i n gf i e l d b u ta l s oh a sm u c ha c a d e m i cg u i d a n c ea n dr e f e r e n c e dv a l u et oo t h e rs o f t w a r ef i e l d a n e x a m p l eo f c o m p o s i n gw e b s e r v i c e sb yp e t r ii sd e p i c t e di nt h ee n do f t h i sd i s s e r t a t i o n ， t h e nw ec a nb s et h et h e o r ym e n t i o n e da b o v et oa n a l y s i st h es o u n d n e s s p r o p e r t yo f a c o m p o s e d w e bs e r v i c e k e y w o r d s ：w o r k f l o w ，s o u n d n e s s ，p e t r in e t ，w f n e t ，e f c ，c o m p o s e dw e bs e r v i c e s 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 如不实，本人负全部责任。 论文作者( 签名) ： 兽丝喜 2 0 0 5 年4 月2 6 日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊 ( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文 档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被 查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河海大学研究 生院办理。 论文作者( 签名) ： 7 隧够詹 2 0 0 5 年4 月2 6 日 塑塑查兰堕主堡塞 三堡鎏整里堡堡鱼墨生坌堑兰壁! l 第一章绪论 1 1 研究背景 工作流起源于生产组织和办公自动化领域，它是针对r 常工作中具有固定 程序的活动而提出的一个概念。目的是通过将_ 丁作分解成定义良好的任务、角 色，按照一定的规则和过程来执行这些任务并对它们进行监控，以提高办事效 率、降低生产成本、提高仓业生产经营管理水平和企、l p 竞争力“。 在8 0 年代中期，f i l e n e t 和v i e w s t a r 等公司率先开拓了工作流产品市场。 进入2 0 世纪9 0 年代，在i n t e r n e t 应用 _ _ i 益普及的情况下，现代企业的信 息系统的分布性、异构性和自治性的特征越来越显著。在这种技术背景下，工 作流管理系统成为简化企业复杂信息环境，实现业务流程自动执行的必要：1 ：具。 这样的一个转变，把工作流技术带入了一个崭新的发展阶段，使得人们从更深 的层次、更广的领域对工作流展开了研究。 1 9 9 3 年工作流管理联盟( 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 ) 的成立标志着 工作流技术开始进入相对成熟的阶段。为了实现不同1 ：作流产品之间的互操作， w f m c 在工作流管理系统的相关术语、体系结构及应用编程接口( w a p i ) 等方丽 制定了一系列标准。 通俗地讲，所谓的工作流是指一些任务按照特定规则在网上协同执行以完 成某种目标。这类似自动化生产线上原料经过一系列自动加工产生成品。在【 作流中，规则u ，以看作自动化过程，其载体是网络。从形式化角度来说，1 ：作 流是指各种对象( 事件、任务、操作) 按照既定的规则在可执行的系统中进行 方向性、可控制的迁移并且各种对象、遗留系统可以协同工作。从技术的角度 来讲，t 作流技术就是使用网络资源连接组织中的各个环节、有效提高工作效 率的一种集成应用技术。其中涉及了网络通讯、信息组织、x m l 、数据库系统、 安昔：、系统集成等各项技术。从功能的角度来讲，完整的工作流系统是一种有 效设汁、管理并执行业务流程的图形化工具。通过管理工作活动系列，调动与 各种活动步骤有关的人员、i t 资源，对业务过程进行自动化处理。业务的执行 顺序由工作流逻辑的计算机表示形式来驱动。 河海大学硕士论文 工作流过程建模合理性分析与应用 h 前工作流具有代表性的定义有： 工作流管理联盟的定义：工作流是类能够完全或者部分自动执行的业务 过程，它根据一系列过程规则，文档、信息或任务能够在不同的执行者之间进 行传递与执行1 3 、。 i b m 的定义：工作流是业务过程巾的一种计算机化的表示模型，定义了完 成整个过程所需的各种参数。这些参数包括过程中每一个单独步骤的定义、步 骤唰的执行顺序、条件以及数据流的建立、每一步骤由准负责以及每个活动所 需要的应用程序“1 。 a a l s t 的定义：工作流是一系列工作的偏序集。工作的序列可以有多种方 式，比如活动x 与y 满足x s 是转换方法。当处理1 个复杂的模型时，f 仍然存在状态爆炸的问题。并且仅初 步探讨了简单活动到状态的重构，对于更为复杂的流程也没给出重构的方法m ，。 北京大学的赵文根据改进的工作流过程元模型，研究并提出了一种基丁p 门 系统的工作流过程模型过程网。根据转换规则把业务过程映射为过程网，并给出 了千h 应的化简规则，应用规则进行化简验证过程模型巾的死锁和缺乏同步两种结 构冲突并得到验证结果。文中提出的化简规则未能更多地应用于比较复杂的 ：作 流过程模型，化简规则集的完备性是下步要研究和解决的问题之。 总的米况，由于在业务过程重组中的重要性，关于合理性验证的问题是当前 的一个热点问题。多位学者从不同的角度分析和探讨了这个问题，并在某些方而 取得了一定的成果。但是还没有一种方法能够彻底的解决合理性验证的问题。从 河海大学硕士论文 工作流过程建模合理性分析与应用 这些研究成果也可以看出，学者们采用的方法多种多样，各种成果问的关系并小 火，这也间接说明合理性验证问题目前的研究并不成熟。 1 4 本文目的及主要工作 、i k 务过程重组是当前管理思想创新的一个代表，它的根本目的是，埘企业的 、i k 务流程进行根本性的再思考和重新设计，达到反映快速化、制造敏捷化，重组 业务组织和业务流程，从而显著提高管理效率和水平，增强企业的核心竞争力。 其主要手段是通过对现有流程进行分析和改造。因此，业务流程的制定和修正对 企业的经营具有至关重要的作用。然而，不合理的工作流程有可能给企业带来不 必要的损失。因此，利用技术手段在流程实施之前进行正确性分析具有重要的意 义。 本义主要工作如卜j ： ( 1 ) 综述了当前合理性验证的研究成果，分析现有成果的局限性。 ( 2 ) 分别分析x p d l 元素：任务、连接弧、条件以及子网，给出了x p d l 向p e t r i 网然后到工作流网的转化规则。由于x p d l 是w f m c 制订的业务过程模型描 述标准，因此该映射适合所有业务过程建模工具。 ( 3 ) 根据定义用可达树验证，并给出了可达树的改进方法。 ( 4 ) 利用自由选择网的一些研究成果，对符合自由选择结构的过程模型给出了 种验证算法。该算法类似p e t r i 网活性和有界性的验证算法，但是根据 工作流网的特征进行了改进，降低了验证的复杂度。由于绝大多数的工作 流模型具有自由选择网的特征，因此算法具有较强的实用价值。 ( 5 ) 给出了合理性验证应用的一个实例，应用工作流思想研究w e bs e r v i c e s 的复合问题。首先给出了w e bs e r v i c e s 复合构造的常用类型，然后对这 些类型进行了形式化描述，并利用上文结论，对复合的w e bs e r v i c e s 的 合理性进行验证。 1 5 本文结构 本章是绪论部分，主要介绍工作流的一些基本概念、业务过程建模方法与分 析技术、并给出了国内外关于模型合弹性研究的背景及成果、以及本文所作的工 作简介。 河海大学硕士论文 工作流过程建模合理性分析与应用 第二章主要介绍p e t r i 网的概念、符号、基本性质以及常用的分析技术；刘 基于p e t r i 网技术的工作流分析方法给出了简要说明。是本文的理论基础。 第三章讨论x p d l 到工作流网的映射问题，在简单介绍x p d i ，语言后，3 3 节研究从x p d l 到工作流网映射方法；3 4 节给出映射算法。由于x p d l 已经成为 事实卜的工作流过程描述语言，研究x p d l 到工作流网的映射，是有其理论和现 实的意义的。 第| ) r q 章利用p e t r i 网技术对业务过程模型的合理性验证。给出可达树验证方 法，并对其不足进行分析和改进；根据工作流网的特点，给出符合自由选择网结 构的工作流网的合理性验证方法，并和p c t f i 网的验证算法进行详细比较和复杂 度分析。 第五章是本文所介绍方法的一个应用，探讨基于_ 作流方法的w e bs e r v i c e s 组合的合理性验证问题。总结了w 曲s e r v j c e s 复合的几种常用方式；提出了复合 w e b s e r v i c e s 构造的p e t f i 表示方法；给出了复合规则；介绍了复合的w e bs e r v i c e s 的合理性验证方法。 第六章总结全文并提出了进一步工作。 9 河海大学硕士论文 工作流过程建模合理性分析与应用 第二章p e t r i 网基础 在奉章中，对以后备章节将要用到的p e t r i 网的一些基本知识、概念、术语 和方法作简单介绍，详见文献 2 卜2 4 。本义所用的符号基本按照i s o i e c1 5 9 0 9 标准符号集。在本章中还给出了一些图例，以利于更好地理解。最后，对基于 p el ri 网技术的工作流分析方法给m 了简要说明。 2 1p e t ri 网概述 p e t r i 网是一种系统的数学和图形的描述与分析工具，由德国科学家c a r l a d a mp e t r i 在1 9 6 2 年提出。p e t r i 网分析方法和技术既可以用于静态的结构分 析，又可以用于动态的行为分析，特别适用于具有并发、异步、分布、并行、不 确定性的信息处理系统。经过几十年的发展，p e t r i 网理论得到了极大的十富， 其应用己经涉及计算机学科的各个领域，如线路设计、网络协议、软件工程、人 工智能、形式语言、操作系统、并行编译、数据管理等。基本p e t r i 网是一种 有向二部图( ad i r e c t e db i p a r t i t eg r a p h ) ，包含朋个基本元素，分别是：两种 类型的节点：库所( p l a c e ) 和变迁( t r a n s i t i o n ) ，以及有向弧( a r c ) 和表示资源流 动的标记( t o k e n ) 。通常在图形上，库所用圆或椭圆表示，标记用小黑点表示， 变迁则用矩形表示。需要注意的是，由于p e t r i 网是二部图，所以，一条弧不会 连接两个相i 司类型的节点，即库所与变迁一定是交替出现的。 2 1 1 i s o 标准定义 根据2 0 0 3 年颁布的i s o i e c1 5 9 0 9 标准“，p e t r i 网是分析和规范并发的 动态离散系统的形式化的、图形化的可执行的建模技术标准。具体解释如下： “形式化”：p e t r i 网具有严格的数学定义，从而网系统的许多静态和动态 性质l 叮以，4 格数学证明；因此，用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 _ 门槛；“动态离散系统” 包括信息系统、操作系统、网络协议、银行业务、电子商务以及通信过程等； “并发”：p e t ，f i 蚓适用于许多独立的动态实体的并发系统，如多代理系统、 分布式数据库、网络环境以及现代通信系统； “舰范”：p e t r i 网系统通过形式的系统规范来表达和验证； “分析”：p e t r il 】【 9 系统可以用数学方法证明系统动态或静念行为是甭满足 规范，方法包括可达图、不变量分析等； “建模”：p e t r i 网建模是一个不断循环迭代的过程，可以不断地发现缺点 与错误，不断地修改与再分析，最终保证规范的j 下确性，并实现与规范的致 性。 h 前在业务处理领域，p e t r i 网技术得到了广泛的应用。相对于其他方式， 用p e t r i 网来描述1 作流的形式化模型的优越性有如下几点”2 ： 1 p e t r i 嗍作为离散事件系统建模技术提供了直观的图形标识，在直觉上 容易理解和应用，并提供了强大而又形式化的描述能力。 2 p e t r i 具有形式化的语义，个p e t r i 模型加上相应的语义就能描述一 个业务过程。 3 p e t r i 基于状态而不是基于事件，使其具有描述更复杂过程逻辑的优势。 4 p e t r i 具有坚实的理论基础和比较成熟的分析方法。使用基于p e t r i 理 论建立的w f n e t 模型的业务过程定义，其i f 确性、可靠性验证和性能分析 也可以借用p e t r i 阏或其他数学工具和分析工具的分析技术加以解决。 2 1 2 p e t r i 网的基本概念 定义2 1 ：p e t r i 网n = ( p ，r ；f ) 称为有向网的充分必要条件是： o ) p u t 中( 网非空) ( 2 ) p i n t = ( _ 元性) ( 3 ) r ( p x t ) u ( t x p ) ( 流关系仅在p 和t 的元素之问) ( 4 ) d o m ( f ) wc o d ( f ) = p u 丁( 网中无孤立元素) 其中：p = p j ，p ：，p 。；称为的有穷库所集，h ：jpj 。 n20 t = t ，f ：，) 称为的有穷变迁集，研= l t i a m 0 ； f 表示流关系，是山n 中一个p 元素和一个n 元素的有序序偶的集合， 河海大学硕士论文 工作流过程建模合理性分析与应用 其中：d o m ( f ) = xj j y ， f ) ，c o d ( f ) = x i b y ， f 。 图形卜，库所表示为圆，变迁表示为长方形，流关系表示为有向弧，例如： ( x ，y ) f ( p x r ) 图形表示为 ( x ，y ) f c f r p ) n n 表示为 定义2 2 ：( 网系统) r 1押 、f i 六元组= ( s ，t ，f ，k ，w ，螈) 构成网系统的条件是： ( 1 ) p n = ( s ，t ，f ) 构成有向网，称为的基嘲； ( 2 ) k ：p - + u 沏) ，是位置上的容量函数，m 表示无穷； ( 3 ) w ：f 寸n + ，是弧集合e 的权函数。w ( x ，y ) 表示弧( x ，y ) 的权值； ( 4 ) m ：尸一n ，是网的标识，对砌p ，m ( p ) 世( p ) 表示在某个状态下 各个库所巾t o k e n 的个数。m o 是初始标识。 定义2 3 ：( 前集和后集) 设n = ( p ，t ：f ) ，x ：p u t ，对任一元素x ： 4 x = y ( y ，x ) f 称为x 的前集( p r e s e t ) 或输入集； x = y 1 ( x ，y ) f ) 称为x 的后集( p o s t s e t ) 或输出集。 定义2 4 ：( 变迁发生的条件) t 在状态m 有发生权的条件是： v p 4t ：m ( p ) w ( t ，p ) n m ( p ) + w ( t ，p ) 丘( p ) 。 t 在m 有发生权记为：m t ：也况m 授权( e n a b l e ) t 发生( o c c u r ) 即：要有足够的t o k e n 数供t 触发并且触发后t o k e n 不越界。 定义2 5 ：( 变迁发生的结果) 若m t ，n t 在m 可以发生，并且将产生个新的标示m ，m 的定义是，对任意【) p m ( p ) m ( p ) 一w ( p ，t ) i fp m ( p ) + i v ( t ，p ) f f p m ( p ) 一w ( p ，t ) + w ( t ，p ) m ( p ) 4t t + t + 一4 t i fp r 一t i f p g + t + d 表示变迁触发序列，m 经口到肘，记为m p m 。 河海大学硕士论文 工作流过程建模合理性分析与应用 2 i 3p e t r i 的行为与结构特征 定义2 6 ：( 可达性) 对有效转移的启动可以改变t o k e n 的分布。如果存在一个从m o 到 i 的启动序 盯= m 1 1 t l m 】t m 。，简化仃= t i t 2 t 。 或者m o 二专m ，m o 盯 m 列，称m 是从m 。可达的。肩动序列表达为：l ( n ，m 。) 。实际上用r ( n ，m 。) 表示从表 示m o 叮达的所有标识集合。这样可达性问题就转化为对于网( n ，m 0 ) 和给定杯 以m 。，寻找是否存在m 属于r ( m 。) 。 定义2 7 ：( 有界性，活性) 是p e t r i 网最重要的特性。有界性保证了状态的规模不会无限增大，活性保 证无死锁操作。 令n = ( p ，t ：f ) 是一个p e t r i 网，。是一个网系统， ( 1 ) 变迁t r ，是活的，当且仅当对v m r ( n ，m o ) 。3 m r ( n ，m ) 寸i t ： ( 2 ) 。是活的，当且仅当t 中的所有变迁l 在。中都是活的； ( 3 ) 库所p p 是k 一有界的，当且仪当了k ( k n ) ，v f r ( n ，m 。) 专m ( p 1 足 ( 4 ) e 。是有界的，当旦仅当p 中的所有库所p 都是有界的。 定义2 8 ：( 结构活，结构有界) 令n = ( p ，1 ；f ) 是一个p e t r i 网。 ( 1 ) _ 是结构活的，当且仅当存在一个标识肼，( n ，m ) 是活的； ( 2 ) n 是结构有界的，当且仅当对任意的标识肘，( n ，m ) 是有界的。 定义2 9 ：( 可逆性) 对任意从m o 可达的标识m ，都是从m 可达的即： v m ，( m o 二斗m ) 一( m 帆) 。 定义2 1 0 ：( 家态h o m es t a t e ) 是l u 逆性的概念扩展。令( n ，m 。) 是。个网系统，m ”是家态当且仪当 对任意的可达标识m ，都有m - 二斗m ”。 定义2 1 1 ：( 强连通) p e t r i 网是强连通的当且仅当对坛，y p ，存在从砸吣钓有向路径。 定义2 1 2 ：( 并发、冲突、混惑) 河海大学硕士论文 工作流过程建模合理性分析与应用 设m 是网系统的有效标识， 并发：若m t m t 。 ，f 1 和f 2 的触发互不影响。即 ( m t - me t 2 ) 斗( m t 2 呻m l l ) 。 并发是丁作流建模中经常使用的技术，活动并行执行以提高工作流的效率。 冲突：m h a m t ： ，但是、m t 1 ，t ：j 。等价描述： m t l a m i t 2 - - - ( m t 】 一m t 2 ) ( m t 2 斗一 tj ) 混惑：一个网中同时存在并发和冲突，并且并发的实施会引起冲突的消失( 减 少) 或出现( 增加) 。 、k 务过程建模的目的就是要使系统在满足需求的情犹卜，提高工作的并发 度、减少冲突、杜绝混惑情况。而p e t r i 网的这些性质能够描述上述情况，并l 可 以通过p e t r i 这些特性的分析达到这个嗣的。 定义2 1 3 ：关联矩阵 设= ( p n ，肘。) ，其中p n = ( p ，t ；f ) 是一个纯网，即：v x z ：+ j n 矿：巾 用s 一i 素作序表的列向量矿：p 寸z 称为的s 一向量： 用t 一元素作序表的列向量u ：t z 称为的t 一向量： 用t x p 作序标的矩阵c ：t x p 斗z 称为的关联矩阵，其矩阵元素 乞l = 其中g = g l 一 g l 1 。( o ，只) 5 ，c ：1 ( 辟，o ) f 0 o t h e r ” 1 0 o t h e r 定义2 1 4 ：状态方程： 设= ( 州，峨) ，其中p n = ( p ，t ：f ) 是纯网，则c 与存在一一对应的关系。 r i m 2 m ( p ，) ，m ( p 。) ，m ( p 。) n 这样，m t ， 的充分必要条件为： v i 1 ，2 ，m ：( c ) ；m ( f ) 。 若m i t 。 m 。，则有m 2 = m 。+ ( c ) 毛。推广之，若m 。 盯 m ，就可以推出状态方程为： m = m 。+ c l ，u 片中c l u 是矩阵乘法；盯是的转移序列；u 是的t 向量。 定义2 1 5p - 不变量，非负p 一不变量 令6 l 为分量全为0 的t - 向量，i 为系统的一个p - 向量： 若c i = 口，就称i 为的p 不变量； 若， 巳，就称i 为非负p - 不变量，其中眈为分量全为0 的p 向量。 河海大学硕士论文 工作流过程建模台理性分析与应用 定义2 1 6t 一不变量与s 一不变量的定义对称 设i 为网系统的一个。卜向量，臼。为分量全为0 的p - 向量： 若c j = 臼，即在p f f e 弓l 起的变化均为0 ，就称i ，为的t 邢不变量； 若t 一f i 变量j 目，就称j 为非负t 一不变量。 关联矩阵和不变量是进行结构分析的主要方法之一，通过网系统的关联矩阵 和不变量，就可以很方便地求出p 一不变量。 设i 是的p 一不变量，m m o ，则1 7 ，m = 1 7 m 。 设o - 是的m 。到m 的转移序列：m 。 口 m 。于是m = m 。、+ c 1 u ， 其中u 是对应，盯的t 一向量，两边同时乘以t ，则得： t m 。+ i c 1 = 1 1 m 因为i t 为p 不变量，故1 1 c 1 = ( c i ) 1 = 9 r , 占是分量全为0 的t 向量。 2 1 4p e t r i 网的子类 山于p e t r i 网的复杂性，很难有一种通用的方法可以用于所有系统模型的分 析。目前，大部分研究人员都只对于描述某一特定系统的某一种特殊类型的p e t r i 网提i j j 了分析或综合的方法。本沧文主要研究符合p e t r i 网某些子类特征的工作 流网合理性验证，因此卜面给出p e t r i 网的一些主要予类，并说明其问的关系。 定义2 1 7 ：状态机( s t a t em a c h i n e ) 、标识图( m a r k e dg r a p h ) 令n = ( p ，丁；f ) 是一个n 州网。 ( j ) n 为状态机( 简称s m ) ，当且仅当v t t ：l + t i = i t + i = l ： ( 2 ) n 为标示图机( 简称m g ) ，当且仅当v p 尸：+ p i = p + i = 1 。 如图2 1 ( a ) ，2 1 ( b ) 。 定义2 1 8 自由选择网( f r e ec h o i c en e t ，f c 网) ，扩充自由选择网 ( e x t e n d e df c ，e f c 网) 令n = ( p ，l ，) 是一个r 删网。 ( 1 ) 称n 为自由选择网，当且仅当：坳p ，l p + 降1 或+ ( p 4 ) = 扣) ， 等价的定义还有，p ：p ，p 】np 2 中j j b + i = p 2 + 卜】。 肯义是一个库所到1 个变迁的每条弧不是唯一的输入弧就是唯一的输出弧。 ( 2 ) 称n 为扩充自由选择网，当且仅当：。，p ：p ip l + n p 2 + m p j * ： 如图2 1 ( c ) ，21 ( d ) 河海大学硕士论文 工作流过程建模合理性分析与应用 定义2 1 9 - 非对称选择网( a s y m m e t r i cc h o i c en e t ，a c 网) 令n = ( p ，丁；f ) 是一个凡f “网，称n 为a c 网，当且仅当： 奇1 ，只p ，如果p 1 4 n 岛+ 巾那么p i + p 2 * 或者p i + 三岛+ 如图2 1 ( e ) 。 ( a ) s m f c 、f c f b l m g ( d ) e f c ( e ) a c 图2 1 p e t r i 网f 类的示例 图2 2 表示各类子网间的关系。 幽22 p e t r i 网各子类问关系 6 河海大学硕士论文 工作流过程建模合理性分析与应用 2 1 5p e t r i 网的扩展 前面所述的p e t r i 刚是基本p t 刚，p e t r i 网还具有很强的扩展性。为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 嘲等高级嘲系统的扩展方 式。高级网提高了建模能力，遗憾的是，建模能力和i 百分析性“不是冤家不聚首”， 提高了建模能力就增加了可分析性的难度，存在一个建模平衡问题。本文采用的 方法是选取较严的并且足以建模的子类来分析，所得到的结果也可以用于高层 p c t r i 网的分析。 2 2p e t r i 网的分析技术 2 2 1 p e t r i 网的分析方法 可分为行为特性分析方法和结构分析方法两人类： 分层或化简：在保证网系统基本性质不受的情况下进行分层或化简，以简化 问题的复杂性。 可达树方法：是一种简单有效的分析方法，将p e t r i 网运行的所有可达状态 以树的形式枚举出来，这样，有界性、活性等性质容易得到验证。其缺点是对一 个较大的网系统，存储空间和时间开销太高，仅适合于规模较小的网。 矩眸方程求解：也称为不变量方法，通过对p 一不变量、t 不变量、矩阶 的秩等运算，用来研究周期性等性能，并且可以用来进行互斥、死锁分析等。 结构分析方法：基于p e t r i 网的许多性质是由网的结构决定的，它们独立卡 网的初始标识m 0 ，即这些特性适合于网的任何初始标识，通常用网的关联矩阵及 其相关的齐次方程表示进行分析。 2 2 2 基于p e t r i 网技术的工作流分析 创建或修正一个业务流程，会对组织产生深远的影响。由于过程定义是这个 过程的蓝图，所以必须首先确保其正确性。然后是应使案例的完成时问和资源能 力需求尽可能少a 相对应的，也存在两种类型的工作流分析方法：定性分析和定 量分析，即合理性分析和性能分析。 尽管采用p e t r i 州技术的工作流模型l 叮读性不是非常好，但是山于其具有严 河海大学硕士论文 工作流过程建模台理性分析与应用 格的数学定义和丰富的分析方法，对于工作流的建模与分析研究人员有着很大的 诱惑力。特别是当业务流程较为复杂，如存在并发、冲突等情形时，用p e t r i 网 技术进行分析有着明碌的优势。因此，在实际应用中可以采用直观易读的有向网 络图进行工作流建模，而在模型分析时，通过一种具有语义不变性的映射方法将 有向网络图转化为相同语义结构的p e t r i 网，进而利用丰富的p e t r i 网理论进行 模型分析”。 工作流模型的合理性分析 合理性分析关心所定义的过程在逻辑上的正确性，包含两个方面的含义：一 是指工作流模型结构上的正确性，也就是说，工作流模型是安全的、无死锁的； 另一方面指1 作流模型语义的i 卜确性，测试工作流的行为是否与实际业务一致， 即在完成业务目标上与实际业务流程是等价的。采用的技术主要有图论和线性代 数技术。 2 3p e t r l 网的化简技术 化简技术是简化系统复杂性的一种有效手段，具体思想是利用一些约束或规 则简化系统而保持某些特性不变。即原系统的所有性质在被简化的系统中依然保 留。简化过程可以递归进行，直到容易分析某些性质为止。p e t r i 的化简规则可 以参考文献 2 s ，2 6 。交叉使用化简和其他结构分析方法对复杂系统进行分析，可 以互相补充，收到更好的效果。 2 4 本章小结 本章介绍了p e t r i 网的基本概念、p e t r i 网的结构与行为特征、子类、高层p e t r i 网、分析方法；讨论了基y - p e t r i 网技术的工作流分析技术，是下文的技术基础。 河海大学硕士论文 工作流过程建模台理性分析与应用 第三章x p d l 到工作流网模型的映射算法 ! i l l 第一章所述，业务过程建模的方法很多，这些方法各有自身的适应领域和 优缺点，对自身方法定义的过程模型合理性也应当提供支持。然而当考虑的经营 过程较为复杂，如存在并发、冲突等情形时，用p e t r i 嘲方法进行工作流模犁分 析有明显的优势。因此，在实际应用中可以采用相应的方法进行工作流建模，而 在模型分析时，通过一种具有语义4 ；变性的映射方法将有向蝴络图转换为相同语 义结构的p e t r i 网，进而利剧丰富p e t r i 网理论进行模型分析“1 。 根据w f m c 的标准，、i k 务过程的表示采用x p d l 语言来描述，如果能够直接在 x p d i ，层面上进行分析，那么业务过程的合理性验证将变得比较统。然而，x p d i ， 虽然足业务过程定义的标准， 日是由于x p d l 语言缺乏必要的的数学基础和逻辑基 础，使得由其捕述的模型没有很好的模型分析算法作为支撑。如果我们直接对 x p i ) l 进行分析，那么分析过程将变得非常复杂，并且在分析中将会涉及到很多其 他的问题。因此有必要先将其映射至1 p e t r i 网，然后利用p e t r i 网的方法进行分析 和验证。 本章讨论工作流模型到工作流网的映射问题，首先在3 1 节和： 2 节简单介绍 x p d l 语言和a a ls t 博士的从有向图到：i ：作流网的任务结构方法后，在3 3 节研究从 x p d i 。到工作流网映射方法；3 4 节给出映射算法。 3 1 x p i ) l 简介 x p d l ( x m lp r o c e s sd e f i n el a n g u a g e ) “7 1 是工作流管理联盟提出的一种基 t - x m l 的工作流过程定义语言，目的是为了方便工作流过程定义在不同。t ：作流产 品之1 1 i | 的交换，客观上也能促进第三方工作流过程定义。【j 具的出现。 x p d l 的提出是有历史根源的。在x p d l 之前，工作流管理联盟提 过w p d l ( w o r k f l o wp r o c e s sd e f i n e 1 a n g u a g e ) ，采用类似巴科斯一诺尔范式的格式， 以一个产生式规则集合的形式进行过程定义。当x m l 的应用成为信息技术的主流 时，工作流管理联盟在x m l 基础上经过发展，并采用x m l 。语言描述格式，形成了现 在：的x p d i 。 河海大学硕士论文 工作流过程建模合理性分析与应用 x p d l 是一个通用的框架，这也是x p d i 。的一个重要特性，这个框架可以支持 开发暂的特殊使用目的，而对外表现形式却相同。开发者的实现和它的外部接 可以独屯分丌，凶为不管你是如何实现的，采用什么图形描述( 状态图，活动图 等) ，只要外部接l j 符合x p d l 规范，那么就可以保持相| 一j 的表示形式。 x p d l 中主要实体元素包含i 组属性，第一组是所有元素共有的属性，第_ 组 是各个元素自身特有的属性，第三组是对其它元素的引用属性，第四组是提供工 作流执行引擎使用的陈述性信息，第五组属性是仿真和过程优化的相关信息。 山于工作流管理联盟的权威性，x p d 。已经成为事实上的工作流过程描述语 言。住可以预见的将来，x p d l 将凶为其简单、适应性强和标准化程度高而得到j “ 泛的应用，各种t 作流户：品对x p d l 的支持也将得到大大强化。 黑体字标出了分支类型以及其后续活动。可以看出，在计算机的处理中， 类型和后续活动是隐式的，也比较复杂。根据p e t r i 网的性质，利用库所和变迁 能够显式表示o r ，a n d 的s p l i t ，j o i n 类型。在p e t r i 网中，使用库所分支来表 示选择关系( o r s p l i t ) ；使用变迁分支来表示同步关系( a n d s p l i t ) ；选择汇聚 ( o rj o i n ) 通过一个库所汇聚来完成；同步汇聚( a n d j o i n ) 通过一个汇聚变迁来 完成。x p d l 的节点和p e t r i 网并不是一一对应的关系，我们需要寻找相应的映射 算法，将用户建立的表示业务流程的x p d l 映射成p e t r i 网，从而进一步将其映射 为t 作流网。 河海大学硕士论文 工作流过程建模合理性分析与应用 3 2 相关研究- a a ls t 的任务结构方法简介 模型定义工具中，通常用户采用简单有向图方式建立业务流程。如果直接对 简单有向图模型进行分析，那么分析过程将变得非常复杂，并且在分析中将会涉 及到很多其他的问题。鉴于以上原冈，a a l s t 提出了任务结构“”的映射算法，将 削户建立的表示业务流程的有向图映射成p e t r i 网，从而进步将其映射为工作 流网。以f 是a a l s t 提出的任务结构映射算法。 定义3 1 多元组w = ( x ，u ，t ，s ，d ，t r i g ，n a m e ，i ) 称为任务结构，其中组成元 素必须保持致性： i 任务实体集合x