（计算机应用技术专业论文）工作流实例成批处理模式的挖掘算法研究.pdf

摘要 工作流是一类能够完全或部分自动执行的业务过程，活动是工作流中的一个 逻辑步骤或者环节。工作流活动的成批处理，是指通过将同一类型活动的多个工 作流活动实例进行合并处理，从而使原本多个活动实例的分别执行成组合并执行。 成批处理可以降低活动执行成本和提高活动执行效率，但现有的工作流系统几乎 没有考虑到成批处理的问题，也没有提供这一方面的支持。 尽管支持成批处理的工作流系统及成批处理的工作流模式己引起关注并开展 了探索性研究，但仍有很多工作需要进一步开展与完善。例如该系统在运行时需 要完成下列设定：1 ) 哪个哪些活动可进行成批处理；2 ) 哪个哪些活动处于同一 成批处理区；3 ) 成批处理区中活动的成批处理方式。但事实上，如同合理恰当地 定义工作流模型一样，上述设定工作在实践中如果完全只依赖工作流模型设计人 员完成，则不仅要求设计者具备大量的相关业务经验知识，而且容易受建模者主 观经验的影响，耗时且容易出错。 针对上述问题，本文提出了工作流实例成批处理模式的挖掘问题，并开展了 深入研究。本文的工作主要从两个方面展开：1 ) 对于现有工作流系统，研究怎样 利用其工作流日志识别可成批处理的工作流活动及其可能的成批处理方式，进而 识别出成批处理区；2 ) 对于支持成批处理工作流系统，研究怎样从其工作流日志 中挖掘出包含成组处理类型工作流活动的工作流模型及其相应的成组工作流子过 程。 论文的主要内容与贡献是：1 ) 描述了隐含在工作流过程中的可成批处理的工 作流活动，并定义了其成批处理特征：2 ) 提出了适用于现有工作流系统的工作流 活动成批处理特征识别算法及活动成批处理区识别算法；3 ) 定义了适用于支持成 批处理工作流系统的活动实例成批处理模式，并提出了相应的活动实例成批处理 模式挖掘算法；4 ) 进行了大量的仿真实验，且仿真实验证明，这些算法能较好的 解决不同工作流环境下的活动实例成批处理问题，有利于支持成批处理的工作流 系统的实际应用。 关键字：工作流；成批处理特征识别；成批处理模式挖掘：工作流挖掘 a b s t r a c t aw o r k f l o wi sap a r t i a lo rt o t a la u t o m a t i o no fab u s i n e s sp r o c e s s ，i nw h i c ha c o l l e c t i o no fa c t i v i t i e si sal o g i c a lu n i to rs t e po fw o r k b a t c hp r o c e s s i n gi nw o r k f l o w i st h ea c c o m p l i s h m e n to fs e v e r a lr e q u i r e m e n t si no n ea c t i o nb yc o m b i n i n gm u l t i p l e w o r k f l o wa c t i v i t yc a s e st o g e t h e r ，w h i l ei nt r a d i t i o n a la p p r o a c h e s ，t h e ya r eh a n d l e db y s e v e r a la c t i o n s b a t c hp r o c e s s i n go fa c t i v i t yc a s e sb a s e do nc e r t a i nr u l e sc a nu s u a l l y e c o n o m i z es y s t e mr e s o u r c e sa n di m p r o v et h es y s t e me f f i c i e n c y ，b u ti t i sa l m o s t n e g l e c t e db yc u r r e n tw o r k f l o wa n dv e r yl i t t l es u p p o r ti so f f e r e di nc u r r e n tw o r k f l o w s y s t e m s e x p l o r a t o r yr e s e a r c ho nt h ew o r k f l o wm a n a g e m e n ts y s t e m ss u p p o r t i n gd y n a m i c b a t c hp r o c e s s i n g ( d b p ) a n dd i f f e r e n td b pp a t t e r n si nw o r k f l o wh a sb e e nd o n ea n di t h a sd r a w nm a n yr e s e a r c h e r sa t t e n t i o n h o w e v e r t h e r ea r es t i l ls o m ep r o b l e m sn e e dt o b ei n v e s t i g a t e d t h ef o l l o w i n gt h r e ep r o b l e m sa r en o ts o l v e dy e t ：1 ) d e t e r m i n a t i o no f w h i c ha c t i v i t yd e s e r v e sb a t c hp r o c e s s i n g ( h e r e a f t e rb a t c h d e s e r v i n ga c t i v i t y ) ；2 ) i f i ti s ab a t c h d e s e r v i n ga c t i v i t y ，h o wt h em u l t i p l ec a s e so ft h ea c t i v i t ya r eb a t c h p r o c e s s e d ； a n d3 、) t h es e t t i n go ft h eb a t c hp r o c e s s i n ga r e a s ( b a t c hp r o c e s s i n gp a t t e r n s ) i nf a c t ，j u s t 1 i k et h ed e f i n i t i o no fw o r k f l o wm o d e l s ，t h em o d e l i n go fb a t c h d e s e r v i n ga c t i v i t ya s w e l la sb a t c hp r o c e s s i n ga r e ai sa l s oat i m e - c o n s u m i n ga n de r r o r p r o n et a s k t h e yc a n b ee a s i l yi n f l u e n c e db yt h ep e r c e p t i o no fb u s i n e s sp r o c e s sd e s i g n e r ( h e r e a f t e rd e s i g n e r ) m o r e o v e r ，d e s i g n e r sm a y n o tk n o we x a c t l yw h i c ha c t i v i t yd e s e r v e sb a t c hp r o c e s s i n ga t w o r k f l o wb u i l d i n gt i m es i n c et h e r ei sn or e a ld a t aa tt h a tt i m et og i v eu sc o n f i d e n c e e v e nm o r ed e s i g n e r sm a yi g n o r et h e s ek i n d so fb a t c hp r o c e s s i n gf e a t u r e sd u e t oc e r t a i n r e a s o n sa n dt h i sh a p p e n sv e r yo f t e n t oo p t i m i z eb u s i n e s sp r o c e s s e s ，t h e r e f o r e ，i tl s b a d l yi m p o r t a n tt oe x p l o r eaw a y t oi d e n t i f ya n dm o d e lb o t hb a t c h d e s e r v i n ga c t i v i t i e s a n db a t c hp r o c e s s i n ga r e a sa u t o m a t i c a l l y a i m i n ga ts o l v i n gt h ea b o v ep r o b l e m s ，t h i sp a p e rp r o p o s e sa n de x p l o r e st h e p r o b l e mo fm i n i n gb a t c hp r o c e s s i n gp a t t e r n s f r o mw o r k f l o wl o g s t h i sp a p e rh a s c a r r i e do nar e s e a r c hi n t oi tf r o mt h ef o l l o w i n gt w oa s p e c t s 。f i r s t ，i nc u r r e n tw o r k f l o w e n v i r o n m e n t d o e sr e s e a r c ho nt h ei d e n t i f i c a t i o no fb a t c h - d e s e r v i n ga c t i v i t i e sa n d t h e i r b a t c hp r o c e s s i n gf e a t u r e sa sw e l la sr e c o g n i t i o no fb a t c hp r o c e s s i n ga r e a si nw o r k f l o w s e c o n d ，i nw o r k f l o ws y s t e ms u p p o r t i n gw o r k f l o wa c t i v i t i e s b a t c hp r o c e s s i n g ，d o e s r e s e a r c ho nt h em i n i n go fw o r k f l o wm o d e l sw i t hb a t c hp r o c e s s i n ga c t i v i t i e sa n di t s r e s p o n d i n gs u b - p r o c e s s t h em a i nc o n t e n t sa n dc o n t r i b u t i o no ft h i sp a p e ri n c l u d e s ：1 ) d e s c r i b et h e b a t c h d e s e r v i n ga c t i v i t y i nw o r k f l o wa n dd e f i n ei t sb a t c hp r o c e s s i n gf e a t u r e s ；2 ) p r o p o s eaa l g o r i t h mf o ri d e n t i f i c a t i o no fa c t i v i t y b a t c hp r o c e s s i n gf e a t u r e sa n da a l g o r i t h mf o rr e c o g n i t i o no fb a t c hp r o c e s s i n ga r e a si nw o r k f l o w i nc u r r e n tw o r k f l o w e n v i r o n m e n t s ；3 、) m a k ead e f i n i t i o no fb a t c hp r o c e s s i n gp a t t e r ni nw o r k f l o ws y s t e m s u p p o r t i n gw o r k f l o wa c t i v i t i e s b a t c hp r o c e s s i n ga n dp r o p o s ear e s p o n d i n ga l g o r i t h m f o rm i n i n gw o r k f l o wa c t i v i t yc a s e s b a t c hp r o c e s s i n gp a t t e r n ；4 ) s e v e r a ls i m u l a t i v e e x p e r i m e n t sa r ed o n et ov e r i f ya l g o r i t h m s e f f e c t i v e n e s s t h ee x p e r i m e n t a l r e s u l t s h o w st h e s ea l g o r i t h m sc a ns o l v et h ep r o b l e m so fa c t i v i t yc a s e s b a t c hp r o c e s s i n gi n d i f f e r e n tw o r k f l o we n v i r o n m e n t sa n df a c i l i t a t et h ea p p l i c a t i o no fw o r k f l o ws y s t e m s u p p o r t i n gw o r k f l o wa c t i v i t i e s b a t c hp r o c e s s i n g k e yw o r d s ：w o r k f l o w ；b a t c hp r o c e s s i n gf e a t u r e sr e c o g n i t i o n ；b a t c hp r o c e s s i n g p a t t e r nm i n i n g ；w o r k f l o wm i n i n g 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写的成果作 品。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：，粤 日期：加捧 ，月夕p 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权湖南科技大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 怍若整铬。，灿 导师签名：州渤 日期：胪，年，月如日 日期：d g 年岁月弓0 日 湖南科技大学硕士学位论文 第一章绪论 1 1 课题背景及其意义 一在制造业信息化、电子商务以及现代服务业信息基础设施中，存在大量以过 程为核心的应用需求。业务流程描述了企业资源的使用方式，以自动化或者半自 动化方式来管理流程能够大幅度提高业务执行的工作效率，降低成本，使企业能 更快地适应不断变化的需求和业务的增长。起源于生产组织与办公自动化领域的 工作流技术为实现这一目标提供了先进的技术手段。该技术自2 0 世纪8 0 年代中 期出现以来就得到广泛关注并被大量应用于企业实际运作，也一直是研究的热点 之一。 工作流是一类能够完全或部分自动执行的业务过程，活动是工作流中的一个 逻辑步骤或者环节。工作流活动的成批处理，是指通过将同一类型活动的多个工 作流活动实例进行合并处理，从而使原本多个活动实例的分别执行成组合并执行。 成批处理可以降低活动执行成本和提高活动执行效率，而这一语义在实际应用中 也非常普通，并十分重要。例如，企业或政府集中采购业务就需要对伺一供应商 的不同采购申请活动合成一个集中采购活动，即将来自多个采购申请部门的多张 申请单合并到集中采购部门的一张采购订单来处理；物流优化配送中需要将若干 个客户的订单合并为一次运输单以节省运输费用。 在工作流的实际应用中还有很多这种需要在某个阶段对过程或活动实例进行 合并处理的情形。然而，现有的工作流系统几乎没有考虑到活动成批处理的问题， 也没有提供这一方面的支持。刘建勋教授对支持成批处理的工作流系统开展了探 索性研究( 详见文献 1 ，2 ) ，提出了可支持成批处理的工作流模型，分析了支持 成批处理的工作流执行服务系统设计与实现问题，并提供了基于事件驱动机制的 调度解决方案。虽然在文献 1 ，2 当中对成批处理的工作流模式进行了研究，但仍 有很多工作需要进一步开展与完善，例如该系统在运行时需要完成下列设定：1 ) 哪个哪些活动可进行成批处理；2 ) 哪个哪些活动处于同一成批处理区；3 ) 成批 处理区中活动的成批处理方式。 工作流挖掘( w o r k f l o wm i n i n g ) 是一种新的工作流建模方法，即从工作流过 程日志中自动挖掘得出工作流模型。在过去的十年中，国内外学者对工作流挖掘 问题做了大量的研究，一系列工作流模型的挖掘算法被提出。但是，由于传统的 工作流模型中并不支持活动的成批处理，现有的工作流挖掘算法均未考虑工作流 的成批处理特征识别问题。 第一章绪论 工作流挖掘技术的最大优点是克服了传统工作流建模方法中构建工作流模型 易受建模者主观经验的影响( 即模型的流程常常过于理想化，不能够反映复杂和 灵活的实际执行情况) 等弊端，而工作流挖掘所建立的模型基于实际执行后的数 据归纳，真实客观，同时建模效率也可以得到较大提高，并能为工作流模型的再 设计与优化提供参考。事实上，如同合理恰当地定义工作流模型一样，支持成批 处理的工作流系统中成批处理活动或活动集合的设定也并不容易。在实践中如果 完全依赖工作流模型建模人员进行设定，不仅要求建模者具备大量的相关业务经 验知识，并也容易受建模者主观经验的影响，耗时且容易出错。 鉴于这些原因，本文通过借鉴工作流挖掘技术及其思想，提出了工作流实例 成批处理模式的挖掘问题，尝试从工作流系统的执行日志中发现工作流活动成批 处理特征及工作流活动实例成批处理模式。这将有助于解决实际应用中的成批处 理活动的判定、成批处理区工作方式的判定、成批处理区的具体划分方法等问题， 对提高成批处理的工作流系统的实际应用价值具有十分重要的理论与现实意义。 1 2 课题的主要工作与创新 本文所做的主要工作有如下几点： 1 、描述了现有工作流系统环境下的隐含在工作流过程中的可成批处理的工作 流活动，并定义了其成批处理特征； 2 、提出了现有工作流系统环境下的工作流活动成批处理特征识别算法及活动 成批处理区识别算法； 3 、定义了适用于支持成批处理工作流系统的活动实例成批处理模式，并提出 了相应的活动实例成批处理模式挖掘算法； 4 、对算法的有效性进行了仿真实验测试，并对实验结果进行了分析。 1 3 论文的结构与组织 本文的组织结构如下： 第一章：绪论。主要阐述本课题的产生背景和研究意义，并给出本课题所做 的主要工作及本文的组织。 ，第二章：相关研究。着重介绍与工作流相关的一些理论及工作流挖掘技术的 研究现状，为后面的讨论做准备。 第三章：研究框架与问题描述。主要介绍本文的研究框架、研究的主要问题， 并说明工作流活动实例成批处理与支持成批处理工作流系统的概念。 第四章：工作流活动成批处理特征识别。主要讨论工作流活动成批处理特征 识别问题的解决方案。具体而言，描述并定义了工作流活动成批处理特征等，提 湖南科技大学硕士学位论文 出了现有工作流系统环境下的工作流活动成批处理特征识别算法及活动成批处理 区识别算法，并对算法进行了仿真实验验证。 ， 第五章：工作流活动实例成批处理模式挖掘。主要讨论工作流活动实例成批 处理模式挖掘问题的解决方案。具体而言，描述并定义了工作流活动实例成批处 理模式等，提出了支持成批处理工作流系统环境下的活动实例成批处理模式挖掘 算法，并通过仿真实验验证了算法的有效性。 第六章：结论与展望。对本文所做工作进行了简要回顾，并针对存在的不足 及未来的研究方向进行了简要展望。 本文的组织结构可用图1 1 描述如下： f i g 1 1o r g a n i z a t i o no ft h i sp a p e r 图1 1 论文结构图 湖南科技大学硕士学位论文 第二章相关研究 为了理解工作流活动成批处理的概念和内涵，以及为了讨论工作流活动成批 处理挖掘算法，我们有必要先了解与此相关的一些研究。因此，本章将着重介绍 与工作流相关的一些理论及工作流挖掘的概念和研究现状。 2 1 工作流技术简介 工作流技术起源于生产组织与办公自动化领域。1 9 9 3 年8 月，工作流管理联 盟( 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 ) 的成立标志着工作流技术开始进入 了相对成熟的阶段。w f m c 的主要职责是负责工作流及工作流管理系统( w o r k f l o w m a n a g e m e n ts y s t e m ，w f m s ) 的一些标准化工作。目前该组织的成员已经超过了 2 0 0 个，其中包括软件厂商、科研机构与咨询机构。1 9 9 4 年1 1 月2 9 日，w f m c 发布了著名的工作流参考模型( w o r k f l o wr e f e r e n c em o d e l ) ，它详细描述了w f m s 的各个主要组成部分、各部分的功能及相互之间的接口。这些标准的制定对于实 现不同厂家的产品之间的互操作及基于工作流执行服务开发新的应用都具有重要 而深远的影响。在过去的十年里，人们已经可以很容易的接触到工作流管理技术。 除了纯粹的工作流管理系统外，如s t a f f w a r e 、c o s a 、a c t i o n w o r k f l o w 等，许多 其它的软件系统也都使用了工作流技术。s a p 等企业资源计划( e n t e r p r is e r e s o u r c ep l a n n i n g ，e r p ) 系统、客户关系管理( c u s t o m e rr e l a t i o n s h i p m a n a g e m e n t ，c r m ) 系统、供应链管理( s u p p l yc h a i nm a n a g e m e n t ，s c m ) 系统、 企业间的电子商务( b u s i n e s st ob u s i n e s s ，b 2 b ) 应用等都嵌入使用了工作流技 术。 对工作流以及工作流管理系统，不同的研究者和工作流产品供应商给从不同 的角度给出了不同的定义，到目前为止，仍没有完全统一的定义。在本文中，我 们以工作流管理联盟的定义为标准，下面首先给出与工作流技术相关的概念。 2 1 1 工作流的相关概念 工作流( w o r k f l o w ) ：是一类能够完全或者部分自动执行的经营过程，它根 据一系列过程规则、文档、信息或任务能够在不同的执行者之间进行传递与执行。 工作流管理系统( w o r k f l o wm a n a g e m e n ts y s t e m ，w f m s ) ：是一个软件系 统，它完成工作流的定义和管理，并按照在计算机中预先定义好的工作流逻辑推 进工作流实例的执行。 业务流程( b u s i n e s sp r o c e s s ) ：指在现实环境中，能够实现业务目标和策略 第二章相关研究 的相互连接的过程和活动集。如公文处理流程，投保过程及项目开发过程等。 工作流模型( w o r k f l o wm o d e l ，也称为过程定义，即p r o c e s sd e f i n i t i o n ) ： 是计算机所能识别的业务流程的形式化描述，用来支持运行过程的自动化。过程 可分解成一些子过程和活动，其定义主要包括运行过程中涉及到的各种数据和参 数，如过程的开始和终止条件、各个工作环节( 活动) 及相互之间的控制流和数 据流关系以及其它的相关信息，如组织成员。应用和数据等。工作流模型由过程 模型、组织模型、资源模型以及工作流相关数据四部分组成。过程模型用来定义 工作流的过程逻辑，它包括组成工作流的所有活动以及活动间的依赖关系，它是 整个工作流模型的基础与核心。组织模型用来定义企业人员的组织结构，其主要 任务是为企业人员执行工作流过程提供柔性的组织定义。资源模型用来定义企业 资源的组织结构。而工作流相关数据用来定义工作流执行过程中需要用到的数据。 过程( p r o c e s s ) ：是业务流程的规范视图，由一系列为共同目标联接在一起 的协同的过程活动组成。 活动( a c t i v i t y ) ：是工作流中一个逻辑步骤或环节的工作任务，可分为人工 操作和自动处理两类。活动是过程执行中可被工作流机调度的最小工作单元。它 包含的信息包括：开始和结束条件；可参与到此环节中的用户；完成此活动所需 的应用程序或数据；以及关于此活动应如何完成的一些限制条件( 如时间上的限 制等) 。 过程，活动实例( p r o c e s s a c t i v i t yi n s t a n c e ) ：过程实例是某个工作流过程的 一次执行。在过程实例的执行过程中，w f l v i s 负责解释相应的流程定义来生成有 关的活动实例，并根据定义中的控制规则协调这些活动之间的顺序关系，同时根 据数据流动关系的定义完成活动之间的数据传送。从参与者的角度来说，过程实 例的执行实际上是由参与者处理它所涉及的那个环节的数据。完成该环节的任务 之后由w f m s 根据相应结果激活后续环节，同时通知后续参与者对之进行处理， 由此依次反复直至整个过程完成。每个活动实例代表一个活动的一次调用，只和 一个过程实例相关，并使用过程实例的数据。一个过程实例可能由若干活动实例 组成，但一个活动实例不能同时属于几个过程实例。一般情况下每一个活动实例 都将表现为一个工作项( w o r k l t e m ，它将由某个或某组用户负责完成) 。 参与者( p a r t i c i p a n t ) ：是部分或全部执行某个活动实例的资源( 注：资源 最根本的特征是它能够执行特定的任务) 。参与者包括实际完成某个活动的人或 设备，它把恰当的资源分配给某个可以开始的活动。每位参与者都必须具有属于 某个( 某些) 角色的属性。 工作项( w o r k l t e m ) ：是在一个过程实例中由工作流参与者进行的具体工作。 一个活动一般包含一个或几个工作项，这些工作项构成任务给工作流参与者完成。 6 湖南科技大学硕士学位论文 工作项通常是通过工作列表表达给用户。 工作项列表( w o r k l i s t ) ：是一个参与者所负责的所有工作项的详细描述。 代理( a g e n t ) ：在工作流系统中，一个独立的执行实体被定义为代理。 角色( r o l e ) ：角色标识代理在过程模型中对某项任务或相关任务集合具有 的访问权限和完成能力。角色用来指定指定代理的职责，它表示的是责任的集合， 而代理是扮演一个或多个角色的物理实体。针对不同的工作流系统，同一企业组 织结构的划分可能不同，危色与代理实体的映射关系由授权完成。 2 1 2 工作流管理系统的体系结构 随着对工作流产品需求的不断扩大，许多公司纷纷推出了不同的工作流产品。 这些工作流产品都有自己的特点，也有自己的协议和接口标准，它们在不同的应 用领域进行了应用。为了统一工作流技术研究和开发领域的相关工作，更好的支 持企业经营流程的建模、分析与实施，工作流管理联盟提出了有关工作流管理系 统的一些规范，定义了工作流管理系统的结构及其应用、管理工具和其他工作流 管理系统之间的应用编程接口。 雷 量擞 f i g 2 1a r c h i t e c t u r eo fw o r k f l o wm a n a g e m e n ts y s t e m 图2 1 - v 作流管理系统的体系结构图 图2 1 为工作流管理联盟提出的工作流参考模型的体系结构图。包括过程建模 第二章相关研究 工具、过程定义、工作流执行服务和工作流引擎、任务表和任务表管理器、工作 流控制数据j 工作流相关数据、应用程序和工作流应用数据等。图中所示的工作 流管理系统主要由三类构件组成：1 ) 软件构件：完成工作流管理系统不同组成部 分功能的实现；2 ) 系统控制数据：工作流管理系统中的一个或多个软件构件使用 的数据；3 ) 应用与应用数据：不是工作流管理系统的组成部分，而是属于外部系 统和数据，它们被工作流系统调用来完成整个和部分工作流管理的功能。 工作流管理系统可以用来定义与执行不同覆盖范围( 单个工作者、部门、全 企业、企业间) 、不同时间跨度( 分钟、小时、天、月) 的经营过程。这完全取 决于实际应用背景的需求。按照经营过程及组成活动的复杂程度的不同，工作流 管理系统还可以采取许多种实施方式。从较高的的层次来抽象考虑工作流管理系 统，所有的工作流管理系统都提供了以下三种功能： 1 ) 建立阶段功能：主要考虑工作流过程和相关活动的定义与建模功能； 2 ) 运行阶段的控制功能：在一定运行环境下，执行工作流过程，并完成每个 过程中活动的排序和调度功能； 3 ) 运行阶段的人机交互功能：实现各种活动执行过程中用户与i t 应用工具之 间的交互。 图2 1 给出了这三种功能之间的关系。其中，工作流管理系统建立阶段的功能 主要完成经营过程的计算机化的定义。在这个阶段，利用个或多个建模技术与 工具，完成实际的经营过程到计算机可处理的形式化定义的转化，所得到的定义 通常可称为过程模型、过程模板、过程元数据或过程定义。 在完成过程模型的定义后，所生成的工作流模型将工作流执行服务软件进行 实例创建并控制其执行过程。工作流执行服务对使用工作流模型描述的过程进行 初始化、调度和监控过程中每个活动的执行，在需要人工介入的场合完成计算机 应用软件与操作人员的交互。工作流执行服务可以包括一个或多个工作流引擎， 前者是一种集中式的实现方式，而后者是一种分布式的实现方式。分布式的实现 方式又可以分为同构和异构两种不同的情况。这种分布性要求客观上是由企业的 实际运行环境决定的，工作流管理系统可以采用不同的方法来满足企业应用对于 分布性的要求。工作流引擎是工作流管理系统的核心软件部件。它的主要功能有： 解释过程定义，控制过程实例( 创建、激活、挂起、终止等) ，按照过程定义已 确定的业务逻辑调用各项活动。为用户工作表添加工作项，维护工作流控制数据 和工作流相关数据，调用应用程序，提供监督，管理和审计功能。 2 1 3 工作流参考模型 工作流管理联盟提出的工作流参考模型从另一个角度说明了工作流系统的体 - 8 湖南科技大学硕士学位论文 系结构、应用接口及特性。其主要目的是为了实现工作流技术的标准化和开放性， 支持异构工作流管理系统与产品之间的互操作，并使其它的应用可以使用该结构 和定义好的通过a p i ( 应用编程接口) 访问不同的工作流管理系统提供的服务， 实现快速高效的集成。 如图2 2 所示，该模型定义了一些组件( c o m p o n e n t ) ，包括过程定义工具、 工作流管理工具、工作流机、工作流执行服务、工作流客户应用和工作流机直接 调用的应用以及这些组件之间相互通信的五类接口。这些接口是被工作流执行服 务所支持的a p i 调用，处于工作流执行服务的边界，用于和其它资源、代理以及 应用进行交互。 接 团 f i g 2 2w o r k f i o wr e f e r e n c em o d e l 图2 2 工作流参考模型 工作流参考模型中涉及到了如下三种数据： 1 ) 工作流控制数据( w o r k f l o wc o n t r o ld a t a ) ：工作流执行服务工作流引擎 通过内部的工作流控制数据来辨别每个过程或活动实例的状态。这些数 据由工作流执行服务i 作流引擎进行控制。用户、应用程序或其它的工 作流执行服务工作流引擎不能对其直接进行读写操作，它们可以通过向 工作流执行服务i 作流引擎发消息请求来获得工作流控制数据的内容。 2 ) 工作流相关数据( w o r k f l o wr e l e v a n td a t a ) ：工作流管理系统通过工作流 相关数据来确定过程实例状态转换的条件，并选择下一个将执行的活动。 这些数据可以被工作流应用程序访问并修改。因此，工作流管理软件需 要在活动实例之间传递工作流相关数据。 3 ) 工作流应用数据( w o r k f l o wr e l e v a n td a t a ) ：这种数据是指那些由应用程 第二章相关研究 序操作的数据。它们是针对应用程序的，是企业完成具体的业务功能所 需要的数据，如产品结构数据、定单数据、生产作业计划数据等。工作 流管理系统无法也不需要对它们进行访问。 2 1 4 工作流执行路由关系 工作流管理联盟确定了用来描述工作流的六个原语，包括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 ) 路由：最简单的路由形式是任务的顺序执行，即一个任务 接着另个任务被顺序的执行。通常在他们之间存在清晰的依赖关系，例如前一 个任务的结果是后一个任务的输入。 并行( p a r a l l e l ) 路由：如果两个任务能被同时或以任意顺序执行，称之为并 行路由。在这种情况下，两个任务都需要被执行，且互不影响。这两个任务开始 于a n d s p l i t 节点，随后重新同步于a n d j o i n 节点。a n d s p l i t 使两个任务同步并 发执行，而且只有在任务都已经完成后，才能执行a n d j o i n 节点。 条件( c o n d i t i o n a l ) 路由：也称为选择路由。当两个或更多任务之间存在选择 时，称之为选择路由。选择路由开始于o r s p l i t 节点，最后重汇合于o r 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 ) 路由：有时需要执行一个任务多次，例如一个任务被反复执 行，直到满足其后的“检查”任务结果为止，这种路由形式称之为循环( 或迭代) 路由。 2 2 工作流挖掘简介 2 2 1 工作流挖掘概念 工作流管理系统由预先建立的工作流模型所驱动，它最重要的功能之一就是 工作流建模。商业化的工作流管理系统，如s t a f f w a r e 、c o s a 、a c t i o n w o r k f l o w 等，都提供了一般的业务过程建模与执行功能。但是，工作流建模并不是一件容 易的事情，产业界的实践表明定义工作流模型非常耗时而且易错，在大部分的情 况下需要专家的参与。目前已有系统中建立时的过程定义与运行时的过程执行也 并不能完全相符合，而动态的修改过程定义与过程实例又将带来一系列的困难。 针对这一问题，“工作流挖掘”( w o r k f l o wm i n i n g ) 及类似的概念“过程挖掘 ( p r o c e s sm i n i n g ) 被提出，即从工作流过程日志中自动挖掘得出工作流模型。 工作流挖掘是一种新的工作流建模方法。为了比较它与传统的工作流模型建 1 0 湖南科技大学硕士学位论文 立方法的不同，考虑如图2 _ 3 所示的工作流生命周期模型其包括工作流设计、工 作流配置、工作流执行、工作流诊断四个阶段。设计阶段的主要任务是构建工作 流模型。配置阶段主要是根据设计好的工作流模型，在工作流管理系统中进行具 体配置，以使系统按照业务模型执行。在执行阶段工作流过程实例被系统执行； 同时，工作流系统还可以生成记录业务过程运转情况的系统日志。诊断阶段可以 为设计阶段提供输入从而使工作流生命周期成为一个循环的过程。从工作流生 命周期的角度看，传统的工作流建模方法主要集中于前两个阶段，通常由建模者 根据企业工作流程来定义模型；而工作流挖掘方法则主要针对后两个阶段通过 收集和分析系统在运行阶段的事务数据，自动的推导出能反映企业业务实际执行 过程的工作流模型，从而为工作流维护及工作流模型再设计提供参考。 w 0 m w d w 日 o w 口n 丑0 w c o n f n z m t m a f i g2 3w o r k f l o wh f e - c y c l e 图23 工作流生命屑期模型图 工作流挖掘的起点是收集工作流过程的执行信息，并假定能够得到符合下列 要求的事件记录：1 ) 每一个事件涉及一个任务，即一个工作的逻辑单元；2 ) 每 一个事件涉及一个实例，即一个工作流过程实例；3 ) 事件在时间上都是有序的。 这些事件记录一般都容易从工作流日志中得到，但是，对于较复杂的工作流模型， 工作流日志中并不能记录它的每一种可能执行路线，另外，实际的工作流日志中 往往是有噪声的，即部分记录不正确、不完整或者记录的仅仅是个例外。因此， 如何从业务记录中提取出符合实际的过程的工作流模型，是一件富有挑战性的工 作。 2 2 2 工作流挖掘算法 自a g r a w a l 与g u n o p u l o s 首次将过程挖掘的思想应用到工作流领域以柬，工 作流挖掘技术引起了国内外学者的广泛关注与研究，一系列工作流模型的挖掘算 法被提出。”。其中，较为典型并具有实际应用价值的有如下三个：1 ) a a l s t 等提 出的基于工作流网的n 算法m - ；2 ) h e r b s t 等提出的基于随机活动图的归纳式算法 ( i n w o l v e ) - - 1 ；3 ) s c h i m m 的基于块状结构模型的多阶段挖掘方法”。 a a l s t 等人的a 算法能够成功的处理一类与实际应用相关的工作流网 第二章相关研究 ( w f n e t ) ，并能构建出一个符合工作流日志行为要求的最简工作流网。工作流 网是一种对工作流的控制流维度建模的p e t r i 网，它定义了单个案例的动态行为。 任务通过变迁建模，因果关系使用库所和弧建模，库所对应着条件，能用做任务 的前条件和或后条件。仅算法的基础是由工作流日志导出的活动间的四种时序关 系： w 、- w 、拌w 与0 w 。其中 w 描述活动的顺序出现，专w 描述了活动间的因 果关系，撑w 与j w 用于区别并行与选择。寸w 、撑w 及j j w 都能由 w 关系导出，因此， 该算法仅要求工作流日志关于活动间的 w 关系是完整的，而不要求工作流日志中 包括所有可能的活动执行序列。该算法能够很好的处理不含短循环( 循环长度为l 或2 ) 的结构化工作流网( s w f n e t ) ，但对于包含短循环或非自由选择结构的工 作流网等，算法得出的模型在行为特性上与实际模型存在着差异。 0 t 算法在应用时要求过程中活动名是唯一的，即工作流模型中不允许有多个构 建块表示同一个任务。但这一要求与现实中的一些工作过程有冲突，h e r b s t 等人 提出的归纳式算法解决了这一问题。它主要有归纳与转换两个阶段，在归纳阶段 根据工作流日志生成一个随机活动图( s a g ) ，在转换阶段将它转换为由a d o n i s 定义语言( a d l ) 表示的块状结构工作流模型。此外，它也适合于解决一般的无 重复活动结点的工作流模型挖掘问题。但是，该算法在转换阶段并不能将所有的 s a g 都有效转化为等价的a d l 工作流模型，这影响了它的性能。尽管部分工作流 管理系统( 如m q s e r i e sw o r k f l o w ) 使用类似于s a g 的描述语言，但该算法在归 纳阶段产生的随机活动图是工作流模型的次优描述，并不能清晰的表示出活动的 并行行为。 s c h i m m 的多阶段挖掘方法则主要挖掘块状结构的工作流模型。与前两种方法 类似，该方法首先生成初始工作流模型，然后进行模型优化。不同的是，其初始 模型是面向块的元模型而不是面向图形的元模型，对初始模型的优化基于符号重 写规则而不是基于图形的相关技术。另外，它能挖掘出更准确的工作流模型，其 生成的工作流模型符合完备性、最小性及无冗余这三个要求。该方法也有一定的 局限性，例如，它没有解决多活动名问题，但这一点对实践影响不大，因为许多 工作流管理系统( 如m q s e r i e sw o r k f l o w ) 不会出现这一问题。此外，在应用该方 法时，需要对原始工作流日志文件进行有效的数据预处理。 2 2 3 工作流挖掘实