（计算机软件与理论专业论文）时态工作流的时间异常处理算法.pdf

中山大学硕士论文时态工作流的时间异常处理算法 论文题目 专业 硕士生 指导教师 时态工作流的时间异常处理算法 计算机软件与理论 郑婷婷 余阳副教授 摘要 市场竞争的加剧，对工作流产品的时效性、柔性和可靠性提出了更高的要求。 而动态多变的业务环境，加上业务流程常具有一定的时间约束，工作流系统的运 行过程中时间异常的出现频率大大增加，工作流系统对时间异常处理的需求也日 益迫切。为了提高工作流产品的时效性和柔性，本文从业务过程对时间异常处理 的需求出发，在时态工作流模型的基础上讨论了时间异常的处理，提出一种时间 异常的处理算法，并通过一系列的仿真实验对算法的执行效率进行了检验。具体 地讲，本文的主要内容包括以下几个方面： 1 ) 在时态工作流模型的基础上，给出了时间异常的定义，讨论了时间异常的 处理措施和一般处理步骤。 2 ) 提出一种调整后续任务的完成时间的时间异常处理算法。该算法以提高案 例的完成率为目的，提出了松弛度的概念，主要思想是通过计算后续任务的松弛 度，使案例在发生了时间异常后仍尽量保证后续任务的完成，从而保证案例在其 有效期内完成，并给出了各种路由结构下详细的计算和时间调整方案。该算法具 有复杂度较低、具有良好的可操作性、能很好地适应频繁的时间调整，并能一定 程度地适应修改案例和模型导致的动态调整等特点，具有良好的动态适应性和自 适应性。 3 ) 给出了一个应用实例，并通过一系列的仿真实验来检验算法的执行效率。 多次的实验数据统计表明，算法性能表现良好，能有效处理任务超时导致的时间 异常，即使在资源负载较大的情况下或部分案例较为紧迫的情况下，系统也能达 至i j 较高的案例完成率。 本文的研究成果促进和丰富了对工作流时间管理技术及对工作流柔性理论 h 中山大学硕士论文时态工作流的时间异常处理算法 的研究，一定程度上完善了时态工作流及其柔性理论，在物流、生产制造、电子 政务等领域中具有一定的应用价值。 关键词：时态工作流，时间异常，松弛度，算法，仿真 i i i 中山大学硕士论文时态工作流的时间异常处理算法 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： a n a l g o r i t h mf o rh a n d l i n gt i m ee x c e p t i o n so f t e m p o r a lw o r k f l o w c o m p u t e rs o f t w a r ea n dt h e o r y z h e n gt i n g t i n g y uy a n g ( a s s o c i a t ep r o f e s s o r ) a b s t r a c t m o r ed r a s t i cc o m p e t i t i o nm a k e si tm o r ei m p o r t a n tf o rw o r k f l o wp r o d u c t st o s u p p o r tt h ec h a r a c t e r i s t i c so fh i g h e ra b i l i t yt oc o n t r o lt i m e ，f l e x i b i l i t ya n dr e l i a b i l i t y b e c a u s eo ft h ed y n a m i ce n v i r o n m e n ta n dc e r t a i nt i m ec o n s t r a i n t so fb u s i n e s s p r o c e s s e s ，t h ef r e q u e n c yo ft i m ee x c e p t i o n so c c u r r i n gi n w o r k f l o ws y s t e m si s s i g n i f i c a n t l yi n c r e a s i n g ，a n dh a n d l i n gt i m ee x c e p t i o n si ss t r o n g l yd e m a n d e di n w o r k f l o ws y s t e m s i no r d e rt oe n h a n c et h ea b i l i t yt oc o n t r o lt i m ea n dt h ef l e x i b i l i t yo f w o r k f l o wp r o d u c t s ，h a n d l i n gt i m ee x c e p t i o n sb a s e do nt e m p o r a lw o r k f l o wm o d e li s d i s c u s s e di nt h ep a p e r , a n da na l g o r i t h mf o rh a n d l i n gt i m ee x c e p t i o ni sp r o p o s e d a s e r i e so fs i m u l a t i o ne x p e r i m e n t sa lee x e c u t e dt oc h e c kt h ee f f i c i e n c yo ft h ea l g o r i t h m a n dt h er e s u l t sa r ea n a l y z e d t h er e s e a r c ho ft h i sp a p e ri n c l u d e sa sf o l l o w s ： 1 ) t h ed e f m i t i o no ft i m ee x c e p t i o ni sg i v e nb a s eo nt e m p o r a lw o r k f l o wm o d e l t h em e a s u r e sa n dt h eg e n e r a lp r o c e s st oh a n d l et i m ee x c e p t i o n sa led i s c u s s e d 2 ) a na l g o r i t h mw h i c ha d j u s t st h ef i n i s h i n gt i m eo fl a t e rt a s k st oh e l pt h ec a s e s r e c o v e r i n gf r o mt i m ee x c e p t i o n si sp r o p o s e d i no r d e rt oe n h a n c et h ec o m p l e t i o nr a t e o ft h ec a s e s ，t h ec o n c e p to fl a x i t yi sp r o p o s e di nt h ea l g o r i t h m , a n dt h em a i ni d e ao f t h ea l g o r i t h mi se n s u r i n gt h ec o m p l e t i o no ft h el a t e rt a s k st of m i s ht h ec a s e sb e f o r e t h e i rd e a d l i n e se v e ni ft i m ee x c e p t i o n so c c u r t i m ec o m p u t i n ga n da d j u s t i n gs t r a t e g i e s f o rd i f f e r e n tr o u t i n gs t r u c t u r e sa r eg i v e n t h ea l g o r i t h mi sl o wi nc o m p l e x i t y , w h i c hi s a l s oe a s yt oi m p l e m e n t a n di t s 盘f o rf r e q u e n t l yt i m ea d j u s t i n g ，w h i c hi sg o o da t a d a p t a b i l i t y 3 ) as i m p l ee x a m p l ei sg i v e n ，a n das e r i e so fs i m u l a t i o ne x p e r i m e n t sa l e i m p l e m e n t e dt ov e r i f yt h ee f f i c i e n c yo ft h ea l g o r i t h m t h ed a t ao ft h ee x p e r i m e n t s i v 中山大学硕士论文时态工作流的时间异常处理算法 s h o w st h a tt h ea l g o r i t h mi sg o o da tp e r f o r m a n c e ，w h i c hc a ne f f i c i e n t l yh a n d l et i m e e x c e p t m n sc a u s e db yo v e r t i m eo ft a s k s e v e ni ft h er e s o u r c ei so v e r l o a d i n go rc a s e s a r eu r g e n t ，t h ea l g o r i t f a nc a ns t i l ll e a dt oh i g hc o m p l e t i o nr a t e t h ea c h i e v e m e n t so ft h i sp a p e re n r i c ht h er e s e a r c ho nt h et i m em a n a g e m e n ta n d t h et h e o r yo f w o r k f l o wf l e x i b i l i t y , a n di m p r o v et h er e s e a r c ho nt e m p o r a lw o r k f l o w a n di t s f l e x i b i l i t y , w h i c ha r ea l s oo fg r e a tu s ei nt h ea p p l i c a t i o no fl o g i s t i c s ， m a n u f a c t u r i n g ，e - g o v e r n m e n t ，a n do t h e ra r e a s k e yw o r d s ：t e m p o r a lw o r k f l o w , t i m ee x c e p t i o n ，l a x i t y , a l g o r i t h m , s i m u l a t i o n v 中山大学硕士论文 时惫工作流的时问异常处理算法 _ _ _ 一 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者躲智奶 醐：叫年f 月溯 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 导师签名：仓， 日期 期一日 ， 未 j 口 砖孙旨槲 名月 签r 者f雠年 文一f捌1 位期 学日 中山大学硕士论文时态工作流的时间异常处理算法 1 1 研究背景 第一章引言 本课题来源于时态工作流过程模型及其柔性研究( 国家自然科学基金编号： 6 0 5 7 3 1 6 0 ) 。 1 9 9 3 年工作流管理联盟( w f m c ) 的成立和它在次年发布的工作流系统参考 模型( w o r k f l o wr e f e r e n c em o d e l ) f 1 】标志着工作流技术开始进入相对成熟的阶段， 涌现出了大量工作流系统产品【2 1 。 市场竞争的加剧，对工作流产品的时效性和柔性提出了更高的要求。时态工 作流【3 j 将时间作为一个维度引入工作流描述，对工作流时态信息相关问题的研究 产生了广泛的影响。而工作流系统的柔性体现为系统灵活、动态地处理变更和异 常的能力【4 】。在工作流执行时可能存在多种潜在的工作流异常，而其中一类与时 间有关的异常称为工作流时间异常f 熨。近年来，动态多变的业务环境和激烈的市 场竞争，加上业务流程常具有一定的时间约束，工作流系统的运行过程中时间异 常的出现频率大大增加，工作流对时间异常处理的需求也日益迫切。但现有的工 作流系统仍缺乏对各种异常处理的有效支持【5 l 。 为了提高工作流产品的时效性和柔性，在时态工作流的基础上，本文主要研 究了时态工作流中时间异常的处理问题，提出一种时间异常的处理算法。算法以 提高案例的完成率为目的，具有较好的动态适应性和自适应性，其成果将丰富关 于时态工作流柔性理论的研究。 1 2 研究现状分析 时态工作流【3 1 将时间作为一个维度引入工作流系统，全面、系统地描述组成 工作流的各元素及其关系的时态特性。而在工作流时间管理中，时间信息的建模、 验证和分析是最基础、最核心的问题i s 。目前，对工作流系统时态信息的研究主 1 中山大学硕士论文时态工作流的时间异常处理算法 要集中在以下方面： 1 ) 对时间信息的建模。在时间信息的建模方面国内外已有很多研究成果，这 里不再一一列举。时间因素的引入对工作流系统的影响是广泛的，但目前的研究 多只集中于时间工作流过程模型上，只有为数不多的模型考虑到工作流的柔性、 动态性、异常处理等动态因素对时间信息建模的影响。p a n a g i o t i s 探讨了时间工 作流描述中对不确定性的支持以及基于时态数据库的实现方法【6 】，y id u a n 等基 于时态逻辑对柔性工作流进行建模【7 】，s a d i q 等考虑了在动态业务流程建模中时 间信息和动态性的处理【8 】，j o h a n ne d e r 等对时间信息建模时也考虑了在工作流执 行时时间信息的动态变化【9 】，时态工作流模型中则将基础元模型中的“活动”分 解成了任务( t a s k ) 和连接符( c o m e c t o r ) 【3 】【1 0 1 ，使得在建模时可以将状态规则和转 移规则分开描述，有利于提高工作流的柔性。 2 ) 对过程模型中时态信息的合理性、有效性的验证。可分为静态和动态两方 面的验证。b e t t i n i ，李建强，j o h a n ne d e r 等对时间信息进行了建模，并对活 动的时间约束、截止期限、执行时间等进行了静态的验证1 彤】；对工作流执行 时a a r j , o m v , c 提出了一种在过程执行中对当前活动结点的时间约束进行动态验 证的方法1 1 4 】，且基于活动延迟、顺序活动延迟和并行活动延迟，求得基本工作 流组件( o r - s p l i t , ，a n d s p l i t ，o r - j o h a , ，a m d - j o i n ) 的等价延迟【1 5 】。 3 ) 结合过程模型中的时态信息对模型进行性能分析。并通过对系统的工作效 率、资源负载等的计算，对活动的等待时间、实际执行时间和案例的完成情况进 行计算与预测【1 6 乏1 1 。李建强等在分析资源负载的基础上，提出一种预测案例最小 执行时间的算法【1 6 , 1 7 ；n u r m i 等在对系统中资源的工作性能和任务的等待时间进 行了预测t 2 0 j ；刘胜则通过对各种路由结构案例停留时间的分析，预测案例在资 源约束条件下的停留的情况1 2 n 。 而激烈的市场竞争和业务环境的动态变化，对工作流系统的柔性提出了越来 越高的要求。工作流柔性包括灵活性、动态性和自适应性三个方面，其中，工作 流系统对执行过程中出现的异常作出反应和处理的能力称为系统的自适应性 2 2 l 。为支持系统的柔性，学者们对工作流的过程元模型作了灵活性、动态性、 自适应性等各方面的扩展【1 0 ，2 2 之6 1 。但目前各种工作流系统仍缺乏对各种异常处理 的有效支持。国内外己形成的一些关于异常处理的描述和方法【2 7 琊】，包括基于 2 中山大学硕士论文时态工作流的时问异常处理算法 e c a 规则的方法【2 7 - 2 9 ，基于知识库的方法【3 0 1 、基于多层日志的方法【3 等，这些 现有的异常处理方法抽象层次大都比较高，只是给出了一些基本的思路。 总的来说，目前在时间信息建模和异常处理策略的研究上，存在以下不足： 1 ) 目前所见到的模型和处理方法往往只比较关注过程模型中变迁延迟的时 间约束，即任务的可能超时情况，而对案例的各种时间属性关注不足。而时态工 作流的观点认为案例有自己独立的生命周期属性，它是业务对象中数据有效期的 表示。案例在执行的过程中，既不能违反过程模型中定义的时间约束，也不能超 过它自身的截止期限。尤其在案例的完成时间比较紧的情况下，它有可能没有违 反过程定义的最长完成时间的约束，却不能在其截止期限之前完成。另外，现有 研究大都是以同一工作流的同一实例为前提的。而对同一工作流不同实例或不同 工作流不同实例的时间相关问题甚少涉及。 2 ) 发生超时异常时，相应处理方案往往只是给出了一些基本思路，没有全面 考虑活动、案例的最小、最大时间约束等各种时态信息和结合各种路由结构分析。 每个活动、每个案例有其完成所需要的最小时问限制，小于这个最小时间，活动、 案例将无法正常完成；每个活动、案例也有其规定的最大完成时间，超过这个最 大时间，活动、案例的完成将超时。而处理方案应该结合不同的超时情况和路由， 结构分析。 3 ) 往往只是给出使用方案进行异常处理的思路和简单的应用实例，缺乏通过 案例完成率、资源负载等参数对处理策略的执行效果进行的科学分析。我们不能 只通过对特定案例的调整结果，轻易地断言异常处理方案的效率。只有通过结合 对一些实验结果的分析，例如案例的完成率是否有所提高，资源的负载率是否可 以容忍等，才能得知这种方案的效率和性能。 1 3 研究的目标与意义 本文提出的算法主要针对活动违反其基本时序约束和其截止期限( 或期限时 间) 约束所导致的时间异常，主要目的是使案例在发生了上述时问异常的情况下， 仍能保证案例在其有效期内完成。还对算法进行了仿真和性能上的验证，力求提 高案例的完成率。其研究在理论上的意义在于： 3 中山大学颀士论文时态工作流的时间异常处理算法 1 ) 丰富了对工作流柔性的相关问题的研究。现有的异常处理方法抽象层次 大都比较高，远不能满足现实业务环境的需要。本算法针对各种路由结构给出了 详细的时问调整方案，且是可以在仿真平台中实现的，对工作流的时间异常处理 提供一种切实、可行的算法，这种方法具有良好的动态适应性和自适应性，能很 好地适应频繁的调度。而对时间异常处理的研究也有助于解决其他类型的工作流 异常问题。 2 ) 促进了对时态工作流相关问题的研究和发展。时态工作流将时间作为一个 维度引入工作流描述，对工作流时态信息相关问题的研究产生了广泛的影响。因 此异常处理和恢复也需要全面考虑时间的因素，例如案例的生命周期、过程模型 的时间约束等。 现有工作流产品对时效性和柔性的支持非常有限，而对时态工作流柔性的研 究顺应了社会实践对工作流理论提出的新要求，在生产制造、电子商务、电子政 务、物流等方面将具有广阔的应用前景。 4 本文章节安排 本文首先介绍了课题的研究背景，阐述了面临的问题并分析了相关研究的现 状。为了提高工作流产品的时效性和柔性，本文从业务过程对时间异常处理的需 求出发，在时态工作流模型的基础上讨论了时间异常的处理，提出一种时间的处 理算法，并通过一系列的仿真实验对算法的执行效率进行了检验。最后对全文进 行总结，提出了一些待改进的方面。全文共分六章，其中各章内容安排如下： 第一章，主要介绍了本课题的研究背景，对本文的研究内容和范围做出界定， 指出研究意义并进一步分析了研究现状。 第二章，分别介绍了本文所涉及到的技术理论知识和相关技术。 第三章，结合研究背景的需求，在时态工作流的基础上讨论了时间异常的处 理，给出了时间异常的定义和处理时间异常的一般步骤。 第四章，提出了一种完成时间调整的异常处理算法。提出了松弛度的概念， 详细给出了各种路由结构的完成时间的计算、调整方案。给出了一个简单的实现 例子，最后简单讨论了算法执行时的几个细节。 4 中山大学硕士论文时态工作流的时问异常处理算法 第五章，使用了我们基于时态工作流模型对仿真的需求开发的一个仿真工 具，设计了一系列仿真流程和仿真实验对算法的执行效率进行检验，并对仿真结 果的数据进行了分析。 第六章，对本文的研究进行总结，并指出下一步需要进行的工作。 5 中山大学硕士论文时态工作流的时问异常处理算法 第二章相关技术简介 2 1 时态工作流 2 1 1 时态信息的表示 目前在对时间系统的规范化模型研究较少。不同学者建立的时间工作流模型 中，时间的表示也是多种多样的。没有规范化的时间表示和时间运算作支持，会 给过程模型的深入分析和实现带来困难。因此在对时态信息进行建模、验证之前， 要先明确对时态信息的表示。 对时间轴结构的表示，我们选择离散模型，以方便我们表示计算机中的时间， 离散模型认为时闸轴是由一系列离散的时间点( t i m ep o i m ) 构成的，并且相邻的时 间点之问的距离都等于一个最小不可分割的计时单位c ，称这个单位为“时间量 子 ( c h r o n o n ) ，时间点就是一种最基本的一种时间元素类型。基于对时间系统 的定义和时间点基本类型，还可扩展出两种时态信息元素的类型：时间区问( t i m e i n t e r v a l ) 、时间距离( t i m es p a n ) 刚。时间区间表示为【t 驰t m ，其中t m 和t m 是两 个时间点，且t m t m ；时间距离是一系列连续时间点的个数，它表示持续的一个 时间段。 根据绝对时间和相对时间的概念和使用上的区别，我们还可扩展出几种时态 信息元素类型：相对时间点、相对时间区间和相对时间距离【3 】。 2 1 2 时态工作流简介 总的来说，现有的支持时间管理的过程模型在理论研究和认识上都存在一些 的通病，即基础模型薄弱、非系统性和片面性等1 3 1 ，具体表现在： 1 ) 对时间系统的规范化模型、工作流元模型及其时间属性研究较少，相关基 础研究薄弱，很多理论没有规范化的时间表示和运算作为支撑，没有全面系统的 6 中山大学硕士论文时态工作流的时间异常处理算法 元模型基础。 2 ) 目前对工作流时间约束的研究主要集中在过程建模阶段对过程模型的活 动腱程方面的时间约束和时序约束，忽视了其它维度上如资源、案例的时间特 性的研究，且现有研究大都是以同一工作流的同一实例为前提的，甚少涉及同一 工作流不同实例或不同工作流不同实例等情况下的时间相关问题研究。 3 ) 在时间因素对工作流柔性等相关方面的影响涉及较少。 在传统的工作流中，将工作流的组成元素分为三个维度：资源( r e s o u r c e ) 、案 例( c a s e ) 和过程( p r o c e s s ) p 6 】，如图2 1 所示。在这个三维空间里有三个基本概念任 务( t a s k ) 、工作项( w o r ki t e m ) 、活动( a c t i v i t y ) 。资源是活动的执行者，它可以是人、 程序或设备的代理，资源具有主动性；案例体现为要处理的数据或叫信息，它包 括应用数据和相关数据；过程是由一系列任务组成的；任务与案例结合( 实例化) 叫工作项；工作项与资源结合( 触发) 成为活动。 而在现有时间管理的过程模型中，常常只关注在过程维度中的任务执行时间 上，对工作流中其他维度上时间因素的影响，没有一个统一的认识。因此，时态 工作流强调，应在以上视图中引入时间维，对工作流中的所有组成元素及其关系 都赋予时问属性，全面考虑时间因素对工作流的综合影响。t i ：c s o i c a s ed h n e n s i o n d i m e n s i o n 图2 1 工作流的三维视图 在以上视图中增加时间维后，组成工作流的元素并不是多了或少了什么，它 体现在工作流的所有组成元素及其关系都具有了时问属性，就如同世闻万物处于 时问维中，每个事物及其事务问的关系都被打上了时间的印记。 【定义2 1 】( 时态工作流，t e m p o r a lw o r k f l o w ) 时态工作流就是将时间作为一个 7 中山大学硕士论文 时态工作流的时间异常处理算法 维度引入工作流系统，全面、系统地研究工作流系统中各元素及元素间关系的时 态特性及其规律【3 1 。口 2 1 3 相关概念介绍 这里只介绍时态工作流与本文相关的一些观点。要全面理解时态工作流请参 阅参考文献 3 1 。 传统工作流理论认为“过程决定案例的生命周期 3 6 】，而时态工作流的观 点认为案例有自己独立的生命周期属性，它是业务对象中数据有效期的表示。在 过程定义期，过程的含义是过程定义，w f m c 称它为w o r k f l o wt y p ed e f m i t i o n 【1 1 。 过程是易变的，我们可以用版本管理的方法管理过程的变化。过程模型的时间属 性包括：版本的创建时间、版本有效时间、实例化时间、实例有效时间等。过程 仅仅定义了案例的“最大 生命周期，案例的有效期小于或等于过程实例的有效 期，用户可以通过修改案例的有效期反映对案例处理紧迫性的要求，而不必修改 过程定义。案例的时问属性有：案例的创建时间、案例的有效时问、案例就绪时 间、调度完成时间、触发时问等。 传统工作流理论将“条件 映射为库所、“任务”映射为变迁【3 6 1 。时态工作 流进一步明确为：被调度f 分派给资源) 前的任务被映射为库所，由工作流引擎负 责调度，时间属性包括调度延迟时间s d ( s c h e d u l e d e l a y ) ，即引擎从任务就绪到 完成任务调度所花费的时间；调度后的任务被映射为变迁，有触发延迟时间 f d ( f i r e d e l a y ) 和执行延迟时间e d ( e x e c u t e d e l a y ) 两个时间属性，触发延迟是指任 务从分配到资源至资源选取任务所花费的时间，执行延迟则是资源执行任务的时 间。 一个过程是由一系列子过程、任务和连接符组成的。时态工作流把汇聚 ( j o i n ) 、分支( s p l i t ) 结构和相关约束( a n d ，o r ) 从活动中提取出来，抽象为连接符 ( c o n n e c t o r ) 。连接符可以看作是一种具有特定功能的任务。事实上，连接符在路 由控制的同时，也同时要负责数据的路由，还要负责案例数据必要的合并和复制， 总体来看，连接符的职责属于工作流管理的范畴，应该由w f m s 来完成，即它 的执行者是w f m s ，或更确切地说是工作流引擎。总之，我们将基础元模型中 的“活动”分解成了任务和连接符，任务承担的是“业务任务 ，是w f m s 分配 8 中山大学硕士论文时态工作流的时间异常处理算法 给用户去完成的，而连接符承担的是“管理任务”，是w f m s 自己要完成的，它 通常是自动化任务( 由w f m s 根据规则判定后续任务) ，也可以是人工交互任务 ( w f m s 通过入机交互决定后续任务) 。职责分离后，我们可以在活动中仅描述状 态规则，而在连接符中主要描述转移规则。这种职责的分离增强了任务的独立性， 有利于业务任务定义的复用( 与路由无关) 和柔性工作流的实现。 2 2 工作流柔性的研究 2 2 1 工作流柔性的概念 日趋激烈的市场竞争环境和企业的快速发展对工作流的柔性提出了新的要 求。灵活、动态地处理变更和异常的能力体现为工作流系统的柔性【4 】，概括地说， 能够支持工作流变更和异常的系统即可称为具有柔性的系统。工作流系统的柔性 主要表现在3 个方面：灵活性( f l e x i b i l i t y ) 、动态性( d y n a m i s m ) 和自适应性 ( a d a p t a b i l i t y ) f 4 j 7 1 ，有的学者将这3 个概念分别称为动态工作流、柔性工作流和自 适应工作流和 2 2 1 。也有学者在研究时对这3 个方面不加以严格区分。 系统的灵活性是工作流系统执行部分说明的过程定义的能力【4 】，其难点在于 如何对部分流程信息进行建模，在过程定义阶段使用不完全说明的方式涵盖各种 可能的情况 2 2 , 3 8 】。 系统的动态性是指工作流系统在业务流程发生变化的情况下做出相应的改 变的能力，其难点在于如何进行版本管理以及将运行中的工作流实例迁移到新的 工作流模型中 4 , 2 2 , 3 8 】。 系统的自适应性是工作流系统对过程中发生的异常情况做出反应和处理的 能力，其难点在于如何处理无法预料的异常情况【4 ，2 2 ，3 7 1 。 根据实现柔性的阶段的不同，还可以将工作流管理系统中的柔性分成选择柔 性和适应柔性两大类p 蚋。选择柔性是在工作流建模阶段对可预见的情形进行说 明和定义，从而给用户提供一定的自由度，其不足在于对所有可能的选择必须在 建模时预知；而适应柔性则是在工作流执行期间支持用户对工作流程进行各种适 应性的调整或更改，从而处理各种异常或紧急情况【3 趴。 9 中山大学硕士论文时态j 二作流的时间异常处理算法 根据适应柔性对工作流产生影响的时间的不同，适应柔性可分为型调整和实 例调整：型调整指对工作流的修改不影响当前运行的流程，除非整个流程从头开 始重新运行；而实例调整则意味着对工作流的修改可以“即时生效 ，因此也把 实例调整称为动态适应，也有人把这种强调动态适应的工作流称为“a d h o e 工 作流 3 8 1 。 2 2 2 工作流柔性的研究现状 我们在总结工作流柔性的研究成果时，还将按照文献 4 , 2 2 , 3 7 1 的3 个特性作为 标准进行分类分析。 1 ) i 作流灵活性的处理。邓水光提出了一种基于e c a 规则和活动组合的动 态工作流模型，用柔性活动封装流程中的不确定因素，并利用选取规则和组合规 则来约束柔性活动的具体化，还设计了一个检验算法来保证形成的流程的合法性 【2 矾。孙瑞志等对w f m c 参考模型的一般活动节点进行了扩充，定义一个称为“黑 盒”的新的节点类型来标识个语义不确定的节点，“黑盒”节点的语义一般要 在流程执行中，在工作流执行的一些结果逐渐明朗以后才能确定，这时“黑盒 才能变成“白盒 2 5 1 。 2 ) t 作流动态性的处理。朱文华等根据调整点和执行点的关系阐述了修改流 程对正在执行中的案例的可能造成的影响和实例的适应性策略【3 8 】。邢建川等阐 述了流程定义在动态修改后的演化和迁移策略【3 5 】。r e i c h e r t 等提出了一系列 保证流程在运行时修改操作的正确性的策略 3 9 1 。s m a r i 等也提出了可以有效支持 流程动态修改的算法，并对算法的效率用实验进行了验证f 4 们。曹化工等则讨论 了工作流管理中的版本管理技术【4 。 3 ) i 作流自适应性的处理。就是工作流对异常情况的反应和处理。这部分内 容将在下节详细叙述，在此不再重复。 l o 中山大学硕士论文时态工作流的时问异常处理算法 2 3 工作流时间异常的处理研究 2 3 1 工作流的异常处理 工作流异常可以定义为一种对正常工作流流程状态的偏离，这种偏离主要指 工作流实例运行状态与其原始定义的不一致，也可能指某些情况下与所期待状态 的不一致，异常处理是工作流领域研究的一个难点【5 】。工作流系统的异常处理是 指系统对过程中发生的异常情况做出反应和处理的能力，也称为系统的自适应性 【4 】，是工作流系统柔性的一个重要方面。 对于工作流异常有很多种分类的方法，例如按照异常的激发源可将异常分为 系统异常和任务异常，按对异常的知晓程度可分为可预测的异常和不可预测的异 常【3 2 】等。 对于可预测异常，通常指已充分了解可能出现的异常情况并可明确地定义异 常处理的过程，现有的处理方法包括基于e c a 规则的方法 2 7 - 2 9 ，基于知识库的 方法【3 0 1 、基于多层日志的方法【3 1 1 等。对这种异常有效、及时的反应和处理，可 大大提高工作流的执行效率。 而对于不可预测异常，通常在模型定义阶段不能准确预知，因此往往在发生 时需要通过人工干预来解决。m o u r a o 等提出了一种指导人工干预处理异常的方 法，力求保证人工干预的正确性和工作流系统运行的一致性【4 2 1 。对不可预测异 常的处理是工作流系统异常处理的难点所在，可尽量将不可预测的异常转变成可 预测的异常，然后对可预测的异常事件进行处理，在这个方面w e b e r 等人提出了 基于c b r ( c a s e 。b a s e dr e a s o n i n g ) 的方法，通过对过去异常处理案例的学习来处 理未知的异常，提高工作流管理系统异常处理的智能性【4 3 】。 a a l s t 等给出了一个异常处理的实现架构【4 4 1 。张志君等指出异常处理过程可 能采用的操作包括忽略、重试、修改模型、修改实例、后向恢复等，常见的描述 异常处理实现的方法包括失败补偿法和e c a 规则法【3 虬。孙瑞志等对异常处理过 程中的元素如活动、异常事件、异常处理策略以及处理措施等进行了形式化描述， 指出异常处理措施可分成忽略、取消、替代和补偿几种基本策略，并对不同的处 理策略下的处理过程进行了描述【3 4 l 。邢建川等也对异常检测模型、异常处理算 中山大学硕士论文时态工作流的时问异常处理算法 法进行了简单的描述【3 5 1 。g a j e w s k i 等提出的异常处理过程包括：终止发生异常 的活动；挂起相关的过程实例；定义新的过程模型；重启被挂起的实例或重新生 成新的实例【4 5 1 。 2 3 2 时间异常处理 由于实际业务过程大多具有时效性，因此处理工作流的异常需要考虑时间问 题。工作流时间异常是指在工作流实例执行过程中由于工作流系统内部或外部产 生的错误或意外所引起的工作流时序约束集与工作流模型不一致的情况f 5 】。 时间异常也有多种分类方法，按照违反的时序约束类型可分为活动延迟异常 ( 某一活动不能满足其期望的延迟时间限制) 、有限延迟约束异常( 整个流程不能满 足其期望的时间限制) 、期限时间异常( 某一活动或子过程不能满足其期望的开始 或结束时间限制) ：时问距离异常( 某两个活动之问的时间距离约束得不到满足) 、 固定日期约束异常( 固定日期与某一活动的绑定失效) 等【5 1 。 总结上述一些论文 3 2 , 3 4 , 3 5 , 4 4 1 提出的一些处理异常的措施，概括来说主要包 括：忽略、重试、取消、修改模型、修改实例等。对于发生了时间异常的过程实 例来说，以上措施可就其作用效果可分析如下： 1 ) 在某些情况下，如果发生了异常后继续按原来的过程定义执行也能消除 时间异常导致的时问不一致，则发生的异常可以忽略； 2 ) 重试是指对于出错的任务重新执行，直到任务运行正确完成或者超过了 设定的最大重试次数，在处理活动延迟超时异常方面这种措施不可行； 3 ) 如果出现的时间异常使得整个流程不能再继续执行下去，且已执行的行 为不需要进行补偿或没有办法补偿，则只能取消整个实例的执行； 4 ) 修改模型的措施会影响接下来生成的实例，这就涉及到工作流模型动态 演进、实例迁移和版本管理等问题，而在实际应用中，对一些偶发的时间异常的 解决往往不能轻易地修改模型的过程定义； 5 ) 修改实例可以采用补偿法或e c a 规则消除时间异常对当前实例的影响， 且不会影响其它实例的j 下常执行及过程模型的定义，因此往往可以明显提高工作 流的执行效率。 关于时间异常处理，目前一些处理方案往往只是给出了一些基本思路。 1 2 中山大学硕士论文时态工作流的时间异常处理算法 j o h a n ne d e r 等在工作流模型中引入选择活动和替换活动，提出动态调整工作流 计划( 包括改变后续替换活动的选择策略或删除后续活动的选择性活动等) 、提高 活动优先权、缩短后续活动调度周期、重新商讨截止期限等措施1 9 1 。而王远提出 了时间异常的分类方法，从比较通用的层次上提出了一系列异常处理算法，包括 扩展或修改产生异常的时序约束、调整产生时间异常的案例中未执行活动的延迟 时间等【5 】，但仅指出按比例调整的思想，并未给出调整未执行活动延迟时间的具 体算法，未详细考虑活动的路由结构、活动的最短完成时间、触发延迟和执行延 迟等因素。 在防止实例的超时异常方面，相关研究包括：j l e oz h a o 等提出了通过预测 任务执行时间、分配剩余时间和计算任务优先级等方法来提高工作流系统的效率 【4 6 1 ；j i nh y u ns o n 等也提出了一种寻找关键路径、静态分配剩余时间的算法【4 7 ， 4 8 1 ，将活动的计划执行时间与实际执行时间之差按一定的比例分配到后续活动， 并给出了较详细的实现方案；j o h a n ne d e r 还等以减少活动的的触发延迟时间为 出发点，从资源选择工作项的角度给出了一系列的选择算法【5 1 巧3 1 ，以保证实例按 时完成；p a n a g o s 等也在考虑资源竞争的条件下提出了一种动态的剩余时间分配 算法【5 4 1 。 2 4 工作流仿真简介 工作流仿真是对模型进行跟踪，利用离散事件驱动的仿真引擎模型，执行工 作流模型中的各项活动，自动推进工作流实例对过程，工作流仿真的目的是对所 定义的流程进行分析和评价，通过动态运行、结合仿真指标，分析仿真数据，发 现问题，改进或优化流程【5 6 1 。经过多次仿真运行，可以得到一系列关于工作流 模型运行的统计数据，如时间、成本和资源利用率等，根据这些仿真数据，可以 对模型的各项性能作出分析和评价。仿真的基本流程如图2 2 【5 7 1 。 中山大学硕士论文时态工作流的时间异常处理算法 仿真目标 构建仿真攫型 仿真环境设露 坊真工具平台 仿襄致 据记囊 图2 2 流程仿真的基本过程图 仿真的第一步是选择合适的仿真工具平台，并根据工作流过程模型和所关心 的仿真目标来构建仿真模型。仿真目标是指要进行分析的那些性能指标，如工作 流实例的平均执行时间、资源利用率等。 仿真模型除了具备过程模型的结构和时间约束等要素外，通常还包括以下模 块【5 6 , 5 7 】： 1 ) 流程实例牛成模块。用于按照假定的和现实相符的规律来生成流程实例， 比如泊松分御、均匀分布等。 2 ) 任务实例和资源调度模块。用于决定资源分配和资源调度方式。 3 ) 定时、延时和计时模块。仿真模型存在唯一一个绝对时钟，它和所有任务 相关联，既可以记录流程实例的开始和结束时间、任务实例的开始、结束、实际 执行和等待时间、资源忙和空闲时间等，也用于生成特定分布的时延( 流程实例 生成时延和任务执行时延) 。 4 ) 运行日志记录和统计模块。用于收集所有和将来分析有关的运行数据( 包 括时间数据和资源数据) ，统计模块则对这些数据进行统计分析。 5 ) 运行监控模块。用于协助用户在仿真运行时查看一些运行数据或信息。通 常以动画将仿真过程呈现给用户，使用户可以清楚地看见每个实例托肯的流动、 实例的等待、资源的调度等基本情况等，或可以通过预定义的监控面板查看其它 运行信息。根据收集的仿真日志数据可以对仿真结果进行分析和评价。 工作流仿真工具设计的仿真机制通常包括用户界面层、业务逻辑层和数据库 层，示例如图5 。3 所示1 5 6 , 5 9 。 常用的仿真工具包括c p nt o o l s ，e x s p e c t 等。目前很多关于柔性策略的研 中山大学硕士论文时态工作流的时问异常处理算法 究，由于抽象层次较高，只给出了一些基本的处理思路和简单的应用例子，常缺 乏通过仿真实验对执行效果的科学分析，但要了解处理策略的真正效率并不能仅 仅通过个别例子的运行结果来轻易地断言异常处理方案的效率。只有进行多次、 反复、全面的仿真实验检验，并对实验结果参数进行科学的统计和分析，才能比 较清楚地得知方案的执行效率和性能。 用户界面层 业务逻辑层 数据库层 图5 - 3 工作流仿真机制示例 中山大学硕士论文+时态工作流的时间异常处理算法 第三章时间异常处理方法概述 3 1 引言 为保证案例在其有效期内完成，针对案例在执行时某些任务时违反了其时序 约束导致时间异常发生的情况，需要采取一些异常处理措施。在本文我们只考虑 发生了时间异常后工作流的执行逻辑没有失效，即工作流案例还可以继续执行的 情况。 在这里我们约定工作流模型在执行前没有逻辑和静态时序约束的错误，即在 没有发生时间异常时，时态工作流网中过程结构及其时间约束是能满足模型所定 义的静态时问约束的。这是因为逻辑错误和静态时序错误应该在建模阶段，利用 模型逻辑验证方法和静态时序验证方法加以检查与解决，而不会将模型的错误延 续到执行阶段。这里所指的工作流时间异常是由于实例执行过程中的意外和错误 产生的。不应将模型的错误与工作流运行时发生的异常混为一个问题，在这一点 上很多现有的研究成果都没有进行区分。 根据工作流所处的不同时期，我们将对时间异常处理的操作分为定义期和执 行期两个阶段。针对工作流执行时可能出现的可预测异常，可以在定义期预先定 义一些异常处理措施，包括定义异