（计算机科学与技术专业论文）基于过程挖掘的柔性工作流系统研究.pdf

摘要 工作流技术，能有效地协调和组织跨部门的资源，提高企业的办 公效率和改进企业的经营管理模式，保证业务处理过程具有不可抵赖、 不可推脱、不可拖延、可限时、可监控、可考核、快速、在线、可追 溯、可协作等特性，给企业提供了规范化、自动化的办公平台。为了 适应市场的动态变化，业务流程需要不断变更和扩展，要求工作流管 理系统在流程实例执行的过程中支持实时修改模式，以快速响应需求 的变化。传统的工作流技术已经不能适应动态变化业务流程，柔性工 作流成为了工作流技术的变革的方向和研究热点。 为了提高工作流模式的正确性和可验证性，论文采用动态工作流 网从数学上形式化描述模式。针对模式的设计很难符合实际的业务流 程，提出了柔性工作流挖掘模型并设计了实现的算法。模型支持从零 日志开始，在实例执行过程中动态构建模式，并记录下模式每条分支 的执行频度，使得最常用的路径可见度最高，最接近企业的业务实际 流程。从而大大提高了柔性工作流建模的客观性和模式执行过程的灵 活性。模型和算法在实际应用中得到了很好的证明。 课题来源于中南大学与中国移动通信公司长沙分公司合作的项 目长沙移动流程自动化管理系统。工作流管理系统采用b s 结构， 模型设计和修改器采用具有丰富的图形界面的c s 结构。技术上采用 o r a c l e l o g 作为底层数据库，采用基于a s p n e t 平台的c 拌结合a j a x 实现。 关键词柔性工作流，动态工作流网，过程挖掘，形式化描述，使 用频度 a bs t r a c t w i t ht h ed e v e l o p m e n to f e n t e r p r i s ei n f o r m a t i o nr e v o l u t i o n ，w o r k f l o w a st h ek e yt e c h n o l o g yt o e n t e r p r i s ei n f o r m a t i o ns y s t e m ，h a sb e e n b e c o m i n ga ni m p o r t a n tb r a n c ho fc o m p u t e ra p p l i c a t i o nr e s e a r c h t om e e t t h ei n c r e a s i n gn e e d sf r o me n t e r p r i s e s ，p r o c e s sm o d e lm u s tb em o d i f i e d f r e q u e n t l yd u r i n gt h et i m ew h e nt h ew o r k f l o ws y s t e mi sr u n n i n g t h e t r a d i t i o n a lw o r k f l o wi sf a i l e dt om e e tt h i sn e e d h e n c e ，f l e x i b l ew o r k _ f l o w b e c o m e st h ef u t u r ew o r k f l o wm o d e la n dan e w h o t s p o t t oi m p r o v et h e v e r i f i a b i l i t yo fp r o c e s sm o d e l ，w eu s ed y n a m i c w o r k f l o wn e ta si t sf o r m a ld e s c r i p t i o nl a n g u a g e t on a r r o wt h eg a p b e t w e e nt h ep r o c e s sm o d e lm a n u a l l yd e s i g n e da n dt h ea c t u a l o n ei n e n t e r p r i s ep r o c e s s ，ap r o c e s sm i n i n gm o d e la n da l g o r i t h m so ff l e x i b l e w o r k f l o wi sp r o p o s e d i t sp r a c t i c a l i t yi sp r o v e db yt 1 1 eg i v e n e x a m p l e t h i sr e s e a r c hi sb a s e do nt h ew o r k f l o w m a n a g e m e n ts y s t e mp r o je c t f o rc h i n am o b i l eo fc h a n g s h a 1 1 1 ep o p u l a ra s p n e n a j a xt e c h n o l o g y , a n do r a c l e10 9d a t a b a s ea r eu s e dt oi m p l e m e n tt h i ss y s t e m k e yw o r d sf l e x i b l ew o r k f l o w , w o r k f l o w - n e t ，w o r k f l o w m i n i n g ， f o r m a ld e s c r i p t i o n ，u s ef r e q u e n c y h 硕士学位论文第一章绪论 第一章绪论 工作流管理系统因其具有广阔的市场前景，无论在应用还是科研领域都成为 了人们关注的焦点，如何提高系统对市场变化的动态适应能力和工作流模式的客 观性是目前的研究热点，为此一些新理论新技术被提出来，柔性工作流、过程挖 掘、工作流网是其中的典型代表。工作流模式，指的是描述工作流任务节点、路 径的模型，也称工作流过程模型或者工作流模型，以下简称模式。 1 1 课题的研究背景 工作流管理技术起源于8 0 年代初期的企业无纸化、自动化、计算机使能的 工作环境表单传递应用系统【l 】。随着计算机网络、数据库、信息系统等一系 列的计算机技术的发展，工作流管技术迅速发展成办公自动化领域一项新兴技术。 随着企业信息化建设的推进，工作流技术得到了越来越广泛的应用，如今已经变 成实现企业信息化的重要底层支撑技术和计算机应用技术的一个重要分支【2 】。 工作流是利用计算机技术实现业务流程的重组、管理与自动化的计算模型， 业务的参与者之间为了实现某一个目标，在计算机的环境下按照一定的规则互相 传递信息、文档和任务。工作流管理联盟给出了工作流概念的定义、参考模型和 接1 2 1e 4 1 。 目前，在企业的发展过程中业务过程不断地更新，需要在工作流实例执行过 程中支持动态变更模式1 5 j 。传统的刚性工作流管理系统只允许在设计阶段定义模 式，不支持在执行阶段修改工作流模式，刚性的过程描述限制了人们选择更熟悉 或更符合实际情况的操作方式，使得工作流管理系统缺少处理异常和支持过程变 更的能力，以及缺少对过程执行的人工干预和补救措施等。因此，工作流技术正 从刚性工作流向柔性工作流变革1 6 】。 1 2 课题的研究现状 1 2 1 工作流管理系统的研究现状 工作流技术的出现，使得企业在计算机技术支持下，实现业务过程建模、自 动执行、重组、并发异步、改变了企业低效率、繁琐复杂的运作方式，给信息系 统的开发带来新的模式，在工作框架下松散耦合了不同功能的应用系统 9 1 。国内 硕士学位论文第一章绪论 外学者对工作流技术做了一系列的研究， 前市场化的工作流管理系统的类型很多， 工作流系统。 ( 1 ) w e b s p h e r 6m q w o r k f l o w 并开发出了许多市场化的产品，由于目 无法逐一介绍，下面介绍几种比较典型 w e b s p h e r em qw o r k f l o w ( 原名：m q s e f i e sw o r k f l o w ) 是i b m 开发出来基于 w e b 服务的i b mw e b s p h e r e 和企业消息中间件i b mm q 软件平台的工作流产品， 该系统有如下几个特点：利用w e bs e r v i c e 技术与外部程序实现方便地松散耦合； 利用m q 的消息队列作为任务之间、应用程序之间的底层通信机制，保证任务能 友好协调、准确快速的运行；w e b s p h e r e 支持分布式的多处理引擎和多服务器， 适应企业的跨组织跨部门大型应用；强制性规定了任务的制定必须遵循i s 0 9 0 0 0 标准。采用m qw o r k _ f l o w 内部特有s d d s 和通用的x m l 作为互相传递的消息格 ；p 【1 0 ，1 2 】 , t - h o ( 2 ) e n h y d r as h a r k s h a r k 是l u t r i s 公司组织开发的一个开源工作流引擎。s h a r k 的特点是：采用 用j a v a 语言开发，具有很好的跨平台型，支持多服务器集群；采用松散耦合的模 块化设计思想，以服务器的控制台为微内核，在外部添加其他各个功能模块如： 包管理器、持久层服务器、日志管理器、流程库、过程实例运行模块、客户端等 同按照标准实现接口调用。这种模块化的结构使得系统很容易扩展和维护，也方 便集成其他应用【屹】。 ( 3 ) w i d e w i d e ( w o r k f l o wo ni n t e l l i g e n td i s tr i b u t e dd a t a b a s ee n v i r o n m e m ) ，是西班牙、 意大利和荷兰等国的五个单位协作开发的工作流管理系统。具有以下特点：是基 于分布式主动数据库技术工作流管理系统的典型代表；采用事件驱动的方法，根 据e c a 规则进行异常处理；分别用组织模型、信息模型和模式描述工作流模式 和工作流的基本要素、资源之间的相互关系旧。 ( 4 ) u l t i m a s u l t i m a sw o r k f l o w 是u l t i m a s 公司在1 9 9 4 使用n e t + w e bs e r v i c 实现的第 一套跨组织跨行业工作流管理系统。系统有以下特点：采用w e bs e r v i c e 技术， 对外部程序提供丰富的接口，与其他e r p 系统具有很好的互操作性；能有效的管 理企业的组织结构，全面整合企业的业务流程，提供比较完善的过程运行监控与 统计分析。支持一定的模式修改，因此具有一定的柔性。有一定的数据恢复与容 错能力。目前已经发展成为实现企业信息化建设的整套解决方案 1 8 , 1 9 。 ( 5 ) c o s a c o s a 是s o f t w a r el e y g m b h 开发的工作流管理系统，其体系结构非常近 w f m c 提出的参考模型。c o s a 的主要特点有：支持过程版本控制，过程重用 2 硕士学位论文第一章绪论 但不支持活动重用；支持动态性、能够在运行时修改模式；支持面向多服务器的 分布式结构，具有较好的开放性 2 0 l 。 1 2 2 目前工作流管理系统的缺陷 目前工作流管理系统存在着以下方面的问题 2 1 2 3 ( 1 ) 各具特色的工作流管理系统，缺乏公共遵循的参考标准。 ( 2 ) 目前的工作流系管理统缺乏可信、容错、稳定与安全的保障机制。工 作流系统作为企业的办公系统，很多意外情况需要检测与处理，要能给用户创造 一个可信的办公环境。 ( 3 ) 缺乏成熟、严谨的形式化理论支撑。工作流管理系统，作为信息系统 的新模式，模式的验证、任务处理与执行的因果、模式的描述与分析都急需完善 的数学理论。 ( 4 ) 缺乏完整、规范的柔性支持。大部分处于研究阶段，怎样实现方便快 捷的模式修改界面、保证模式修改的合法性、使得修改不影响工作流管理系统的 运行效率，是需要进一步研究的内容。 ( 5 ) 缺乏对工作流表单数据与模式之间联系的描述。目前工作流的任务推 进与节点控制方面基本上能够满足用户需要，但是在表单数据与模式的关联和表 单数据之间的关联方面的处理能力非常不足。 ( 6 ) 缺乏业务流程建模的客观性保证机制。如何提高设计出的工作流管理 系统的模式能符合企业实际的管理流程，或者说采用工作流挖掘技术从企业管理 模型的业务流程中挖掘出工作流模式是非常值得进一步研究的课题。 1 2 3 柔性工作流的研究现状 企业在发展、市场在变化、业务在不断地扩展，业务的处理流程也必须跟着 变更。因此工作流模式也不可能一成不变，要求在工作流管理系统运行的状态下 动态修改工作流模式。传统的工作流管理系统，在模式实例化以后就不允许再修 改，所以不很好地能动态适应企业和用户的实际需要。智能、方便、快捷、稳定 的柔性工作流系统成为研究热点和发展方向。对此国内外学者也做了大量的研究， 具有代表性的有如下： ( 1 ) 采用a g e n t 技术的柔性工作流系统 利用a g e n t 独立自治、可互相协作、强鲁棒性、对环境的动态适应性和移动 性来提高工作流的柔性。由于a g e n t 理论还处于研究阶段，该技术还不成熟，目 前在市场上还没有实际应用的商业化的产品【2 4 】。 ( 2 ) 基于e c a ( e v e n t c o n d i t i o n - a c t i o n ) 规则的柔性工作流系统 将变化的需求当作异常，用异常处理策略来实现柔性。然而频繁的异常处理 硕士学位论文第一章绪论 操作并不符合系统设计的范式，复杂的处理过程大大降低了系统的性能【2 5 捌。 ( 3 ) 基于本体驱动的柔性工作流系统 在信息不完整的情况下进行推断假设；在预定义的子过程或资源不可用的情 况下找出替代的过程或替代的资源；在实例执行完后对推断假设和替代选择进行 效果评估。这三项工作一定程度上实现了业务过程的柔性【2 7 1 。 ( 4 ) 商用的柔性工作流系统i n c o n c e r t 商用的柔性工作流系统中比较著名的是i n c o n c e r t ( t i b c os o f t w a r ei n c ) 它是 一种开放式的具有柔性的工作流产品，采用了面向对象的技术和c s 结构。可以 在分布式、多操作平台的异构网络环境下运行，支持“基于发现的工作流设计 。 首先它根据工作流任务的实际执行来创建模版；其次它支持类的继承，允许父工 作流过程定义的属性可以被它的子工作流继承。该系统能够实现不同企业工作流 管理系统的交互，但缺点是对于流程临时变更的处理能力不足。 1 2 4 目前柔性工作管理流系统的缺陷 目前柔性工作流系统尚处于理论研究阶段，还没有成熟的市场的产品，大多 数系统还不支持柔性。国内外学者对此做的理论研究中出现了一些成果，主要集 中在工作流模型的正确性分析、动态修改的实现策略、动态修改的实现方法、动 态修改的操作、动态修改可能会导致出现哪些问题、以及怎样解决其中的问题、 怎样更好地支持柔性工作流。总的来说还存在如下问题【2 9 ，2 3 】： ( 1 ) 缺乏对工作流模式严格的形式化描述与证明理论。模式的正确性证明 来源于它有一个正确性的描述，目前还没有统一的形式化描述语言； ( 2 ) 缺乏模式修改中正确性的保证方法。由于模式本来就是复杂而且容易 出错的，在执行过程中动态修改模式，直接操纵模式的定义，需要严格的正确性 检验； ( 3 ) 缺乏成熟的柔性工作流产品； ( 4 ) 缺乏提高修改的模式过程中，保证模式客观性的机制，如何找到最常 用，最切合实际情况的业务模式成为亟待解决的问题： ( 5 ) 缺乏对修改严格的控制，大量的修改，导致模式的不一致、不稳定； ( 6 ) 性能问题。通过异常处理这种方式去操作后台数据； ( 7 ) 临时变更功能不强。例如在i n c o n c e r t 系统中模式变更会中断i n c o n c e r t 基于工作流日志。 4 硕士学位论文 第一章绪论 1 3 课题的研究意义和内容 课题来源于中南大学与长沙移动公司合作的长沙移动流程自动化管理系 统，系统旨在建设成长沙移动公司内部的o a 办公平台，整合公司各部门的业 务流程，从中提取可以i t 化的部分，行成规范、标准、自动化的办公流程，提高 办公的效率，防止各个部门在业务处理过程中出现的任务延迟、处理抵赖、互相 推卸责任、敷衍了事、争执等问题。支持在工作流实例运行过程中添加和修改模 式，以动态适应公司的业务要求。采用工单处理数量和质量作为进企业管理与考 核的重要参考指标。从实际运行效果来看，系统已经通过湖南省软件评测中心测 试，在长沙移动公司得到了大规模的使用。主要特点如下： ( 1 ) 支持用户在工作流模式实例化以后( 即在工作流模式运行的过程中) 动态地构建和修改工作流网。以动态适应企业和任务处理用户的业务扩展和变更 需求。 ， ( 2 ) 采用动态工作流网来形式化描述工作流模式，提供了数学上的理论依 据，提高工作流模式的正确性和可验证性，减少模式在被修改后出现运行异常。 ( 3 ) 实现柔性工作流挖掘模型与算法，结合过程挖掘的技术可以大大提高 工作流模式的客观性。 ( 4 ) 按照不同的应用主题对模型库进行分类存储，用户可以根据不同的应 用主题和是使用频度需要选择不同的可见度，这样可以使得柔性建模过程中，减 少模式修改的混乱，增加用户的易用性。 工作流的生命周期包括工作流设计、工作流配置、工作流执行和工作流诊断 四个阶段。在工作流设计阶段，往往要求建模者充分了解企业流程的业务逻辑， 从中提取可以计算机化的部分并描述成可执行的业务流程模型。因此，建模的客 观性完全依赖于建模者的主观理解，使得工作流建模变成一个复杂的过程，而且 模型和企业实际的业务逻辑有很大的偏差。工作流过程挖掘( p r o c e s sm i n i n g ) 的 目标是：倒转过程，收集和利用已有信息系统的数据，从而支持工作流的设计和 分析【3 3 1 。从企业已有的信息系统提取与实际发生过的业务过程，增加了人工建模 的客观性。 系统采用柔性构建和挖掘技术结合，在工作流网的构建阶段，先设计一个通 用的工作流模式，允许用户在使用的过程中动态添加和修改模式，并记录下模式 每条路径的执行频率，使得模式从无到有建立起来。当流程管理员和用户需要提 取标准化、规范化的流程时，可以对模式库进行挖掘，按照应用主题和按执行频 率的要求，采用剪枝算法剪去不符合要求的路径、节点和规则，挖掘出不同概率 层次( 可见度) 的路径。 5 硕士学位论文第一章绪论 将过程挖掘和柔性工作流技术结合，有以下优点：( 1 ) 在模式实例运行过 程中支持动态修改工作流的模式，动态适应业务模型的变化和用户的新需求；( 2 ) 可以很方便地从模式库的众多的路径中看到大多数人走过的路径，挖掘出最符合 实际情况的模式；( 3 ) 通过归类和可见度限制可以方便用户使用流程，即普通的 用户只用关心最熟悉、最简单、最符合情况的路径和分支。 1 4 论文的组织结构 论文第一章介绍了柔性工作流系统的研究现状、产品和存在的缺陷。阐述了 本课题过程挖掘的思想，课题研究的意义。在第二章中将介绍实现模型和算法的 关键技术，以及课题中使用的动态工作流网。第三章将全面介绍论文的核心思想 与创新点动态挖掘模型与算法，阐述模型的思想与组成并设计了用算法实现， 给出算法的正确性分析。在第四章将介绍课题立足的项目长沙移动流程自动化 管理系统中柔性工作流系统的分析与设计。第五章介绍实现项目的主要功能模 块的实现技术，论文在最后的第六章的总结了模型和算法的优劣，并对下一步工 作提出了展望。 6 硕士学位论文 第二章柔性工作流管理系统及支撑技术介绍 第二章柔性工作流系统及支撑技术介绍 工作流管理联盟( w f m c ) 给出了工作流管理系统的体系结构和参考模型， 已经成研究者和为软件设计人员的参照标准。由于企业业务流程的不断更新，要 求在工作流执行的过程中，可以动态修改模式。如何提高工作流管理系统的柔性， 成为工作流领域的研究热点。 2 1 工作流的定义 工作流是利用计算机技术实现业务流程的重组、管理与自动化的计算模型。 在工作流计算模型中，业务人员在计算机管理环境下按照一定的规则互相协作、 互相传递信息、文档和任务，从而实现某一任务目标【l 】。 于1 9 9 3 年成立的工作流管理联盟( w o r k f l o wm a n a g e m e n t c o a l i t i o n ，w f m c ) 给出工作流的定义是：工作流是一类能够完全或者部分自 动执行的经营过程，它根据一系列过程规则，文档、信息或任务能够在不同的执 行者之间进行传递与执行例。 2 2 工作流的体系结构和参考模型 2 2 1 工作流管理系统体系结构 如图2 1 所示，工作流管理系统主要以下三中不同类型的组件构成，这三种 组件分别是： ( 1 ) 核心程序：实现系统不同组成部分的功能； ( 2 ) 系统控制数据：不同功能模块的程序需要使用的数据； ( 3 ) 应用数据：是外部应用的数据，不是系统主要组成部分，它们被调用来 扩展功能。 7 硕士学位论文 蔓三章柔性工作流管理系统及支撑技术介绍 图2 1 工作流参考模型体系结构 2 2 2 工作流管理系统参考模型 工作流管理联盟( w f m c ) 在1 9 9 4 年给出了工作流管理系统的参考模型，如 图2 2 所示。描述了工作流管理系统的各个组成模块的功能与接口，对他们的结构、 功能以及数据传递格式，做出了详细的规格说明。如图2 2 所示。己经成为设计该 类型软件的工业参考标准。 雷 硕士学位论文 第二章柔性工作流管理系统及支撑技术介绍 工作流管理工 具 接口5 l 过程定义工具 接 丁接口l| | 至匦四l 接口4 竺业 降 韭竺： i 作流机器直接 调用的应用程序 图2 2 工作流参考模型 其他工作流执行服务 各个模块的描述如下。 ( 1 ) 定义工具，通常是指使用流程设计工具，用来对流程的模式进行定义， 将逻辑业务过程转化为计算机能够识别的定义语言，能够让系统明白怎样去解释 说明这些语言所表达的意思。 ( 2 ) 工作流执行服务，它所完成的是工作流的核心工作，主要是对定义好的 业务流程进行解析和驱动，实现对流程的任务分解和节点活动判断，任务的分配 等等工作。 ( 3 ) 管理工具，主要是对流程实例的运行状态进行监控，对任务的执行情况 进行监督，及时发现运行过程中的错误和人员执行情况。 ( 4 ) 客户应用，主要是一些外部的应用程序，根据具体需要而实现的一些程 序应用，由具体使用的客户决定。 ( 5 ) 直接应用程序，是指由引擎直接调用的应用程序，用于完成引擎所需的 各项任务。 接口1 主要是完成对数据的传输和过滤，将数据解析过来后经过转变成为计 算机的形式化语言，接口2 也主要是完成对各项数据的传输和接口的调用，并对 数据进行相应的检测。接口3 主要是对一些接口设置提供帮助，完成数据的传输 工作。接口4 主要是实现外部监控系统对引擎的数据进行分析和判断，记录日志， 并及时发现情况和完成数据传递。接口5 主要是完成对数据的分析和判断，任务 的分配以及数据的传递工作。 9 硕士学位论文第二章柔性工作流管理系统及支撑技术介绍 2 3 工作流网 工作流网w f - n e t ( w o r k f l o w n e t ) 是a a l s t 在p e t r i 网的基础上定义的。w f - n e t 网作为一种从过程的角度出发描述和分析复杂系统的模拟工具，具有形式化的语 义定义、直观的图形表达和严格的数学基础等优点，很适合描述具有并发、异步、 分布和包含不确定性因素的复杂系统。因此基于w f n e t 的工作流建模越来越广泛 应用于流程的业务模型描述中。 一个p e t r i 网p n = ( p ，t ，用其中： ( 1 ) 尸是有限个库所的集合。 ( 2 ) 琨有限个变迁的集合且p n t = 西。 ( 3 ) 腿弧的集合( 尸r ) u ( 丁尸) 。 p n 称为工作流网，当且仅当它满足下面的两个条件： ( 1 ) p n 的两个特殊库所：f 和o 。库所f 是一个起始库所，没有前驱节点， 即：f = o 。库所o 是一个终止库所，没有后继结点，即：o = o 。工作流网必 须有一个起始节点和一个终止节点；( 2 ) 如果在p n 中加入一个新的变迁f ，使 f 连接库所o 与f ，即户 d ) ，= f ，这时所得到的p n 是强连接的。工作流网中没 有孤立状态节点，即所有节点都必须在起始节点和终止节点的通路上【3 6 1 。 采用工作流网形式化描述工作流模式，提供数学基础的理论证明，提高了模 式的可验证性。w f n e t 中，用变迁表示工作流的处理节点即任务，用库所表示工 作流中的分支条件。当输入库所有托肯值：表示变迁从等待状态转变成就绪状态 的条件满足。输出库所为变迁的执行结果，产生一个托肯到输出库所中去。在选 择、并发、同步等结构中要借助同步器实现。工作流网有如下3 种结构： ( 1 ) 顺序结构( s e q u e n c e ) 如图2 3 所示，变迁( 任务t ) 的执行条件是：它的输入库所尸j 里面有托肯， 变迁刀的执行后果是：它的输入库所彤有托肯。 图2 3s e q u e n c e ( 2 ) 选择结构 选择结构比顺序结构要复杂很多，分为如下几种情况： 与分支( a n ds p l i t ) 如图2 4 所示，任务t 1 而成为下一步任务的条件是：条件p j 等待的数条件 1 0 硕士学位论文 第二章柔性工作流管理系统及支撑技术介绍 已经满足：即p j 有托肯( p 1 = t r u e ) 。t 的执行函数是：p 2 & & p 3 ，同时生产两 个条件，即同时使得两个彤和丹里面托肯，也就是丌执行完后，并发执行地 后继的两条路径。 忍 42 4a n d _ s p l i t 或分支( o r _ s p l i t ) 如图2 5 所示，任务刀就绪的条件是：p l = t r u e ，t 的执行函数是：即f i p 3 ， 产生一个托肯到用或者p 3 中去，使得p 2 = t m e 或者p 3 = t r u e ，也就是丌执行完 后，选择后继的路径之一执行。 丑 图2 5o rs p l i t 与合并( a n d _ j i o n ) 如图2 6 ，变迁刀变成就绪状态的条件是：p l & & p 2 = t r u e ，即尸j 和丹要同 时有托肯，刀的执行函数是：p 3 = t r u e ，执行完后，直接执行后继的路径。 4 2 6 a n dj i o n 或合并( o r j i o n ) 如图2 7 ，变迁丌变成就绪状态的条件是：p 川尸2 r n l e ，力的执行函数是： p 3 = t r u e ，处理完后直接执行其后继的路径。 硕士学位论文第二章柔性工作流管理系统及支撑技术介绍 k t 1 图2 7o r _ j i o n ( 3 ) 循环结构( r e p e a t ) 如图2 8 ，变迁力变成就绪状态的条件是：尸川即= t m e ，执行函数是： 尸3 l i 丹= 1 m e ，选择p = - t r u e 就进入循环，否则跳出循环。刀既是”的输出库所又 是t 1 的输入库所。 2 4 工作流挖掘 j - - ：l t 1 4 2 8r e p e a t 在工作流设计阶段，建模者根据对企业流程的业务逻辑的理解，从中提取可 以计算机化的部分并描述成可执行的业务流程模型。因此，建模的客观性完全依 赖于建模者的主观理解，使得工作流建模变成一个复杂的过程，而且结果往往与 企业实际的业务逻辑有很大的偏差。 工作流挖掘( 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 ) 或工 作流模式挖掘( w o r k f l o ws c h e m a sm i n i n g ) ，它的目标是：倒转过程，收集和利 用已有信息系统的数据，从而支持工作流的设计和分析。工作流挖掘是为了增加 人工建模的客观性，从企业已有的信息系统提取实际发生过的业务过程【9 】。 系统中集成过程挖掘的技术，可以大大提高工作流建模的客观性。使得模式 符合企业实际的业务。 1 2 硕士学位论文第二章柔性工作流管理系统及支撑技术介绍 2 5 柔性工作流 企业用户使用工作流系统办公的过程中需要新添路径，出现了在设计阶段工 作流实例的模式不能满足用户的应用的需求；也可能有有由于意外事件，如设计 阶段出现没有考虑到的情况，在运行阶段模式中的某个活动的误操作，这个两种 情况都需要系统支持用户调用流程设计器或者修改器动态修改模式，并且上传到 模式库中，实时反映到运行的工作流实例中。 2 6 本章小结 本章介绍了工作流的基本概念、体系结构和模型。进一步分析了论文即将使 用的工作流形式化描述语言，工作流网。介绍了工作流挖掘技术和柔性工作流系 统。 1 3 硕士学位论文第三章柔性工作流挖掘模型及算法研究 第三章柔性工作流挖掘模型及算法研究 3 1 模型构建的依据 在工作流设计阶段，用户很难把握企业的实际业务流程，以往企业都要花大 量的资金请咨询公司设计各中业务的流程规范，但是设计出来的规范也很难符合 企业的实际情况。工作流过程挖掘技术就是为了解决这一问题而出现。 在工作流执行的过程中企业的业务过程需要修改是在所难免的，。所以很难在 工作流设计阶段设计出完美的流程，支持模式动态修改的柔性工作流系统就应运 而生。 论文设计构建模型的基本思想是基于使用次数的，即路径被使用的次数越高 说明路径越符合企业的实际情况，可以引用鲁迅的一句话：“地上本没有路，走的 人多了就变成了路 。模型的优点如下： ( 1 ) 采用的动态工作流网作为模式的形式化描述，从而提高工作流模式的正 确性和可验证性； ( 2 ) 在构建阶段，支持柔性修改模式，提高了模式对企业业务流程变化的动 态适应能力； ( 3 ) 结合过程挖掘，大大提高了建模的客观性； ( 4 ) 在执行过程汇总，直接将执行概率记录在模式中，挖掘时只需动模式库 挖掘，不需要遍历整个日志数据库，从而大大提高了挖掘的性能； ( 5 ) 用户可以根据不同的概率和不同的应用主题，挖掘出不同可见度的标准 化流程。 3 1 1 通用流程构建阶段 在未知企业需求的情况，按照不同的应用主题建立通用的流程，用户可以按 照需求任意添加和修改路径，具体思想如下： ( 1 ) 建立通用的工作流模式，该模式有极大的柔性，在执行过程中用户可以 按照意愿任意添加和修改路径； ( 2 ) 按照不同应用主题将模式库中的模式分类； ( 3 ) 在执行过程中记录下每一种应用主题的每一路径的执行概率。 1 4 硕士学位论文第三章柔性工作流挖掘模型及算法研究 3 1 2 标准化流程提取阶段 在通用流程运行了一段时间后，可以按照不同应用主题和不同的概率要求， 。提取标准化的流程模式。具体描述如下： ( 1 ) 输入应用主题和可见度( 概率) ； ( 2 ) 遍历通用流程模型库，筛选出满足该概率的弧； ( 3 ) 通过剪枝算法剪掉孤立的节点； ( 4 ) 去掉规则集中不存在的节点和规则表达式。 3 2 柔性工作流挖掘模型的形式化描述 为了适应动态工作流挖掘的要求，本文采用动态工作流网d w f n e t ( d y n a m i c w f n e t ) 来形式化描述工作流模式。 定义3 1 动态工作流网d w f n e t = s ，e ，d t ，钟，几，其中s 为源库所， 即开始节点，e 为汇集库所，即结束节点，d t 为动态变迁集，御为动态库所集， ，为连接d t 和d p 之间的弧。 定义3 2 动态变迁集d t ，表示工作流过程中的任务节点，动态变迁用矩形 表示。动态变迁具有一个三元组属性( s t a t e ，d t e n t r y 0 ，d t _ b o d y 0 ) 。 ( 1 ) s t a t e ，变迁的状态，s t a t e = 就绪，等待，完成 。 ( 2 ) d r _ e n t r y 0 ，变迁的入口函数，规定了变迁就绪的条件：d p 一 卿的布 尔表达式) 。例如变迁出的入口函数c ：c o d ( c ) = 缸lx d 尸x 出 ， d o m ( c ) = t r u e ，f a l s e ，其中c o d ( c ) 表示c 的定义域，d o m ( c ) 表示c 的值域。当 c - - t r u e 时变迁西转换为就绪状态，c = f a l s e 时西变迁为等待状态。 ( 3 ) d r _ b o d y 0 ，变迁执行函数，规定了变迁毋发生后如何将托肯输出到后 继库所集中：d p 一 控制变量赋值语句) 。例如变迁办的执行函数r ： c o d ( r ) = xix d p ，x d t ) ，d o m ( r ) = t u r e ，f a l s e 。 定义3 3 动态库所集凹，表示变迁被激活或者变迁执行的条件集。动态库所 用圆圈表示。根据出现在变迁的前与后分别分为输入库所和输出库所。 定义3 4 连接库所和变迁的弧f ：d o m ( f ) uc o d ( f ) = d tud p d o m ( f ) = xi3 y ：( x ，y ) f ) c o d ( f ) = yi = i x ：( 工，y ) ，) ，的属性是个四元组： 肛t ，d p ，d ，矿) ，其中d t 是弧连接的变迁，d p 是弧连接的库所， d 是弧的方向，d = i n ，o u t ，i n 表示弧的方向是从库所指向变迁，当前库所作 为输入库所，o u t 表明弧的方向是从变迁指向库所，当前库所是作为输出库所。 硕士学位论文第三章柔性工作流挖掘模型及算法研究 形为弧的权重，也就是该分支被执行的次数，作为弧的置信度。 3 3 模型构建与算法描述 如图3 1 所示，模型的主要组成部分是工作流模式库和动态修改接口，分别 描述了模型的静态结构和动态行为。 3 3 1 模型的静态结构 模式库中存储所有按主题分类的动态工作流网，模式库的组成包括： ( 1 ) 动态变迁集( d r ) ，存储已创建的变迁集。在动态构建的过程中约定： 变迁一定要可达，即每个变迁一定要有输入库所。变迁表示工作流实例中的任务 或者活动。 ( 2 ) 动态库所集( 钟) ，存储已创建的库所集，库所表示工作流实例中的任 务发生条件和任务发生后的结果。为了保证构建的连续性，在动态构建的过程中 约定：每个非结束库所必须有后继变迁。 ( 3 ) 动态规则集( 伽) ，存储各个变迁的入口函数和执行函数。 ( 4 ) 动态弧集( 胛) ，存储变迁和库所之间的连接，和被执行的次数，作为 挖掘时的置信依据。 ( 5 ) 角色集( r ) ，存储工作流参与者的抽象，与变迁存在一对多的映射关 系，与参与者之间也存在一对多的映射关系。 ( 6 ) 参与者集( u ) ，是角色的实例，是变迁的执行者和模型动态构件者。 模式库 工作 流引 擎 洲幢 动 态 变 迁 集 ! 型医 圄1 喜 输入k 一j 警l 医磊器k 修改模式 骓| | i | 8 1 3 1 动态挖掘模型结构图 1 6 新 建 弧 硕士学位论文第三章柔性工作流挖掘模型及算法研究 3 3 2 模型的动态行为 模型的动态行为分为两个阶段，即工作流模式动态构建阶段和动态挖掘阶段。 在的动态构建阶段，按照柔性工作流的要求，支持用户在流程执行过程中能 动态构建和修改变迁、库所、规则和角色，详见算法3 1 ，在此阶段中有如下操作： ( 1 ) 新增变迁a d d t ( ：d t = d tu 西) 。 ( 2 ) 新增库所a d d _ p ( d p ) ：d p = d pu d p ) 。 ( 3 ) 新增弧a d d f ( j 9 ：f = fu 厂) ，其中： 厂- 触，d p ，d ，叫，d t 为现有变迁集中的某一变迁，咖为现有库所集的某一 库所，d 弧的方向，w 为该弧的权重，初始值为0 。 ( 4 ) 添加规则a d d _ r ( d r ) d r = d ru d r ，d r 包括两种类型：变迁西的 入口函数d te n t r y o ，变迁西的执行函数d t _ b o d y o 。 ( 5 ) 执行变迁的执行函数d t _ b o d y o ：产生托肯到出的输出库所集p 中，其 中：p d p p = d t psd o m ( d t b o a y 0 ) ，同时增加托肯流过弧的权重，将 这些弧的置信权重加l ，即f 阶+ 。 ( 6 ) 触发就绪变迁a c t i v a t e o ：搜索变迁集，执行变迁的入口函数d t ，entry0 将d te n t r y o = = t u r e 的变迁的s t a t e 设置为就绪状态。 在挖掘阶段，即工作流模式的提取和标准化阶段，根据输入的主题的和置信 粒度，输出完整的工作流网。具体算法见算法3 2 。 3 3 3 算法描述 模式的一个执行实例，就是一个工作任务单( 以下简称工单) 从工作流网开始 节点到结束节点的一次流转。每一个工单的当前步骤处理者，可以根据需要采取 相应的动态构建模式的行为。 在柔性构建阶段，先建立通用的工作流模式，初始时只有开始节点和结束节 点，其他的节点、路径和规则由终端用户动态添加和指定，具体详细步骤见算法 3 1 。 1 7 硕士学位论文 第三章柔性工作流挖掘模型及算法研究 算法3 1 柔性构建工作流网算法 输入：工单主题正叻e a m ，工单号血o ，当前变迁d t _ c ，可信粒度艿。 输出：下一变迁。 s t e p l 判断d t c 是否为第一步变迁( 即i f ( 毋c = 书) ) ，如果是则转算法3 2 ， 否则转s t e p 2 ： s t e p 2 搜寻模式库中的弧集凡查找d t c 的可信输出库所集d p j ，其中： v p 冬d p j ：p = d t c b f ( d t ，d p ，d ，矽) ：f d t = d t c f d p = p f d = o u t 八 w 碡6 即：输出库所p _ o u td 卯j 与d te 构成的弧厂( d t , d p ，d ，w ) 中f d t = d tc ， f d p = p _ o u t ，说明弧变迁端为d tc 库所端为p _ o u t ：f d = o u t ，表明po u t 为d t c 的输出库所：，胗= 万，表明弧的置信权重必须大于等于艿； s t e p 3 用户判断d p j 是否能满足要求，如果能则转s t e p 4 ，否则转s t e p 5 ： s t e p 4 执行变迁d tc ： l 、调用d t c 的函数体d r _ b o d y 0 ，产生托肯到d p j ； 2 、增1 j 1 f 的可信度，阶+ ； 3 、调用a c t i v a t e 0 触发所有满足条件的变迁为就绪状态； s t e p 5 添加当前变迁d tc 的输出库所： l 、查找d p ，如果有合适的咖f 就继续，否则就转s t e p 7 。 2 、在弧集f 中添加弧月a l l ，d p _ i ，o u t ，d 夕； 3 、添加d t i 执行后果规则a d d _ r ( d r ) ，在规则库中添加d t _ b o d y 0 ，添加d t c 产生托肯到咖f 的赋值语句； s t e p 6 工作流引擎查找出下一变迁集d t i ，用户判断d t i 是否满足的要求， 如果是，转s t e p 9 ，否则转s t e p 8 ； s t e p 7 新增库所a d d _ p ( a p ) d p = 卿u 勿 ，查询d t 是否有适合作为勿 的后继和前驱变迁，如果有则添加该库所的后继和前驱变迁。否则执行s t e p 8 ； s t e p 8 新增变迁西： ， l 、遍历d p ，查找是否有满足的建立该变迁的输入库所和输入出库所，如果 是则继续，否则转s t e p 7 ； 2 、添加弧，其f o r = a t j ，n p = 勿f ，f d = o u t ； 3 、新增d tj 的入口函数d t e n t r y ( ) 和体函数d t _ b o d y 0 ： s t e p 9 结束。 1 8 硕士学位论文第三章柔性工作流挖掘模型及算法研究 当通用流程运行了很长一段时间后，模型库存储了大量不同主题的工作流网， 工作流网路径中的频度属性，记录下了该路径执行的概率。这些工作流网有两大 类用途： ( 1 ) 企业管理者可以从中提取标准化的工作流模式，按照概率排序，可以挖 掘出最贴近业务实际的模型。 ( 2 ) 终端用户在发工单时，可以选择不同的概率，系统给他展现不同概率下 的工作流网。使得普通用户不必去关心与之无关的路径。大大提高了工作流系统 的易用性。 这个阶段叫模式的挖掘阶段，即从通用流程的模式中，按照不同的主题和概 率要求，减去不符合条件的分支与规则，挖掘出满足用户的要求工作流网。详见 算法3 2 。 算法3 2 根据输入主题和可信粒度输出当前的工作流网算法 输入：工单主题，可信粒度万。 输出：工作流网。 s t e p l 搜索模式库，找到匹配输入主题的工作流网w fn e ti ，如果没有找 至0 至0 则转s t e p 2 ，否贝0 转s t e p 3 ； s t e p 2 初始化工作流网d w f n e t = s ，日； s t e p 3 遍历工作流网，剪掉所有可信度小于输入可信度的分支弧，如果 f c ； s t e p 6 遍历规则集合，去掉所有包含被去掉库所的逻辑条件； s t e p 7 重复s t e p 4 s t e p 6 ，直到所有库所和变迁都