（计算机软件与理论专业论文）时态工作流建模、分析和挖掘研究.pdf

中山大学博士学位论文 时态工作流建模、分析和挖掘研究 专业：计算机软件与理论 博士生：潘炎 指导老师：汤庸教授 摘要 近年来，工作流技术逐渐成为了计算机应用领域中的最为活跃的研究热点之一工作流 系统的时问管理问题在工作流管理中扮演了十分重要的角色。对工作流过程模型中的时间信 息进行有效的管理，保证时间约束得到满足，具有十分重要的意义。本文从时间建模、性能 分析、调度优化和工作流挖掘四个方面对时态工作流技术进行研究 工作流设计者需要有效的方法去建模和分析工作流过程模型中时间行为。针对已有的时 间工作流模型中缺乏对时间不确定性和资源的有效时间约束的描述能力，在对f i n 进行扩 展的基础上，提出了模糊时态工作流网f t w f - n e t s 讨论了其时态算子的计算，以及利用 f l w f - n e t s 对工作流过程中的时态行为进行建模和时间可能性分析的方法。它可以描述工作 流系统中的不确定的时间信息，并进行计算和分析。并引入资源的有效时问和变迁的有效时 间，可以更加全面地描述工作流系统中的时态现象和规律。 工作流的性能分析在实现成功的工作流管理的过程中发挥着十分重要的作用在许多情 况下，特别是在工作流系统开发的早期，工作流的设计者可能从以前的活动执行情况的统计 信息中获得或根据自己的经验估算出工作流的每个活动的大概执行时间，他们希望有一种 有效的时间性能评估方法，来估计某个工作流程的平均周转时间在扩展f 1 w f - 协的基 础上，提出了一种用于工作流模型时间性能分析的方法，首先将扩展的f l w f m t s 分解成 为一系列没有选择控制结构的子网，然后估算每个子网的周转时间，最后计算得出整个工作 流模型的平均周转时间 在多流程多实例同时执行的工作流系统中，工作流管理者需要有效的手段对流程的执行 进行调度优化，这对优化企业的资源配置和提高生产效率有着非常重要的意义考虑到工作 流系统中资源和活动的动态特性和时间信息的不确定性，在对模糊时态工作流网f t w f - n c t 进行着色扩展的基础上，提出了着色模糊时态工作流网c f v w f - n c t ，用以描述和计算多个 流程多个实例同时执行的情况下资源和活动的时间信息。在此基础上采用遗传算法来优化调 度序列，从而为工作流管理者提供一种有效地进行流程调度和优化的手段。 工作流挖掘越来越受到工作流管理的研究者们的青睐。一些企业没有工作流系统，且企 1 1 - l 中山大学博士学位论文 业业务流程会随时间动态变化。考虑到手工建立工作流模型是困难且耗时的工作，工作流管 理者需要有效的方法来自动建立和定时更新工作流模型。为此，提出了一种和用事件日志自 动挖掘工作流模型的算法t 可以挖掘带有循环结构的工作流模型。接着用一个具体的实例来 说明算法的执行过程。最后，通过实验比较来说明该算法可以利用活动的时间区间的重叠来 排除活动间的依赖关系，明显减少了算法中时间昂贵的独立性溯试的次数，从而改善算法性 能。 关键字：时态工作流，工作流模型，p e t r i 弼，时问建模，时问性能分析，调度优化，工作 流挖掘 中山大学博士学位论文 r e s e a r c h0 1 1t e m p o r a lw o r k f l o w m o d e l l i n g ，a n a l y s i sa n dm i n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：y a hp a n s u p e r v i s o r ：p r o f e s s o ry o n gt a n g a b s t r a c t f o rr e c e n ty e a r s , t i m em a n a g e m e n ti nw o r k f l o wh a sb e e no n eo ft h em o s ta c t i v er e s e a r c h a r e a si nw m k f l o wm a n a g e m e n t t u n em a n a g e m e n ti nw o r k f l o ws y s t e m sp l a y sak e yr o l ei n w o r k f i o wm a n a g e m e n t i ti so fg r e a ti m p o r t a n c et om a n a g et h et i m ei n f o r m a t i o ni nw o f k f l o w s e f f e c t i v e l ya n dt oa v o i dt h ev i o l a t i o no ft i m ec o n s t r a i n t s i nt h i sp a p e r , t e m p o r a lw o r k f l o wh a s b e e ns 岫d i e df r o mf o u ra s p e c t s , i n c l u d i n gt i m e m o d e l i n g ，p e r f o r m a n c ea n a l y s i s ，s c h e d u l i n g o p t i m i t i n na n dw o r k l o wm i n i n g w o r k f l o wd e s i g n e r sn e e de f f e c t i v ea p p r o a c h e st om o d e la n da n a l y z et h et e m p o r a lb c h a v i o m i nw o r k f l o wm o d e l s t h eu n c e r t a i n t i e si nt i m ea n dt i m e - r e i s t e dc o n s t r a i n t si nw o r k f l o wm o d e l s s h o u l db ct a k e ni n t oc o n s i d e r a t i o n b a s e do ri n t r o d u c i n gt i m ec o n s t r a i n t so ne l e m e n t si n f u z z y - t i m i n gp e t r in e t s , t h i sp a p e rp r o p o s ean c ww o r k f l o wm o d e ln a m e df u z z yt e m p o r a l w o r k f l o wn e t s ( f t v v f - l l e t s ) t h ec a l c u l a t i o no ft e m p o r a le l e m e n t si nf w f - i l e t si sg i v e n t h e n t i m e m o d e l i n ga n d t i m e p o s s i b i l i t ya n a l y s i s o ft e m p o r a l p h e n o m e n ai n f v v f - u e t sa r e i n v e s t i g a t e d r l w f - i l e t sc a l lb eu s e dt om o d e lt i m ei n f o r m a t i o ni nt h o s ew o r k f l o w s , w h i c hh a v e t i m eu n c e r t a i n t ya n d h a v et i m ec o n s t r a i n l so i lr e u - ma n da c t i v i t i e s , a n da n a l y z et h et i m e p o a s i b i l i t yo ns o m ec o n s t r a i n t s t u n ep e r f o r m a n c ea n a l y s i sf o rw o r k f l o wm o d e l sp l a y sa l li m p o g t a l l tr o l ei nt h ep r o o f a c h i e v i n gs u c c e s s f u lw o r k f i o wm a n a g e m e n t i nm a n yc a s c s e s p e c i a l l yi nt h ee a r l ys t a g eo f w o r k f l o ws y s t e md e v e l o p m e n t , i ti sl l e c e a s a i yf o fw o r k f l o wd e s i g n e 培t oe v a l u a t et h ea v e r a g e t u r n a r o u n dt i m eo fp r o c e s s e sb ye f f e c t i v ea p p r o a c h e s b ye x t e n d i n gf u z z yt e m p o r a lw o r k f l o w n e t sw i t hc h o k ep o s s i b i l i t yf u n c t i o n s , aw o r k f l o wm o d e ln a m e de x t e n d e df u z z yt e m p o r a l w o r k f l o wn e t s ( e f r w f - n e t s ) h a sb e e np r o p o s e d i td e c o m p o s ea ne f t w f - n e ti n t oas e to f f r e e - c h o i c ea n b n e t s , t h e ne v a l u a t et h et u r n a r o u n dt i m eo fe a c hs u b n e t ，a n df i n a l l yc a l c u l a t et h e a v e r a g et u r n a r o u n dt i m eo f t h ew h o l ep r o c e s s e f f e c t i v ea p p r o a c h e sf o rw o r k l o ws c h e d u f i n go p t i m i z a t i o na r en e e d e dt oi m p r o v et h e v 中山大学博士学位论文 e f f i c i e n c yo fb u s i n e s sp r o c e s s e s b ye x t e n d i n gf u z z yt e m l r a lw o r k f l o wn e t sw i t hc o l o rs e t , n w o r k f l o wm o d e ln a m e dc o l o r e df u z z yt e m p o r a lw o r k f l o wn e t s ( o t w f - n e 融h a sb e e n p r o p o s e d a n dt h ec a l c u l a t i o no ft e m p o r a le l e m e n t si nc f w f - n e t si sg i v e n t h e nnw o r k f l o w s c h e d u l i n go p t i m i z a t i o nm e t h o db a s e do ng e n e t i ca l g o r i t h mi si n v e s t i g a t e d f i n a l l yt h e e f f e c t i v e n e s so ft h em e t h o di sp r o v e db ye x p e r i m e n tr e s u l t s w o r k f l o wm i n i n gh a sa t t r a c t e di n o r ea n dm o r er e s c a r c h a m e y e si nw o r k f l o wm a n a g e m e n t s o m eo r g a n i z a t i o n sd on o th a v ew o r k f l o w s y s t e m s a n db u s i n e s sp r o c e s s e se v o l v e sd y n a m i c a l l y w i t ht i m e w i t ht h e 鲢i d e m t i o nt h a tc r e a t i n gnw o r l 田o wm o d e lb yh a n di sc o m p l i c a t e da n d t i m e - c o n s u m l n g , al e a m i n ga l g o r i t h mi sp r o p o s e dt oa u t o m a t i c a l l yd i s c o v e rw o r k f l o wm o d e l s w i t hi t e r a t i v es t r u c t u r e s a n d 柚e x a m p l ei sg i v e nt oi l l u s t r a t et h ee x e c u t i o np r o c e s so ft h e a l g o r i t h m f i n a l l y , e x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h mu s e , 5t h eo v e r l a po fa c t i v i t i e s i n t e r v a l st oe l i m i n a t et o m ed e p e n d e n c yr e l a t i o n so fa c t i v i t i e s , t oa st or e d u c et h en u m b e ro f t i m e - c o n s u m i n gi n d e p e n d e n c et e s t sa n di m p r o v et h ea l g o r i t h m sp e r f o r m a n c e k e y w o r d 戤t e m p o r a lw o r k f l o w , w o r k f l o wm o d e l p e t r tn e t , t i m em o d e i h n g , t i m ep o s s i b i l i t y a n a l y s i s , s c h e d u l i n go p t i m i z a t i o n , w o r l d l o wm i n i n g v i 中山大学博士学位论文 第1 章引言 1 1 引言 时间是自然界无所不在的客观属性，所有信息都具有相应的时态属性。随着 信息技术的深入和发展，信息系统面临许多新的应用和新的需求，对时态信息处 理的需求越来越追切。时态信息处理己成为许多新一代信息系统的关键技术，在 某些系统中，信息的时态性还起着关键性作用。 时态工作流技术，主要是研究工作流模型中的时间行为。近年来，工作流技 术逐渐成为了计算机应用领域中的最为活跃的研究热点之一。随着企业的市场竞 争的日趋激烈和业务环境的不断变化，对业务流程管理的要求也变得越来越高。 其中，工作流系统的时间管理问题在工作流管理，特别是工作流过程管理扮演了 十分重要的角色。 实际的业务流程中存在许多时间约束，如一个个工作任务( 活动) 或者整个 业务流程必须在规定的时问长度内完成等。在流程的实际执行过程中，如果违反 了这些时间约束，就有可能给企业带来损失。如在客户投诉处理中。客户的投诉 没能得到及时的回应和处理，将会影响客户的满意度；有时间限制的合同没有及 时完成，将要支付违约金等等。由此可见，对工作流过程模型中的时间信息进行 有效的管理，保证这些时间约束得到满足，对工作流管理具有十分重要的意义。 时间管理问题在人工智能、时态数据库与实时系统等领域已经取得许多研究 成果。但是，由于工作流建模的复杂性与工作流实例执行的动态性，上述领域的 时间建模与管理技术难以直接应用于工作流的时间管理。在如今竞争激烈的市场 环境中，企业能在竞争中取得优势的一个重要因素在于它是否能够实时有效地获 得和掌控企业业务流程中的信息。为此，工作流管理系统应能提供过程与时间的 必要信息1 1 】： 在模型建立阶段，定义工作流控制逻辑与业务过程的时间信息，并检测它 中山大学博士学位论文 们的可行性； 在实例执行阶段，通过时间监控与仿真，识别与预测可能的时问问题； 支持工作流时间计划的临时调整( 如扩展期限约束) ，并提供超前 ( p r o - a c t i v e ) 机制以警告潜在的时间违反； 对于不可预测的紧急事件或组织延迟，时间仿真可以寻找工作流执行的 替换路径，以减小或弥补时间延迟； 工作流参与者需要任务紧急程度的信息，以便按照全局目标管理个人的 工作计划； 一旦出现时间违反，工作流系统应该触发异常处理以重新获得实例执行 的一致状态。 总的来说，我们可以把工作流模型中的时闻行为分析分为三个步骤：建模、 分析和优化。 建模，主要是指工作流模型中时问行为的建模，如何采用合适的形式化方法 来描述业务流程中的活动和资源的时态信息和约束。 分析一般可以分为定性分析和定量分析两方面，定性分析主要是模型中的特 性分析，例如模型的合理性分析、可调度性分析；定量分析主要有性能分析，是 指通过仿真或严格的理论分析获得和系统性能相关的量化指标( 业务平均处理时 间、资源平均利用率等) 来评估建立的经营过程工作模型是否满足目标需求【】o 优化一般是指使用启发式搜索或遗传算法等方法，找出一种最佳的解决方案 ( 如效率最高，所用时间最少或成本最低等) 。 另外，近年来，随着工作流技术研究的深入，研究者们开始研究如何根据企 业应用系统的事件日志中的时间信息来自动构建出企业的工作流模型，这就是所 谓的过程挖掘或工作流挖掘。 1 2 研究动机和内容 为此，本文的研究主要围绕上述四个方面的内容，即工作流模型中的时间建 模和分析、时阃性能分析、多流程的调度优化以及工作流模型挖掘。 第一方面是工作流模型的时间建模和时间可能性分析。工作流系统的时间管 2 中山大学博士学位论文 理问题在工作流管理中扮演了十分重要的角色。实际的业务流程中存在许多时间 约束，如一个个工作任务( 活动) 或者整个业务流程必须在规定的时间长度内完 成等。在流程的实际执行过程中，如果违反了这些时间约束，就有可能给企业带 来损失。如在客户投诉处理中，客户的投诉没能得到及时的回应和处理，将会影 响客户的满意度；有时间限制的合同没有及时完成，将要支付违约金等等。由此 可见，对工作流过程模型中的时间信息进行有效的管理，保证这些时间约束得到 满足，对工作流管理具有十分重要的意义。 要实现工作流的时间管理，首先要解决如何用形式化的方法去描述时间信息 和时态行为。工作流设计者需要有效的方法去建模和分析工作流过程模型中时间 行为。p e t r i 网技术以其严谨的数学基础和较强的描述能力受到了研究者们的青 睐。人们已经提出了多种基于扩展p e t r i 网的工作流时间描述模型( 【2 】- 【7 】) 。然而， 在上述这些模型中，时间信息都是确定性的，缺乏对不确定性时间信息的描述能 力。而在实际的工作流应用中，由于资源和活动具有动态特性，使得各种时间信 息常常是非确定性的，难以被精确描述。t m u r a t a ( 【8 】，【9 】) 提出了模糊时间密 高级p e t r i 网( f u z z y - t i m i n gp e t r in e t 。f r n ) 。f t n 能对工作流过程中的模糊时间行 为进行描述和分析。但f t n 中缺乏对时间约束的描述能力。z h o u 1 0 等在对f 1 n 进行扩展而提出的扩展模糊时间p e t r i 网e f t n 中加入了对变迁的有效时间约束 的描述，但是e f t n 忽略了资源的有效时问约束。另外，现有的工作流模型对资 源的有效时间( 即资源的生命周期) 的研究还很少。只有文献【l l 】中对其进行了 初步的探讨。为此，本文的第4 章在综合现有的研究成果的基础上，对f i n 进 行扩展，提出了一种新的工作流模型模糊时态工作流网f t w f - n e t s 。给出了 f t w f - n e t s 中各种时态元素的计算方法，并讨论了利用f t w f - n e t s 对工作流中的 时态现象进行时间建模和时间可能性分析的方法。最后用一个实验室检验流程的 例子来解释这些方法的使用。与已有的时间工作流的模型相比，f t l i r f n e t s 具有 以下特点：( 1 ) 它可以描述工作流系统中的不确定的时间信息，并进行计算和分 析。( 2 ) 它引入资源的有效时间和变迁的有效时间，可以更加全面地描述工作流 系统中的时态现象和规律。利用p r w 卜n e t s ，可以有效地对工作流过程中的时态 行为进行建模和时间可能性分析： 第二方面是工作流模型的时间性能评估。工作流管理的目标是，通过将工作 3 中山大学博士学位论文 活动有序化，以及合理地调用与这些活动相关联的人力资源和信息资源，来帮助 企业高效地达到业务目标 1 6 1 。工作流的性能分析在实现成功的工作流管理的过 程中发挥着十分重要的作用。在已有的研究中，p c t f i 网已经被广泛地使用于业 务流程的性能分析* ( 0 6 1 2 1 1 ) 。但是，当前大部分研究工作都是基于随机过程 和随机p c t r i 网的。这类方法都是假设工作流实例的每个活动( 变迁) 的执行时 间服从负指数分布，而这一假设在实际的环境中往往很难满足。另一方面，在许 多情况下，特别是在工作流系统开发的早期，工作流的设计者可能从以前的活动 执行情况的统计信息中获得，或根据自己的经验估算出工作流的每个活动的大概 执行时问，他们希望有一种有效的时间性能评估方法，来估计某个工作流程的平 均周转时问。 本文的第5 章在扩展第4 章f t w f - n e t s 的基础上，提出了一种用于工作流模 型时间性能分析的方法。我们将介绍一种将扩展的f t w f n e t s 分解成为一系列 没有选择控制结构的子网的算法，然后估算每个子网的周转时间，最后计算得出 整个工作流模型的平均周转时间。 第三方面是工作流中多流程的调度优化。在多流程多实例同时执行的工作流 系统中，工作流管理者需要有效的手段对流程的执行进行调度优化。这对优化企 业的资源配置和提高生产效率有着非常重要的意义。p e t r i 网是用于工作流建模 和分析的重要工具( 【7 1 1 2 3 ) 。目前，对基于p e t r i 网的工作流的调度问题的研究 主要集中在可调度性分析方面( 1 5 1 ，【6 】) ，对调度优化的研究还比较少而与工作 流系统类似的柔性制造系统f m s 的调度优化问题则有很多研究成果( 【2 4 卜 2 9 1 ) 。 其调度优化的方法主要可分为基于启发式搜索和基于遗传算法两种。基于启发式 搜索的方法( 【2 4 卜 2 6 1 ) 需要依赖较强的领域知识来进行优化，其通用性较差，而 工作流的调度优化需要通用性较好的方法。而在基于遗传算法( 1 2 7 1 2 9 1 ) 的方法 中，h a o 2 9 等提出了一种基于增强确定时间p e t r i 网和遗传算法的f m s 调度优 化方法，采用变迁序列作为染色体，具有较好的通用性，但是该文没有考虑了变 迁序列有并行变迁时的时间计算问题，而且没有考虑时问信息的不确定性。 为此，考虑到工作流系统中资源和活动的动态特性和时间信息的不确定性， 本文的第6 章在对第4 章的模糊时态工作流网f t w f - n e t 进行着色扩展的基础上， 提出了着色模糊时态工作流网c f t w f - n e t ，用以描述和计算多个流程多个实例 4 中山大学博士学位论文 同时执行的情况下资源和活动的时间信息。在此基础上采用遗传算法来优化调度 序列，从而为工作流管理者提供一种有效地进行流程调度和优化的手段。 最后一个方面是工作流模型挖掘。工作流模型挖掘，是指根据企业应用系统 中的事件日志，挖掘出符合企业业务流程的工作流模型。在早期的企业应用系统 中，往往没有工作流管理机制，但这些系统通常都会记录某个工作人员在什么时 间执行了什么业务活动，这些信息一般称为事件日志。事件日志事实上记录了业 务流程的一个个执行实例。另一方面，对于一些已经建立了工作流管理系统的企 业，其业务流程也会随着市场竞争和业务需求的变化而发生改变。我们知道，为 一个复杂的业务流程建立工作流模型往往是十分困难的事情，它需要经验丰富的 专业人士的参与并且需要花费大量的时间和成本，再考虑到业务流程会随时间推 移而动态改变，使得工作流模型需要定时进行更新。如果能为工作流设计者和管 理者提供一种自动建立和更新工作流模型的方法，将可以大大降低工作流建模 和更新的复杂度和成本 为此，工作流研究者尝试通过对应用系统的事件日志的分析，挖掘出符合企 业业务流程的工作流模型。a g r a w a l ，r 【4 1 】等定义了工作流日志的概念，并提出 了一种根据工作流日志自动构建工作流模型的算法。该方法依据工作流日志中活 动的先后顺序关系来确定表示工作流模型的有向图中活动问的连接关系，然后采 用有向无环图的传递消减来对图进行化简。但是，与实际的工作流模型相比，算 法得到的有向图可能会遗漏某些边或者产生多余的边，其准确性跟工作流日志的 规模和质量有很大关系。p i n t e r , s s 【4 2 】等对a g r a w a l ，r 的工作进行了扩展，认 为工作流日志中每个工作流中活动的执行时间是一个包括开始时间和结束时间 的时间区间，在此基础上提出了两个新的算法，由于时间区间比单个时间提供了 更多的信息，使得活动间的依赖关系的判断变得更简单高效，使该算法可以减少 遗漏的和多余的边的数量。w i lv a nd e ra a l s t 4 4 等采用p e t r i 网来表示工作流模 型，提出了另一种挖掘工作流模型的a 算法。其假设给定的工作流日志是完备的。 算法的时间复杂度为指数时间。但a 算法对工作流日志的完备性假设及其对工作 流模型的结构假设过于严格，而现实中的工作流日志一般都是不完备的并带有噪 声。针对这一问题，s i l v a , r 4 5 1 等提出了一种基于概率理论的工作流模型的挖 掘方法，采用a o 图( a og r a p h ) 来表示工作流模型，通过一定的模型结构假 5 中山大学博士学位论文 设，根据工作流日志中活动的依赖关系，以及活动间的独立性的计算，可以在多 项式时间内挖掘出符合条件的工作流模型。算法可以挖掘到隐含的分支和合并节 点( 即在日志中没有出现的节点) ，并可以处理噪声。但是，该文所挖掘的工作 流模型不能带有循环结构，而循环结构是工作流模型中最常见的四种控制结构之 一 因此，我们在扩展 4 5 1 的算法的基础上，设计了一种新的挖掘算法，可以挖 掘带有循环结构的工作流模型，同时，我们借鉴 4 2 1 的做法，认为工作流日志中 记录了每个活动的开始时间和结束时间，可以通过活动的时间区间的重叠来排除 活动问的依赖关系。 1 3 本文的组织结构 本文研究的工作流模型中的时间行为建模与分析、时间性能分析、多流程 的调度优化和工作流模型的挖掘。本文共有8 章内容，其安排如下： 第1 章是引言部分，介绍了本文研究的背景，动机和内容，以及本文的组 织结构。 第2 章介绍了本研究涉及的相关理论的基本概念和基础知识。 第3 章分析了本文研究涉及的相关领域的研究现状和不足。 第4 章介绍了模糊时态工作流网( f t w f - n e t s ) ，给出了f r w f - n e t s 中各种 时态元素的计算方法，并讨论了利用f r w f - n e t s 对工作流中的时态现象进行时 间建模和时问可能性分析的方法。 第5 章在对模糊时态工作流网( f r w f - n e t s ) 弓l 入选择概率函数的基础上， 介绍了扩展模糊时态工作流网( e f l w f - 眦t s ) 的工作流模型，并给出其中的时 态元素的计算方法。接着给出了一种分解e f r w f - n e t s 的算法，并讨论了基于该 分解算法的时间性能评估方法。 第6 章在对模糊时态工作流网( f i w f - n e t s ) 进行着色扩展的基础上，介绍 了着色模糊时态工作流网( c f r w f - n e t s ) 的工作流模型，并给出其中的时态元 素的计算方法。接着给出了一种基于遗传算法的多流程多实例的调度优化方法。 第7 章介绍了一种基于带时间区间的活动日志的工作流模型的挖掘方法， 6 中山学博士学位论文 可以挖掘带有循环结构的工作流模型。并利用工作流活动的区间信息来减少独立 性判断的次数，从而优化算法的效率。 第8 章总结了本文研究的主要内容以及下一步的研究方向。 7 中山大学博士学位论文 第2 章相关理论基础 本文的研究除了涉及工作流的基本概念和p e t r i 网的理论之外，在第4 章使 用了模糊数学的知识，在第6 章的调度优化中使用了遗传算法，第7 章的工作流 模型挖掘涉及到贝叶斯网络的概率模型。为便于理解，本章将分别对这些相关理 论的基本概念和原理进行介绍。 2 1 工作流的基本概念 2 1 1 工作流的定义 工作流技术是计算机应用领域的研究热点之一。关于工作流的研究已经二十 多年的历史，但目前工作流仍然没有统一的定义，文 4 6 1 中列举一些常见的工作 流的定义，它们分别从不同的角度来描述工作流。 ( 1 ) 工作流管理联盟w f m c 的定义 工作流是一类能够完全或者部分自动执行的经营过程，根据一系列过程规 则，文档、信息或任务能够在不同的执行者之间传递、执行 4 6 1 。 ( 2 ) g i g ag r o u p 的定义 工作流是经营过程中可运转的部分，包括任务的顺序以及由谁来执行、支持 任务的信息流、评价与控制任务的跟踪、报告机制 4 6 1 。 ( 3 ) i b ma l m a d e nr e s e a r c hc e n t e r 的定义 工作流是经营过程中的一种计算机化的表示模型，定义了完成整个过程所需 用的各种参数，这些参数包括对过程中每一个单独步骤的定义、步骤间的执行顺 序、条件以及数据流的建立、每一步骤由谁负责以及每个活动所需要的应用程序 【4 6 】 ( 4 ) a m i ts h e t h 的定义 工作流是涉及到多任务协调执行的活动，这些任务分别由不同的处理实体来 9 中山大学博士学位论文 完成，一项任务定义了需要做的某些工作，它可用各种形式来进行定义，包括在 文件或电子邮件中的文本描述、一张表格、一条消息以及一个计算机程序。用来 执行任务的处理实体可以是人，也可以是计算机系统( 比如一个应用程序、一个 数据库管理系统) 【4 6 1 。 ( 5 ) w m ev a nd e r a a l s t 的定义 工作流是一系列工作的偏序集。工作的序列可以有多种方式，比如工作x 与y 满足x y 当且仅当x 在y 开始之前就已经就绪【4 6 】。 ( 6 ) 罗海滨、范玉顺等的定义 工作流是通过计算机软件进行定义、执行并监控的经营过程，而这种计算机 软件就是工作流管理系统【4 6 】。 2 1 2 工作流技术中的核心概念 文f 4 7 】中列出了工作流技术中的一些重要的核心概念。 【定义2 - l 】工作流过程定义。工作流的过程定义是业务过程的计算机化的 形式表示。它定义的是过程运行中会涉及到的各种参数，如业务过程的开始和终 止条件、各个工作环节及相互之间的控制流动与数据流动关系等 4 7 1 。 【定义2 - 2 1 活动。工作流中的活动，指的是工作流中的一个逻辑步骤或 称环节。它包含的信息包括：开始和结束条件；可参与到此环节中的用户；完成 此活动所需的应用程序或数据；以及关于此活动应如何完成的一些限制条件( 如 时间上的限制等) 【4 7 。 【定义2 - 3 过程实例。过程实例指的是某个工作流过程的一次执行。在 实例的执行过程中，工作流管理系统w f m s 将解释相应的过程定义，生成有关 的活动实例并根据过程定义中的控制规则协调这些活动实例之间的顺序关系，同 时根据数据流动关系的定义完成活动实例之间的数据传送。一般情况下每一个活 动实例都将表现为一个工作项 4 7 1 。 2 1 3 工作流管理系统w f m s 工作流管理联盟w f m c 给出了工作流管理系统( w o r k f l o wm a n a g e m e n t s y s t e m ，w f m s ) 的定义： 中山大学博士学位论文 【定义2 - 4 】工作流管理系统是一个完全定义、管理和执行工作流的系统， 它通过计算机表示的工作流逻辑来驱动软件有序地运行f 4 9 1 。 工作流管理系统的作用，就是将现实世界中的业务过程转化成某种计算机化 的形式表示。并在此形式表示的驱动下完成工作流的执行和管理( 【4 7 】，1 4 9 ) 。 工作流管理联盟发布的工作流系统参考模型【4 9 】包含了如图2 - 1 所示的主要 部件，它定义了w f m s 的各主要组成部分、各部分的功能及相互之间的接口 图2 - 1w f m c 的工作流系统参考模型 下面简单介绍该参考模型的各个组成部分。 ( 1 ) 工作流执行服务( w o r k f l o we n a c t m e n ts e r v i c e ) 工作流执行服务是工作流管理系统的核心部分。它借助于一个或多个工作流 引擎，来激活并解释过程定义的全部或部分，并同外部的应用程序进行交互来完 成工作流过程实例的创建、执行与管理，如过程定义的解释、过程实例的控制( 创 建、激活、暂停、终止等) 、在过程各活动之问的游历( 控制条件的计算与数据 的传递等) ，并生成有关的工作项通知用户进行处理等等，为工作流程的进行提 供一个运行时环境【钥。 在工作流执行服务的外部定义了五个接口： 接口1 ( i n t e r f a c e1 ) ：r 作流定义转换接口。 接口2 ( i n t e r f a c e2 ) ：7 - 作流客户端应用程序接口。 接口3 ( i n t e r f a c e3 ) ：应用程序调用接口。 接口4 ( i n t e r f a c e4 ) ：不同工作流系统间协同工作接口。 接口5 ( i n t e r f a c e 5 ) ：管理和监视接口。 中山大学博士学位论文 这五个接口被统称为w o r k f l o w a p i ( w a p i ) 。 ( 2 ) 过程定义工具( p r o c e s sd e f i n i t i o nt o o l s ) 过程定义工具的主要功能是给用户提供一种对实际业务过程进行分析、建模 的手段，并生成业务过程的可被计算机处理的形式化描述【4 7 】。它通过接口1 与 工作流执行服务连接。 ( 3 ) 客户端应用程序( w o r k f l o wc l i e n t a p p l i c a t i o n s ) 客户端应用程序的作用是给用户提供一种手段，以处理过程实例运行过程中 需要人工干预的任务 4 7 1 。它通过接口2 与工作流执行服务连接。 ( 4 ) 被调应用程序( i n v o k e d a p p l i c a t i o n s ) 被调应用程序是指工作流执行服务在过程实例的运行过程中调用的、用以对 应用数据进行处理的应用程序 4 7 1 。它通过接口3 与工作流执行服务连接。 ( 5 ) 管理及监控工具( a d m i n i s t r a t i o n m o n i t o r i n g t o o l s ) 管理及监控工具的功能是对w f m s 中过程实例的状态进行监控与管理，如 用户管理、角色管理、审计管理、资源控制( 包括过程管理及过程状态控制等) 4 7 1 。它通过接口5 与工作流执行服务连接。 2 2 p e t r i 网理论 本文的第4 、5 、6 章采用了基于p e t r i 网的工作流模型，为此，本节对p e t d 网理论中的重要概念，术语，标记，以及与工作流相关的理论进行介绍。p c t f i 网的相关详细理论可以参考文献【2 3 】和【3 0 1 。 2 2 1p e t r i 网的定义 p e t r i 网理论最早是在1 9 6 2 年由德国的c a la d a mp e 埔提出。和其它系统模 型一样，p e 砸网系统由两类元素组成：一类表示状态的元素，另一类表示变化 ( 例如事件) 的元素1 3 0 l 。p e t r i 网的图形表示形式是一类特殊的有向图，它主要 由库所和变迁这两种元素组成： 库所( p l a c e ) ，也称s 一元素或者s - 元，它是p e t r i 网中的状态元素，通 中山大学博士学位论文 常用于表示一种资源。在p e t r i 网的图形表示中，库所通常用圆圈表示 库所所代表的资源的数量用圆圈中的小黑点的个数表示，这种小黑点称 作托肯( t o k e n ) 。 变迁( t r a n s i t i o n ) ，也称为t - - 元素或者t - 元，它是p e t r i 网中的变化元 素，通常用于表示某个事件或者状态的转换，在p e 研网的图形表示中， 采用矩形表示变迁。 p e t r i 网的图形表示是一种特殊的有向图，在该图中，库所和变迁交替地出现 在由有向弧连接而成的路径上，一条有向弧只允许从库所指向变迁，或者从变迁 指向库所。每条有向弧上都用数字标明该弧的权值，表示该弧所连的变迁触发时 消耗或产生的托肯的数量。如果弧上没有标明权值，则表示该弧的权重为1 【定义2 5 】 3 0 三元组n = ( s ，瓦f ) 称为有向网( 简称网) 的充分必要条 件是： ( 1 ) s n t = 中 ( 2 ) s u t 中 ( 3 ) f s x t u t x s ( 4 ) d o r a ( f ) u c o d ( f ) = s u t 其中，d o r a ( f ) = f x i | y ：( x ，y ) f ) ，c o d ( f ) = y i3 x ：( x ，y ) e f s 和t 分别称为n 的库所集和变迁集，f 为流关系。 【定义2 - 6 1 3 0 设x e x 为n 的任一元素，则 。x = yj ( y ，x ) e f 称为x 的前集( p r e - s e t ) 或输入集， x = z l ( x ，z ) f ) 称为x 的后集( p o s t - s e t ) 或输出集 【定义2 - 7 1 1 3 0 若v x x ：x n x = 中，则n 为单纯网；若v x e x ：x = y a x = y 。 x = y ，则n 为简单网。 以上是关于有向网的定义。p e t r i 网系统是在有向网的基础上加入资源的初 始分布的描述，并规定框架上的活动规则。具体的说，就是标明每个库所的初始 托肯数量。库所容量和变迁与托肯之间的数量关系等。 记n = 0 ，l ，2 ， ，n = l ，2 ，3 ，) ，d 表示无穷 【定义2 8 】 3 0 k ：s n u ( 称为有向网n ： s ，t ，f 的容量函数 中山大学博士学位论文 对给定的容量函数k ，则m ：s - - - n o 称为n 的一个标识( m a r k i n g ) 的条件 是：v s s ：m ( s ) k ( s ) w ：f - - , n 称为n 上的权函数，对( x ，y ) f ，w ( x ，y ) = w ( ( x ，y ) ) 称为( x y ) 上的权。权函数规定了每个变迁发生一次引起的有关资源数量上的变化， 对任何的( x ，y ) e f ，o ，则t 在m 可以发生( 被触发) ， 将标识m 改变为m 的后继m ，m 的定义是，对于任何s e s ： m 毽) = 膨o ) 一w ( s ，f ) 若s e t f - 肼o ) + o ，s ) 若s f 一l m o ) 一w ( s ，f ) + ( f ，5 ) 若s l f 3 t m ( s )拳岳l 。 标识由m 变化到m 的后继m 记作m t m 。 2 2 2p e t r i 网