（计算机应用技术专业论文）一种支持动态变更的柔性工作流模型研究.pdf

东南大学硕士学位论文 摘要 目前国内外己有很多工作流管理系统的产品，但是它们大部分都不支持在工作流运行的过程 中动态地修改业务过程。一旦工作流程确定，系统就一直按照模型规定的业务过程执行然而， 随着企业规模的扩大，市场需求的快速变化，在工作流建模阶段不可能预先定义好所有的业务过 程。因此，企业在经营过程中往往需要通过对业务过程的重组来适应市场需求，提高企业竞争力 本文就是重点研究如何在工作流运行的过程中动态地修改工作流模型，并把相关的工作流实例快 速地迁移到新模型中运行 文章先对柔性工作流系统进行了初步的研究，扩展了工作流管理系统体系结构，提出了一种 支持动态变更的柔性工作流管理系统该系统采用p e t r i 网模型进行建模，着重分析了工作流实 例迁移过程中所存在的动态变更错误，并结合自由选择网的经典理论，提出了一种基于p e t r i 网 模型的工作流实例迁移算法，算法的时间复杂度是多项式级的。 然后，设计了工作流模型正确性验证算法，该算法能有效地验证工作流模型的正确性，并且 算法的时间复杂度也是多项式级的。 最后，结合工作流实例迁移算法，实现了一个具有柔性的，支持动态变更的工作流仿真系统 关键字：工作流，柔性工作流，迁移，多项式，p e t z i 网 东南大学硕士学位论文 a b s t r a c t al o to fp r o d u c t i o n si n v o l v e di nw 蝴sh a sb e e np m v a i l i n gn o w a d a y s b u ti nm o s to ft h e s e p r o d u c t i o n s , i ti sn o ta l l o w e dt oc h a n g et h ew 0 础o wm o d e li nr u nt i m e o n c et h ew o r k f l o wp r o c e s s m o d e l e d , t h es y s t e mn 脚a l o n ga c c o r d i n gt h ew o r k f l o wm o d e l h o w e v e r , w i t ht h ee x p a n s i o no f e n t e r p r i s ea n dx a p i dc h a n g e so f m a r k e tr e q u h m e 咄t h eb u s i n e s sp r o c e s sc a nn o td e f i n ec o m p l e t e l yi n t h em o d e lp h a s e s o , f n t e l ，r i s eu s u a l l ya d a p tt ot h em a r k e tr e q u i r ea n di m p r o v e 印船f p 慨c o m p e t e t i o n b y b u $ i n c j k q p r o c e s sr e e n g i n e e r i n 粤h o w t o m o d i f y t h e w o a i l o w m o d e l i n r u n n i n g t i m e i sr e s e a r c h e d i n r i f f sp p c l a n d t h e r e l a t e d w o r k n o w i n s t a n c e i s m i g r a t e d t o t h e n e w m o d e l q u i c k l y n 坤f l e x i b l ew o i k n o wi sa n a l y z e di nt h i st h e s i s a n dt h ea r c h i t e c t u r eo f w 蹦si se x t e n d e da n da 0 0 1 f i l ma r c h i t e c t u r ef o raw o r k f l o wm a n a g e m e n ts y s t e mt h a ts u p p o r td y n a m i cc h a n g ei sp r o p o s e d t h e w o r k f l o ws y s t e mi sm o d e l e db yp e t r in e td y n a m i cc h a n g eb u gd u r i n gt h ew o d d l o wi n s t a n c em i g r a t i o ni s a n a l y z e di nt h i sp a p e ra n dan e ww o r k f l o wi n s t a n c em i g r a t i o na l g o r i t h mb a s e d 0 1 1t h ep e t r in e tm o d e li s p r o p o s e d 1 1 ”t i m ec o m p l e x i t yo f t h ea l g o r i t h mi sp o l y n o m i a l t h em e t h o d so fv e r i f y i n go fw o r k f l o wp r o c e s sm o d e l smr e s e a r c h e di n t h i st h e s i sa n da n a l g o r i t h mw h i c hc a nv e r i f yt h ew o z k f l o wp r o c e s sm o d e l se f f i c i e n t l yi sd e s i g n e d t h et i m ec o m p l e x i t y o f t h ea l g o r i t h mi sp o l y n o m i a l a c c o r d i n g t ot h ew o r k f l o wi n s 乜, n c e m i g r a t i o na l g o r i t h m , as i m u l a t i o nf l e x i b l ew o r k f l o w a r c h i t e c t u r ew h i c hs u p p o r td y n a m i cc h a n g ei sd e s i g n e di nt h i st h e s i s k e y w o r d s ：w o r k f l o w ，t l e x m l ew o r k f l o w ，m i g r a t i o n ，p o l y n o m i a i ，p e t dn e t 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：垭日期：掣 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院办理。 第一章引言 1 1 研究背景 第一章引言 随着企业竞争的日益激烈，传统的企业管理模式已经不能再满足现代企业的需求。先进的信 息技术越来越多地被运用到企业管理中来，促使企业管理的信息化，不断地调整优化企业的各种 业务过程，加速企业流程重构，从而使企业实现有效有序的管理和高度的灵话性，提高企业经济 效益和市场适应能力工作流技术正是顺应这一需求孕育而生的，通过合理的调用和分配相关的 信息及资源来管理业务过程中的各个活动，从而促使业务目标的高效实现。 工作流的概念起源于生产组织与办公自动化领域。它是针对日常工作中具有固定流程这特 征而提出的一个概念，将工作分解成定义好的任务，角色，按照一定的规则和过程来执行这些任 务并对它们进行监控，从而提高办事效率、降低生产成本、提高企业生产经营管理水平和企业竞 争力目前对工作流的定义尚未形成一致，根据工作流管理联盟( 肝m c ) 对工作流的定义【i l ：它是 指一类能够完全或者部分自动执行的业务过程，它根据一系列过程规则，使得文档、信息或者任 务能够在不同的执行者之问传递与执行。在实际应用中，可以广泛地把凡是由计算机软件系统控 制其执行的业务过程均称为工作流工作流管理系统是支持企业经营过程高效执行并监控其执行 过程的计算机软件系统1 2 l 。简称工作流系统，它是以业务过程的形式化表示为基础的。这种将实 际的业务过程转化成形式化表示的过程称为工作流建模。在早期的工作流管理系统中，工作流系 统是通过。硬编码”的方式嵌入到应用系统中的显然，这样的系统缺乏灵活性后来，人们把 工作流的业务过程定义与其执行分开。把工作流系统分为建模阶段和运行阶段，建模阶段是对工 作流过程进行定义，而运行阶段是对工作流过程定义的解释执行这样，企业业务过程的分析就 集中在工作流建模阶段，建模完成后就可以反复地执行，现在的工作流管理系统大都是这种模式 随着企业经营环境与业务需求的不断变化，不得不对业务过程进行不断地调整传统的工作 流管理系统在流程定义的时候隐含假设了所有任务的实现和它们之问的协作均能被事先准确、完 善的定义，一旦工作流模型建好系统就一直按照模型规定的业务过程执行。显然，这样的工作 流系统很难适应现代复杂的生产环境和瞬息万变的市场环境 这个问题，可以通过引入柔性工作流而得到很好的解决。柔性工作流”这一名词是相对于 传统工作流中的刚性( r i g i d i v y ) 太强而言的。传统工作流不支持对工作流实时地动态变更，所谓动 态变更是指在工作流运行过程中对工作流模型进行某种修改或调整，有时也称动态调整，它是相 对于工作流定义时( 此时工作流还没有运行) 对工作流模型的静态修改而言的。目前国内外学术界 对于柔性工作流并没有给出一个被大家所公认和接受的明确定义本文定义：如果一个工作流管 理系统支持对于正在运行的工作流过程进行实时、动态的修改。那么就称这个工作流管理系统是 具有柔性的工作流管理系统，简称柔性工作流系统简单地说，柔性即表示了动态适应情况变化 的能力。广义上来讲，柔性包括系统的可重构性、可重用性和可扩展性。柔性是实现企业业务过 程重组( b p r ) 的必要条件激烈的市场竞争、用户需求的多样化以及任务的多变性使得企业的业 务过程咀及组织问的协作必须不断地作出调整以适应新的变化，为了快速响应这种业务过程的变 革，要求各个组织具有高度的开放性和灵活性，即必须建立具有柔性特征的过程管理系统 1 2 国内外研究现状 目前，柔性工作流国内外均尚且处于研究阶段，大部分工作流产品还不具备柔性。然而，不 少大学和科研机构成立了专门小组对柔性工作流的各个方面进行研究，并取得了一些成果，发表 了不少有关柔性工作流方面的文章，开发了一些柔性工作流原型，为柔性工作流的实现提供了一 东南大学硕士学位论文 些方案和思路。 ( 1 ) 文献3 1 将交互作为整个工作流的框架，认为工作流模型的解释执行并非全部自动化， 可以在用户的参与下，将模型的描述和实例的执行交织在一起，工作流模型跟实例的执行不必完 全一致，在执行过程中可由用户交互地处理，减少模型定义的复杂性，这种方法有很好的柔性， 但是对用户提出了极高的要求，因为用户不但要解释模型而且要交互地执行实例，还可能需要 建立部分的模型。文献【4 】认为工作流建模越简单。工作流执行时越具有柔性和适应性，而例外处 理机制是工作流管理系统的基本特征但是从工作流执行模块和运行的角度看，该例外处理机糊 过于复杂文献【3 4 】主要是从工作流执行的角度来考虑，使单个工作流实例在执行的过程中具有 足够的灵活性。 ( 2 ) 在文献【5 】中，作者采用异常处理的方法，利用e c a ( e v t - c o n d i t i o n - a c t i o n ) 规则，针对 工作流变更时的不同情况对工作流实例采用不同的处理策略。文献【6 】提出了一种移交策略描述语 言，在一个移交策略中定义了一些规则，以保证新旧工作流实例能够转换成功。文献【5 ，6 1 主要是 从工作流变更的角度来考虑，讨论模型更改后如何使运行中的实例迁移到新模型中继续执行，但 这两个文献都是针对规则库中的几种有限的变更起作用的，缺乏对任意的工作流变更的支持。 ( 3 ) 文献【7 偎出了一种基于协调理论和反馈机制的工作流建模方法。该方法扩展了传统活 动网络模型，提出了新的建模机制，增加了请求、服务、协调、多实例化等新的建模元素。与传 统的活动网络模型相比，该机制在工作流建模方面提供了很大的柔性，在提高模型描述能力上有 明显优点其主要是从工作流建模的角度出发，在建模的时候考虑到工作流执行过程中可能会出 现的情况，并增加协调机制，提高工作流执行的灵活性，但是它不支持在工作流运行中对模型的 动态修改 目前，工作流的柔性缺乏从工作流建模，工作流的系统框架，动态变更，以及实例迁移的角 度综合考虑本文首先扩展了传统的工作流体系结构接着提出了一种支持动态变更的柔性工作 流体系结构。该结构能够支持运行中工作流模型的变更本文最后提出了一种基于p c 自r i 网的工 作流实例迁移算法，把相关的工作流实例迁移到新模型中运行仿真系统实验表明该工作流体系 结构适应企业业务过程重组的需要，具有较好的开放性与灵活性。 1 3 本文的主要工作 本文针对现有工作流管理系统中存在的对动态性支持不足、缺乏一定柔性及适应能力差等问 题，提出了一种支持动态变更的柔性工作流管理系统，并从工作流系统的建模阶段和运行阶段这 两个层面来展开讨论。 首先，工作流模型是对业务过程的抽象表示，工作流建模是工作流技术理论研究和实际应用 的基础：本文采用p e 俩网来描述工作流模型，并设计了基于自由选择网的工作流模型验证算法， 该算法的时间复杂度是多项式级的 其次，工作流执行是工作流模型在实际应用中的具体映射，本文对相关技术的讨论遵循由静 而动的原则逐步深入地分析了工作流动态变更后实例迁移过程中所存在的动态变更错误，并结 合自由选择网的经典理论，提出了一种基于p e 一网模型的工作流实例迁移算法该算法确保迁 移后的的实例能正确地运行 最后设计了柔性工作流仿真系统，并举例分析工作流实例迁移 1 4 论文的组织结构 本文一共分六章。 第一章为引言，介绍工作流技术的研究背景。重点分析了传统工作流技术存在的不足，引 入柔性工作流的具体原因，并讨论了国内外在该方向上的研究动态，最后说明了本文的主要工作 2 第一章引言 第二章是柔性工作流管理系统，重点介绍工作流模型的基本理论，扩展了传统的工作流管理 系统，提出了一种支持动态变更的柔性工作流管理系统接着介绍了基于p e * r i 网的工作流过程 模型 第三章是工作流实例迁移策略，具体研究模型变更后如何处理运行中工作流实例。分析了实 例迁移过程中存在动态变更错误，并结合p e t r i 网的经典理论，提出了工作流实例迁移算法，最 后分析算法的时间复杂度。 第四章是工作流模型验证，具体分析工作流网建模的正确性，并提出基于p e t r i 网的工作流 模型验证算法，该算法的时间复杂度是多项式级的 第五章是仿真系统与实例分析，主要是柔性工作流仿真系统与实例分析 第六章是总结与展望 东南大学硕士学位论文 第二章柔性工作流管理系统 2 1 工作流管理系统 工作流管理系统是一个软件系统，它的主要功能是：完成对工作流的定义和管理，并按照预 先定义好的业务过程推进工作流的执行l i j 通常，工作流管理系统是指运行在一个或多个称为工 作流机的软件上的用于定义、实现和管理工作流运行的一套软件系统，它和工作流执行者( j l ， 应用) 交互，推进工作流实例的执行，并监控工作流的运行状态嘲在很大程度上，工作流管理 系统为企业的业务系统运行提供一个软件支撑环境，非常类似于在单个计算机上的操作系统只 不过工作流管理系统支撑的范围比较大，环境比较复杂而已，所以也有人称工作流管理系统是业 务操作系统。在工作流管理系统的支撑下，通过集成具体的业务应用软件和操作人员的界面操作， 才能够良好地完成对企业业务过程运行的支持。所以工作流管理系统在一个企业经营过程中的应 用是一个业务应用软件系统的集成与实旖过程 。 从比较高的层次来抽象地考察工作流管理系统。它主要提供三种功能；建立时功能、运行时 控制功能以及同用户和应用程序交互功能各功能之间的关系具体如图2 1 所示： 图2 - l 工作流管理系统的特性 ( 1 ) 建立阶段的功能： 建立时功能主要是通过某种具体分析、建模及系统定义手段，将现实世界的业务过程转 化为能被计算机处理的形式化表示这种形式化表示被称为过程定义( 也称工作流模型) 。过 程定义中一般包含：业务过程中各个活动步骤的描述，同这些活动相关的各种计算机或人工 操作以及活动之间进行切换的控制规则等 ( 2 ) 运行阶段的控制功能： 主要是对某个计算机环境中工作流业务过程的管理及各活动步骤之间的状态转换运行 时控制系统将解释过程定义，完成过程可操作实例的创建和控制，调度过程中各活动步骤， 为所涉及的用户生成待处理的任务，并在合适的时机调用有关的应用程序资源等等这些服 务一般称为“工作流执行服务”可能通过一个工作流引擎提供服务，也有可能用到多个协作 的工作流引擎。工作流引擎是工作流运行时控制系统的核心部分，各种过程实例的执行都是 4 第二章柔性工作流管理系统 由它所负责完成的。 ( 3 ) 运行阶段的人机交互功能： 主要是对：j ：作流实例执行过程中各个活动的处理。在工作流实例的执行过程中，经常需 要_ h j 户通过某种应用程序来完成过程定义所要完成的处理与操作。例如，填写一个表单，或 使用某个应川程序生成新的文档，或处理其它活动传递过米的文档等。 根据以上工作流管理系统的各功能的分析，工作流联盟给出了一个工作流管理系统的参考模 型，如图2 - 2 所示： 骨 酉霁巍 图2 - 2 工作流管理系统的参考模型 下面是对此工作流管理系统参考模型作简要的说明： ( 1 ) 过程定义工具 提供一种对实际业务过程进行分析和建模的手段，是工作流管理系统中的一个重要组成部 分，也是实施工作流管理系统的起点。借助于工作流过程定义工具，工作流业务过程将铍建立起 来，帮助人们理解工作流元素之间的复杂关系。工作流模型的两个主要元素是条件和活动。条件 可以是组织中的一个角色、文档、数据或程序等。活动可以是一项工作或一个事件。 ( 2 ) 工作流过程定义 过程定义( 数据) 包含了所有能被工作流执行子系统执行的业务信息。这些信息包括起始和 终止条件、各个组成活动、活动调度规则、各业务的参与者需要做的工作、相关应_ i j 程序和数据 的调h j 信息等。 ( 3 ) 工作流执行子系统( e s ) 和j 作流引擎 工作流执行子系统也称为( 业务) 过程执行环境，包括一个或多个工作流引擎。工作流引擎 是t 作流管理系统的核心软件组元。它的功能包括：解释过程定义；创建过程实例并控制其执行； 调度各项活动；为用户工作表漆加i ：作项：通过应_ h j 程序接口( a p i ) 调埘应埘程序；提供监督 和管理功能等。工作流执行子系统可以包括多个一i ：作流引擎，不同工作流引擎通过协作共同执行 工作流。 5 东南大学硕士学位论文 ( 4 ) 工作表和用户接口 工作表及用户接口是与群组工作人员相关的元素。工作表中包含工作人员应完成的工作项 目。一般说来每个用户都有一个工作表与之对应，在一些特殊的情况下也有一个工作组对应一个 工作表。一 2 2 柔性工作流管理系统 在引言中已经阐述了柔性工作流的一些基本概念。这里，将集中从用户，建模者和管理员等 人的视角更深层的研究工作流柔性问题，并提出柔性工作流管理系统。 2 2 1 两类柔性工作流 根据柔性实现的阶段不同，可以将工作流管理系统中的柔性分成选择柔性和适应柔性两大 类。选择柔性是在工作流建模阶段对可预见的情形进行说明定义，从而给用户提供一定的自由度； 而适应柔性则是在工作流执行期间允许用户对工作流程进行各种适应性的调整或变更，能够快速 的实现企业业务过程重组，适应市场需求。 ( 1 ) 选择性柔性( f l e x i b i l i t yb yc h o i c e s ) 选择柔性就是要为用户提供选择，在执行到工作流的某一点时，用户可以从预先定义的 执行路线或操作中自由选择。图2 - 3 给出了一个选择柔性的示意图。在工作流的执行路径可以预 知的情况下，选择柔性是非常有用的。从图中可以看到，s t a r t ，和e n d 节点抽象地代表了整 个或者部分工作流的起点和终点。在起点和终点之间有若干条路径可供用户选择，这些路径都是 可预见并且在工作流建模阶段定义好的。 图2 - 3 选择柔性 虽然选择柔性为用户提供了极大的方便，但是它有一个弱点，就是对于那些可能的选择必须 在建模时直接或间接的预知，而这一点在很多情况下是很难做到甚至于无法做到的，于是便提出 了下面的适应柔性】 ( 2 ) 适应柔性( f l e x i b i l i t y b y a d a p t a t i o n ) 现实中，企业业务过程对环境变化的依赖非常敏感。因此，无法在流程建模时对所有可能的 任务和任务之间的协调机制进行完善的定义，常常需要在流程执行的过程中不断地对工作流模型 进行动态的修改。因此，仅靠选择柔性无法处理这些问题。如何使工作流系统能够随着企业经营 环境与市场需求的变化而动态的修改工作流模型己经成为目前工作流管理系统研究的一个热点 所以，设计支持动态变更的柔性工作流是必须的，也是符合发展趋势的工作流模型的动态变更 主要包括以下几种变更模式： ( a ) 工作流业务过程的动态变更 工作流系统在静态建模时建立的业务过程由于不适应新环境的变化和需求，在运行的过程 中需要对其进行调整。这些调整一般包括：添加新的活动、删除已有的活动、修改现有活动的执 行依赖关系等这种变更是最常见的变更模式，本文主要是讨论这种变更情况图2 4 就是一个 适应柔性中的业务过程修改示意图。 6 第二章柔性工作流管理系统 ( b ) 资源状况的动态变更 在工作流系统的实际应用中，资源状况的变动也是经常发生的比如，原来的旧设备要替换 成新设备，这时就需要对资源分配的状况进行调整。同样，资源状况的变更可能会导致组织状况 的变更，例如，新的设备需要引进新的人才来操作 ( c ) 组织模型的动态变更 系统参与人员的变动和组织结构的调整也是经常发生的。因此，工作流系统必须具有组织状 况的动态变更与任务重分配的功能，同时必须能够对已经分配好的任务的进行动态调整。 图2 - 4 适应柔性 从图2 4 中可以看到，原先定义好的业务过程经过修改之后增加了一个节点( 如图中虚线所 示) ，这样一种改变是在工作流运行的时候发生，也就是工作流业务过程的动态变更。 根据适应柔性对工作流产生影响的时间不同，可以把适应柔性分为型调整( t y p ea d a p t a t i o n ) 和实例( i n s t a n c ea d a p t a t i o n ) 调整两类。型调整指对工作流模型的修改不影响当前运行的工作流实 例，除非整个实例从头开始重新运行。显然，型调整比较简单，是基于版本控制的。而实例调整 则意味着对工作流的修改可以即时生效，文中我们把实例调整称为实例迁移，这是我们的研究重 点如前所述，在工作流建模阶段，很多具体情况都无法事先预料到，因此需要在执行过程中动 态的调整来适应这些情况。此外，除了要求适应之外，这里还要强调动态动态适应强 调的就是要动态改变运行中的工作流而不需要整个流程重新运行才能按更改后的流程执行，工作 流管理系统应该要支持动态适应的一套机制。本文主要解决工作流实例的动态适应问题，着重研 究模型变更后对工作流实倒的调整，提出了一种支持动态变更的柔性工作流管理系统。该系统在 保持工作流管理系统参考模型基本结构的基础上添加一些新的模块。如图2 - 5 所示 2 2 2 扩展的具有柔性的工作流管理系统 为了提高工作流管理系统的适应能力，本文对传统的工作流管理系统进行扩展，增加了三个 功能：工作流模型验证，工作流模型修改以及工作流实例迁移图2 - 5 描述了扩展之后的工作流 系统体系结构的基本部件和基本接口。该模型可以用于柔性工作流系统的设计与实现。 7 东南大学硕士学位论文 罔广i 图2 - 5 扩展的具有柔性的工作流管理系统 瑗员 下面分别介绍新添加的各个接口的功能： ( 1 ) 模型验证 对于面向过程的工作流系统而言，过程定义是业务过程自动流转的基础。然而，业务过程的 定义比较容易出错，仅凭流程设计者的经验或者操作者的反复实验来发现差错的方法效率低下。 如果在工作流系统投入使用后发现流程有错的话，有可能会带来灾难性的后果，所以工作流模型 的错误越早发现越好因此，在工作流执行前之前，需要采用验证方法，对业务过程中的各项特 性进行检测，以保证工作流模型的正确性。即不会出现死镇，活锁，及不能正常运行到终止状态 的状况一般工作流模型定义后就要验证该模型是否正确，若不正确必须重新修改该模型，直到 模型正确 ( 2 ) 工作流模型修改 随着企业经营环境与业务需求的不断变化，常常需要在工作流运行过程中对业务过程进行 重组，优化，促使企业更快的发展，提高企业竞争力业务过程的更改映射到工作流管理系统中 就是改变原来已经定义的工作流模型。具体表现为添加一个活动，删除一个活动，以及调整活动 的次序等等，本文的模型修改直接在建模工具的可视化界面中修改。修改后的模型也要验证其模 型的正确性，即也要通过模型验证模块，若不正确就要重新修改该模型，直到模型正确。 ( 3 ) 工作流实例迁移 该模块是柔性工作流系统支持动态变更的关键组件实例迁移就是在工作流模型动态变更 后，正确处理当前正在运行着的一些实例，使之能够正确并及时地迁移到变更后的模型中运行。 本文第三章将具体研究实例迁移算法 显然，扩展后的工作流管理系统具有良好的柔性，支持工作流动态变更，并能及时地处理运 行中的工作流实例 2 3 基于p e t r i 网的工作流建模方法 工作流过程模型是对工作流的抽象表示，也是对业务过程的抽象表示。工作流系统建立阶段 的主要功能是完成对工作流过程的建模，从实际业务过程向计算机可处理的形式化定义转化所 得到的定义通常称为工作流过程模型，简称工作流模型l 。p c 廿i 网作为一种图形化和数字化的建 模工具，已经被广泛应用于各个领域进行系统建模、分析与控制。由于p e t r i 网适合于描述并发， s 第二章柔性工作漉管理系统 异步、分布、并行，不确定性和随机性的信息处理系统，进行系统模型的构造，分析及评价”， 因此，在工作流领域，p c t f i 网也得到了广泛的应用 p e t r i 网是由两类元素组成的，即：代表资源的库所和代表活动的变迁。两者之间用弧连接， 弧由变迁指向库所或者是由库所指向变迁，两类相同的元素不能连接图形化描述为：库所用圆 来描述，变迁用横或竖来描述，库所中的托肯用实心小圆点标识在工作流建模中，p e t r i 网用 变迁表示工作流中的任务，库所表示任务实施的条件 2 3 1p e t r i 网的基本概念 定义2 1 p e 啊网【1 2 1 ： p e t r i 网是一个三元组( p ，t ；f ) ( 1 ) p 是有限个库所的集合； ( 2 ) t 是有限个变迁的集合( s n2 = m ) ； ( 3 ) f ( s 乃u ( t x s ) 是弧的集合( 流关系) ； 库所p 称作变迁啪输入库所，当且仅当存在一个从p 到f 的有向弧。库廖币称作变迁f 的输出库所， 当且仅当存在一个从倒p 的有向弧。本文用t 表示变迁t 的输入库所集合，符号t 。、p 和p 有 类似的含义，即p 是共享p 作为输入库所的变迁集合。本文用1 p l ，i t l 分别表示该p e t r i 网中的 库所总个数与变迁总个数。 一 任何时刻，库所当中都包含零个或者多个托肯，托肯用一个黑点( t o k e n ) 表示系统的状 态m ，是托肯在库所上的分布，我们将一个状态用一个向量表示，假如有库所集：p l ，p 2 ，p 3 ， p 4 。则状态可以表示为向量( 1 ，2 ，3 ，4 ) 这意思为：p l 库所中含有1 个托肯，p 2 库所中含有2 个托肯，p 3 库所中含有3 个托肯，p 4 库所中含有4 个托肯这里用m ( p i ) 表示p i 库所中所含有的 托肯数即m ( p 1 ) = 1 ，m ( p 2 ) = 2 ，m ( p 3 ) = 3 ，m ( p 4 ) = 4 。对于任何两个状态m 1 和m 2 ， m 1 m 2 。当且仅当对于所有的p e p ：m i ( p ) m 2 ( p ) ； 在p e t r i 网的执行期间，库所中托肯的个数可能会改变的变迁是p e t r i 网中的活动组件，它 们根据下列实施规则改变p e t r i 网的状态： 变迁t 称作就绪的，当且仅当t 的每个输入库所都包含至少一个托肯； 就绪的变迁可以实施。如果变迁t 实施，那么从每个输入库所p 中消耗一个托肯，并为每 个输出库所p 产生一个托肯。 给定一个p e t r i 嘲( p t ，f ) 和一个状态m 1 ，本文有如下符号： 膨o 肼，：变迁往状态m 1 下是就绪的而且在状态m 1 下实施t 得到状态m 2 ； 以 ，：存在一个变迁t ，使得肘o 厶； 肼l 三号m ：实施序列盯= f 2 f 3 。使得状态m l 通过一组( 可能为空) 中间状态 m 2 ，m 3 。m i 到达状态 钿，即朋j 生 ，2 q 坞m ： 状态m n 称作从m 1 可达( 符号 二吖) ，当且仅当存在一个实施序列盯使得 j | i 三专肘，注意，空实施序列也是允许的，a pm i 二 九 9 东南大学颐士学位论文 我们使用( p ，m o ) 表示拥有初始状态地的p e t r i 网p n 。一个状态材是( p ，m o ) 可达状态， 当且仅当m l 二一膨： a a l 髓在p e t r i 网的基础上提出了工作流网的概念，其主要是对p e 耐网模型作了一些限定，使 其能够有效地描述工作流模型工作流网有这样一个特点：它有两个特殊的库所，其一表示过程 的开始，其二表示过程的结束。分别称它们为源库所和结束库所，用i 和o 表示，见定义2 2 定义2 2 工作流同1 1 3 】 p e t r i 网，m o ) 被称为工作流网，当且仅当： ( 1 ) 存在一个源库所j p ，使得i - o ； ( 2 ) 存在一个宿库所o e p ，使得o = m ； ( 3 ) 每一个节点x p u t ，都位于从i 到0 的一条通路上； ( 用e 肼j ) 是一个工作流网，若添加一个变迁f 到( 州m o ) ，用来连接宿库所0 和源库所i ( 即f = o f l t = f ，如图2 6 所示) ，那么所得的p c l f i 网是强连通的【“ 我们称添加了新变迁t 的网为工作流网p n 的扩展网，记做p n = ( p ，t ，聊，其中：p = p ； t = t u t ： 万= ，u 如，f ) ，( ，。，f ) 如图2 7 所示： o 1 陲1 2 - 6 工作流网对应的扩展网两= ( - 亍，而 2 3 2 从活动图到p e t r i 网的转化方法 用活动图描述的工作流模型在可读性上是最好的，对于非专业人员也是最自然、最直观的 过程表达方式活动图包含两类元素：节点和有向弧，其中节点表示活动有向弧标识活动之间 的偏序关系。一般情况下，每一个用活动图建立的工作流模型均可以转化为p c t f i 网模型过程 中的每一活动对应p e 耐网中的一个变迁，活动的前置和后置条件对应p v t r i 网中的库所。 工作流联盟定义的六种控制结构为i l i ：与分支，与汇合，或分支，或汇合，顺序结构和顺 环结构，下面提供对工作流联盟定义的六种活动图的结构转化为p e l r i 网的转化方法。 o 卜 ( d ) 与汇合节点转化 吟长 ( o 与分支结构转化 图2 1 7 箭头的右边均给出到相应p e t r i 网的转化模型。为了进一步说明p e t r i 网模型的描述能 力，下面以旅游投诉处理过程为例，把该业务过程从活动图转化为p e t r i 网模型。 旅游部门首先将刚刚收到的投诉记录下来，然后联系投诉的游客与投诉相关的部门。若要向 游客询问更多的信息，还要通知被投诉的部门并询问它们的最初反应这两个任务可以并行执行 ( 也就是能同时或任意次序执行) 。之后，就可以根据搜集的数据并做出决策，根据决策，作出 支付赔偿或者发拒绝信，最后投诉被归档。这个流程的活动图如图2 8 所示： o m 走冉弘内瞳吐 n e g a t i v e 轴l d _ l e t t r 图2 - 8 投诉系统的活动图结构 转化为相应的p e t r i 网模型为： c e t m 矗p j m m _ 掣垤和叫u _ - 图2 - 9 投诉系统对应的p e a i 网结构 其中，活动图中的活动节点对应p e t r i 网中的变迁节点在p e l r i 网建模中的第一个库所中含 有一个托肯，代表该工作流开始执行的触发条件 2 4 本章小结 本章先介绍了传统的工作流管理系统的体系结构，然后在此基础上提出了一种支持动态变更 的柔性工作流管理系统，并分析了采用p e a i 网建模的优点，最后举倒说明从活动图模型到p e 醯 嘲模型的转化方法 东南大学硕士学位论文 第三章工作流实例迁移 由于企业经营环境与业务需求的不断变化，通常需要对工作流的业务过程作出一些变更，从 而适应市场的需求工作流模型变更后面临的主要问题就是如何处理运行中的工作流实例，并把 相关的工作流实例快速地迁移到新模型中运行本章主要讨论工作流实例迁移问题 3 1 实例迁移与迁移策略 目前对工作流实例的处理方法主要有以下几种【i 1 ： ( 1 ) 重新启动策略：当工作流模型改变时，当前运行的工作流实例全部被放弃执行该策略在 有些情况下是经常用到的。比如，由于以前实施的计划和流程效率低下，需要替换采购部的管理 队伍，而新的管理队伍可能会撤消当前所有的采购订单。但是这种直接取消所有已运行的工作流 实例有时也是不现实的比如在制造型企业中，重新启动意味着己经组装好的部件不是被丢弃就 是要被分解，造成的损失很大 ( 2 ) 继续执行策略：在这种情况下，所有当前运行的工作流实例都可以完全按照原有的工作流 模型执行，但是新创建的工作流实例就必须基于新的工作流模型执行。这样，工作流系统中可能 会同时运行着几种不同版本的工作流模型 ( 3 ) 迁移策略：这种策略影响所有运行的工作流实侧，但是不同于继续执行策略和重新启动策 略。工作流实例通常处于流程执行的不同阶段，这样就会出现一种问题，当工作流实例执行到某 个阶段时。该实例的后续任务可能无法依照新的过程模型继续执行。为了使实例可以基于新模型 继续执行，迁移策略可能要恢复( u n d o ) 或补偿( c o m p e n s a t e ) 己完成的若干任务( t a s k ) ，最坏的情况 就是已经接近完成的业务过程实例必须被回退( t - o n b a c k ) 到开始状态，意味着所有己经执行结束的 工作都会丢失或被取消，这种特倒也就相当于重新启动。 现在，工作流实例迁移策略主要侧重于理论研究，国内外也发表了不少有关迁移的文章文 献 1 5 1 提出了变化区域的概念将变更直接影响到的部分称为变化区域，并相应地称工作流变更 发生之前为旧区域，变更发生之后为新区域，使用网替换( n e t r e p l a c e m e n t ) 法来实现实例迁移 文献【l 研旷展了文献f 1 5 】中的变化域概念，将文献f 1 5 】所指的变化区域称为静态变化域，并提出了 动态变化域概念，指出当实例运行在动态变化域的时候不能马上迁移，否则可能会引发动态变更 错误( d y n a m i c c h a n g e b u g ) ，只有当实例运行出动态变化域的时候才能迁移到新的模型上运行该 策略能够确保实例迁移的正确性，但这不是个充要条件一有的实例运行在动态变化域的时候也 是可以迁移到新模型中运行的。而且该方法求动态变化域的时间复杂度是阶乘级的( 刀( m ) 2 ) ， 在工作流节点很多的情况下就会变的很复杂 文献【1 7 课用继承的概念，把对工作流模型的变更看作在旧模型中添加了一些东西，即继承 了原来的模型这种策略主要是限定了几种模型变更方法，并针对这几种工作流模型变更提出了 相应的实例迁移策略文献【1 8 1 也提出了一种基于变化域的工作流实例迁移算法，但是它是基于 活动图所描述的。没有严格的数学证明过程。 本章分析了工作流实例迁移过程中所存在的动态变更错误，并结合自由选择网的经典理论， 提出了一种基于p e t r i 网模型的工作流实例迁移算法主要是根据工作流实例迁移后的状态是否 可达，来确定该实例能否正确迁移，算法的时间复杂度是多项式级的。 1 2 第三章工作流实例迁移 3 2p e t r i 网的基本概念1 9 】 定义3 1 ( 强连通) 一个p e t r i 网系统是强连通的当且仅当：对于搬，y ( p u n 都有一条通路连接x ，y 。 定义3 2 ( 自由选择网) 一个p e t r i 是自由选择网当且仅当 v f l ，t 2e t ，若f i n e t 2 西，则t i = o t 2 定义3 3 ( 可达集) ( i v , m o ) 中从m o 出发所有可以到达的状态的集合称为该系统的可达标识集记做r ( ，m o ) 定义3 4 ( 话性定义) ( n ， 如) 是活的当且仅当v f t ，m r ( n , m o ) ：3 m 。r ( n ，膨) ；m 会实施f 定义3 5 ( 有界性) ( ， “) 是有界的当且仅当3 k n + ：y p p m e r ( n ，g o ) ：m ( p ) j 肘j m ，与肼。； 即有 如i ：膨) ；符合定义3 1 1 ，该定理成立 定理3 1 3 状态膨在合理的工作流网( p ， “) 中是可达的，当且仅当 f 在其扩展网( p ，m o ) 中是 可达的 证明： ( 1 ) 肼在( 只，m o ) 可达jm 在( p ，m o ) 中可达，显然成立 ( 2 ) m i 生( p n , m o ) 可达jm 在( p j 也肘o ) 中可达，分为两种情况： o 在( 两，m o ) q ，若从状态 ，。到达状态肼没有实施变迁f ，则必有：了盯= f i t ： = m o 三号m ，显然m 在( p ， “) 中也是可达的。 0 在( e n , m o ) 中，若从状态m o 到达状态 ，时实施了变迁f ，由于( p ，m o ) 是合理的工作 流同，t 的实施必然是从终止状态变到初始状态，因此必有： j 口= f i t 2 。j ：，膨o 二 m 。l 峨! 而w ，显然有! m 。印肘在( p ，m o ) 中也是 可达的若多次实施f ，也同样有! m 综合( 1 ) ，( 2 ) 该定理成立 由定理3 1 3 可知状态材在工作流网( p m o ) 中的可达性可以转化为状态m 在其扩展网 而) 中的可达性。由定理3 j1 2 可知合理的工作流网其扩展网是一个活的、有界的和循环的p 晚i 1 7 奎里查兰垦主兰堡丝苎 网。而具有活的，有界的和循环的自由选择嘲的状态可达性是可以在多项式时问内判定的删，所 以自由选择工作流网( 户，g o ) 的状态可达性问题也可以在多项式级的时间内判定 定义3 1 4 冽 设：m 。，m ：是( p ， 如) 的两个状态，i 是( p ，m o ) 的一个争不变量。如果，m = ，鸩， 则称m i 与m 2 同一( a g r e e o n ) 于，；当m 与 ，2 同一于( p ，j | l 厶) 的所有争不变量，s j i 称m 。等 价于m z ，记作：m l ，2 定义3 1 5 陷阱( t r a p ) 若，c p 有( p ) c ( p ) ，则p 为一个陷阱若v p p 均有心p ) = 0 ，则称为陷阱p 没 有被m 标记( m a r k ) ，否则就称为陷阱p 被材标记。若p 中没有一个陷阱包含p ，则称p 为p 中的最大陷阱。 定理3 1 6 p o l 喾i