（计算机应用技术专业论文）工作流活动多实例的建模和调度研究.pdf

工作流活动多实例的建模和调度研究 摘要 工作流活动多实例，特指一个活动，有多个不同的工作流参与者。每个工作 流参与者都执行一个同构的活动。工作流活动多实例所代表的业务流程在现实中 非常常见，最常见的比如投票、选举和多个专家审核论文等。 但工作流活动多实例正式提出之后，一直没有得到广泛的应用。除了工作流 管理自身相关理论的不成熟外，多实例本身所具有的一些特点也造成了应用上的 困难。 多实例从一个整体的角度去表示群体执行同样任务的情况。这种表示上的灵 活性对工作流执行中的调度分配、任务的结束和资源共享等一系列问题提出了控 制要求。 本文首先在总结相关研究工作的基础上，对工作流活动多实例进行了分类并 进行了详细的解释，同时与传统意义的工作流进行了区别和比较。 然后，对工作流的建模问题进行了讨论和阐述，并且提出将传统的复杂流程 转化为一种顺序路由流程进行建模描述，解决了以前工作流活动多实例的建模困 难的难题。 最后，提出了分组触发的思想，并为分组触发思想设计了一套调度框架。分 组触发思想将和活动触发汇聚相关的部分从w l m c 的工作流参考模型的工作流 引擎中单独分离出来，将与活动相关的部分作为为工作流引擎服务的外围模块。 同时分组触发使用映射表解决了“活动多实例的现实意义一流程执行路由”之间 的映射。使得活动执行时只要按照映射表指明的路由即可，而不用随时要考虑多 实例的现实意义，有利于计算机的执行。并使用了现实业务流程进行了例证。 关键词：工作流；多实例：建模；调度：分组殃射 r e s e a r c ho nm o d e iin ga n ds c h e d u i eo ft h ew o r k f i o w m u i t i p l el n s t a n c e sa c t i v i t y a b s t r a c t m u l t i p l ei n s t a n c e sa c t i v i t yi sa na c t i v i t yw h i c hh a sm u l t i p l ep a r t i c i p a t e s e v e r y p a r t i c i p a n t w i l lj o i nt oo n eo fi n s t a n c e so ft h i s a c t i v i t y t h eb u s i n e s sp r o c e s s e s p r e s e n t e db ym u l t i p l ei n s t a n c e sa c t i v i t yi sv e r yc o m m o ni nr e a l i t y , s u c ha s v o t e p r o c e s s ，a u d i t i n gp r o c e s sa n ds oo n m u l t i p l ei n s t a n c e sa c t i v i t y h a s n tb e e nr e a l i z e di nt h ec o m m e r c i a lw f l v i s ， w h e r e a si tw a sp u tf o r t hs e v e r a ly e a r sa g o s o m ec h a r a c t e r so ft h em u l t i p l ei n s t a n c e s a c t i v i t yr e s u l ti nt h a ts i t u a t i o na sw e l la st h el a c ko f t h et h e o r yo nt h ew f m s s u p p o r t i n gm u l t i p l ei n s t a n c e sa c t i v i t yi sv e r yf l e x i b l e a tt h es a m et i m e ，t h i s f l e x i b i l i t ya l s oi n d u c e st h ed i f f i c u l t yo ft h em o d e l i n ga n dt h es c h e d u l eo fm u l t i p l e i n s t a n c e s a sar e m i t ，aw e l lm e c h a n i s ms h o u l db ep u tf o r w a r dt ot a k ec o n t r o lo f i t f i r s t ，t h i sp a p e rc l a s s i f i e sa n de x p l a i n st h em u l t i p l ei n s t a n c e sa c t i v i t yo nt h eb a s i s o fo t h e r s r e s e a r c h t h en e x tp a r td i f f e r e n t i a t e st h em u l t i p l ei n s t a n c e sa c t i v i t yf r o mt h e t r a d i t i o n a la c t i v i t y , a n dd i s c u s s e st h ed i f f e r e n c eb e t w e e nt h e m a f t e rt h a t ，t h em o d e l i n gm e t h o do f m u l t i p l ei n s t a n c e sa c t i v i t yi sd i s c u s s e da n da n e x a m p l ei sp r e s e n t e dt os h o wh o wt oe x t e n dt h ea o v - n e tt om o d e lt h em u l t i p l e i n s t a n c e sa c t i v i t y a n dt h e n ，t h eg r o u pt r i g g e rm e t h o di sp u tf o r t ha n da na l g o r i t h mf r a m e w o r kf o r i ti sd e s i g n e d i nt h i sm e t h o d ，t h ep a r tt h a tm a n a g e st h er o u t i n go f t h ea c t i v i t i e sw i l lb e s e p a r a t e df r o mt h ew o r k f l o we n g i n em o d u l ew h i c hi st h ek e r n e lm o d u l eo ft h ew f m c w o r k f l o wr e f e r e n c em o d e l b e s i d e st h a t ，am a pt a b l ei sa l s ou s e dt os o l v et h em a p p i n g p r o b l e mf r o m b u s i n e s sp r o c e s sr e a l i t y t o w o r k f l o wr o u t i n g i nt h ee n d ，t w or e a l i s t i cp r e s e n t a t i o n sw i l lb eg i v e nt or e p r e s e n tt h ea l g o r i t h m f r a m e w o r ko f m u l t i p l ei n s t a n c e sa c t i v i t y k e y w o r d s ：w o r k f l o w ；m u l t i p l ei n s t a n c e s ；m o d e l ；s c h e d u l e ；g r o u pm a p p i n g 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含未获得 ! 篷；翅遗直基他霞噩犍型直明 鲍! 奎拦卫窒2 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作 签字日期：1 卯存 月门日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：赤勿多厶 签字日期：乙卯乐 月己 日 学位论文作者毕业后去向： 工作单位： 通讯地址； 导师签字 拯一 勃一 外斗 名 一 签 者 卜 1，l z 目，r 序 口 伊 ： 话编 期 电邮 字签 工作流活动多实例的建模和调度研究 1 概论 1 1 工作流概述 工作流的概念起源于生产组织和办公自动化领域，提出的目的是通过将 工作分解成定义良好的任务、角色，按照预先正确定义的规则和过程来执行 这些任务并进行监控，以达到提高工作效率、降低生产成本、提高企业生产 经营管理水平和企业竞争力的目标。在网络技术和分布式数据库技术迅速发 展，多机协同曰益成熟的基础上，工作流技术于2 0 世纪8 0 年代中期发展起 来。工作流技术一出现马上就得到广泛的重视和研究，它为企业更好地实现 经营目标提供了先进的管理和支持手段。 现在，工作流管理技术已成功地运用到电子政务、医院、电信、银行等 行业，然而它更重要的应用还是在工业领域，特别是先进制造业领域，如柔 性制造和敏捷制造。 1 9 9 3 年8 月，工作流管理联盟w f m c ( 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 s ( w o r k f l o w m a n a g e m e n ts y s t e m ) 的一些标准化工作，标志着工作流技术进入了相对成 熟相对规范的阶段。目前该组织的成员已经超过了2 0 0 个，其中包括软件厂 商、科研机构与咨询机构，国内的东兰公司也是其中的一名成员。1 9 9 4 年 1 1 月2 9 日，工作流管理联盟发布了著名的工作流系统参考模型( w o r k f l o w r e f e r e n c em o d e l ) 【”，它详细描述了w f m s 的各个主要组成部分、各部分的 功能及相互之间的接口。 w f m c 在工作流相关术语【”、结构体系、应用程序接口( 4 1 、管理控制 接口【引、过程语言描述( 6 1 等方面制定了一系列标准和规范。这些工作在很大 程度上促进了工作流技术的发展和工作流管理系统在企业中的应用。 1 2 工作流多实例的研究内容 工作流活动的多实例是指多个参与者共同完成一个活动，活动多实例控 制是工作流进行任务分配时经常遇到的问题。 工作流活动多实例的建模和调度研究 在建模阶段，定义一个多实例活动来替代对多个活动进行建模，可以极 大地简化工作流程的定义，它可以从一个整体的角度去表示群体执行同样任 务的情况。但这种表示上的灵活性同时带来了工作流管理系统其他方面的复 杂性。工作流多实例对模型的解析、工作流执行中的调度分配、任务的结束 和资源共享等一系列问题提出了控制要求1 2 】。 1 3 工作流多实例的相关研究现状 工作流系统中，多实例并不是一个十分复杂的概念，相关的概念有循环 路由任务、多任务等。 文献“1 分柝了工作流中多个实例被触发的情况，指出可以从三个方面 来拓展工作流管理系统。这三个方面是从消息传递的角度来考虑的：分为同 步异步消息( s y n c h r o n o u sa n da s y n c h r o n o u sm e s s a g i n g ) 触发、终止多实例 流程( a b o r t so fr e l a t e de x e c u t i o np a t h s ) 和采用独占方式执行嵌套流程 ( e x c l u s i v ee x e c u t i o no f n e s t e dp r o c e s s e s ) 。通过这些手段来保证一个实例不 与其他实例产生访问资源冲突，以弥补现实中工作流管理系统的缺陷，适用 现实流程的复杂性。 文献【1 5 从实体一关系图的角度出发，为了处理实体之间的多对多关系， 提出了p r o c l e t 的概念，一个p r o c l e t 是一小段过程，多对多的关系可以通过 p r o c l e t s 之间的多次消息( p e r f o r m a t i v e ) 触发来生成活动的多个实例。p r o c l e t 来管理多个活动实例之间的消息传递和通信。 但是，文献【1 4 】和文献【1 5 】的多个实例触发机制实质上采用的是一种消息 触发下的循环控制技术和多线程技术，并不是严格意义上的工作流活动多实 例。这只是程序设计，或者说是工作流管理系统的设计和工程实现上的一个 技巧。从严格的意义来讲，这种方式不能做到一个活动的多个实例的同步。 因为它是先执行了一个活动实例之后，再触发或者晚是复制了一个或多个同 样的活动来循环执行或并行执行。这种设计方式得目的主要用于解决工作流 相互之间或工作流和外部程序之问的多次接口调用。 作为工作流领域的权威，v a nd e ra a l s tw m p 等在其著作w o r k f l o w p a t t e r n ) ) 中总结了近十年来工作流的发展成果【1 6 】，提出了：【作流中常见的模 工作流活动多实例的建模和调度研究 式，这本书作为工作流相关技术十多年的总结和沉积，对工作流后来的发展 和实用化起了相当大的推动作用，已成为本领域的经典著作。v a nd e ra a l s t w m p 在书中认识到了工作流多实例在现实建模中的重要性，首次提出了多 实例的名称( m u l t i p l ei n s t a n c e s ) ，并且第一次提出了多实例的分类。根据 多实例的自身性质，可分为四类： 不需要同步的多实例； 设计期可以预先确定的多实例： 运行期可以预先确定的多实例： 运行期无法预先确定的多实例； 但遗憾的是作者也仅仅进行了分类，并没有更深入的讨论多实例的相关 问题，也没有分析如何对多实例进行同步控制。 文献i ”i 在工作流建模中引入了多实例化的活动，将活动的多实例作为 一个要素加以了考虑，以允许一个活动的多个实例同时运行。在研究工作流 建模机制中，认识到多实例是一个重要考虑的因素，但没有讨论多实例的具 体表现形式，也没有提出相关的机制和算法。 相对于活动的多个实例，文献【”1 更关注于多个工作流的合并机制。在 协调理论和面向对象理论的指导下，从协调机制的角度研究工作流。通过将 相关活动过程从原有的工作流工程中分离出来，统一为标准形式进行协调。 从工作流程问的相互关系出发，强调了多个过程的活动之间时间顺序上的协 调，其着眼点在于多个不同工作流间的相关活动的协调，与本文讨论的多实 例的同步有相似之处，但两者解决的问题不同，其协同控制机制也不同。 作为国内最早研究工作流的著名学者和本领域的国内权威，史美林教授 和孙瑞志教授于2 0 0 5 年在他们的论文1 2 1 中，明确的提出了工作流多实例的 同步控制并对工作流多实例的同步控制进行了探讨。文献【1 2 】对工作流的多 实例的一些常见模型进行了列举，并提出了使用s h e l l 的方法来进行活动多 实例的同步控制。与i b m 的f l o w m a r k 所采用的b u n d l e 方式有一些类似。 但是创建多实例的方式和思想不同。前者根据用户的登录信息动态创建，而 f l o w m a r k 则创建活动的多个实例。文献【”j g , - 工作流多实例所涉及的其他问 题没有更深入的讨论。 工作流活动多实例的建模和调度研究 文献p 6 1 给出并分析了常见的多实例执行的p e t r i n e t 模型。 很多学者经过研究指出，当前建模方式大多数是基于x m l 的或者是基 于节点边的方法，如果不加以扩展，不能适用对工作流活动多实例的描述 和建模1 1 6 , 2 3 4 , 3 5 。 a d n e n eg u a b t n i 和f r a n c o i sc h a r o y 等在文献”1 中，利用动态更改的相 关思想 3 1 , 3 2 , 3 3 1 ，提出了使用基本的路由原语x o r s p l i t 、a n d j o i n 和 o r j o i n 等进行多实例的描述，f r a n c o i sc h a r o y 等在文献3 0 1 中，对这种简 单的建模方法进行了一些验证。这种建模方式简单但是不能反映多实例中和 组织视图有关的触发条件，比如当前活动完成后，按照活动参与者的部门进 行下一个活动的触发。而且，这种建模方式只能用于静态多实例，对动态多 实例是无法描述的。 在实际的产品中，部分工作流系统实现了对多个实例的支持，但也并不 是真正意义上的多实例。文献列举了工作流产品f o r t e ( f o r t es o f t w a r e ) 和v e r v e 等利用循环和并行分支实现了多实例，v i s u a lw o r k f l o ( f i l e n e t ) 和i - f l o w ( f u j i t s us o f t w a r e ) 用子流程的方式实现了多实例。i b m 的f l o w m a r k 采用b u n d l e 方式解决同步问题，即得到活动的实例化数目后，就由b u n d l e 来创建一定的实例数目。 1 4 本文的研究内容、目的及意义 本文的研究内容主要集中在与工作流活动多实例相关的以下几个方面： 1 首先对工作流模型进行了深入的分析： 2 提出并分析了工作流活动多实例和传统工作流的区别。提出了工作 流活动多实例的分类方法和在各种不同的工作流管理系统中的表 现形式： 3 ，分析了工作流活动多实例的执行模型，并提出了相关模型下的触发 方式；同时与传统意义的多个实例进行了区别对比； 4 分析并比较了常用的工作流建模方法，提出了活动多实例的建模方 法。 5 在分析了流程实例和活动实例的有限自动机的基础上，提出了活动 工作流活动多实例的建模和调度研究 多实例的实例池的概念和分组触发的思想； 6 提出了在分组技术下对活动多实例进行同步和调度的相关算法； 7 分别对静态多实例和动态多实例下的相关算法并进行了举例说明 和验证。 本文在总结他人的研究的基础上，提出了一种新的多实例的控制机制， 为真正的工作流活动多实例的实用化做出了有益的尝试和探讨。 1 5 论文的组织结构 本文的组织结构如下： 第一章分析总结了他人的相关研究成果，提出了本课题的研究意义； 第二章对工作流模型及接口进行了比较详细的介绍和分析： 第三章描述了工作流多实例的相关内容，第一次提出并分析了工作流活 动多实例和传统工作流的区别； 第四章提出了活动多实例的建模方法。本文选用了活动网络图，作为所 涉及的活动多实例的流程建模工具： 第五章提出了活动实例池和分组的定义和相关内容： 第六章提出了基于活动实例池和分组技术的活动多实例的调度算法，并 在静态多实例和动态多实例的条件下分别讨论了相关算法的实现； 第七章是本文的结论和未来所要研究的方向； 最后是本文的致谢语和参考文献。 工作流活动多实例的矬模和t | i ；| 度研究 2 工作流技术和工作流管理系统 为了理解工作流多实例的概念和内涵，以及为了讨论工作流多实例和通 常的工作流的区别，我们有必要先了解工作流技术和工作流管理系统的相关 概念。 特别要指出的是，工作流多实例很容易和通常意义下的些工作流概念 相混淆，有时候甚至会导致概念误解。 所以，本章将着重讲解一些工作流相关的基本概念，为下一章讨论工作 流多实例做准备。 2 1 工作流技术的相关概念 工作流技术的相关概念目前尚无统一、明确的定义，不同组织和产品都 有不同的描述，但其本质和基本特征是一致的，即一一工作流是业务过程的 模型【1 ，2 1 。它将现实中的业务逻辑和规则以合适的模型在计算机中进行表示 并对其实施计算。 在本文中，我们以工作流管理联盟的定义为标准。 下面给出与工作流相关的概念p 1 ： 工作流( w o r k f l o w ) ：是计算机支持的业务流程的全部或部分自动化。 在此流程中，文档信息或任务按照预定的规则，在工作流管理系统中流转， 实现组织成员间的协调工作，以达到业务的整体目标或是促使此目标的实 现。 工作流管理系统( w f m s ：w o r k f l o wm a n a g e m e n ts y s t e m ) ：能定义、 创建和管理工作流执行的软件系统。它将现实世界中的业务过程使用某种方 法或工具进行建模，转化成计算机所能识别的形式表示，即工作流逻辑，并 在此形式表示的驱动下完成工作流的执行和管理。使用w f l v i s 可以充分利 用各种资源，有效地跟踪业务过程，提高业务过程定制和执行的速度与质量。 业务流程( b u s i n e s sp r o c e s s ) ：指在现实环境中，能够实现业务目标和 策略的相互连接的过程和活动集。如公文处理流程，投保过程及项目开发过 程等。 工作流活动多实例的建模和调度研究 过程定义( p r o c e s sd e f i n i t i o n ) ：计算机所能识别的业务流程的形式化 描述，用来支持运行过程的自动化。流程一般被分解成一些子过程和活动， 其定义主要包括运行过程中涉及到的各种数据和参数，如过程的开始和终止 条件、各个工作环节( 活动) 及相互之间的控制流和数据流关系以及其它的 相关信息，如组织成员、应用和数据等。 过程实例( p r o c e s si n s t a n c e ) ：实际运行中的一个业务流程，即过程定 义的实例化。业务流程的每个实例均代表一个能独立控制执行、具有内部状 态的工作流执行实体。在过程实例的执行过程中，w f m s 负责解释相应的 流程定义来生成有关的活动实例，并根据定义中的控制规则协调这些活动之 间的顺序关系，同时根据数据流动关系的定义完成活动之间的数据传送。从 参与者的角度来说，实例的执行实际上是由参与者处理它所涉及的那个环节 的数据。完成该环节的任务之后由w f m s 根据相应结果激活后续环节，同 时通知后续参与者对之进行处理，由此依次反复直至整个过程完成。 活动( a c t i v i t y ) ：工作流中一个逻辑步骤或环节的工作任务，可分为 人工操作和自动处理两类。活动是流程执行中的基本工作单元，要求有人员 的参与或由计算机自动完成。 工作项列表( w o r k l i s t ) ：是一个参与者所负责的所有工作项的详细描 述。 工作流应用数据( w o r k f l o wa p p l i c a t i o nd a t a ) ：是指各个活动执行中 应用程序或参与者所处理的数据，如应用数据库中的记录、被处理的文档等。 工作流相关数据( w o r k f l o wr e l e v a n td a t a ) ：指系统主控部件运行服务 用来控制工作流实例的状态和执行的数据，相关数据在流程定义中一般为全 局变量，又可细分为控制数据和参考数据。 工作流模型( w o r k f l o wm o d e l ) ：工作流过程依赖于一个形式化的工作 流模型来描述工作流任务之间的控制流和数据流。工作流模型由4 部分组 成，它们分别是过程模型、组织模型、资源模型以及工作流相关数据。 过程模型用来定义工作流的过程逻辑，它包括组成工作流的所有活 动以及活动之间的依赖关系，它是整个工作流模型的基础与核心， 其它模型均为其提供支持。 工作流活动多实例的建模和训度研究 组织模型用来定义企业人员的组织结构，它包括几种不同形式的组 织元素以及每种组织元素内部的递阶层次关系。组织模型的主要任 务是为企业人员执行工作流过程提供柔性的组织定义，为过程模型 提供“人”的支持。 资源模型用来定义企业资源的组织结构，它包括几种形式的资源容 器元素以及容器内部的递阶层次关系，直至最终的原子级别资源个 体，资源模型的主要任务是为企业人员执行工作流提供“物”的支 持。 工作流相关数据用来定义工作流执行过程中需要用到的数据，它包 括简单的数据类型与复杂的企业对象。它主要用于各种条件的判 断，以实现工作流机对不同活动的选择性路由。工作流相关数据为 工作流的执行提供了“信息”的支持。 代理( a g e n t ) ：在工作流系统中，一个独立的执行实体被定义为代理。 它由所包含的个体、团队成员、工具及它们相应的职责所构成。在组织模型 中代理包括两种实体a c t o r 和g r o u p 。 a c t o r ：一个a c t o r 是个体处理单元，它可以是人员或和自动工具。 与a c t o r 相关联的有工作时间表、身体状况或故障等因素，这些因 素可以综合确定一个a c t o r 的当前状态。 g r o u p ：一个g r o u p 是a c t o r 的集合组成，其中a c t o r 的职能具有公 共的特征。 角色( r o l e ) ：角色标识代理在过程模型中对某项任务或相关任务集合 具有的访问权限和完成能力。角色用来指定代理的职责；代理是扮演一个或 多个角色的物理实体；角色表示的是责任的集合；角色的定义是在过程定义 中完成，而代理是在组织模型分析时才。定义。针对不同的工作流系统，同一 企业组织结构的划分可能不同，角色与代理实体的映射关系是由授权完成 的。在一个工作流中定义角色具有重要的意义，角色与代理分离保证了授权 的灵活性，使得在组织机构变化时，对工作任务的分配不会有影响，当一个 任务可以被一个以上的代理执行时，“角色一一授权一一代理”动态映射模 式有利于工作流管理系统的工作负载平衡。 工作流活动多实例的建模和调度研究 例如，假设医院某个诊疗流程有一个血常规检查的活动，这个活动的角 色是化验科血常规化验员，一个化验科可能有数个用户( 在化验科工作的医 护人员) 都可被授权这个角色。当一个化验员由于某种原因，如新手不熟练、 工作效率因各种原因降低或其它原因导致工作项积攒过多时，业务流程的某 个环节就会出现瓶颈，导致系统负载过高。此时，良好的工作流系统就可以 自动地将新的血清化验任务分配给另一个化验员，或将化验员角色再授权给 其他代理，进行系统分流，以实现负载平衡。 相关的概念的关系如图2 1 所示： 蔼三蠹。 出_ 由 图2 1 工作流相关概念的关系 2 2 工作流管理系统参考模型 w f m c 给出了一个工作流管理系统的参考模型如图2 2 所示，它确定了 工作流管理系统的各主要组成部分、各部分的功能及相互之间的应用编程接 口。这些接口是被工作流运行服务所支持的a p i 调用，处于工作流执行服务 的边界，用于和其它资源、代理以及应用进行交互。 工作流活动多实例的建模和调度研究 工作流定义工具建模阶段 1 r 接口1 u 运行阶段 工作流a p i 及交换格式 圈鹫 工作流执行服务 妾口4其他工作流执行服务 ，j 、 回 r 、 o = = = = = = = 兰j睡虱。亡= = = = = = 型 一p 皿一p 皿丽两西丽_ 固困序的交互功能 图2 - 2 工作流参考模型 w f m c 为工作流系统定义了5 类完整的工作流管理系统的接v i 描述： 接口1 【7 _ 引，工作流服务和工作流建模工具间接口，包括工作流模型 的解释和读写操作； 接口2 1 9 】0 】，工作流服务和客户应用之间的接1 5 ，这是最主要的接 口规范，它约定所有客户方应用与工作流服务之间的功能操作方 式； 接口3 1 4 1 ，工作流机和直接调用的应用程序之间的直接接口； 接口4 t 9 1 ，工作流管理系统之间的互操作接口； 接口5 1 ，工作流服务和工作流管理工具之间的接口。 i i x , j - 此模型作一个简要说明。 工作流执行服务：它包含一个或多个工作流引擎，解释过程定义的全部 或部分，并同外部的应用程序进行交互，来完成工作流过程实例的创建、执 行与管理一一如过程定义的解释、过程实例的控制、创建、激活、暂停、终 止等，调度各活动之间的路由、计算控制条件与传递数据等，并生成有关的 工作项通知代理进行处理等等，是工作流系统的运行基础。工作流执行服务 般是由个工作流引擎提供的，在大型w f m s 中工作流的运行控制可能 需要多个工作流引擎共同完成。这一点涉及到w f m s 系统之间的互连，为 实现有效的互连，需要定义互连模型、互连一致性级别及操作元素集，这些 o 工作流活动多实例的建模和调度研究 操作集合构成接口4 ( 互操作接口) 。 工作流引擎：工作流引擎负责根据工作流的语义，提供工作流的运行保 证，是整个w f m s 的中枢。引擎主要完成以下功能，解释工作流语义、根 据系统运行状态及产生的事件与工作流语义中定义的运行规则进行匹配，从 而控制活动的创建、激活、挂起及终止：管理群体工作人员信息及其权限， 分配项目给工作人员；提供工作人员到达及系统运行的轨迹与历史，维护工 作流控制数据与工作流相关数据，与应用或用户交换工作流相关数据，调用 执行外部应用等。 过程定义工具：对实际业务过程进行分析、建模的工具，并根据业务过 程生成可被计算机处理的形式化描述( 过程定义) ，这是建模阶段的主要内 容。过程定义工具与工作流执行服务之问的交互是通过接口1 ( 工作流过程 定义读写接口) 完成的，它为工作流过程定义信息的交换提供了标准的互 换格式及a p i 调用。 客户应用程序：给用户提供可与工作流执行服务交互的界面，以处理工 作流实例运行过程中需要人工干预的任务。每一个这样的任务被称作是一个 工作项，它包括处理上的一些要求，如处理时间的限制及待处理的数据对象 等。w f m s 为每个用户维护一个工作项列表，保存当前需要该用户处理的所 有工作项。客户与工作流执行服务之间的接口为接口2 ( 客户应用程序a p i ) ， w f m s 的各种服务如会话连接、过程控制、活动控制、过程状态、活动状态、 工作项列表的处理以及过程实例的管理等都可以通过此接口而得到。 被调的应用程序：指工作流执行服务在过程实例的运行中调用的、用以 对应数据进行处理的应用程序。在过程定义中包含有这种应用程序的详细信 息，如类型、地址等。接口3 提供一些标准的服务供应用代理使用，基于这 些服务也可以开发出一些专门的应用直接同工作流执行服务交互，关于这些 服务的语义及语法细节还有待更深入的研究。目前初步确定的服务大致可分 成会话建立活动管理( 双向的) ，以及数据处理等几类。 管理及监控工具：其功能是对w f m s 中过程实例的状态进行监控与管 理。如用户管理、角色管理、审计管理、资源管理( 包括过程管理及过程状 态控制等) 。它与工作流执行服务之间的交互是通过接口5 ( 管理及监控接 工作流活动多实例的建模和调度研究 口) 完成的，该接口规范详细描述了需要从过程执行服务所发生的各种事件 上捕获和记录的各种信息，如过程实例信息、活动实例信息、工作项信息及 远程操作信息等。 以上五个接口被统称为w o r k f l o w a p i ( w a p i ) ，这些标准的制定对于 实现不同厂家的产品之间的互操作( 如用一个厂家的管理与监控工具去管理 另外一厂家的工作流执行服务) 及基于工作流执行服务开发新的应用都具有 重要而深远的意义。 2 3 工作流执行路由关系 w f m c 确定了用来描述工作流的六个原语，包括s e q u e n c e ，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 。由这六个原语所组成的原语集是 完备的。用这些原语理论上可以对任何的流程进行建模。基本的执行路由关 系和原语集如下： 顺序( s e q u e n t i a l ) 路由：一个任务接着另一个任务被顺序的执行，任 务b 在任务a 已经完成之后执行的。示例参见图2 - 3 ( a ) 。 并发( p a r a l l e l ) 路由：任务a 和任务b 并发执行，即这两个任务可以 同时或以任意顺序执行。为了模仿并发路由，需要两个组成块a n d s p l i t 和 a n d j o i n 。a n d s p l i t 使任务a 和任务b 同步并发执行，而且只有在任务b 和任务c 都已经完成后，才能执行a n d j o i n 节点。示例参见图2 - 3 ( b ) 。 条件( c o n d i t i o n a l ) 路由：任务a 和任务b 互斥的被执行，为了表示 在两个或多个之间选择，使用两个组成块o r s p l i t 和o r j o i n ，o r s p l i t 使 得任务b 或任务c 之间选择其一进行执行，只要有其中一个任务执行完毕， o r j o i n 便可以执行。示例参见图2 - 3 ( c ) 。 循环( i t e r a t i o n ) 路由：有时需要执行卜任务多次，任务b 被执行一 次或多次。示例参见图2 - 3 ( d ) 。 ( a ) 顺序路由 工作流活动多实例的建模和调度研究 ( c ) 条件路由 ( d ) 循环路由 i l 。8 t i o “ 图2 - 3 工作流路由关系和原语集 2 4 工作流管理系统的分类 从所实现的业务过程和环境的不同，工作流系统大致可分为以下四类 【1 1 ： 管理型工作流：多属于结构化工作流，用于执行协同规则简单、可重复 和可预测的流程。它的执行步骤和规则是事先定义好的，不要求或较少要求 控制复杂流程和访问多个信息系统。例如，大学里的课程选修，完成论文后 的学位申请等。 设定型工作流：与管理型工作流相似，但一般用来处理异常或发生机会 比较小的情况，有时甚至是只出现一次的情况，这与参与的用户有关 协作型工作流：主要针对那些重复性不是很强或没有重复性的工作流， 这类流程主要由参与者的交互来驱动。由于事先无法定义后面的流程，而必 须推迟到过程实例运行时刊能确定，这类动态多变的特点在提供更高灵活性 的同时，也为利用现有工具为过程建模与控制执行带来更多的复杂性。 生产型工作流：实现重要的5 1 k 务过程的工作流特别是与业务组织的功 能直接相关的工作流。与管理型工作流相比，生产型工作流一般应用在大规 1 1 工作流活动多实例的建模和调度研究 模、复杂的和异构的环境下，整个过程会涉及许多人和不同的组织。 根据底层实现技术，可将工作流产品分为三类【1 】： 以通讯为中心：以电子邮件为底层的通讯机制。这种类型的工作流管理 系统适合于协作型工作流和不确定型工作流，而不适于生产型工作流。 以文档为中心：以文档路由为中心，它同外界应用的交互能力有限。许 多基于表的管理型工作流可以用以文档为中心的工作流实现。 以过程为中心：这种工作流系统对应生产型工作流。它们一般建立在数 据库之上，有自己专用的通信机制并且提供了同外部进行交互的接口 从不同工作流管理系统所采用的任务项传递机制的不同，工作流系统可 大致分为以下四类： 基于文件的工作流管理系统，以共享文件的方式来完成任务，这种类型 的产品是产生的最早、发展最成熟、最具多样性的。 基于消息的工作流管理系统，通过用户的电子邮件系统来传递文档信 息，这种类型的产品都已实现了与一种或多种电子邮件系统的集成。 基于w e b 的工作流管理系统，通过w w w 来实现任务的协作，这一类 产品起步较晚，但是发展迅速，已成为一种最新的市场流行趋势。许多供应 商纷纷开发新产品或者在原有产品的基础上增加对w e b 的支持。 群件与套件系统，依据划分标准，这一类产品与前面三种有很大程度的 重叠，但是在这里却有必要把它们单独划分成一类，因为这类产品都需要依 赖自己系统的应用基础结构，包括消息传递、目录服务、安全管理、数据库 与文档管理服务等，它们本身就构成了一个完整的应用开发环境。 工作流活动多实例的建模和调度研究 3 工作流活动多实例 下面将给出工作流及活动多实例的相关概念和内容，以及工作流活动多 实例的描述和分类。 定义工作流活动1 2 工作流活动n 是一个四元组n ，i d 是活动区分于其它活 动的一个唯一标识，u 是活动的参与者的集合，t 是活动属性的集合，v 是 属性的值域。 而活动实f f l j 就是活动定义 的实例化。称 一个活动n 是多实例的就是指在同一个过程实例中至少存在两个活动实例 n 1 和n 2 ( i d l i d 2 ) 具有相同的活 动定义 ，而且具有不同的工作流参与者。 活动多实例是在实际中经常遇到的问题，如：调查问卷，投票选举等。 在工作流管理系统中引入对活动多实例的支持，可以为现实环境中的业务流 程处理带来极大的灵活性和方便性。但是由于活动多实例本身的调度控制复 杂性，必须在工作流管理系统中引入一种控制机制，来支持工作流活动多实 例的调度和执行。 3 1 工作流活动多实例的描述 工作流活动多实例，是由一个工作流活动定义而产生的多个实例，它在 多个工作流参与者的参与下共同完成。 3 1 2 工作流活动多实例的分类 工作流活动多实例从其产生的方式来看，可以分为静态多实例和动态多 实例。 定义静态多实例s m ( s t a t icm u l t i p i ei n s t a n c e s ) 又称为设计期多实例( d e s ig nt i m em u l t i p l ei n s t a n c e s ) ，是指在设 计期就能够确定的多实例。这里的确定，是指在流程定义人员定义工作流程 工作流活动多实例的建模和训度研究 时，某个活动要产生的实例的数目、活动的参与者( 角色、资源和数据流等) 就已经确定了。流程定义人员在设计时便定义了一定相应数量的活动或者指 定了某个活动在运行时应该产生的实例数。 业务流程中经常出现的问卷调查通常就是静态多实例的典型代表。问卷 的发放数量在定义流程时就可以确定，这种情况只需要在设计流程时指定数 目就可以了。 定义动态多实例d m i ( d y n a m i cm u l t i p l ei n s t a n c e s ) 又称为运行期多实例( r u n t i m em u l t i p l ei n s t a n c e s ) ，是指在运行 期才能够确定的多实例。一般出现在流程定义人员定义工作流程时，无法确 定了某个活动要产生的实例的数目的情况下。多实例的数目要依据运行期的 一些信息才能确定。 这种情况一般是由于其它一些模糊性信息造成的。其主要原因有如下几 种： 活动参与者不明确； 活动间相互依赖，且所依赖的活动的执行不一定总是成功。并且当 所依赖的活动的执行失败后不会造成工作流事务的回滚； 活动间相互依赖，且所依赖的活动是动态多实例； 活动依赖与其它未确定的属性和外界条件，如时间不确定等。 3 1 3 活动多实例在不同类型的工作流系统中的表现形式 工作流活动多实例在不同类型的工作流系统中的表现形式是不一样的。 下面从工作流所面向的业务流程方面来分别讨论一下活动多实例在四种主 要的工作流管理系统中的表现形式： 管理型工作流：在这种类型的系统中，流程的协同规则简单，并且可重 复和可预测。既可以使用多实例，也可以在流程中定义多个活动。以静态多 实例的情况居多，很少出现动态多实例。 设定型工作流：此型工作流和管理型工作流类似，但是还要处理些随 机性的异常事件和特殊事件，因此偶尔会出现有动态多实例，但还是以静态 工作流活动多实例的建模和调度研究 多实例为多。 协作型工作流，主要针对那些重复性不是很强或没有重复性的流程，这 类流程主要由参与者的交互来驱动。由于事先无法定义后面的流程，而必须 推迟到过程实例运行时才能确定。由于这些特点，这种类型的工作流以动态 多实例为主。 生产型工作流：这种工作流中静态多实例和动态多实例的出现概率和具 体所涉及的特定领域的流程有关。如以产促销的企业的流程主要是以静态多 实例为主，像海尔，海信等，有固定的产品流程。而以销促产的企业则动态 多实例为多，像戴尔这种以定制直销为主要业务的企业。 3 2 工作流活动多实例的执行模型 假设某工作流的流程定义如图3 1 所示 ( 9 ( d ( 弓 图3 1 流程定义( 包含四个活动) 根据运行语义的不同，文献【1 2 】提出了几种典型的多实例运行模型 如图3 2 至图3 5 所示： 佃咂h 珀 图3 - 2 没有多实例时的运行模型 粗 剀3 3 活动b 具有2 个实例的执行模型 工作流活动多实例的建模和调度研究 图3 - 4 活动b 、c 是多实例，汇聚后触发 图3 - 5b 、c 的多实例各自形成子流程 以上几种执行模型经由不同的组合可以形成其它很多复杂的执行模型， 在此不一一列举。在此基础上，可以归纳出活动多实例的前后触发情况： o n e j o i n ：前序活动a 的某个实例a 完成，就触发活动a 的后继活动 b 的实例的执行。根据触发b 的实例个数，可以分为1 一l 触发和1 - n 触发两 种触发方式。 1 1 触发：当前活动的当前实例完成后，触发后继活动的一个实例进入 就绪状态，准备被工作流执行服务调度。 1 一n 触发：当前活动的当前实例完成后，触发后继活动的指定数量的实 例进入就绪状态，准备被工作流执行服务调度。 a