（计算机应用技术专业论文）工作流时间验证的研究与应用.pdf

大连理上火学硬士学位论文 摘要 时间问题是一个企业提高效率和信誉的重要因素。因此，时间的验证与分析成为当 今工作流研究的一个热点问题。在一个实际的工作流中，常常有一些可跨越活动和可替 换路径，对可跨越活动适当取舍和可替换路径适当选择，会提高截止期限被满足的可能 性。并且，在执行过程中，人们往往关心某些状态是否存在可达性，以及处理结果产生 的最迟时间截止期限。目前对工作流建模主要采用工作流图和p e t r i 网，普遍存在 的问题是当系统中结点过多时，容易引起状态爆炸。 为了解决上述问题，本文介绍了一种基于工作流图的时间模型，提出了使用四种关 键路径对工作流截止期限进行动态验证的方法。这种方法不必计算所有活动实例的截l e 期限，只需根据实际需要，针对部分实例计算，减少计算量，提高了工作流的执行效 率。在一个实际的工作流中，常常有一些可跨越活动和可替换路径，对可跨越活动适当 取舍和可替换路径适当选择，会提高截止期限被满足的可能性。 对活动增加截止期限的约束条件并验证可达情况，是人们在实际应用中对工作流系 统提出的新要求。本文提出了一种基于层次时间p e t r i 网的工作流模型。在基于t p n 的 工作流模型中增加截止期限约束条件，并将各个路由结构按照给出的规则分层提取，得 到只有顺序结构的h t p n 模型。模型转化的同时进行了物理可达性的验证；给出层次时 间树算法，利用得到的层次时间树对活动进行静态和动态时间验证。 在理论研究基础上，以f l e x w o r k 系统为背景，将上述两种时间验证思想相结合， 利用层次划分思想在建模阶段进行物理可达性验证，采用关键路径进行时i n 静态和动态 可达性验证，开发了一个工作流管理系统，理论研究成果在该系统中得到了较好的应 用。 关键词：截止期限；关键路径；t 刚；层次时间p e t ri 网；层次时间树 二 作流时间验证的研究与应用 w o r k f l o wr e s e a r c ha n da p p l i c a t i o na b o u tt i m e v e r i f i c a t i o n a b s t r a e t t h e r ea r es o m eo p t i o n a la c t i v i t i e sa n da l t e r n a t i v ep a t h s d e a d l i n ew i l le a s i l ys a t i s f yb y u t i l i z i n gt h e m 。w h e n t h ew o r k f l o w w o r k s , p e o p l e f o c u so ns t a t e sw h i 磕w i l lb er e a c h e do ra n d t h ed e a d l i n e 确em a i nm e t h o d so f m o d e l i n ga r ew o r k f l o w g r a p ha n d 涮n e t w h e n t h e r ea r e m a n yn o d e s ，s t a t t l se r u p t i o nm a yb a p p e n i no r d e rt oe s t i m a t et h el a t e s tf i n i s h i n gt i m eo f a n a c t i v i t yn o d e , at e m p o r a lm o d e lb a s e d o n w o r k f l o wg r a p hi si n t r o d u c e d 。t h e nw e p m p o 瓣f o u r k i n d so f c r i t i c a lp a t h s , w h i o ha r eu s e dt o v e r i f yt h ed e a d l i n eo f t h ew o r k t l o w 。b yt h em e t h o d ，船d o n tn e e dt oc a l c u l a t et h ed e a c l l i n e so f a l lt h ea c t i v i t i e s b u to n l yt oc a l c u l a t es o m e o f t h e m , a c c o r d i n g t ot h ef a c t s 讪em e t h o dr e d u c e s c a l c u l a t i o n ，a n di m p r o v e st h ee x e c u t i o ne f f i c i e n c yo f w o r k f l o w 。 t h ed e a d l i n eo f a c t i v i 每a n dr e a c h a b i l i t 3 , v e r i f i c a t i o nh a v eb e e nr e c o g n i z e da so l l eo f t h e m o s ts i g n i f i c a n tt i m el i m i t a t i o n so f t o d a y sw o r k f l o w s i nt h i sp a p e r , an e wt e m p o r a lm o d e l ， h i e r a r c h i c a l l y t i m e d p e t r i n e t o - i t p t , o ，i sp r o p o s e dt h r o u g hi n c o r p o m t i n gt h e d e a d l i n e c o n s t r a i n t si n t ot p n w ep r e s e n tr u l e st of e t c hs t r u c t u r e s h i e r a r c h i c a l l y + w k l et p ni s c o n v e r t e d o 王 弱垮 。p h y s i c a lt e a c h a b i l i t yi sv e r i f i e d 。a na l g o r i t h mo f h i e r a r c h i c a l l yt i m e d t r e e i sp u tf o r w a r d t h e n 妣m e t h o d o f v e r i f y i n g t h e t i m i n gt e a c h a b i l i t yi sg i v e n w ed e m o n s t r a t e t h e a p p l i c a t i o no f o u r m e t h o dw i t ha ne x a m p l e o nt h ef o u n d a t i o i l so ft h e o r e t i c a lr e s e a r c h w eh a v e d e v e l o p e da w o r k f l o wm a n a g e m e n t s y s t e m 碰ss y s t e m i sf l e x 黜b a s e do nt h e 潞t h r e e l a y e r ss t r u c t u r e i ns o m e 凌熊# 蕊t h i s s y s t e mh a sp e r f o r m e dt h ep r o d u c t i o n so f t h et h e o r e t i c a lr e s e a r c h ， k e yw o r d s ：d e a d l i n e ；c r i t i c a lp a t h ；t p n ；h i e r a r c h i c a l l yt i m e dp e t r in e t ；h i e r a r c h i c a l b , t i m e dt r e e - 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其它人已经发表或撰写的研究成果，也不包含为获 得大连理工大学或其它单位的学位或证书所使用过的材料。与我一同工 作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：到基建艮日期： 大涟理工大学硕士学位论文 弓l意 谶几年来，工作流技术的研究和应用已引起了许多研究人员和技术人员的普遍重 褪。像诗算极支持懿协商工作、炙缎办公、表擎传递、协作系统帮办公叁动毡这些壤念 狠翠就曩经提出，傲出子实现技术秘应用领域豹限蒯一再被虢捅。随着裔憋嚣2 微机静普 及，分布式网络通讯和业务流重组技术的发展，使得这一切将成为现实。因前，企业规 模在不断扩大，信息资源正以惊人的速度在不断增长，面对这样一个异构、分布、松散 藕合蘩豹计算邵凌、寝攒缝织、分布决策，激殿客户羧务器绪搦，联邦罨统帮分毒式 处理技术( w w w 、c o r b a 、o l e 、j a v a ) 。无不预示着以前单一的集中的信息处理 方式的终结。实现这一切，首先簧建立一个相关任务能以有效的集中管理方式执行的异 构分蠢式执蠢琴壤，建毖工作淀譬壤系统孕弯产袋了。 工作流技术律为糯代企业实现过程管理与过程控髑的一颁关键技术，为企业业务过 程提供了个从模垂! 建立、管理到遮行、分析的完整框架；i 司时，工作流管理系统通过 一套集成他、客户操作的软件工具为这个框架提供了全过程的支持。 实瑷工 筝滚戆胃嚣羲器窝对工佟流管理酶藏璃实施，需簧对王 睾雾蠡瀵鍪进行合理毪 验证与分析 1 】。时间问题是一个众业提高效率和信誉的重要因素。因此，时间的验证与 分析成为当今工作流研究的一个热点问题 2 ，3 ，4 ，5 ，6 】。 弱多 诲多学者罄谯对活魂秘过疆戆裁止裁隈麓遂避嚣磅突。e d e r 2 撬爨了一静较努 的时间建模方法，并避于亍了严谨翰静态验证，德动态验证方法较粗糙。m a r j a n o v i e 3 提 出了动淼验证方法，但两个活动间若存在大量其他活动，则动态验证的计簿量会比较 大。e d e r 4 l 对截止款限鲍约束限制在一个时间段走，即聚耀上、下爨遴行约束。 s o n 6 789 1 分爨采鼷c p i 算法帮 c s f n 法，利爝藏露l 臻穆蠢我工孛# 流疆孛静筵键路径； 并采用b q n j g 法对活动截止期限进行了静态验证，估计活动截此期限。国内举者对截止 期限也脊一些研究【l ，5 】，大多都集中在使用p e t r i 网方法。 实筏工佟滚的露绺撬嚣帮霹王 睾滚管理戆袋凌实夔，霉簧鼹工终滚模鍪滋学合瑗整 验证与分析【l j 。m a t t h i a s 在基于时间和优先衩的扩n p e t r i n ，使用状态等价方法、优 先权原则和最大阶原则证明系统是否等价，为得出p e t r i n 0 0 状态的不可达性提供了充分 的条传 1 0 1 。在p 酬阙中增由b 事件执行时闯对、嘏迟触发时间对等时阕约束条髂，验诞 了瓠行净捌中事辞豹掰执彳亍往【li 、1 2 1 。通过分簇瓣惑意细纯嶷迁节点窥健鬻节杰，揭 示了工作流过程的执行阶段的任务分配与参与者状态之间的关系【1 3 。 工作流时间验证的研究每i 应用 在工作流实际执行过程中，人们彼往关心某些状态是褥存在w 达性。例如，在客户 投瞽摹系统牵，客户更关心授诉辩的处骥臻栗# 否产撰，对簸瑾投谣静过程著不憋兴趣。 同时，客户还关心处理结果产嫩的最迟时间截止期限。目前对工作溅建模点要采用 工作流图和p e t r i 网，普遍存在的闯颓是当系统中结点过多时，容易引越状态爆炸。 为了解决上述闻题，本文掇怒了嬲群验 燕方法，当活动执纾孵闯是弱定焦豹时候袋 用第一种方法，当执行时间是浆区间内的不定值时采用第二种方法。根据实际需求， 将薄糖方法耀缝会，怼蒸于x m l 熬2 1 2 传浚管理系统遴露了辩阖上戆静态秘动态验涯。 第一种方法采用工作流图的建模方法。一个工作流的建立最终是为了实现动态运 行，因j 逢程运行封孪动态验证工 譬流豹致往格外重甏。焉阻上文献有豹嚣迸行了静态验 证，有的虽进行了动态验证， 鲢工作摄大、方法粗糙。针对以上阎题，文中提出了一辇孛 将工作流图映射为e b f 圈、e b s 图、e w f 囤和e w s 阐的方法，定义了这四个图上的关键 路径，并零月这四个关键路径砖工佟滤进行了较详缨麴魂态验证。 第二种方法在基于时间p e t r i 网的工作流模型中增加截止期限的约束条件，提出了 按照貉交缩襁进撂工馋流努屡静愚戆，哭需按照文串_ 舞鑫鹣蔑鬟g 将并发缨梅、选择结构 和循环结构分层提取，得到只有顺序缩构的层次时间w 匝网( h i e r a r c h i c a l l yt i m e dp e t r i n e t ， 疆霹) 工干譬流模黧。t p n ( t i m e dp e t r in e t ) 转亿成h t p n 的过程就是物理可达幢 的验证过程，然后采用层次时间树( h i e r a r e h i e a u yt h n e dt r e e ，h t r ) 对截止期限进行 了静态和动态验诞。 将两秘方法攘结合，在蒸予酵阗p e t r i 麴兹工传滚模毽孛增趣截丘颓羧懿绞索条 件，按照分层提取的方法对模型进行了物理可达性的验证；取得各子网的关键路径，进 季亍静态验谣，对不可迭豹状态通过调蘩挠东路径和截丘麓隈静约柬条俘，实现辩阔静淼 可达；在工作流实际执行阶段，根据当前时间，对模型中的具体滔动进行时间动态可达 往的验证。此验证思想应厢在了本实验窟的工作流管理系统中。 2 大连理工大学硕士学位论文 1 工作流时间管理综述 1 1 工作流系统 1 1 1 基本概念 十几年来，不同的研究者对工作流分别提出了不同的定义。到目前为止，对于工作 流仍没有完全统一的定义。列举如下一些有代表性的定义，从不同的角度对工作流概念 进行了描述： 工作流管理联盟的定义【1 4 ：工作流是一类能够完全或者部分自动执行的经营过 程，根据一系列过程规则，文档、信息或任务能够在不同的执行者之间传递、执行。 g i g a g r o u p 的定义f i5 】：工作流是经营过程中可运转的部分，包括任务的顺序以及由 谁来执行、支持任务的信息流、评价与控制任务的跟踪、报告机制。 i b m a l m a d e n r e s e a r e h c e n t e r 的定义 1 5 】：工作流是经营过程中的一种计算机化的表 示模型，定义了完成整个过程所需用的各种参数。这些参数包括对过程中每一个单独步 骤的定义、步骤间的执行顺序、条件以及数据流的建立、每一步骤由谁负责以及每个活 动所需要的应用程序。 以上这些对工作流的定义是用非形式化语言对工作流所进行的描述，虽然各有不 同，但基本上都达成了这样的一个共识：工作流是经营过程的一个计算机实现，而工作 流管理系统则是这一实现的软件环境。这些工作流的定义分别反映了经营过程如下几个 方面的问题，即经营过程是什么( 由哪些活动、任务组成，也就是结构上的定义) 、怎 么做( 活动间的执行条件、规则以及所交互的信息，也就是控制流与信息流的定义) 、 由谁来做( 人或者计算机应用程序，也就是组织角色的定义) 、做得怎样( 通过工作流 管理系统进行监控) 。 图1 1 显示了与工作流相关的基本概念及其联系 1 6 】。 业务流程( b u s i n e s sp r o c e s s ) ：在功能确定的组织结构中，能够实现业务目标和策略 的相互连接的过程和活动集。例如：公文处理过程、投保过程及项目开发过程等。 活动( a c t i v i t y ) ：指的是工作流中的一个逻辑步骤或称环节。它包含的信息有：开始 和结束条件、可参与到此环节中的用户、完成此活动所需的应用程序或数据以及关于此 活动应如何完成的一些限制条件如时间上的限制等。 工作流管理系统( w f m s ) ：一种能定义、创建和管理工作流执行的系统。就是将现 实世界中的业务过程转化为某种计算机所能识别的形式表示( 工作流逻辑) ，并在此形 3 工作流时间验诳的研究与应用 式褒示浆驱动下竞藏工终滚静挠行耪管理。使掇宅霹酸燕努零l 矮金泣资源，有效逡舔踪 工作过程，提黼工作过程定制的速度与质擞。 戴务漆疆 圈1 1t 作流灏本概念之间的关系 f i g i it h e r e l a t i o nb e t w e e nb a s i c c o n c e p t so f w o r l d l o w 工具 过程定义( p r o c e s sd e f i n i t i o n ) ：业务过程的计算机形式表示，它怒义的是过稳运 行申涉及到的各种参数：如业务过程的开贻和终止条件、各个工作环节( 见后面的解 释) 及相互之间的控镑流动与数据流动关系等。不同豹w 蹦s 所实现瓣工作淀禳羹是 各不相润静。褒举期静其有工作流管理功熊鹣系统中，这种表示是通i 雯“硬编礴”静方 式究成的，因此姆致修改工作流程上的困难。在后来的w f l v t s 中逐渐出现了使用有向 图、条件化有向嬲p e t r i n e t 、活动模型、语离动作( l a n g u a g ea c t s ) 理论、基于约束条 等鹬形式语言文法表示浚及蒸予霉耘懿甄溅示等。这鍪系统一簸螯爨侯育一令霹携纯 的弛务过程建楼二c 具，以使用户能够以比较盥观的方式对实际的业务过程模型进行建 模，并得到相应的形式化表示。不同的过稷模型各有其不同的特点，一个好的模型成该 鸯e 较强的接述能力、翕于使用、易于修改以便筵够逶残不凝变佳懿王终繇壤魏要求。 过程，活动羹捌( p r o c e s s a c t i v i t yi n s t a n c e s ) ：指韵避莱个工作流避稷的一次执行。 在实例的执行过稷中，w f m s 将解释相应的j 蹬程定义，生成有关的活动并根据过程定义 中的控制规则协调这些活动实例之间的顺序关系，网时根搬数据流动关系的定义完成滤 - 4 大涟埋工大学硕士学位论文 动实例之间的数据传送。一般情况下姆一个活动实例都将表现为一个工作项 ( w o r k i t e m ，窀蒋由策个或莱缰用户受责完成) 。因魏祆用户静螽度来说实饼豹执行实 际上是由用户调用相应的应用程序对他所涉及的那个环节有关的数据进行处理，处理完 之后由w 0 v i s 根据相应的结果决定激活詹续的那个环节并生成相应的工作项，同时通 知与此有关的男些用户对之邀行处理。由此依次艨复进霉，直至整个：过程熬党成。巢个 用户所负责的所有工佟项将构成其工作项列表( w o r k l i s t ) 。那些被称作是工作流威用 数据酌，其孛露一部分将露王俘滚避程定义一道麓予控露l 王终浚瓣瑟嚣。这部分数豢一 般被称作是工作流相关数据。 1 1 2 工髂流系统豹分类 工作流系统根据其用途和技术的不屈，可分为以下鳗辨： ( 1 ) 管理工作流( a d m i n i s t r a t i v ew o r k f l o w ) ：用于执行简单协同规则的可重复和 越预测戆滚程，它匏掇学步骤窝规_ # 楚事笼定义憝，不要求控裁复杂滚疆翻游滔多令詹 息系统。例如申请学位、登记车辆。 ( 2 ) 特羯王佟流( a d h o e w o r k f l o w ) ：多潮予撬行办公流链理弊常情况，能够提 供含作协同功能，但不控制各工作顺序，支持它的w f m s 也称为群件。 j 萎? = e w f 专d ( i ，d ，i 3 e m s = e 七硅g ，j x i j 并发结构 条件选择结掐 e 嚣= m a x e 十d ( 川g i ，i 叶办 e w f = m 叛0 酝”+ 露( 费 g i ，i - + j e b # = i t l a x 拯& p 十d ( ，) iv i ，i 一， 嚣；= m a x 黾f + 露( 引v i ，i _ 办 露0 ，= m a x e m 十d ( 川g i ，f _ _ ， 可蘩抉选择结橡 嚣= m a x e s 士d q ) t v i ，i 啼处 嚣w = m a x e w ，? 十d ( 刃 v # ， 一歹 耳咐= m a x e w ，十d ( ，) f v i ，i 砷 回魑进笠煎矍 顺序结构 并发结构 l 8 f = e e v + d ( 歹x i _ j l e s = 蠢日+ 菇( d ，i j l w r = e f + a ( i ，n ， + j 三摊= m i n l # + d o ) l v ，i - - - , 蠢 l w 。m i n l w p + d ( ，) j v f ，i 呻， 纽：- 三竺垫坚坚壁! ! ：盟! ! ! ! 1 2 丑 = m a x l + d ( j ) v i ，ioj 条件选择结构 五= m a x l + 矗( 歹) l g i ，i 哼歹 五m = m i n l m ，+ d ( _ ，) j v i ，i ， m = m i n l m ，十d ( j ) l g i ，i 呻， e # ，= m i n 滔十矗( 歹) l v i ，i 一， 可静换选择结构 氏= m a x 留w + d ( 力l v f ，f 叶办 e w l ? = m i n e 盯十d ( 川v i ，i 叶， 1 5 ：e 作流时间验证的研究与应用 2 1 2 时间工作流图的说明 工作流图按表2 1 给出的公式计算出的 值和l 一值如图2 2 所示。这个时间图中最重 要的信息是活动的e _ 值，特别是活动l 的e 一值。因为l 是最后执行的活动，因此它的结束 时间就是整个过程的结束时间。 特别的，整个工作流图的最早结束时间可能是2 1 ，即e 。此情况发生时，d 和i 不 执行，j 被执行，而k 不被执行，并且执行包括b 的条件分支被执行。另一方面，如果所 有的可删除活动被执行，工作流结束时间最早为5 l ，最晚为7 2 ( 例如e ；冒) ，关键取决 于可替换活动和条件分支的选择。 活动的l 一值表明，过程执行时，包括此活动的路径是否会引起时间错误。尤其， 如果一个活动的所有l - 值都大于相应的e 一值，那么，包括此活动的各路径中很可能存 在不违反时间约束的路径。但是，如果存在l 一值小于相应的e _ 值，那么就存在可能引 起时间违反的路径。例如，如果在运行阶段c 被执行，而整个过程的截止期限定为 2 1 ，那么这个截止期限会被违反。 图2 2 经过建模阶段计算后的工作流时间图 f i g 2 2w o r k f l o wt i m e dg r a p ha f t e rt h eb u i l d t i m ec a l c u l a t i o n s 2 2 用工作流图描述的工作流模型 在一个实际的工作流中，常常有一些可跨越活动和可替换路径，对可跨越活动适当 取舍和可替换路径适当选择，会提高截止期限被满足的可能性，因此，文中以e d e r 的 一1 6 大连理工大学硕士学位论文 建模方法 2 】作为研究基础。一个时间工作流的正确性主要取决于结构、语义和时间约 束。关于工作流的静态验证问题，已在文献 2 】和 4 5 】中论述。因此，本文是在此基础上 对时间工作流截止期限进行动态的分析和验证。 在如图1 所示的工作流模型中，i n 和o u t 分别表示工作流入口和出口。a 是开始活 动，执行需要2 个时间单位；a 之后是条件分支( c o n d i t i o n a ls p l i t ) ；k 之后是可替换分支 ( a l t e n m t i v es p l i t ) ：b 、l 是可跨越活动( o p t i o n a l ) ，以右上角的空心圆表示：d 之后 出现无条件分支( u n c o n d i t i o n a ls p l i 0 ，e 、f 并发执行；r 是终止活动( f i n a la c t i v i t y ) 。 氧鳓啦姆 幽r 獭。秘逝镑。 e 岛 o 茸 e b 誊二b b 誊 。蚤礤i l 薄口 1 e 抵跨+ 缸 静舞 图2 3一个时间工作流图例 f i g 2 3a ne x a m p l e o f t i m e dw o r k f l o w 图2 4 是活动结点的时间描述。a c t i v i t y 是活动名 称；d u r a t i o n 是建模阶段活动的执行延迟；o p t 标记可跨越 活动；e l 表示此活动的最早最迟结束时间；b w 表示若 出现条件分支，则选择最优儇差分支运行；f s 表示跨过， 保留所有可跨越活动，并且。选择最优最差可替换路 径。 图2 4 活动结点时间描述 f i g 2 4a na c t i v i t yn o d e i nt h et i m e dw o r k f l o w g r a p h 活动结点形式化地描述为：n o d e ( i ) = ( d u m t i o n , e ，l ，o p t ) ：这里， e = ( e b f , e b s , e w f , e w s ) ，l = ( l b f , l b s ，l w f , l w s ) ，o p t o ，1 ，o p t = 1 表示i 是可跨越活动， o p t - - 0 时表示i 不是可跨越活动。 图2 3 中的工作流在建模后，通过计算 3 】，得到各结点的时间描述，如表2 2 所 示。 1 7 工作漉时间验证的研究与应用 缓设该羔终流嚣始裁程豹l l 誊凝必0 煮，裂实穰鲠：懿工终滚动态模鍪专主述模黧稷 潮。以下对实例截止期限的动态验证都建建立在此模型的基础之上。 表2 2 活动续点豹时间接述 2 3 截盘期限瓣动态验逶方法 在工作流中，活动结束的最迟期限称为截止期限。潜活动实例的结束时间超过丁这 个墩迟期限，则称该活动违反了此截止期限的时间约束。 倒麴：产瑟菠囊密臻麓戆，窖户蠢厂家役潺对，客户整求厂家奁7 天凌答复。厂家 程溅常处理的情况下，不能在第七天内答复，但是如果省略其中的鲅环节或者缩短某 些环节的处理时间，则可以实现在截止期限七天内答复。所以，在客户提交投诉后，幼 态刿甄截止甥殴跳褥潢足，楚保证厂家经鬻避程鞭剥进行敕必要蘩律。函照，对王终漉 截止麓隈进行动；蠢验证授其熬溪。 2 3 1 执行时间的戳止期限 对于一个王作流计划，王僚漉设计者能够分配各个瀣渤和整个工馆滚过程的执行时 蠲酾截止麓疆。遴鬻，实酝执符辩麓簿台瀵渤静颈绉计或卷诗菇静魏嚣瓣阂。蘧舔，许 多活动的执行时间值。在仿真过程中被详尽的描述和使用。这些值或者来源于以前执行 的缀验值，或者由专家根据自跫的经验和期凝分配给活动的。特别的，最常使用的时间 蕊毽摆：最多辩阕、最多辩阉鞠最叛繁羲费麓次数。 另一方面，活动和进程酶截止期限各翻满足箕允许鸯勺最大执行时间。这些截止期限 也称为确切截止期限。在过程的时间建模阶段，这些截止期限是相对于过程的开始时间 。1 8 大连理工大学硕士学位论文 描述的。在过程实例化阶段，利用日历把所有的相对截止期限转化为绝对时间点，修改 分配的截止期限或者分配新的截止期限。 在工作流计划中，没有必要给每一个活动确定截止期限。事实上，根本没有哪个截 止期限可以分配给活动的。但是，把截止期限和活动联系起来是有好处的。这样做的很 重要的原因是能监测到活动和包括这些活动的进程的执行过程，从而，当活动发生延迟 时，能预先探测出违反截止期限的活动。这种截止期限称为内部截止期限，在后文中我 们将描述在建模阶段和实例化阶段，这些截止期限是如何被计算出来的，以及在运行阶 段，我们是如何使用它们的。 活动的执行时间和截止期限可能不一致，这点很重要。在现有的工作流管理系统 中，它们是如何被使用的呢? 找出以上两者的区别，对某些实例是很有用的。当超过某 些截止期限可能会引起大量的时间消耗时( 例如反转整个过程) 。在那些实例中，当一 个活动执行时消耗的时间超过了工作流计划中分配给它的时间时，就要采取预先探测方 法来估计截止期限被满足的可能性，修改工作流参数，改换适当的参与者和过程管理 者。 2 3 2 时间计算 在工作流计划中给活动分配了执行时间和截止期限，对时间进行计算，从而计算出 过程中活动的最优和最差的开始和结束时间，计算出活动的松弛时间，更新现有的截止 期限，把时间信息转换成绝对时间，等等。尤其，在以下三个阶段要进行时间的计算。 建模阶段，时间信息( 活动执行时所需的时间和外部截止时间) 被记录下来，并 且，计算工作流的一般时间信息。而且，基予以上时间信息和过程结构，计算几个活动 的开始和结束时间。过程设计者可以利用这些信息定位时间瓶颈和进行进一步优化工作 的候选人。 过程实例化阶段，过程被实例化，并产生它的时间信息。利用时间日历这些时间信 息被描绘成绝对时间点。此外，整个过程的截止期限被详细的描述出来，而且内部活动 的截止期限被计算出来。 1 )在运行阶段，过程的执行过程受到监测，在各种条件和替换执行点处，随着 做出的决策一起，活动执行时间也被记录下来。当活动被列在工作列表时，那些时间信 息被顺序的使用来调整内部截止期限。 很明显，外部截止期限的分配是个反复的过程。设计者首先要分配活动的执行时 间。在过程建模阶段，时间的计算后来被用来计算整个过程的执行时间和所有活动的相 1 9 二作流时间验证的研究与应用 对谴霉。然惹，设计纛霹戳对一些淫动爨乡 邦截燕期限重颡赋馕，再次计算瓣瓣售惠。 如果外部截止期限不得到满足，设计者可能要修敬工作流静结构或者修改截止期限。 从以上可以看出，复杂活动或者包括顺序、w 替换、条件、可删去和并行执行的予 过程能够按照上葱的步骤计算出来。但是，对于德环，我们需要关于重复次数的额外信 惠。设计者可隧按以f 三耱方式鑫辍这方嚣信惑。 1 ) 如果重复次数固定，设计省可以准确的分配这个数字。 2 )设计者可以提供需要的黧复的最小值、最大值和平均值。从而得到循环体所 嚣要静瓠行豺阉。 3 )循环体部分w 以看作一个复杂的活动，设计者可以定义这个复杂灞动的执行 时间。 后蕊的内容，我们不过于详细的考疼循环体，只是把他们爵作复杂的活动。 2 + 3 3 糨美定义与定理 从工作流的开始结点到结束结点形成结点序列，各结点执彳子延迟之和最大的序列称 为该工作流的关键路径。关键路径上的活动称为关键活动。 定义2 。t ： 1 ) 蠢掉图中所有可跨越活动；选择所有用时锻少的可替换路径。并且，当工作流 运行到浆个条件分藏处，根据外部实际情况的判断，选择了用时最少的条件分支。这 撑形成粒强稼为e b f 阉。 2 ) 绦窝蚕中所寄可跨越活囊：选择所有翊辩壤多静可替撩鼹径。并且，经过条件 分支处的判断，选择了用时最少的条件分支。这样彤成的图称为e b s 图。 3 ) 去掉图中所有w 跨越活动；选择所有用时最少的可替换路径。并且，经过条件 分支签敬髑瑟，选择了瑷蠢最多鳇祭 譬分支。这梯形成弱楚称为e w f 强。 4 ) 保留图中所有可跨越活动；选择所有用时最多的可替换路径。并且，经过条件 分支处的判断，选择了用时最多的条件分支。这榉形成的图称为e w s 图。 强2 , 3 中模型豹e b f 鎏、e b s 强、e f f 圈彝e w s 淫，如图2 5 掰示。 定义2 2 ：设工律滚中所有活动盼集合为n ，对任意i 属予n ， 1 ) 谯e b f 图中，糟e b f ( i ) = l b f ( i ) ，则i 称为e b f 活动，凼e b f 活动组成的各路径 中，活动执行延迟之_ 翔最大的路径称为e b f 关键路经。 2 程e b s 霞中，装e b s ( i 产l b s ( i ) ，爨i 称凳e b s 活凌，内e b s 活豁维成瓣各路径 中，活动执行延迟之和最大的路径称为e b s 关键路径。 - 2 0 大连理i ：火学硕士学位论文 ( a ) e b f 图 争图程m 3 图啦m 图瑚一 ( b ) e b s 图 ( c ) e w f 图 ( d ) e w s 图 图2 5一个时间工作流图的e b f 图、e b s 图、e w f 图和e w s 图 f i g 2 5e b f e b s 、e w f a n d e w s g r a p h s o f t i m e dw o r k f l o w 3 ) 在e w f 图中，若e w f ( i ) = l w f ( i ) ，则i 称为e w f 活动 中，活动执行延迟之和最大的路径称为e w f 关键路径。 4 ) 在e w s 图中，若e w s ( i ) = l w s ( i ) ，则i 称为e w s 活动 中，活动执行延迟之和最大的路径称为e w s 关键路径。 由e w f 活动组成的各路径 由e w s 活动组成的各路径 如果将e b f 图中的结点表示成事件，有向边表示成活动，那么e b f 图就转化成了 a o e 一厩j ( a c i t i v i t y o ne d g e ) 。a o e - 网中有至少一条关键路径。所以，e b f 图会有至少一条 e b f 关键路径。同理，e b s 图会有至少一条e b s 关键路径，e w f 图会有至少条e w f 关 键路径，e w s 图会有至少一条e w s 关键路径。 一2 1 工作流时间验证的研究与应用 因此，一个工作流图在四种情况下，会分别形成e b f 图、e b s 图、e w f 图和e w s 图。从而，形成四种关键路径，且每种关键路径至少一条。 定理2 】：在静态时间工作流模型中，n 为工作流图中活动结点的集合， 1 ) 任意j 属于n ，若e b f 0 ) = e b s ( j ) ，则从i n j 之间无可跨越活动；并且，若i r r j 之间有可替换路径，则可替换路径所用的时间是相同的。 2 ) 任意j 属于n ，若e w e ) 一e b f 0 ) 寸e ，( e 为极小的正数) ，则当不考虑可跨越活 动与可替换路径时，若i r l 之间有至少两条的路径，则从i r r _ j 之间各路径所用时间大 致相同，且其差值的绝对值不超过e 。 证明：在静态模型中， 1 ) 在i n l 的路径上，如果有可替换路径，则令最差替换路径与最优替换路径执行 延迟的差值为m ，其中，m 0 ：如果有可跨越活动，则令所有可跨越活动的执行延迟之 和为d ，其中，d 0 。这样可得到e b f 0 ) + m + d = e b s ( j ) 。又由题意得知：e b f 0 ) = e b s ( j ) 。所 以，m + d = 0 ，即：m = 0 ，d = 0 。得到，i n _ j 之间无可跨越活动；并且若i n _ j 之间有可替 换路径，则最差替换路径与最优替换路径执行延迟的差值为o ，说明各可替换路径所用 的时间是相同的。如图2 6 所示。 2 ) 证明过程与1 ) 相似。定理得证。 如果将上述定理中开始结点血转化为图中任一结点，则得到如下推论。 推论：对于任意i 、j 属于n ，且i 、i 处于同一条路径上，i 是 的后续活动： 若e b s ( i ) 一e b s ( j ) = e b f ( i ) - e b 坷) ，则j i 之间没有可跨越活动，也没有可替换路径。 若e b f ( i ) - e b f 0 产e w f ( i ) 一e w f ( j ) ，则当不考虑可跨越活动和可替换路径时，j i 之间 无较优路径，即若j i 之间有多于一条的路径，则各路径上活动延迟之和相等。 如图2 7 所示，证明过程与定理相似。 二卜咽。毋。，咽。 图2 6 从i n _ 1 的路径 f i g 2 6t h e r o a df r o mi nt o j 2 3 4 截止期限的动态验证过程 图2 7在同一路径上的两个活动 f i g 2 7t w o a c t i v i t i e s0 1 1t h es a m er o a d 2 2 大连瑗 二太学硕士学位论文 霹予经意i 、j 震予n ，i 是l 黪鬃续活麓，活凌j 缝隶慰亥l 笼e ( j ) ，当j 绥泰曩重， 预估计活动实例i 能否往d a t e 时刻或之前完成，即动态验证实例i 的截止期隈d a t e 的时 间约束条件能否满足。 ，雾。墓，至出。喜 踅2 8 踺裁疰蘩限d a t e 麓态验蘧 f i g & 8 t h e d y n a m i c v e r i t i c a t i o n t od e a d u n ed a t e 如图2 8 所示。其幼态验证算法如下； 1 ) 豢l 、j 楚予e b f 关键路径上，令e b f 暴产鞠) - e b f 0 ) + e b f ( i ) ，巍 当d a t e e b f 时，则活动i 必然不能满足截止期限d a t e 的约束条件。 当d a t e e b f ( i ) 时，如果按b b f 图执行，则活动i 截止期限为d a t e 的约束条 得能够满足。 2 ) 蓉“j 盘 予e b s 关涟路径上，e b s ( i = 弱) * e b s o ) + e b s 国，翔果去掉霹跨越活 动弗保留执行延迟最少的可替换路径，这时令j _ i 路径上所有活幼执行延迟之和为d 。 。当d a t e d + e 0 ) 时，活动i 关于d a t e 的约束条件不能满足。 当d + e o ) 一- - e b s7 ( i ) 时，活动i 关于d a t e 的约束条锌能够满足。 3 ) 菪i 、j 处于e w f 茨键路径上， 当e w f ( i ) 一e w 晦) ；e b i ) z b t x i ) 时，则j 、i 之闻各路径上活动救行延迟之和相 等。藏辩，活动i 黪截囊鬻鞭霹按秘f 哭键鼹经诗涂。 当e w f ( i ) e w f 0 ) e b f ( i ) 一e b f o ) 时，则强工作流图中j 、i 之间出现了条件分 支，各路径上活动执行慰迟之和不都相等。 a 。当d a t e e ( j ) e b f ( i ) - e b f o ) 对，溺魂i 关于d a t e 的约束条传不姥潢是。 b 当d a t e e a ) = 鳓躺一e b 如时，在工作流圈中，选择j 、i 之澜所有活动执行延迟 之和最小的路径执行，则活动i 关于d a t e 的约束条件恰好满足。 2 3 工作流时问验证的研究与应用 c 当e b i ) z b f 0 ) e w f ( i ) e w f 0 ) 时，活动i 一定可以在时刻d a t e 之前完成。 4 ) 若i 、j 处于e w s 关键路径上，则依据e w s 图 当e w s ( i ) e w a j ) = e b s ( i ) 一e b s o ) 时，j 、i 之间各路径上活动热行延迟之和相等。 活动i 的截止期限d a t e 可按e b s 关键路径讨论。 当e w s ( i ) 一e w s 0 ) e b s ( i ) - e b s o ) 时，e w s ( i ) ：e 0 ) 一e w s 0 ) + e w s ( i ) ，如果去掉 可跨越活动并保留执行延迟最少的可替换路径，这时令j i 路径上所有活动执行延迟之 和为d 。 a 当d a t e d + e 0 ) 时，活动i 关于d a t e 的约束条件不能满足。 b 当d + e 0 ) 一 e b s 7 ( i ) 时，活动i 关于d a t e 的约束条件能够满足。 5 ) 若卜j 路径不在任何一条关键路径上，则依据工作流图 ( 驰a c e e b f ( i ) ，则d a t e 不能满足； ( 勤珀f f ( i ) d a t e d l m 。时，截止期限约束条件d l ( k ) 必然满足。 当d l m i 。d l d l m 。时，适当选择可替换活动和选择条件分支，截止 期限条件可能满足。 d l d k 。( q ) 时，截止期限约束条件必然满足。 当d l t l i n ( q ) d l ( q ) d l m 。( q ) 时，截止期限条件可能满足。 4 0 - - 大连理工大学硕士学位论文 d l q ) - - 2 0 ，登选箨鬟短搿骜获子丽g 螽，鬟嚣薄凝下q 截壹对鬻为2 2 ，搦不蘸 满足约束条件。但在0 r 1 代表的予网中b 、c - 7 ：网被选择执行，约束条件能得到满足： 予网a 一旦被执行，意味着必须照改d l ( q ) 。 d e ( q ) ：2 6 9 _ - 2 s l 。 1 3 1 1w a n gh a l y a n g , l i nz o n g k a i ，l i ns h o u - x u n aw o 蹦f l o wd e s c i p t i o nm e t h o da n di t st i m e - c o n t r o l l i n gp r o b l e mb a s e do ne x t e n d e dm o d e l j o u r n a lo fc o m p u t e ra i d e dd e