（计算机应用技术专业论文）基于高级petri网的工作流技术的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 工作流技术是实现企业业务过程建模、仿真分析、优化、管理与集成， 从而最终实现其自动化的核心技术。越来越多的企业正在广泛地使用工作流 技术以提高企业的运行效率；时间管理是在企业应用工作流技术的过程中非 常重要的问题，会直接影响到工作流的执行效率。 p e t r i 网以其充分的模拟能力和严谨、丰富的分析方法，逐渐成为工作流 建模理论中的一种主流技术。近年来，研究人员发展了p e t r i 网理论，提出了 很多种p e t r i 网的扩展方案，三种应用最广泛的是基于时间、颜色和层次的扩 展方案。但是这些工作流模型在建模时间信息方面还普遍存在着不足：在上 述这些模型中，时间信息都是确定性的，缺乏对不确定性时间信息的描述能 力。在明确了当前基于p e t r i 网的工作流模型的不足之后，本论文将研究内容 确定为提出一种新的工作流模型着色模糊时间工作流网c t w b 2 q n e t ，它能够 全面地描述与活动中的时间模糊信息。 工作流性能分析是工作流研究中非常重要的一个方面，本文首先研究了 在加入时间因素后对整个工作流的影响，对违反一致性的可能比如：循环、 死锁以及时间上的冲突等也具体的分析并提出了相对的解决办法，并从定性 分析和定量分析两方面讨论了工作流模型的各种分析技术；针对工作流网可 以有一些基本网结构所合成构成这一特点，本文还提出了一套对时间约束 p e t r i 网进行保持时间约束特性不变的网变换规则，并设计了基于这套规则的 网的简化算法，通过反复应用变换规则逐步减小网的规模，进而计算出工作 流系统响应时间。 关键词：工作流；p e t r i 网；工作流建模技术；c t w f n n e t 哈尔滨工程大学硕十学位论文 a b s t r a c t w o r k f l o wt e c h n o l o g yi st h ek e yt e c h n o l o g yt h a ta s s i s t se n t e r p r i s eb u s i n e s s p r o c e s sr e a l i z i n gt h em o d e l i n g ，s i m u l a t i o n , a n a l y s i s ，o p t i m i z a t i o n ，m a n a g e m e n t a n d 。i n t e g r a t i o n ，a n df i n a l l ya u t o m a t i o n m o r ea n dm o r ee n t e r p r i s e sa r ew i d e l y u s i n gw o r k f l o wt e c h n o l o g yt oi m p r o v eo p e r a t i o ne f f i c i e n c y t i m em a n a g e m e n ti s a v e r yi m p o r t a n ti s s u ew h e n w o r k f l o wt e c h n o l o g yi su s e di ne n t e r p r i s e s p e t r ii sb e c o m i n ga m a j o rt e c h n i q u eb yi t ss u f f i c i e n ts i m u l a t i o na b i l i t ya n d p r e c i s ea n a l y s i sm e t h o d t h e r ea r em a n yk i n d so fm e t h o dm o d e l i n gb a s e do n p e t r i - n e t ，w h i c hp r o b l e mi st h et i m eo fm o d e l i n gi sc e r t a i na n dc a nb ed e s c r i b e d p r e c i s e l y i no r d e rt o d e s c r i b eu n c e r t a i nt i m eo fa na c t i v i t ym o d e ，at e m p o r a l m o d e l ( c t w f n n e t ) b a s e do nw o r k f l o wg r a p hi si n t r o d u c e d t h e p e r f o r m a n c e e v a l u a t i o no fw o r k f l o wi sa l l i m p o r t a n tc o n t e n to f w o r k f l o wr e s e a r c h ，t h ep a p e rd i s c u s s e si n f l u e n c eo ft i m ei n s e r t e di n t op e t r in e t s ， a n dm a n ym e t h o d sw h i c hc a nc o r r e c tm i s t a k ep e t r in e t si n t or i g h ta r ep r o v i d e d t h ep a p e rd e b a t e st w ow o r k f l o wm o d e la n a l y z i n gt e c h n o l o g i e s ：q u a l i t a t i v e a n a l y s i sa n dq u a n t i t a t i v ea n a l y s i s t h ep a p e rp r o p o s e sa l la p p r o a c ht oc o m p u t e a n da n a l y s i st h er e s p o n s et i m eo fw o r k f l o wb a s e do ne x t e n d e dt i m e dp e t r in e t s ， s i m p l i f yt h em o d e l sb ya p p l y i n gt h en e tt r a n s f o r m i n gt e c h n i q u e s 、i mm a i n t a i n i n g t h er e s p o n s et i m ea n dt h ed i s t r i b u t i o np r o b a b i l i t y ，a n dc a l c u l a t e st h ep e r f o r m a n c e p a r a m e t e r so ft h em o d e l s k e y w o r d s ：w o r k f l o w ；p e t r in e t s ；w o r k f l o wm o d e l i n g ；c t w f n n e t 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：2 垂睑丞2 日期：。年月z 多日 哈尔滨工程大学硕士学位论文 1 1 研究背景 第1 章绪论 工作流的许多概念源于企业管理理论和实践，随着企业规模不断扩大， 管理的难度也随之上升，信息技术和现代企业管理理论的发展，都为有效 地克服这些困难提供了理论和技术手段，工作流技术便应运而生。“工作流” 是全部或者部分由计算机支持或自动处理的业务过程。随着1 9 9 3 年工作流 管理联盟w f m c 的成立，工作流技术得到了长足的发展，并且成功地运用 在工业，农业，航天等众多领域。在全球范围内，对工作流的技术研究以 及相关的产品开发进入了更为繁荣的阶段，文件管理系统、数据库、电子 邮件、移动式计算、i n t e m e t 服务等都已经被容纳到工作流管理系统之中【1 1 。 然而时间约束及管理的问题逐渐成为工作流技术发展的瓶颈【2 】。时间在 过程生命周期中扮演着重要的角色，几乎所有的业务过程都存在于时序环 境中，且都是时间限制的。在模型建立阶段，工作流设计人员能够利用建 模工具，在定义工作流控制逻辑的同时，定义业务过程的时间信息，并检 查其可行性。在模型实例化阶段，工作流模型投入实际运行时，工作流引 擎对模型进行初始化，创建过程实例，调度和监控过程中每个活动的执行。 工作流管理人员能够通过工作流管理系统，识别与预测可能的时间问题， 及时采取措施处理时间问题。保证工作流顺利执行1 2 1 。若运行过程中发生时 间约束违反，工作流系统应该能够触发异常处理程序重新获得一致性状态。 目前的工作流管理系统大多数没有提供完善的时间管理功能，一般功 能仅局限在给活动赋予执行时间和截止期限，进行一些简单的仿真，当活 动执行时间超过截止期限时能够触发异常进行一些简单处理等 6 1 。正是基于 这个背景，本文对工作流管理系统中存在的各种时序关系进行深入仔细的 研究，力图能够对现实中存在的时间约束关系进行精确的表达。同时，在 我们现有的工作流扩展系统的基础上，给出了时间和颜色相结合的工作流 模型的具体实现方案，具有重要的现实意义。 哈尔滨工程大学硕士学位论文 1 2 工作流技术综述 1 2 1 工作流基本概念 目前对工作流没有完全统一的定义。对工作流的不同理解形成了对它 不同的定义，几个有代表性的描述分别是由工作流管理联盟( w f m c ) 、g i g a g r o u p 、i b ma l m a d e nr e s e a r c h 、a m i ts h e t h 和w m p v a n d e ra a l s t 提出的。 其中工作流管理联盟给出的工作流定义1 4 ：工作流是指整个或部分经营 过程在计算机支持下的全自动或半自动化，在实际情况中可以更广泛地把 凡是由计算机软件系统( 7 - 作流管理系统) 控制其执行的过程都称为工作流。 为了实现不同工作流产品之间的互操作，w f m c 在工作流管理系统的 相关术语、体系结构及应用编程接口等方面制定了一系列标准，w f m c 发 布的w f m cg l o s s a r y 中对工作流相关名词的定义如下【：】： ( 1 ) w o r k f l o w 工作流：业务流程的整体或部分自动化，在这其中，文 档、信息或任务根据一组业务规则在参与者之间传递并被处理。 ( 2 ) w o r l d l o wm a n a g e m e n ts y s t e m 工作流管理系统：利用软件定义工 作流、创建工作流和管理工作流执行的系统，运行在一个或多个工作流引 擎上，工作流引擎能够解释工作流的定义、和工作流参与者交互并能在需 要时触发i t 工具和应用系统。 一( 3 ) b u s i n e s sp r o c e s s 业务流程：一组相关的过程或活动，它们共同体现 了企业目标或策略目标，一般足在组织结构环境下根据功能决定各自的地 位和相互的关系。 7 ( 4 ) p r o c e s sd e f i n i t i o n 流程定义：业务流程的形式化表示，支持自动操 作( 例如建模或工作流管理系统的执行) 。流程的描述是由活动和活动之间的 关系、指明流程开始和结束的规则、单个活动的信息( 例如参与者) 、相关 的i t 应用程序和数据等组成的网络。 ( 5 ) a c t i v i t y 活动：完成流程中一个逻辑步骤的工作的描述。一个活动 可以是手工活动( 不支持计算机自动化) 或者工作流活动( 自动化) 。工作流活 动要求人员或机器资源来支持流程的执行；当一个活动被分配给工作流参 与者时就需要人员资源。 a u t o m a t e da c t i v i t y 自动活动：能用计算机自动处理的活动，在涉及它 2 i 哈尔滨t 程大学硕士学位论文 的业务流程被执行时直接由工作流管理系统来管理。 m a n u a la c t i v i t y 手工活动：在业务流程中不支持自动执行而依赖工作流 管理系统以外的环境的活动。这类活动在流程定义中可被包括进来( 例如流 程建模) ，但不能由工作流管理系统执行。 ( 6 ) i n s t a n c e 实例：一个流程、活动及其相关数据的单个执行表示。每 个实例表示流程或活动执行的一个独立线程，实例之间互不相干，有自己 的内部状态和外部可视的标示符，可用作一个句柄，例如可记录或查询关 于这个单独执行的审计数据。 p r o c e s si n s t a n c e 流程实例：一个流程的单个执行的表示。 a c t i v i t yi n s t a n c e 活动实例：在一个流程实例中一个活动的表示。 ( 7 ) w o r k f l o wp a r t i c i p a n t 工作流参与者：执行工作流活动实例要完成 的工作的资源。一项工作通常是分为多个工作项通过工作列表分配给参与 者。 ( 8 ) w o r k l t e m 工作项：对一个工作流参与者来讲，一个活动中要处理 的工作。 ( 9 ) w o r k l i s t 工作列表：关于工作流参与者的工作项列表( 在一些情况 下，关于一组共享一个公用工作列表的工作流参与者的工作项列表) ，这个 工作列表构成了工作流引擎和工作列表处理器之间接口的一部分。 ( 1 0 ) w o r k l i s th a n d i e r 工作列表管理器：管理用户( 用户组) 和工作流引 擎维护的工作列表之间的软件组件。它使得工作项从工作流管理系统中传 送到用户，并在用户和工作流管理系统之间传送“完成”或其它工作状态 条件。 1 2 2 工作流起源与发展 工作流的发展经历了三个阶段 5 1 ： 第一阶段：早期的工作流系统，应用于某些特定领域( 比如图形、文档、 表单等c s c w 领域) ，是相对独立的应用系统，始于8 0 年代中期。在这个 阶段，由单纯的解决企业日常表单、文档等的电子化与自动化转移到简化 和重组企业的关键业务流程。可以看出早期的工作流系统就是以面向过程 的系统集成技术出现的。 ， 哈尔滨工程大学硕士学位论文 第二阶段：具有底层的通信基础结构，能够实现任务协作的应用系统( l l 如具有消息传递功能的工作流系统) 。从9 0 年代开始，企业越来越突出的信 息资源的异构、分布、松散耦合性，部门职能的分散性，决策制定的分散 性，说明集中式信息处理的时代结束了，而大规模的异构分布式环境、相 关联的任务高效运转并接受监控等需求提到日程上来。工作流管理系统由 最初的无纸办公、协同工作转为结合企业复杂信息环境实现业务流程自动 执行的工具。 i 第三阶段：具有图形用户界面的流程定义工具、用户定义和任务执行 完全分离的工作流系统。随着现代企业从传统的以职能为基础的组织结构 和运作机制转变为以流程为中心的信息集成，工作流管理系统要满足企业 业务重组的需求。 1 3 国内外研究现状 目前国内外关于工作流时间约束方面的研究主要集中在以下几个方 面： ( 1 ) 时间信息表达模型 时间管理的关键在于能够对现实中的各种复杂的时间信息进行有效的 建模表达，这是一个十分具有挑战性的课题，国外率先对这一领域展开了 一系列的研究【删。这几年，国内在这方面的研究也开始蓬勃发展起来 3 1 0 1 1 1 2 u 】。在国外的研究中，e d e r 基于赋时活动图【6 】【7 】，建立包含活动时间属 性的工作流模型，如活动执行延迟、截止期限、固定日期以及时间距离约 束，并将所有的时间约束换算为活动执行结束的时间点。k a f e z a t s l 着重于活 动间的相对同步关系，将活动间的时序依赖转化为统一的二元时序约束， 通过为工作流图的有向边增加时间标签来包含业务过程的时间信息。l i n g t ，j 对工作流网进行时间扩展，提出t 岍n e t 时间工作流网模型，将活动的执 行时间约束映射为变迁时间对约束，并且消除c o n t a c t 情况。而国内的研究 多半是在国外研究的基础上展开的：吴兵【1 3 】在k a f e z a 的基础上提出了活动 关键事件二元关系的建模。杜栓柱 1 2 l 在l i n g 提出的t w n e t 的基础上，给 出了一个扩展t w f n e t ( x t 岍一n e t ) 模型，解决了在多个并行流程中活动在 时间约束下竞争有限资源的问题。李慧芳，范玉顺f ，l i i o 】将时间约束p e t r i 网 4 哈尔滨工程大学硕士学位论文 ( t i m i n gc o n s t r a i n tp e t r in e t s ) 的分析方法和工作流网有机结合，完整地描述 了工作流系统中业务实例的到达时间、活动实例的使能时间、活动可执行 的期限时间以及活动执行延迟，并给出了启发式可调度分析算法。 ( 2 ) 时序一致性验证研究 时序一致性是指时间约束与控制流、资源流、任务流的一致性。时序 一致性验证研究包括静态验证与动态验证。 静态验证是一种事前的验证方法。基于所建立的工作流模型结构，检 查过程型与时间约束的可能冲突，修改或松弛不一致的时间约束，为工作 流设计者进行时间约束的合理设定与有效建模提供帮助。任国珍、王海洋n 3 1 在时序条件模型基础上给出了模型建立时的静态验证分析方法及时序逻辑 推理规则。这种属于静态验证分析的范围。 动态验证是在实例执行过程中，基于实例的当前状态、绝对时间与关 键路径，通过计算关键路径的执行延迟估算尚未调度活动的预期执行时间， 判断时序一致。唐达 1 5 】在工作流图建模方法的基础上，提出了将工作流图映 射为e b f , e b s 、e w f 图和e w s 图，定义了相应图上的关键路径，利用这四 个关键路径对工作进行了较详细的动态验证。h o n g c h e n l i t 坫】考虑了活动之间 的资源共享情况，给出了并发工作流时序约束动态验证的方法。m a r j a n o v i c t l 7 l 引入控制点集合c ，通过c 中元素的动态增减，动态检测潜在的时序约束违 反，但它是以正确的工作流模型为前提的。 ( 3 ) 时间性能分析与优化 时间是衡量工作流性能的一个重要指标，对时间性能的分析主要是对 工作流运行周期时间的分析，即工作流从开始到结束所使用的时间。林闯【1 8 1 提出了由任意多个变迁组成的串联、并联、选择和循环结构的性能等价公 式，给出了定量分析工作流时间性能的通用方法，r e i j e r s - 9 1 也分析了可以由 基本模块组合构造的工作流模型的时间性能。这些方法的局限性在于它无 法分析那些无法由基本模块组合构建的工作流模型。对此r e i j e r s 提出了一 种分析工作流模型其性能上下界的方法。李建强【2 0 】结合工作流模型的资源视 图，对基于p e t r i 网的工作流模型的时问有界性进行了分析与验证。 除了上述主要的几个研究方向之外，还存在一些其他方面的研究，如 多粒度时间约束研究 2 q ，资源时间p e t r i 2 2 1 网的研究等等。 5 哈尔滨t 程大学硕十学位论文 1 4 工作流系统时间管理的不足 ( 1 ) 缺乏统一的时间建模规范与标准。时间建模是一个最新的研究领 域，工作流管理联盟尚未制定时间建模的规范与标准。己有的时间建模与 分析方法，主要基于工作流图模型，所考虑的时间约束也不同，具有很大 的局限性。由于工作流时间层次的性能分析是在逻辑层之后，有了过程模 型，才能进行时间建模与分析，因此可探索基于其他工作流模型的时间管 理方法。为了描述工作流系统中复杂的时间约束，需要一个统一的建模框， 以支持时间约束的规范表示与形式化验证，确保时序约束工作流实例的协 调和有序执行，时序表示与推理技术在工作流管理系统中的应用研究有待 深入。 ( 2 ) 建模与分析的复杂性。工作流系统应用实施的复杂性和特殊性限制 了时间管理的充分发展。现有的工作流模型时间分析方法，要么侧重于过 程模型验证，要么侧重于时序一致性验证。全面的工作流控制描述，应在 过程定义和运行管理中考虑工作流不同实施阶段活动延迟间的关系、活动 逻辑顺序与时间顺序间的关系以及流延迟与时差等，确保过程模型与时间 约束的一致性。过程建模是时间管理的基础，合理、有效的过程模型直接 影响时间管理的成功实施。为此，迫切需要一种集成化的工作流建模方法 体系，既能全面描述业务流程及其相关的时间因素，又能支持过程模型验 证与时序一致性验证。 ( 3 ) 实现的复杂性。为了捕获业务流程功能、时序与组织方面的动态变 化，需要提供柔性的工作流建模方法，但是足够灵活的过程定义机制，又 会使实例运行时的协调与控制难度相应增加。工作流模型固定不变的刚性 结构将扼杀企业在竞争环境中生存所必需的动态性和适应性，如何在精确 定义和柔性定义之间取得适当的平衡非常困难；同时支持时间管理的工作 流应用的开发相对于无时间约束的工作流系统要复杂得多，因为不仅要提 供过程定义和时序一致性验证工具，还要提供有关时间违反的处理策略。 ( 4 ) 国外许多学者都在对活动和过程的截止期限问题进行研究：f i l e r 提 出了一种较好的时间建模方法，并进行了严谨的静态验证，但动态验证方法 较粗糙。m a r j a n o v i c 提出了动态验证方法，但两个活动间若存在大量其他活 6 哈尔滨t 程大学硕十学位论文 动，则动态验证的计算量会比较大。e d e r 对截止期限的约束限制在一个时间 段内，即采用上、下界进行约束。s o n 分别采用c p i 算法和i c s f 算法，利用控 制结构查找工作流图中的关键路径；并采用b q n 算法对活动截止期限进行了 静态验证，估计活动截止期限。而且，在上述这些模型中，时间信息都是确 定性的，缺乏对不确定性时间信息的描述能力。而在实际的工作流应用中， 由于资源和活动具有动态特性，使得各种时间信息常常是非确定性的，难以 被精确描述。在文献 2 3 】和 2 4 】中指出，m u r a t a 等为了支持对不确定性时间的 描述，结合模糊集合理论，提出了模糊时f 司p e t r i n ( f t n ) 。在f t n 中有4 个模 糊时间函数：模糊时间戳、模糊使能时间、模糊触发时间和模糊延迟。使用 f t n 能很好地对工作流过程中的非确定性时间信息进行描述和分析，但它缺 乏对时间约束的描述能力。 1 5 本文研究内容及结构安排 在上述研究背景下，本文的研究工作主要是研究基于高级时间p e t r i 网 工作流建模和分析方法。 首先在分析现有的时间工作流的特点及缺陷同时，结合颜色工作流方 面的特点，把两者结合起来，形成着色模糊时间工作流网t c w f n - n e t 。 对于时间p e t r i 网一致性进行深入研究，针对时间约束冲突比如对违反 一致性的可能性也具体的分析并提出了相对的解决办法。 在工作流模型的分析方面，作者全面的讨论了对工作流管理有重要作 用的各种分析技术。最后提出了一种时间约束p e t r i 网的工作流模型的时间 性能评价的算法及其设计，即基于时间p e t r i 网等效变换的工作流模型的时 间性能计算和分析的方法。 本文分为六部分，其组织结构如下： 第1 章对课题背景、论文研究内容、论文结构和组织进行介绍。 第2 章介绍文中所涉及的基础理论知识，包括p e t r i 网基础理论、工作 流和模糊数学基础理论。 + 第3 章详细介绍时间p e t r i 网工作流中时间约束一致性问题并提出了相 应得解决办法。 第4 章详细介绍本文工作流网模型着色模糊时间工作流网 7 哈尔滨工程大学硕十学位论文 t c w f n n e t 。 第5 章对时间p e t r i 网工作流模型进行分析并给出了时间性能计算和分 析方法。 最后，对本文进行了总结，并提出了进一步的研究工作。 哈尔滨工程大学硕士学位论文 第2 章工作流时间约束与p e t ri 网技术综述 2 1 工作流时间约束综述 现有工作流的研究还不够成熟，尤其是对于具有时间特性的工作流更 是缺乏必要的研究，使工作流产品不能广泛应用。因为实际的业务流程大 多都具有时间限制，时间违反将增加业务成本，同时，只有在工作流技术 中加入时间因素，才能更好的反映整个业务流程的执行过程，有效的实现 工作流执行过程中的动态调度，并能够在此基础上进行相应的量化分析， 通过分析的结果实现对工作流过程模型的评价及优化。 研究具有时间特性的工作流可以在工作流的建模、仿真与验证、工作 流的执行管理等几个方面丰富工作流技术以及工作流管理系统的相关理 论，提高工作流技术对于环境的动态变化的柔性支持，进而扩大工作流技 术的应用范围，因而在理论上具有重要意义。 工作流管理系统应该提供的必要的时间约束管理功能有： ( 1 ) 对时间约束的建模：定义工作流控制逻辑与业务过程的时间信息， 并检查其有效性。 ( 2 ) 实例执行阶段：通过对时间监控和仿真，识别预测可能存在的问题， 提前预告可能存在的时间约束违反，并支持对工作流时间约束计划的动态 调整。 ( 3 ) 时间约束违反处理：一旦出现时间约束违反，工作流系统应触发系 统的异常处理机制以获得实例执行的一致状态。 ( 4 ) 提供给工作流参与者必要的时间信息：以便每个参与者能根据任务 的时间约束，判断任务的紧急程度，从而灵活的安排或调整个人的工作计 划。 2 1 1 工作流时间问题 考虑到现在企业可能的地理和事务处理的分布性，比如可能属于不同 9 哈尔滨工程大学硕七学位论文 的地理时区，以及活动执行延迟、时差、信息流传递的延迟，工作流管理 系统中时间因素主要有】： ( 1 ) 相对与绝对时间：相对时间基于某一参考点而得出的时间值；绝对 时间用实际的日历日期表示。工作流执行时常用绝对时间值表示活动的开 始结束时间。业务分布在地球不同时区要考虑工作流程间的时区差别【2 4 】。 ( 2 ) 时序约束：表示活动执行的时间约束，时间约束强调活动过程本身 的时间限制( 如执行延迟，时序约束更注重活动之间的时间依次性。如活动 b 应在活动a 开始1 天后启动) ，它们从不同的角度描述工作流系统的时间 约束。 ( 3 ) 时序一致性 定义1 【：s 】：一个时序约束与某一给定的工作流模型是一致的，当且仅当 基于工作流模型语义与工作流任务的最大最小执行延迟，该时序约束是满 足的。一个工作流模型，即使具有正确的控制流逻辑，它也可能含有不一 致的时序约束在工作流模型中。 定义2 ：一个时序约束集与某一给定的工作流模型是一致的，当且仅当 基于工作流模型语义和工作流活动的最大最小执行延迟，该集合所包含的 所有时序约束是满足的。 2 1 2 工作流时间约束分类 根据时问约束产生的形式，可以分为显式时间约束和隐式时间约束嘲。 显式时间约束指活动或时间约束显式可见，常由模型定义者定义，而隐式 则指隐含的时间约束，需经过推导和计算来发现。一般来说，时间约束还 可以分为i - 2 9 ： ( 1 ) 绝对时间点约束 定义绝对时间点a r p ：= y 仆4 ，d h m s 其中：y ：表示年，由4 位数字表示，如2 0 0 5 ； m ：表示月，由2 位数字表示，取值范围为 o l ，1 2 ，如0 3 ； d ：表示日，由2 位数字表示，取值范围为 0 1 ，3 1 ，如1 5 ； h ：表示小时，由2 位数字表示，取值范围为 o o ，2 3 1 ，如0 8 ； m ：表示分，由2 位数字表示，取值范围为 o o ，5 9 ，如3 0 ； 1 0 哈尔滨丁程大学硕士学位论文 i i i s ：表示秒，由2 位数字表示，取值范围为 o o ，5 9 ，如0 0 ； 绝对时间点约束常见在流程启动时间、活动启动时间等的定义中。 f 2 ) 日 - i n 段约束 时间段是时间维中任意两点间的距离，是时间的长度，它表示时间坐 标轴上某一固定的区间。 定义时间段：t d = a 跫一a r e , 其中：t d 具有单位的量，单位可以为：年( y ) ，月( 峋，周( w ) ，日( d ) ， 小时( h ) ，分( m ) ，秒( s ) ，如：5 小时1 0 分2 0 秒可以记为“5 h s m 2 0 s ”。时间 段约束t d 在流程定义中常用于指定活动准备的工期长度。 ( 3 ) 绝对时间区间约束 绝对时间区间约束a t s 是指任意两点问的时间，它在时间坐标轴上表 示两固定a t p 间的时间区间。 定义绝对时间区间：a t s = ( a r e - s ，a t p c ) ( 4 珥，t d ) ( t d ，a t p e ) 由定义可知，a t s 有三种定义方式：第一种为两个a t p 点对，其中4 职 表示开始时间点，a t p o 表示结束时间点；第二种为一个a t p 点对和一个距 离时间t d ，其中爿豫表示开始时间点，而t d 表示区间长度：第三种为一 个距离t d 和一个a t p 点对，其中t d 表示区间长度，而a t 只表示结束时 间点。 绝对时间区间约束a t s 可用于指定某种活动准确的生命周期，如全国 计算机等级考试报名时问为( 2 0 0 5 1 1 ，2 0 0 5 3 1 ) 。 ( 4 ) 循环时间点约束 循环时间点l t p 是一系列距离相等的a t p 集合，它在时间坐标轴上由 一系列的点组成。 定义循环时间点：l t p = l d ：l b 其中：l d ：表示循环周期，它是一个时间段t d ，但不能为一个基本 时间单位； l b ：表示循环基准点，它是l d 所指定的周期内的一个时间点； “：l d 和l b 的连接符。 循环时间点约束常用于定义一个循环启动的流程定义，如每个月的1 5 号给员工发工资可以记为：”i m m ：1 5 o o 0 0 o o ”；每年的l o 月1 日放假可 1 1 哈尔滨工程大学硕士学位论文 以记为：”1 y ：1 0 0 1 o o o o o o ”。 ( 5 ) 循环时间区间约束 循环时间区间l t s 是一系列距离相等的a t s 集合。 定义循环时间区间：l t s = l d ： ( l b 。，l b 。) i ( l b 。，t d ) i ( t d ，l b 。) 】 其中：l d ：表示循环周期，它是一个时间段t d ，但不能为一个基本 时间单位； l b 。：表示循环起始基准点，它是l d 所指定的周期内的一个时间点； l b 。：表示循环终止基准点，它是l d 所指定的周期内的一个时间点； t d ：是小于l d 的一个时间段； 循环时间区间l t s 约束一般用于表示一些具有循环时间特征的流程， 如某活动每周- - n 周二可以被启动，可以记为：“1 w ：( 2 ：3 ) ”或“1 w ( 2 ：2 0 ) 或“1 w ：( 2 d ：2 ) 。 ( 6 ) 日历定义 由于不同的企业，其工作时间是不尽相同的。所以在考虑工作流时间 约束时，必须要设置工作日历定义。 定义c a l e n d a r ：2 ( t ，阢，凰，瓦，彬) 其中：t ：同历的类型，可以分为三类：系统日历，作为工作流模型的 日历，系统日历可定义多个，设置其中之一为缺省日历，表示企业的多套 作息制度，而缺省日历为当前执行的日历；流程日历，专门针对某流程而 设计的日历，多用于企业重要流程的日历设置；个人日历，是每个人的工 作日历，用于企业员工需要加班等特殊情况的处理； 哌：表示何种休息的方式，是单休、双休、轮休还是不休，对于单休 则需要指定单休的时间( 周- - n 周日) ；双休需要指定双休的时间；轮休除需 要指定单双休时间外，还应指明单、双休的基准，即某一时间点是单周还 是双周； 风：节假日定义，它是一个四元组( m ，e d ，玩) ，其中m 表示假期 名，b 表示假期的开始时间，d 表示假期的长度，d 曲是对假期的描述； 瓦：表示一个工作日的工作时间，它由许多时间段组成，如上午 8 ：0 0 9 ：0 0 等； 形：表示工时的长度，工时是制造企业常用的逻辑时间表示方式，每 1 2 哈尔滨工程大学硕士学位论文 个企业工时； 无论隐式或显式时序约束，在工作流执行时都要转化为工作流活动过 程的时间属性，所以总的时间约束可以归结为以下6 类： ( 1 ) 基本时序约束( 或延迟约束) ：限制工作流模型中某一任务的期望延迟 时间，具有强制性。它可用相对时间值d i 精确表示，也可用一个时间对表 示它的最大最小期望延迟 m ( i ) ，m ( i ) 】； ( 2 ) 流程延迟和时差：在地理分布的业务流程中，工作流延迟包括活动 执行延迟和活动导航时的信息流延迟； ( 3 ) 有限延迟约束：限制工作流模型所表示的过程延迟，适用于过程所 有的实例类； 。 ( 4 ) 截止期限( 或期限时间) ：限制实例执行中活动过程的开始结束时 间，即活动过程的最大允许执行时间。在过程建立时，相对于过程开始来 指定；在过程实例化时，将所有的相对期限约束转化为绝对时间点； ( 5 ) 时间距离约束( 或相互依赖时序约束) ：限制同一工作流模型中两个任 务之间的时间距离，用相对时间值表示，即源事件结束e ( i ) 和目的事件开始 b 0 ) 之间的时间间隔，有上下界两种约束； ( 6 ) 固定日期约束：限制活动只能在指定的同期执行。f ( a ，t ) 表示活动a 与日期t ( t 是时间段，如星期二的0 ：0 0 - - 2 4 ：0 0 ) 绑定。 2 1 3 时间约束建模的几种方法 在应用工作流技术的系统中过程建模是最关键的一步。因此在开始设 计之前要选择一个良好的参考框架，来清晰地定义和分析过程。首先要确 定准确、清晰的技术和工具来表示过程模型；其次需要一种值得信赖的、 精确的技术或工具来完成正确性分析和验证；最后实际的业务过程是复杂 。多变的，完成过程定义后要确认此模型是否能表示业务的动态特性、可扩 展性和灵活性。过程建模及模型验证分析的主要目的就是要满足这些需求。 当前国内外对工作流建模方法的研究有： ( 1 ) 基于活动网络的建模方法：以活动和活动之间的关系为基础建立的 工作流模型，其特点是用户界面友好，易于理解。 ( 2 ) 基于p e t r i 网的建模方法：如p a p a z o g l o u 和b o u g u e t t a y a 采用着色p e t r i 1 3 哈尔滨f t 程大学硕十学位论文 网来描述工作流过程，a a l s t 则在p e t r i 网的基础上定义工作流网( w o r k f l o w n e t ，w f - n e t ) 来描述业务过程。 ( 3 ) 基于事务模型的建模方法：将事务的概念融入到工作流管理中，采 用一些高级事务模型来描述工作流过程，如嵌套事务模型、s a g a s 等。 ( 4 ) 基于工作流定义语言的方法，如w f m c 提出的x p d l ( x m l p r o c e s s d e f i n i t i o nl a n g u a g e ) b e a 、i b m m i c r o s o f t 等提出的b p e l 4 w s ( b u s i n e s p r o c e s se x e c u t i o nl a n g u a g ef o rw e bs e r v i c e s ) 。 关于工作流建模的方法还有很多，如基于逻辑的方法、基于代数的方 法、集合论和图论方法、面向对象方法、u m l 建模方法等等。 时间建模是在工作流模型中嵌入时间信息、扩展工作流模型使其包含 时间因素或者为活动增加时间属性，只有在模型中加入时间因素才能真正 的处理工作流中与时间相关的种种问题。虽然工作流常用的建模方式很多 种。但在模型中加入时间特性的只有以下的建模方式【，： 2 1 3 1 基于工作流图的方法 e d e f f 7 基于赋时活动图，建立包含活动时间属性的工作流模型，如活 动执行延迟、截止期限、固定日期以及时间距离约束，并将所有的时间约 束换算为活动执行结束的时间点。 表2 1 活动a i 和哆的时序控制关系及时间约束 关系含义约束 a , ：i 生a j2 ；l - f f f f i _ j 1 一q ( s ) q ( c ) a j ( s ) a j ( c ) a i 与吩衔接 i ii q ( s ) q ( c ) = a j ( j ) a j ( c ) 与亘登重叠 1 _ j q ( s ) q ( s ) q ( c ) a j ( c ) 1 一 q 与乃同时开始 i 一 q ( s ) = a j ( s ) q ( c ) a j ( c ) a i 与q 同时结束 i 一 q ( j ) 乃( s ) q ( c ) = a s ( c ) q 覆盖乃 l 一 a j ( s ) a i ( s ) q ( c ) ，是变迁的输入位置集合，f 一 pl ( f ，p ) f ) ，是 变迁的输出位置集合，p = t l ( f ，p ) f ) ，是位置p 的输入变迁集合， p 一川( p ，f ) f ) ，是位置p 的输出变迁集合，wq ，t ) 表示从位置p 到变迁 t 的有向弧的条数，w ( t ，p ) 表示从变迁t 到位置p 的有向弧的条数，m ( p ) 表 示在标识m 下位置p 中的标记数。p e t r i 网由初始状态所能到达的所有状态 的集合叫做p e t r i 网的状态空间，由状态可达图表示，状态可达图刻画了系 1 6 哈尔滨工程大学硕十学位论文 统的动态行为特性。 se n d l e t t e 图2 1 传统p e t r i 网 y 图2 1 给出一个简单的p e t r i 网，它由三个库所( c l a i m ，u n d e r , r e a d y ) 和三 个变j 壬_ ( r e c o r d ，p a y , s e n d _ l e t t e r ) 组成。这个网对过程进行了建模。一个申请 到达库所c l a i m 时，首先被纪录下来，随后选择是p a y 还是写信s e n d l e t t e r 说明拒绝的理由。 2 2 。2 工作流网 对工作流的控制流建模的p e t r i 网被称作工作流i 网( w r n e t ) ，是a a l s t 在p e t r i 网的基础上提出的概念。其定义如下【：6 】： 定义2 ：( w f n e t ) p e t r i 网p n = ( p ，t ，f ) 是工作流网，当且仅当： 存在一个源库所f p ，使得江a ； 存在一个汇结库所0 p ，使得d a ； 每一个节点x p u t 都位于从i 到0 的一条路径上。 从定义1 可以得出w f n e t 的几点性质：i 是唯一的源库所；0 是唯一的 汇结库所；添加一个变迁t 牛到p n ，用来连接汇结库所0 和源库所i ( f f 口 f = d ) ，且f 幸= ，那么所得p n 是强连接的，而且对于每一个节点 x p u t ，都位于从i 到0 的一条路径上。 定义3 ：一个p e t r i 网是强连通的，当且仅当对于该网上的任意两个节 点( 即库所或是变迁) x 和y ，总存在一条从x 到y 的路径。 工作流网完全支持w f m c 所定义的路由结构。而且工作流网提供了许 1 7 哈尔滨工程大学硕十学位论文 多强有力的分析技术用于验证工作流过程的正确性，如合理性、自由选择 的岍n e t 和良构的w f n e t 等。工作流网的结构图如下： ( 1 ) 分支结构 在控制流建模时，考虑到分支结构中a n d s p l i t ，a n d - j o i n ，o r - s p l i t ； o r - j o i n 等这样的路由构造块经常出现，我们使用特殊的符号来表示它们， 如图2 3 所示。 a ) a n d - s p l i tb ) a n d j o i n c ) 0 r s p l i ta ) o r j o i n e ) a n d o r i o i n 图2 2 分支结构的基本结构表示方法 a n d s p l i t ：如图2 2 ( a ) 所示，当活动执行完后，同时有多个转出转移， 可用于定义多个并发的线程。如果是“条件”转移，并发线程的数量将依 赖于每个转移上的转移条件( c o n d i t i o n ) ，这些转移条件的计算将是并发进行 的。 、 a n d j o i n ：如图2 2 ( b ) 所示，该结构可以看作是活动的“预处理集合点 活动开始执行的条件是：活动的所有进入转移的转移条件都是真。可用于汇 合多个并发的线程。并发线程的数量依赖a n d s p l i t 中计算得到的并发线 程的数量。 o r s p l i t ：如图2 2 ( c ) 所示，当活动执行完后，按照转移在列表中的顺 序，对转移条件进行逐个判断( 计算) ，满足则执行该转移，不满足就判断下 一个转移的转移条件。如果计算到一个无条件转移，或者一个转移的条件 是o t h e r w i s e ，则执行该转移。 o r - j o i n ：