（计算机软件与理论专业论文）基于历史记录的工作流时间异常处理研究.pdf

基于历史记录的工作流时间异常处理研究摘要 论文题目 专业 硕士生 指导教师 基于历史记录的工作流时间异常处理研究 计算机软件与理论 谢婷 、余阳副教授 摘要 工作流管理系统主要是负责协调过程实例中的各个任务，以保证过程实例在 其有效期内的顺利完成。然而，过程实例在执行过程中需要调用各类资源，如人 员、软件系统等等，时间跨度很长，其初始化阶段定义的有效期约束难以确保。 一旦违反过程实例的有效期时，即发生时间异常，过程实例将以失败结束。另外， 异常激烈的市场竞争和动态变化的业务环境对过程实例的有效期提出了更高的 要求，加剧了此类时间异常的发生。因此，有效处理时间异常是工作流管理领域 的研究热点，也是实现柔性工作流的关键技术之一。 为了避免违反过程实例有效期这一时间异常的发生，本文提出了一种基于历 史记录的时间异常处理算法。该算法在尽量不增加资源工作强度的前提下，以提 高过程实例在有效期内完成的比率为目标，对潜在的时间异常进行提前处理。首 先，基于业务过程运行的历史数据，建立对应过程的时间概率模型以描述过程和 任务实例执行时间的不确定性。然后，算法通过分析过程的时间概率模型及当前 资源的负载情况，预测当前过程实例的后续时间消耗以有效识别潜在的时间异 常。当存在潜在的时间异常时，工作流管理系统则通过调整资源的任务调度策略， 对等待该资源执行的工作项进行合理的安排，尽可能地减小任务的排队时间进而 消除时间异常。一旦出现调整任务调度策略后仍无法消除时间异常的情况，则选 取紧缩任务执行时间最小的排队序列进行任务调度，并对特定任务的执行时间计 划进行临时性的紧缩调整以进一步弥补时间损失。最后，通过一系列仿真实验证 明启用基于历史记录的时间异常处理算法可以有效地预防和处理潜在的时间异 常，提高工作流实例按时完成的比率。 关键词：工作流、时间异常处理、历史记录、时间概率模型、调整策略 基于历史记录的工作流时间异常处理研究 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： ar e s e a r c ho nw o r k f l o wt i m ee x c e p t i o nh a n d l i n gb a s e do n h i s t o r yl o g s c o m p u t e rs o f t w a r ea n dt h e o r y x i e t m g y uy a n g ( a s s o c i a t ep r o f e s s o o a b s t r a c t 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 ) i sm a i l d yr e s p o n s i b l ef o rc o o r d i n a t i n g t h ev a r i o u st a s k si nt h ep r o c e s si n s t a n c et oe n s u r et h a tt h ep r o c e s si n s t a n c ew i l lb e c o m p l e t e dw i t h i ni t sv a l i dt i m e h o w e v e r , i nt h el i f ec y c l eo fap r o c e s si n s t a n c ea l l k i n d so fr e s o u r c e s ，s u c ha sp e r s o n n e l ，s o f t w a r es y s t e m sn e e dt ob ei n v o k e dt oe x e c u t e t h et a s k sa n dt h et i m es p a no ft a s k si sv e r yl o n g ，s ot h a ti ti sd i f f i c u l tt om e e tt h e o v e r a l ld e a d l i n eo ft h ep r o c e s si n s t a n c e o n c et h ed e a d l i n ec o n s t r a i n td e f i n e da t p r o c e s sb u i l dt i m ei sv i o l a t e dd u r i n gr u nt i m e ，at i m ee x c e p t i o nw i l lo c c u r , a n dt h e p r o c e s si n s t a n c ew i l lb ef a i l e d i na d d i t i o n , t h eo c c u r r e n c ef r e q u e n c yo ft i m e e x c e p t i o ni nw f m s si ss i g n i f i c a n t l yi n c r e a s i n gb e c a u s eo ft h e f i e r c em a r k e t c o m p e t i t i o na n dt h ed y n a m i ce n v i r o n m e n t t h e r e f o r e ，t i m ee x c e p t i o nh a n d l i n gi sa h o ti s s u ei nw f m s s ，a n di sa l s oak e yt e c h n o l o g yt ob u i l df l e x i b l ew o r k f l o w t h ep a p e rp r e s e n t sa na l g o r i t h mb a s e do nh i s t o r yl o g sf o rh a n d l i n gak i n do ft i m e e x c e p t i o n si na d v a n c e ，w h i c hi sc a u s e db yv i o l a t i n gd e a d l i n ec o n s t r a i no fap r o c e s s i n s t a n c e ，w i t ht h eg o a lt oi m p r o v et h eo n - t i m ec o m p l e t i o nr a t eo fp r o c e s si n s t a n c e sa t s m a l l e ri n c r e a s ei nr e s o u r c e sw o r ki n t e n s i t y f i r s t l y , i nv i e wo ft h ei n d e t e r m i n a c y q u a l i t yo ft h ee x e c u t i o np a t ha n dt h ee x e c u t i o nt i m e ，at i m ep r o b a b i l i t ym o d e lo fa p r o c e s sb a s e do ni t sh i s t o r yl o g si sb u i r t h e n , t h ea l g o r i t h mi st od e t e c tt h et i m e e x c e p t i o nv i aa na p p r o a c ho fp r e d i c t i n gt h ee x c e p t i o nb a s e do nat i m ep r o b a b i l i t y m o d e lo ft h ep r o c e s sa n dt h es n a p s h o to fc u r r e n tr e s o u r c ea l l o c a t i o n a ss o o na sa p o t e n t i a lt i m ee x c e p t i o ni sd e t e c t e d ，t h et a s ks c h e d u l i n gp o l i c ya d j u s t st or e c o v e rt i m e l o s s i ft h et a s ks c h e d u l i n gp o l i c yc a n ta d d r e s st h et i m ee x c e p t i o ny e t , c u td o w nt h e e x e c u t i o nt i m eo fs o m et a s k st om a k eu pf o rt h et i m el o s sf u r t h e ra n de n s u r et h a tt h e 基于历史记录的工作流时间异常处理研究 i n c r e a s e dw o r ki n t e n s i t yl i e si nas m a l lr a n g e f i n a l l y , e x p e r i m e n ts h o w st h a ti tc a l l r e m a r k a b l yi m p r o v et h et h r o u g h p u to fp r o c e s si n s t a n c e s k e yw o r d s ：w o r k f l o w , t i m ee x c e p t i o nh a n d l i n g ，h i s t o r yl o g s ，t i m ep r o b a b i l i t ym o d e l ， a d j u s t m e n ts t r a t e g y i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：缮查盛 e t 期：型里垒厶d 呈立 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：蒲描串 日期：纠。年月2 日 导师虢仓 日期：2 0 如年月2 日 基于历史记录的工作流时间异常处理研究第l 章引言 1 1 研究背景 第1 章引言 业务过程是由系列相关的任务组成的，这些任务按照一定的规则前后链接 在一起，相互协作，为特定客户或市场产生规定的输出【l 】。过程实例是业务过程 的运行实例，它具有独立的生命周期。从本质上看，企业的生产经营就是处理一 个个过程实例的过程。 自二十世纪九十年代以来，随着个人计算机、网络技术的普及和推广，以及 信息化建设的日益完善，工作流管理系统( 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 ) 逐步成为企业管理业务过程的核心信息系统。工作流管理系统主要是负责管理业 务过程并组织过程实例在不同的人员以及应用程序间进行路由，为过程实例的处 理提供后勤保障，确保各个过程实例在其对应的有效期内的顺利完成 2 1 。然而， 过程实例在执行过程中需要调用各类资源，如人员、软件系统等等，时间跨度往 往很长，并且参与过程实例执行的人员是高度自主的，每个人完成工作的方式和 耗费的时间都不相同，具有一定的随机性。因此，过程实例在初始化阶段定义的 有效期约束难以在运行阶段得以确保。一旦违反过程实例的有效期，即发生时间 异常，过程实例则将以失败结束。另外，日益激烈的市场竞争和动态变化的业务 环境对过程实例的时效性提出了更高的要求，一定程度上加剧了此类时间异常的 发生【3 】。由此可见，工作流管理系统对时间异常处理的需求日益迫切。 近年来，随着工作流技术的不断深入发展，市场上涌现出了各种各样的工作 流管理系统产品【4 ，5 1 。其中，针对过程实例在运行阶段发生时间异常这一问题， 部分产品，例如j e t f o r m 公司推出的企业工作流产品i n t e m p o ，已经开始提供了 简单的异常处理服务，系统可根据用户在过程建立阶段定义时间限制执行超时提 醒、任务删除等操作。但是，这些时间异常处理服务普遍存在处理粒度过粗、处 理力度过硬等问题，不能有效地处理时间异常，严重制约了工作流管理系统的发 展与普及。 基于历史记录的工作流时间异常处理研究第l 章引言 由此可见，研究违反过程实例有效期这一类时间异常及其相应的处理方法， 为工作流管理系统实现有效的事前机n ( p r o a c t i v e ) 以预防和处理此类时间异常， 对丰富工作流技术、提高企业的竞争力以及推动工作流管理系统的实际应用具有 重要的现实意义。 1 2 研究现状 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 ) 1 6 1 标志着工作流技术开始进入相对成熟的阶段， 随后市场上涌现出了大量工作流相关的产品。尽管工作流技术经过这些年来的发 展已经取得了一定的成果，但是从工作流管理系统的实际应用情况来看，其还远 未达到人们所期待的水平。其中，限制工作流管理系统发展的主要问题为：静态 的模型定义无法适应动态的运行变化【3 】。激烈的市场竞争和动态多变的业务环 境，对工作流管理系统提出了柔性的要求。工作流柔性包括灵活性、动态性和自 适应性三个方面。其中，工作流系统对执行过程中出现的异常做出反应和处理的 能力称为系统的自适应性【_ 7 1 。为实现系统的自适应性，国内外学者已对于异常处 理的描述和方法展开一系列的研究：包括基于e c a 规则的方法【8 1 们、基于多层 日志的方法【l l 】、基于知识库的方法【1 2 】等。 在工作流异常中有一类与时间相关的异常称为工作流时间异常。工作流时间 异常是指在过程实例的运行过程中，由于工作流系统内部或外部发生的错误或意 外使得过程模型中定义的时序约束得不到满足【1 3 1 。工作流时间异常管理则是研究 工作流执行的时间维计划，估计不同的任务执行延迟、避免任务过程实例违反 时间约束及针对时间违反的异常处理，以提高过程实例的完成率。目前，从业务 过程的有效建模到过程实例的动态处理，国内外针对工作流时间异常管理开展了 一系列的研究工作。 1 2 1 模型建立阶段 工作流模型包括了过程模型、组织角色模型等。在工作流模型的建立阶段， 2 基于历史记录的工作流时间异常处理研究第l 章引言 人们试图通过对工作流模型进行一定的扩展以处理工作流时间异常。 在过程模型的逻辑结构上，针对时间异常管理这一问题，e d e r 1 4 ，1 5 】等人引入 了替换结构和可选结构用于动态调整过程实例的执行计划，从而处理运行时发生 的时间异常。 在过程模型的时态建模上，e d e r 1 6 l 提出了对过程模型指定时间约束这一想 法，即把时间约束( 如任务的执行时间上下界约束、固定日期约束) 作为参数附加 到过程模型中，使过程模型具备明确的时序要求。其中，比较有代表性的研究成 果有：t i m ep e t r in e t 1 7 ，18 】和t i m i n gc o n s t r a i n t sp e t r i n e t p g , 2 0 1 。在相关时间约束的 过程模型的基础上，j i - is o n 2 1 】根据m m 1 排队论的理论，通过预测顺序、并行、 选择及循环等四种基本路由结构的等价执行时间，从而分配过程模型中各任务的 截止期限等时间约束，以降低过程实例在运行过程中发生时间异常的频率；考虑 到任务的执行时间和过程实例的执行路径的不确定性，e d e r 2 2 , 2 3 1 基于概率论的理 论知识，通过统计分析过程模型中各任务的历史执行时间记录，为每个任务建立 对应的延迟柱状图( d u r a t i o nh i s t o g r a m ) 扩充时态信息，提高建模的准确性。此 外，当时间约束指定好以后，需要对过程模型中时态信息的合理性、有效性进行 验证。其中，基于过程模型结构，对过程模型与时间约束的可能冲突进行的检验 属于静态验证。文献 1 4 ，1 5 ，2 4 ，2 5 对任务的截止期限、任务之间的时序约束等 进行了静态验证，给出了相应的验证规则。 在组织角色模型的资源分配上，为了减少任务因等待资源执行的耗时，文 献 2 6 提出了基于关键路径的资源分配算法，用于求解在一定过程实例到达率的 前提下执行关键路径上各任务的资源的下界。 工作流时间异常是发生在过程实例的运行阶段的。然而，综上分析，不难发 现：目前的研究仍把重点放在了设计工作流模型的建立阶段上，缺少对运行阶段 的实际关注。尽管人们提出了通过在过程模型中引入替换结构和可选结构以在运 行阶段动态地调整过程实例的执行计划，但是这些思想仍然停留在静态模型阶 段，它要求建模人员对过程实例的一切可能发生的情况进行建模，这种要求是不 符合现实意义的，一定程度上制约了工作流时间异常处理的发展。 3 基于历史记录的工作流时间异常处理研究第1 章引言 1 2 2 过程实例运行阶段 工作流时间异常是发生在过程实例的运行阶段的。鉴于这一事实，不少学者 开始立足于过程实例运行阶段，重新审视工作流时间异常的管理研究。目前，对 过程实例运行阶段的时间异常的管理工作主要从以下两方面进行： 1 ) 时间异常的检测。 在过程实例的执行过程中，动态的业务流程或不确定的任务执行时间往往会 破坏过程模型一致的时序约束，即发生工作流时间异常。而且，时间异常处理是 需要一定的开销的。因此，工作流管理系统需要在过程实例的运行过程中对时间 异常进行识别，尽早地检测到潜在的时间异常以降低异常处理的开销。其中， m a l = i a n o v i c 2 7 , 2 8 1 引入控制点集合c ，在实例运行过程中，通过集合c 中元素的增 减变化，动态检测潜在的时间异常；而针对工作流的不确定性问题，文献【2 9 提 出了满足、弱不满足和强不满足3 种状态的时间约束，改进了时间异常的动态检 测方法；p a n a g o s 3 0 】贝0 通过置信因子提前预测时间异常，提高处理的成功率，降 低异常处理的开销。 2 ) 时间异常的处理。 一旦发生了时间异常，就需要通过一定的措施以弥补时间损失使得过程实例 重新获得一致性状态，即时间异常处理。a a l s t 3 1 】提出了从过程维、资源维、数 据维3 个维度对时间异常进行处理的思想。目前，有关时间异常处理的研究则主 要是集中在过程维上。 针对任务的执行时间超出过程模型定义的时间约束这类时间异常，文献 2 9 , 3 0 1 提出了利用松弛时间动态扩展当前过程实例的后续任务集的时间维计划的处理 方法。为了合理分配松弛时间，p a n a g o s 3 0 】提出了利用松弛时间动态调整的4 种 策略：松弛时间完全分配给下一个将被执行的任务( t s l ) 、根据任务历史完成时 间按比例分配( p e x ) 、根据任务发生异常处理的开销按比例分配( p e s ) 、根据资源 的历史负载情况按比例分配( p l o ) ；而文献 2 9 贝t j 通过引入角色信任度评价技术， 定量分析资源的执行效率，综合考虑资源的工作能力和后续任务集定义的时间延 迟上下限范围分配松弛时间。 然而，上述分配松弛时间的处理方法并不能有效处理违反过程实例有效期这 4 基于历史记录的工作流时间异常处理研究第l 章引言 类时间异常。当发生违反过程实例有效期这类时间异常时，文献 1 3 ，3 1 ，3 2 针对 任务的完成时间这一时间约束，提出了对该过程实例的后续任务集的时间维计划 进行紧缩调整的处理思想，即按照一定的比例紧缩后续任务集的完成时间以弥补 时间延迟。其中，文献【3 2 】以过程实例的最短完成时间为压缩调整的下界，计算 后续任务集的松弛度k ，并对后续任务集的最差完成时间约束按松弛度k 进行压 缩，消除时间异常。然而，由于任务( 特别是人工参与的任务) 的执行时间是不确 定，在对任务的完成时间计划进行简单的按比例紧缩后，并无针对任务在新的时 间约束下能否顺利完成这一问题进行定量分析。 实际上，任务的完成时间属性可细化为排队时间和执行时间两部分【3 3 。3 5 1 ，其 中排队时间即任务等待资源执行的时间。一旦任务被引擎调度，分配到资源的工 作列表后，任务的排队时间和执行时间取决于资源的任务调度策略、资源执行任 务的方式以及资源自身的执行效率。所以，当发生时间异常时，可以通过调整任 务调度策略以缩短某些过程实例在某个任务上的排队时间，以弥补时间延迟 3 6 - 3 引。k a f e z a 3 9 1 针对不同的过程实例提出的3 种任务调度策略：先到先服务 ( f i f o ) 、优先调度截止期限最早的任务( e d f ) 和优先调度延迟最短的任务( s j b ) ， 可在一定程度上弥补时间损失，避免违反实例有效期这类时间异常的发生，但是 这些策略并不能适应工作流中的不确定性问题。 总结上述的研究，我们认为：针对工作流时间异常管理这一问题，尽管国内 外研究人员在过程实例的运行阶段上进行了一定的研究，但是仍存在以下不足： 1 ) 检测时间异常的标准普遍比较模糊。 一方面，由于业务过程模型中存在选择结构及循环结构，过程实例的执行路 径具有不确定性；另一方面，任务的执行时间也是不确定的。因此，不能简单地 用满足或不满足去判断某个时间约束，而是需要引入一种介于满足和不满足的中 间状态来描述这一复杂情况，重新对时间异常检测的标准进行定义。 2 ) 处理时间异常的方法可行性低。 一方面，目前部分时间异常处理方法仅仅针对某一任务的执行时间超出过程 模型定义的时间约束这类时间异常，提出了利用松弛时间临时扩展当前后续任务 集的相关时间维计划的处理方法，但是该处理方法仅适用于存在松弛时间的情 况。一旦发生违反过程实例有效期这类时间异常，那么该方法则无法处理；另一 5 基于历史记录的工作流时间异常处理研究第1 章引言 方面，部分时间异常处理仅仅通过临时紧缩后续任务集的执行时间约束以消除违 反过程实例有效期这类时间异常。然而，该处理方法加重了资源的执行负担，对 资源而言是不友好的。同时，该处理方法也比较主观，它忽略了资源的实际执行 能力，只对任务的执行时间约束进行一味的紧缩。但是，在资源实际的执行过程 中，工作流管理系统并不能确保任务能够满足紧缩后的理想时间约束而顺利完 成。因此，该处理方法的现实可行性比较低。 3 ) 缺乏对任务的时间消耗信息的全面分析与利用。 一般来说，目前的研究工作普遍都将任务的时间属性简单地统一成“完成时 间 这一时间约束来进行研究，并且任务的完成时间约束是以时间区间为基础类 型进行定义的。简单地以任务的完成时间的下界为约束，通过简单地按比例调整 任务的完成时间上界以处理工作流时间异常。这样的做法不仅忽视了任务的排队 时间和执行时间这两类时间属性的差异性，而且并没有充分利用任务的时间消耗 信息。例如，在相同的时间区间上，任务的完成时间服从不同的分布所表现出来 的平均完成时间是不一定相等的，在某些情况下甚至相差很大。因此，简单地对 完成时间区间进行上、下界的分析与研究，一定程度上扼杀了这种差异性，严重 影响了异常处理的效果。 1 3 研究的目标和意义 鉴于现今相关研究领域的不足，为了提前处理违反过程实例有效期这类时间 异常，基于工作流、概率论等理论和研究成果，本文提出了一种基于历史记录的 时间异常处理算法。该算法在尽量不增加资源工作强度的前提下，以提高过程实 例在有效期内完成的比率为目标，在过程实例运行阶段通过动态调整任务的调度 策略，缩短某些任务的排队时间以实现对该类时间异常进行提前处理。同时，在 必要的情况下，适度地对任务的执行时间进行一定的紧缩调整以进一步弥补时间 损失，消除时间异常。最后，通过仿真实验，验证算法的性能。 本文关于工作流时间异常处理的研究对促进工作流相关技术的发展有重要 的意义，可以概括如下： 1 ) 充分利用任务的时间消耗信息，确保时间异常处理结果的有效性。 6 基于历史记录的工作流时间异常处理研究第l 章引言 在多过程实例运行的环境中，过程和任务实例执行时间的不确定性一定程度 上严重制约了工作流相关技术( 特别是工作流时间异常处理技术) 的发展。为了更 好地消除这一不确定性的影响，同时，解决在相同的时间区间上，任务的完成时 间服从不同的分布所表现出来的差异性这一问题，本文提出了种基于历史记录 的工作流时间异常处理方法：该方法针对违反过程实例有效期这类时间异常，通 过学习相关工作流日志中对应过程的历史运行情况，分析当前过程实例的后续时 间消耗及资源在不同任务上的执行能力，进而指导任务调度策略及任务执行时间 计划的紧缩调整以弥补时间延迟，一定程度上提高了时间异常处理结果的可靠性 和有效性。 2 ) 提供了一种资源友好型的时间异常处理方法。 通过一味地紧缩任务的执行时间以处理时间异常的这类处理方法是资源不 友好的，这是因为：该处理方法实际上要求资源在较短时间内完成同样的任务， 即增加了资源的工作强度。为此，本文所提出的基于历史记录的工作流时间异常 处理方法是以调整任务调度策略为主，紧缩任务的执行时间为辅，实现对潜在异 常的提前处理。简单地说，该方法主要通过自动调整任务的调度策略，工作流管 理系统智能地向资源推荐一个任务的执行序列，以减小任务的排队时间弥补时间 损失，尽可能在不增加资源工作强度的情况下，消除时间异常，一举两得；一旦 出现任务调度策略调整后仍无法消除时间异常的情况，则在确保资源工作强度的 增加幅度尽可能小的前提下，通过过程的时间概率模型分析资源在执行不同任务 时所表现出的执行能力，并以执行能力的高低为指导进而对特定任务的执行时间 计划进行临时性的紧缩调整以弥补时间损失。 3 ) 丰富工作流时间管理的相关问题的研究。 工作流时间管理是研究工作流执行的时间维计划，以提高企业业务过程管理 的效率，其主要包括时态信息建模、时序一致性验证和时间异常处理三部分。由 于时间异常一直未能得到有效处理，目前学者们力求通过提高时态信息建模的准 确性以降低时间异常的发生。然而，静态的模型定义始终难以适应动态的业务变 化，人们是不可能在模型的建立阶段准确地预测出一切可能发生的情况，因此， 时间管理一直未得到突破性的发展。只有实现对工作流时间异常的有效处理，才 能降低建立阶段的时态约束要求，从而根本上解决工作流时间管理的核心问题。 7 基于历史记录的工作流时间异常处理研究第1 章引言 4 ) 促进关于工作流柔性的相关研究。 工作流过程模型固定不变的刚性结构一定程度上扼杀了企业在竞争环境中 所必须的动态性和适应性，如何在精确定义和柔性运行之间取得适当的平衡非常 困难。而本文所提出的基于历史记录学习的工作流时间异常处理方法则支持过程 实例在运行过程中任务调度策略以及任务执行时间计划的临时调整，这无疑是为 工作流柔性运行提供了突破口，有利于工作流柔性技术的进一步发展。 1 4 本文的组织结构 本文首先介绍了课题的研究背景，阐述了面临的问题并分析了相关研究的现 状。为了提高工作流产品的时效性和柔性，本文从业务过程对时间异常处理的需 求出发，基于工作流、概率论等理论和研究成果，在尽量不增加资源工作强度的 前提下，以提高过程实例在有效期内完成的比率为目标，提出了一种基于历史记 录的时间异常处理算法，并通过一系列的仿真实验对该算法的执行效率进行了检 验。最后对全文进行总结，提出了一些待改进的方面。全文共分六章，其中各章 内容安排如下： 第一章，主要介绍本课题的研究背景，对本文的研究内容和范围做出界定， 指出研究意义并进一步分析了研究现状。 第二章，分别介绍本文所涉及到的理论知识和相关技术。 第三章，结合研究背景的需求，讨论了在任务的生命周期中相关时间消耗的 实际情况，并提出了一个基于历史记录的时间概率模型以描述过程和任务实例执 行时间的不确定性。 第四章，在基于历史记录的时间概率模型的基础上，提出了一种基于历史记 录的时间异常处理算法，详细分析了算法的设计方案与主要步骤。 第五章，设计了一系列仿真流程和仿真实验对算法的性能进行检验，并对仿 真结果的数据进行了分析。 第六章，对本文的研究进行总结，并指出下一步需要进行的工作。 8 基于历史记录的工作流时间异常处理研究第2 章相关理论技术 第2 章相关理论技术 2 1 工作流基本知识 2 1 1 基本概念 工作流是指整个或部分业务过程在计算机支持下的全自动或半自动化网。 a a l s t 将工作流的组成元素分成了三个维度：资源( r e s o u r c e ) 、案例( c a s e ) 和过程 ( p r o c e s s ) ，如图2 1 所示m 。 羹薄维 藁仍豢 图2 - 1 工作流的三维示意图 在学术界里有关工作流基本概念的使用十分不统一，在此结合这个三维示 图，重申以下六个基本概念以便后续讨论：资源( r e s o u r c e ) 、案例( c a s e ) 、过程 实例( p r o c e s si n s t a n c e ) 、任务( t a s k ) 、工作项( w o r ki t e m ) 、活动( a c t i v i t y ) 。资源是任 务的执行者，它可以是人，也可以是应用程序或设备的代理，资源具有主动性； 案例体现为要处理的描述业务对象的数据，它包括应用数据和相关数据；过程是 由一系列任务组成的，运行中的过程则称为过程实例；任务与案例结合( 实例化) 叫工作项；工作项与资源结合( 触发) 成为活动【3 5 1 。 根据工作流管理联盟( w f m c ) 对于工作流管理系统的定义，工作流管理系统 9 基于历史记录的工作流时间异常处理研究第2 章相关理论技术 是一种能定义、创建和管理工作流运行的软件系统，即将现实世界中的业务过程 转化为某种计算机所能识别的形式表示( 如过程模型) ，并按其所定义的逻辑推进 过程实例的执行，为过程实例的执行提供后勤保障。 简单地说，工作流管理系统主要提供三种功能【5 】： 1 ) 模型定义功能。主要包括业务过程及其相关的时态约束的定义与建模， 资源的分配描述等。 2 ) 控制功能。在多过程实例运行的环境中，完成每个实例中工作项的生成 顺序和调度功能，协调实例间的运行。 3 ) 人机交互功能。在过程实例的运行阶段，实现各活动执行过程中用户与 软件应用之间的交互。 具体地说，在过程实例的运行阶段，工作流管理系统将解释相应的过程定义， 根据过程定义中的顺序依次创建工作项，并将工作项分发到对应资源的工作列表 ( w o r kl i s t ) 中等待资源去执行。当资源空闲时，资源则按一定的任务调度策略从 其对应的工作列表中获取某个工作项并执行。此时该工作项在资源的触发下激活 成相应的活动。一旦资源完成活动以后，工作流管理系统则继续按照过程定义的 顺序创建下一个工作项。由此依次反复进行，直至整个过程实例的完成。 2 1 2 过程模型 工作流管理包含很多方面，过程方面( h 0 控制流) 的管理是最主要的。而过程 模型就是对业务过程的抽象表示。过程模型的建立阶段( b u i l d t i m e ) 主要是完成 过程建模的任务。目前，对过程的建模可采用不同的建模工具【5 】。其中，a a l s t 在p e t r i 网的基础上提出了以工作流n ( w f n e t ) 作为工作流模型，并得到了广泛 的应用。 【定义2 1 】( 工作流网m ) ：当且仅当一个p e t r i 网p 岬，t ，f ) 满足以下条 件时，则被称为工作流网。 1 ) p n 有两个特殊的库所：i 和o 。其中f 库所是一个开始库所( s o u r c ep l a c e ) ， f p 且s i = f 2 j ：库所o 是一个结束库所( s i n kp l a c e ) ，o p 且o o = o ； 2 ) 如果在p n 中加入一个新的变迁r ，使f 分别连接库所o 和f ，即e t = o ) ， t o = f ) ，这时所得到的p n 是强接连的。 l o 基于历史记录的工作流时间异常处理研究第2 章相关理论技术 由约束条件1 ) 可知：工作流网必须具有一个输入库所f 和一个输出库所0 ， 且进入输入库所珀勺标记代表着一个过程实例的开始，而进入输出库所的标记则 意味着一个过程实例的结束。由约束条件2 ) 则可知所有的库所与变迁都位于库所 f 到0 的一条路径上。 工作流网关注业务过程的控制流维度建模，支持以下四种基本路由结构【4 1 】 以表示任务间的执行次序。 1 ) 顺序路由 如果任务一个接一个地执行，则称之为顺序路由，如图2 2 所示。任务t 1 、 t 2 依次顺序执行，t 2 必须在t l 执行完毕后才能执行。这由库所p 2 决定，p 2 对应 于t 2 执行前必须满足的条件。 p l t lp 2 t 2 p 3 图2 - 2 顺序路由 2 ) 并行路由 如果多个任务可以同时执行或按任意次序执行，则称之为并行路由，如图 2 3 所示。任务t l 和t 2 的执行次序有如下三种可能：两个任务同时执行；t 1 先 执行，随后是t 2 ；t 2 先执行，随后是t l 。为了让t l 和t 2 被并行执行，引入a n d - s p l i t 任务；并且为了同步两个或多个并行流而添加a n d - j o i n 任务，当且仅当任务t l 和t 2 都被完成后，任务a n d - j o i n 才能执行。 p 2 t 1 p 4 p 3 t 2 p 5 图2 3 并行路由 3 1 选择路由 如果一个过程存在多个分支，而且仅可以选择其中一个分支执行，则称之为 选择路由，如图2 4 所示。任务t l 和t 2 的执行次序有如下两种可能：t 1 被执行， 则t 2 不能被执行；心被执行，则t l 不能被执行。为了让t l 和t 2 仅有其一被执 行，引入o r - s p l i t 任务；并且为了确保当且仅当只有一个标志出现在p 6 中而添加 1 1 基于历史记录的工作流时间异常处理研究 第2 章相关理论技术 o r - j o i n 任务，当任务t l 或t 2 被完成后，任务o r - j o i n 才能执行。 p 2 t l p 4 p 3 t 2 p 5 图2 4 选择路由 4 ) 循环路由 如果某个或多个任务被反复执行，则称之为循环路由，如图2 5 所示。其中， 循环路由( 1 ) 中的任务t l 至少要被执行一次，相当于程序设计中的d o w h i l e 结 构：而循环路由( 2 ) 中的任务可以被执行多次也可以一次也不被执行，相当于程 序设计中的w h i l e d o 结构。 p l t l p 2 p 3 p lp 3 循环路由( 1 ) t l p 2 循环路由( 2 ) 图2 5 循环路由 本文的研究支持以上四种基本路由结构的组合应用，可以基本满足企业的业 务过程建模要求。 2 1 3 分配与调度 在工作流管理系统的协调下，每一个过程实例的完成必须伴随着一系列的分 配与调度工作，主要包括以下几项： 1 ) 工作流引擎调度。对任意任务来说，当其对应案例数据达到且满足相应 的时序约束时，则通过工作流引擎调度后，任务将被实例化成对应的工作项，并 且工作项被分配到对应资源的工作列表中。目前，在集中部署的工作流管理系统 中，引擎一般使用先进先出的方式工作，即引擎按照任务的先后到达次序进行调 度。 1 2 基于历史记录的工作流时间异常处理研究第2 章相关理论技术 2 ) 资源分配。当新的工作项到来后，若存在多个合适的资源，选择一个资 源并进入该资源的工作列表的过程称为资源分配。资源分配策略一般遵循空闲时 间最长资源优先的原则。 3 ) 任务调度。当资源忙时，工作项在该资源的工作列表中排队等待。一旦 资源空闲，选择一个工作项来执行的过程称为任务调度。通过任务调度，实现工 作项到活动的转化。常用的任务调度策略有：先进先出、后进先出、最短处理时 间优先、最短剩余处理时间优先和最早截止期限优先原则【4 l 】。 2 2 工作流时间异常处理简介 2 2 1 工作流异常的概念 在过程实例的运行过程中，异常事件的发生是不可避免的。简单地说，工作 流异常就是指任何与原过程定义的偏离【1 2 1 。这种偏离主要是指过程实例的运行 状态与其建模阶段所定义的状态不一致。发生工作流异常的主要原因为【4 2 】：一 方面，在工作流模型的建立阶段，建模人员无法全面地描述各种可能发生事件以 及相应的处理措施；另一方面，在运行阶段工作流模型发生了动态演进，即模型 发生了改变。 工作流异常可以从不同的角度进行分类【4 3 4 5 1 ，目前的研究普遍采用了文献 4 3 】的分类方法，即将工作流异常分成四类：基本故障、应用故障、可预测的异 常和不可预测的异常。其中，后两类是人们研究的重点。 1 ) 可预测的异常】：在模型的建立阶段，可以预见的偏离。通常建模人员 对这类异常的出现情况有充分的了解，并明确地定义了对应的异常处理过程。在 实际应用中，这类异常经常被用来描述在业务过程中很少发生的情况。这种做法 可以避免过程定义的复杂化，增强模型的可读性，提高过程的执行效率。 2 ) 不可预测的异常m l ：在模型的建立阶段无法预知的异常情况，通常需要 在异常发生时通过人工参与的方式对该类异常进行处理。 1 3 基于历史记录的工作流时间异常处理研究 第2 章相关理论技术 2 2 2 工作流时间异常的概念 每个过程实例都具有各自独立的生命周期，它可能在尚未完成业务目标时失 效。工作流管理系统必须在各过程实例的执行过程中保证实例在其有效期内顺利 完成。由于任务的执行时间和过程实例的执行路径的不确定性，这个保证分为保 证“相对”满足约束和保证“绝对 满足约束两个极端情况： 1 ) 时间约束相对一致。过程实例的执行路径按照时间最短执行时能满足其 有效期的时间约束。 2 ) 时间约束绝对一致。过程实例的执行路径按照时间最长执行时能满足其 有效期的时间约束。 工作流时间异常是指在过程实例的运行过程中，发生的时间约束不一致情 况。 造成时间异常的原因主要有两个： 1 ) 过程模型中是不能对过程实例的有效期进行有效的时间建模，它只是所 有实例的一个模板。然而，对于某些实例可能有比较特殊的需求，如当面临突发 事件的紧急预案，但过程模型中的时间约束在过程模型没有被修改的情况下是不 会改变的，这样就可能造成这些特殊的实例不能在其有效期内完成，从而出现时 间异常； 2 ) 实例执行过程中的意外和错误产生的，如某个或某些活动的执行超时或 延迟达到了一定程度而造成了时间约束的不一致。 需要注意的是：本文所研究的工作流时间异常并不包括因过程模型定义中的 逻辑错误或时间约束的静态不一致而导致的异常，即过程模型在执行前不存在逻 辑和时间约束的错误。这是因为逻辑错误和静态时间不一致问题应该在模型的建 立阶段，利用模型逻辑验证方法和静态时序验证方法解决，而不应将错误的模型 产生的错误状态与工作流时间异常混为一个问题【13 1 。 2 2 3 工作流异常的一般处理方法 工作流异常处理研究的是：当过程实例在运行过程中发生异常时，由工作流 系统提供的一套处理机制，通过人工和自动处理相结合的方式，对异常进行有效 1 4 基于历史记录的工作流时间异常处理研究第2 章相关理论技术 弥补处理以重新获得实例运行的一致状态。异常处理措施可以分成四种基本策 略：忽略、补偿、替代和取消，具体如下【4 2 1 ： 1 ) 如果在过程实例的运行过程中，在某个活动执行时出现了异常，该活动 己经执行的部分所产生的行为不影响其他活动的执行，并且该活动没有执行的部 分也不影响其他活动的执行，则可以用忽略策略，对此异常进行忽略处理； 2 ) 如果在过程实例的运行过程中，在某个活动执行时出现了异常，并且已 执行的活动己经产生了一定的影响，为了使得整个过程实例能够顺利完成，必须 对已执行的行为所产生的影响进行消除，这时才用补偿策略，即通过完成一系列 补偿活动以消除影响。 3 ) 如果在过程实例的运行过程中，在某个活动执行时出现了异常使得该活 动无法继续执行下去，但存在另外一个可选的活动或另外一条可执行的路径使得 过程实例可以继续执行，就可以采用替代策略； 4 ) 如果在过程实例的运行过程中，出现的异常使得整个过程实例都不能继 续执行下去，而且对己执行的行为不需要进行补偿或无法进行补偿，则只能采取 取消整个过程实例执的措施，此时该过程实例将执行失败。 根据异常所发生的具体情况，系统自动地半自动地采取以上的一种或多种 策略对异常进行事后处理。 2 2 4 工作流时间异常的处理方法 时间异常处理是一个古老的问题。早在工作流技术出现之前，l e e 等人就认 为【4 7 】一个可靠的系统须对异常提供两种基本的处理方法，分别是异常的预防和 异常的处理。异常的预防指“如何防止异常的引入或出现 ，而异常的处理指“在 出现异常的情况下如何保证一个过程按定义进行”。当前，针对工作流时间异常 的处理也主要从这两方面进行。 在工作流领域，时间异常的预防在很大程度上依赖于过程模型的定义，包括 过程的结构定义、时态信息建模等以尽可能地避免过程实例在执行过程中发生的 时间异常。例如，e d e r 【1 4 ，1 5 】提出的在工作流过程模型中引入选择结构和替换结构 的方法。一旦过程实例在运行期间发生了违反其有限期的时间异常，则通过改变 后续替换活动的选择策略或删除后续的选择性活动以弥补时间损失。结合到 1 5 基于历史记录的i 作流目问异常处理研究第2 章相关理论技