（计算机软件与理论专业论文）时态工作流模型研究(1).pdf

时态工作流模型研究 论文题目：时态工作流模型研究 专业名称：计算机软件与理论 硕士生：谢建勤 指导老师：汤庸教授 摘要 随着计算机技术、网络的飞速发展，计算机已经被应用于大多数的社会生产 领域。然而，传统的计算机应用系统基本上是独立运行的，相互之间缺乏必要的 协作与感知，对越来越流程化的生产领域显得有点力不从心。工作流技术的提出 为其提供了较好的解决方案。工作流模型是对工作流的抽象表示，也就是对业务 过程的抽象表示，是工作流中不可或缺的一方面，因此建立相应的工作流模型就 是必不可少的。工作流模型为建模用户提供工作流定义所需要的组件或元素。目 前有许多形式化的过程建模技术，然而，在各种建模技术中，p c t r i 网以其充分的 模拟能力和严谨、丰富的分析方法，逐渐成为工作流建模理论中的一种主流技术。 时间是工作流中的重要属性。近年来研究人员提出的大量基于p e t r i 网的工 作流模型虽然也具有一定的时间描述能力，但是他们对工作流中时间问题的研究 是局部的、非系统化的，这些工作流模型在建模时间信息方面还普遍存在着不足。 比如对资源的描述能力不强，割裂时间与资源信息的联系，时态资源信息如何管 理等等。本文给出了一种将时间信息全面引入工作流模型的建模方法，提出了一 种新的p e t r i 网_ t e m p w f - n e t 。t e m p w f n e t 是对w f n e t 进行的一种时态扩展， 它不仅能像w 卜n e t 一样较好地描述工作流业务过程的控制结构，还对控制结构 的时态信息有较强的描述能力。在本文中将过程模型和资源模型分开描述，这样 更有利于工作流模型的重构。同时将时态信息引入资源模型中，增强了资源的描 述能力。文中应用关系的形式描述资源信息，并提出了利用时态数据库管理工作 流中的资源信息的思想。最后给出了一个实例阐述t e m p w f n e t 的建模过程。 关键词：工作流模型，p e t r i 网，时态信息，t c m p w f n e t 时态工作流模型研究 t i t l e ：r e s e a r c ho ft e m p o r a lw b r k n o wm o d e l i n g m a j o f ：m p u t e rs o f 柳a r ea n dt l l e o r y n a m e ：j i a i l q i n ) ( i e s u p e r v i s o r ：y o n gt a n gp r o f e s s o r a b s t r a c t a st l l ef a s td e v e l o p m e n to fc o m p u t e rt e c h n i q u ea i l dn e t w o r k ，c o m p u t e r sh a du s e d i nm o s tp a n so ft h ep m d u c t i o na r e a s h o w e v e r ，t h et f a d i t i o n a lc o m p u t e ra p p l i c a t i o n s y s t e m s a r e o p e r a t i n gi n d e p e n d e n c e t h e r e a r en o e n o u g hc 0 0 p e m t i o n a n d c o 肌e c t i o n sb e t w e e t h e m ，s ot h e yc a nn o tp e r f d mw e nw h c nt l l ef i c l do fp r o d l l c t i o b e c 锄em o r e 锄dm o f cn o w i l l g t h ea p p 锄n c eo fw o r k f l o wt e c h n i q u eo 岱b r s “a b e t t e rs o l u t i o n t h ew o r k n o wm o d e li sa i ia b s t r a c te x p r c s s i o no f b o t hw o r k f l o wa n d b u s i n e s sp r o o e s s ni san e c e s s a r ya s p e c to fw o r k n o 、ms oi ti sv e r yn e c e s s 缸yt o b u i l dc o e s p o n d i i i gw o r 姐o wm o d e l s 1 1 1 ew o 衄o wm o d e lp r o v i d e st l l en e c c s 船i y c o m p 叫e n t s 蛆dp a r t s f o ru s c fo fb u i l d i n gm o d e l t h e r ea r cm a l l yf b m u l i z c d t e c l l i l i q u e so fb u i l d i n gp r o c e s sm o d e l p e t r i - n c ti sb e c o m i n gam a j o rt e c 王l i q u eb yi t s s u 妇丘c i e ms i m l a t i o na b i l i t ya n dp r c d s ea l l a l y s i sm e t h o d t i n l ei sa i li n l p o n a n ta t t r i b u t co fw o 衄o w s o m esc ：h o l 盯sp r c s e ma b l l n d 强t w o r l 【f l o wm o d e l st h a ta 陀b 嬲e do nt h ep e t r i - n c th a v es o m ea b i t yt od c s c r i b ct h et i m e ， b u tt h e 打r c s e a r c ht 0t i l et i m ei s 蛐ei sp a n i a la n du n s y s t c m a t i s m t h c s ew o r l 【f l o w m o d d sa r ci n s u 伍d e n ti nt i m c - i n f o 珊a t i o n ；s u c ha st l l e r ci sn 0e n 叫g ha b i l i t yi n d e s 喇b i n gt b er e s o u r s e p a r a t j n gt h ec 彻n e c t i o no ft i j l l ea n dr c s o u r c ei n f o 锄a l i 咖， u n a b l ct om a n a g et e m p o r a lr e s o u 黜i n f o 皿a t i o n ，c t c t h i sa r t i d ep r e s e n t sam o d e l b l l i l d i l l gm e t h o dt oc o m b i n et l i ct i n l e i n f o 咖a t i o na n dt h ew o r k n o wm o d e l an e w p e 仃i n e t t e m p w f - n e t t e m p w f n e ti sat e m p o r a le x t c n s i o no fw f _ n e t n o to i l l y i tc a nd e s c r i b et h c 咖t m ls t 皿c t u r c so fw o r k n o wp r o c e s s ，b u ta l s oh a ss t r o n ga b i l i t y i nd e s c r i b i n gt l l et e m p o r a li n f o r i 】1 a t i o ni nt h ec o t r o ls 佃j c t l l f e s i nt t l i sa n i d e ，t l l e p r o c e s sm o d e l 锄dr e s o u r c em o d e l i s d e s c f i b e d p a m t e l y w l l i c h i s g o o d t o r e - e n g i n e e f i n gt h ew o 衄o wm o d e l n et e m p o r a li n f o n n a t i o ni si n t r o d u c e di n t ot l l e 时态工作流模型研究 r c u r c cm o d e l ，w h i c hi n c f c a s e st h ea b i l i t yi 1 id e s c r i b 沁l h er e s o u r c e n ea n i d c d e s c r i b e st h cr e s o u r c ci n f o 瑚a t i o ni nt l l ef o n n0 fr e l a 石o n ，p r e s e n t st 0m a n a g et h e r e s o u r c ei l l f b m a t j o ni nt e m p o r a ld a t a b a s e a tl a s t ，姐e x 锄p l eo fd e s 耐b i n gt h e p r i ) c e s so fb u i l d i n ga1 b m p 限n e ti sp r o v i d e d k e y w o r d s ：w o r l m o wm o d e l p e 打i - n e t ，t e m p o i a li f o 皿a t i o n ，t c m p w f - n e t 时态工作流模型研究 1 1 引言 第1 章概述 在现代社会中，计算机扮演着越来越重要的角色，己经被应用于大多数的社 会生产领域。计算机以及相关应用系统的辅助，是许多工作得以顺利进行的必要 条件。然而，传统的计算机应用系统基本上是独立运行的，相互之间缺乏必要的 协作与感知，对越来越流程化的生产领域显得有点力不从心。因此，为了达成组 织成员之间的协作，特别是异地、异步协作，建立一个能够完成相关任务并能进 行有效的集中式管理的异构分布式执行环境是非常必要的。工作流技术与工作流 管理系统正是此类问题的理想解决方案。作为计算机支持的协同工作( c o m d u t e r s u p p o r t e dc 0 0 p e r a t i v ew o r k ，简称c s c w ) 的一个重要研究方向，工作流管理的 主要目标是通过调用有关的信息资源与人力资源来协调业务过程的各个环节，使 之按照一定的顺序依次进行，从而实现业务过程的自动化。 其实工作流的概念最早起源于生产组织和办公自动化领域，提出的目的是通 过将工作分解成定义良好的任务、角色，按照一定的规则和过程来执行这些任务 并对它们进行监控，达到提高工作效率、降低生产成本、提高企业生产经营管理 水平和企业竞争力的目标。早在八十年代初期，在p c 机尚未作为信息处理工具而 出现的时候，纸张是各行各业中进行日常业务活动所不可替代的载体，包括表单、 文件、信函、技术资料等在内的各类与企业密切相关的文档都是以纸张的形式在 各个部门之间进行传递的。这种古老的载体在信息的处理、组织、存储以及查询 检索方面都是低效的。因此，人们希望出现一种无纸化的、计算机使能的工作环 境。一些公司、企业也建立了自己专用的或者可商品化的表单传递应用系统，通 常运行在大型机或小型机上，用于实现日常表单处理的电子化与自动化。这种系 统可以看成是现代工作流管理系统的一个雏型。 进入九十年代，随着计算机的普及、网络的延伸，现代企业的信息资源越来 越表现出一种异构、分布、松散耦合的特点，企业的分散性、决策制定的分散性、 时态工作流模型研究 对日常业务活动详尽信息的需求以及分布式处理技术的日益成熟，都说明了集中 式信息处理的时代已经过去，实现大规模的异构分布式执行环境，使得相互关联 的任务能够高效运转并接受密切监控已成为一种趋势。在这种不可抗拒的技术背 景下，工作流管理系统也由最初的创建无纸化办公环境转而成为实现业务流程自 动执行的必要工具。这样的一个转变，把工作流技术带入了一个崭新的发展阶段， 使得人们从更深的层次、更广的领域上对工作流展开了研究1 1 1 。 工作流模型是对工作流的抽象表示，也就是对经营过程的抽象表示。由于工 作流需要在计算机环境下运行，因此建立相应的工作流模型就是必不可少的。工 作流模型应该完整地提出支持工作流定义的概念，为建模用户提供工作流定义所 需要的组件或元素。 时间是自然界无所不在的客观属性，所有信息都具有相应的时态属性，工作 流也不例外。在实际的业务过程中大多都具有时间限制，实旌工作流管理需要处 理时间问题，确保工作流执行满足过程的时间约束。可见，研究工作流时间管理， 对于增强工作流管理功能、丰富工作流建模理论以及推动工作流管理软件的实际 应用具有重要意义。近年来，关于工作流模型的时间约束方面的研究很多，然而， 到目前为止，人们虽然提出了不少有意义、有见解的工作流模型，但均只表现了 时间约束的某一方面，未将时态因素全面地引入工作流模型。所以，关于时态工 作流模型的研究还有较长的一段路要走。 1 2 国内外研究现状 在各种工作流建模技术中，p e t r i 网收到人们的普遍关注，已成为目前最具 前途的建模工具。因为利用p e t r i 网技术进行工作流过程建模具有如下优势： ( 1 ) 正式的语义：无论是经典p e t f i 网，还是进行了颜色、时间或者层次扩 展的高级p e t r i 网都具有严格的数学定义。因此，应用p e 仃i 网技术可以对工作流过 程进行清晰、精确的描述。 ( 2 ) 图形化的本质：p e 仃i 网是一种图形化的语言，p e 砸网中各要素以及要 素之间的关系都可以通过图形表现出来。因此，p e t r i 网非常直观，容易学习，并 时卷工作流模型研究 且可以支持用户之间的交流。 ( 3 ) 较强的表述能力：p e t r i 网能够支持建模工作流过程必需的所有原语。 工作流过程中出现的所有路由结构都可以用p e t t i 网进行建模。而且在p e t r i 网中， 可以同时显式地表示状态与事件，这是一个非常有利于工作流过程建模的特性。 ( 4 ) 透彻的研究：由于p e t r i 网具备严格的数学基础，可以支持对各种性质 的推演。因此在过去的四十年中，研究人员对p e t r i 网的基本性质进行了大量的研 究，获得了对p e t r i 网的透彻认识。 ( 5 ) 丰富的分析技术：p e t r i 网拥有大量的分析技术，这些技术能够被用于 证明各种性质( 比如安全性、不变性和死锁等) 以及计算各项性能指标( 比如反 应时间、等待时间和占用率等) 。通过这些p e t f i 网的标准分析方法，可以对工作 流进行评价。l 基于p e t r i 网的工作流建模最早可追溯到二十世纪七十年代。当时m d z i s m 柚将p c t r i 网用于表示办公流程1 4 】。在此基础上，c a 日l i s 提出了一种扩展 p e t r i 网，称为信息控制网( i n f o n n a t i o nc o n t r o ln e t ，简称i c n ) 【5 l ，并将其应用 于办公信息系统的建模。 二十世纪八十年代以来，基于p e t r i 网的工作流建模方法逐步引起了人们的注 意，近年来更是成为工作流领域的一个研究热点。大量基于p e m 网的工作流模型 被提出来。 w m p v a nd e r a a l s t 将工作流管理领域的概念映射到p e 打i 网之上，提出了工 作流网( 、0 r k n o wn c t ，简称w f - e t ) ( 2 】用于对工作流的控制结构进行描述。 他还定义了w f n e t 的合理性( s o u n 血e 鹞) 概念，作为评价工作流控制结构正确 与否的一个标准，并利用标准的p e t i i 网分析技术验证w f n c t 的合理性。w f n e t 是一个具有较大影响的工作流模型，在它之后提出的许多模型都是以它为基础扩 展而得到的。 在文献【6 冲，n a b i lr a d a m 利用p e t f i 网的变迁与库所分别建模任务内部的 原语以及原语之间的状态，并讨论了如何在p e 仃i 网中表示控制流依赖、值依赖和 时态依赖。在此基础上，应用p e t r i 网分析技术去发现任务之问不一致的依赖描述， 测试工作流的安全性以及测试时态约束是否可满足。 时间管理是工作流管理系统必须具备的重要功能。良好的时间管理能力，能 时态工作流模型研究 够增强工作流管理系统的柔性，确保工作流的高效执行，从而提高企业的竞争力。 时间管理的关键在于时间信息的有效建模，已经有越来越多的工作流模型对模型 元素进行时间属性的扩展，并考虑利用p e t r i 网的分析技术去验证工作流模型在时 间方面的正确性。 在文献【7 】中，s e al i n g 等人提出了一种扩展的w f n e t ，称为时间工作流网 ( t i n l ew o r 如o w 卜e t ，简称- 1 w f - n e t ) 。1 w f _ n e t 中的每个变迁都被赋予了一个 区间，变迁的执行时间跨度必须在其中取值。该文献还定义了时间安全性的概念， 并给出了t v 吓n e t 某些行为特性的验证方法。 在州盯n e t 的基础上，杜栓柱等人提出了一种新的时间p e t f i 网工作流模型一 一扩展时间工作流网( e x t c d e dt i m ew o 栅o wn e t ，简称隔，f n e t ) 吼增加 了活动的执行时间，并通过一定的构建规则，能够将多个t 1 f - n e t 合并为一个 x 刑f n e t ，以描述并行流程中的时间约束。另外，x r w f n c t 中还引入了与时区 相关的时间映射函数，可以描述分布于不同时区的工作流程。 基于实际工作流过程对时序约束的需求，李慧芳等提出了时间约束工作流网 ( t i m i n gc o n s t f a i n tw o i l 【n o wn e t ，简称t c w f - n e t ) 【9 】【1 0 l 。t c f n c t 将时间约束 p e t r i 网的分析方法与w f - n e t 有机地结合起来，完整地描述了工作流系统中业务实 例的到达时间、活动实例的使能时间、活动可执行的期限时间以及活动的执行延 迟。 工作流过程不能被简单地看成活动之间的控制流，它事实上还表现为活动之 间的资源流转。单纯对控制流进行建模分析，并不能全面地反映业务流程的特征。 因此，考虑如何对资源信息进行建模是建立完善的工作流模型的必要一环。 在文献【1 1 】中，李建强等基于w f - n e t 提出了多维工作流网，将变迁触发所需 的资源引入工作流模型中，并假设每个活动的执行只需要一种资源的参与。还提 出了模型的时间有界性的验证与分析方法。 在文献【1 2 】中，李玮等讨论了以资源流为主导的工作流建模方法，提出称为 资源任务网( r e s o u 袱i 厂r a s kn e t ，简称r t - n c t ) 的工作流模型。r 厂r - n e t 能够用 于描述任务流与资源流并行的业务过程，它通过设置任务模型中的资源依赖与资 源期望来实现资源流对任务流的控制。在文献【1 3 仲提出的资源条件任务网 ( r e s o u r c cc d i t i o 叽a s kn c t ，简称r c ，i n ) 也是基于类似的思想构建起来的， 4 时态工作流模型研究 并引入了活动的触发时间和持续时间。 在文献【1 4 】中，胡乃静等基于w f - n e t 提出了资源限制流网( r e s o u r c e c c 咀s t r a 证tn o wn c t ) 。在资源限制流网中，变迁的触发需要一定的资源，并且 变迁的执行可能会对资源的值造成影响。在此基础上，该文献考虑了资源冲突对 变迁并发的影响，并提出了资源限制流网中的正确性概念及并发变迁的并发性错 误检验算法。 在上述文献中提出的工作流建模方法中虽然在控制流的基础上包含了资源 信息的流转，但并未提出如何利用数据库对这些资源进行管理。在文献 1 5 中， 严蓉等利用了数据库作为实现数据流转和存储的容器。将工作流中的数据分为控 制数据和应用数据，并在数据库中定义了不同的用户具有不同的权限。但他只是 单独谈到了工作流中的数据流转未将数据流转与工作流过程紧密结合起来。 在文献 1 6 中，陈昌巨等以工作流管理联盟的工作流参考模型为基础，采用 c s 模式开发了一套基于关系数据库( o r a c l e ) 的工作流引擎。通过客户应用程 序对服务器数据库进行访问，服务器向客户端响应服务，以实现企业业务的办公 自动化。 在文献 1 7 中，刘涯等介绍了中国地质大学公文管理系统的实现方案，采用 了一个基于关系数据库的工作流自动化的实现方法。在文献 1 8 中陈爱蓉等给出 了一个关系数据库的工作流管理系统用于维护s 1 2 的数据版本。文献 1 9 中范永 全等和文献 2 0 中余冬梅等也各自介绍了一个基于关系数据库的工作流系统解 决方案。 在文献 2 1 中赵莉香等提出了一种数据库技术和工作流技术相结合的工作 流模型，文中通过建立面向对象数据库模型定义工作流及其完整性约束。将工作 流的描述信息和资源信息一并使用数据库进行管理。 1 3 本文的研究思路及创新点 以前面对基于p e t r i 网的工作流过程建模方法及基于关系数据库设计工作流 引擎的分析为基础，本节对论文的主要工作进行概述，包括论文的主要目标、研 时态工作流模型研究 究思路、创新点等等。 1 3 1 问题的提出 由前文的论述可知，对基于p e 仃i 网的工作流过程建模这一研究领域而言，如 何在p e 仃i 网中有效地建模时间信息、资源信息以及如何管理其时态资源信息已经 成为当前该领域的一个重要课题。然而，纵观近年来国内外提出的各种基于p c t r i 网的工作流模型及基于关系数据库的工作流引擎设计可以发现，尚未对这两方面 有一个比较合理的解决方案。 首先，虽然能够建模时间信息的工作流模型目前较多，比如时间工作流网 1 w f - n e t 用、扩展时间工作流网x 聊f n c t 嘲以及时间约束工作流网t c 、f n e t 【9 l 等，但他们基本上都是基于定时p e 埘网构建起来的，定时p e 仃i 网通过在变迁、库 所上附加时间跨度，在标记上附加时间戳来定量地描述系统的时间特性。他们并 未将时态因素全面地引入到工作流模型中，对于如何在p c t r i 网中显式地表示各种 时态约束( 如流程的时限约束、定期约束等) ，在国内外此方面研究尚比较薄弱。 其次，虽然已经出现了为数不少的工作流模型能够对资源信息进行描述，但 是有相当一部分模型描述资源的能力比较弱，利用这些模型进行资源建模必须接 受较多的限制，并不能贴切地反映现实。比如，虽然文献【1 1 】提出的多维工作流 网能够建模资源信息，但它假设每个活动的执行只需要一种资源的参与，并且没 有讨论活动对资源本身的影响。 研究人员也提出了一些具有较强的资源描述能力的工作流模型，比如资源 任务网r 厂r n c t 【1 1 l 、资源条件任务网r c 厂i n 【1 2 1 以及资源限制流图f 1 封等，但是它们 也存在一些问题：r ，r - n c t 与r c ，i n 都是以资源流为主导的工作流模型，希望以 资源流取代控制流实现对业务过程的控制，但是这种做法仅适用于建模任务流与 资源流并行的业务过程。 虽然已经出现了一些工作流模型能够同时描述时间信息与资源信息，但对于 资源本身固有的时态属性( 如生命周期等) 的研究还非常薄弱。目前仅有文献【2 2 】 将时态信息全面地引入到工作流模型中并对其进行了相关方面的初步探讨，但该 文献只是一个初步的尝试，并未提出一个工作流过程模型的完整定义。 6 时态工作流模型研究 在明确了当前基于p c t r i 网的工作流模型在描述时态信息方面的不足之后，本 论文将研究内容确定为提出一种新的基于p e 仃i 网的时态工作流模型，它既能够继 承现有基于p e t r i 网的工作流模型在建模控制结构方面的理论成果，又能够灵活地 描述工作流过程涉及的各种资源，表达资源在活动之间流转以及发展变化的规律 并提出利用时态数据库更好地管理这些时态资源信息的思想。 1 3 2 主要思路及创新点 在提出新的工作流模型之前，必须考虑基础建模工具能否提供足够的支持。 在工作流网w f n e t 中，用以建模各种对象的标记是没有属性的，标记只能够通过 所处的库所来表达信息。并且工作流网w 卜n e t 并不能很好的表示工作流中的时态 信息。显然，利用工作流网w f _ n e t 不可能建立理想的工作流模型。因此，论文首 先考虑如何对工作流网w f n e t 进行扩展。 根据新的工作流模型的要求，扩展后的p c t r i 网必须能够深入地描述各种对象 的内在属性，表达对象发展变化以及相互作用的规律。并且这种扩展p e t r i 网还应 该能够对时间进行量化的描述，进而实现对各种时态现象的建模。为了达到这样 的目标，一方面可以按照定时p e t d 网对经典p e t r i 网所进行的扩展，将时态元素 引入到工作流的控制流中，形成t e m p w f n e t ，另一方面，对工作流中的资源信息 进行相应的时态扩充，为资源附加时态属性与非时态属性，并将其与过程模型分 开以便更好地对其进行管理，也有利于工作流过程模型的重构，增强工作流模型 的柔性。在本文中提出了利用时态数据库对工作流中的资源信息进行管理的思 想，很好地利用了时态数据库的研究成果。 由于t c m p w f n e t 是在w f - n e t 的基础上提出的，所以可以很好地利用现有的 各种分析技术。w f _ n e t 是一种能够有效地描述业务过程控制结构的工作流模型， 并且在应用p e t r i 网分析技术对w f n e t 的正确性进行验证方面，研究人员已经得到 一些有用的结论。因此，可以利用现有的对w f n e t 的各种分析技术来对t e m p w f n e t 进行分析，以继承他人在工作流控制结构方面已经取得的理论成果。 由于将时态信息全面地引入到了工作流过程模型和资源模型中，因此本文提 出的工作流模型能很好地描述工作流所涉及的各种时态约束。 7 时态工作流模型研究 本论文研究工作的主要贡献及创新点可以总结为如下的两个方面： ( 1 ) 提出了时态工作流过程模型r 釉p w f - n e t 针对工作流网w f n e t 建模能力与建模效率的不足，论文提出了时态工作流网 t e m p w f n e t 。在t e m p 、v f - n e t 中，对工作流网w f n e t 进行了全面的时态扩展，将 时态因素引入到工作流的控制流中并给出了其形式化的定义。相对于工作流网 w f n e t 而言，t e m p w f n e t 能够描述更为复杂的，尤其是具有各种时态现象的系 统或者流程，它是一种更为强大的系统建模工具。 ( 2 ) 提出了时态工作流资源模型 在本论文中将资源模型与过程模型分开，这样更利于工作流过程的重构。资 源具有时态属性与非时态属性标记，在本论文的资源模型中引入了资源的时态信 息，能更好地对其进行描述。文中应用关系的形式描述资源信息，并提出了利用 时态数据库管理工作流中的资源信息的思想。 1 4 论文的组织结构 本文共分为五章，其组织结构如下： 第一章为概述，描述了工作流建模方面国内外的研究现状，总结了其不足之 处，并提出了本论文的研究目标。 第二章介绍文中所涉及的基础理论知识，包括工作流、p e t r i 网和时态信息 三方面，本论文旨在利用p e t r i 网建模时态工作流过程并提出时态工作流资源模 型。 第三章为本论文的重点部分，在本部分中提出了一种新的时态工作流过程模 型和资源模型，并给出其形式化定义。 第四章给出了基于本论文提出的时态工作流模型的建模方法，并通过一个实 例描述了其具体用法。 第五章对本文的工作进行了总结，并提出了进一步的研究方向。 8 时态工作流模型研究 第2 章相关理论基础 2 1 工作流与工作流管理系统 本节将介绍工作流领域的一些重要概念。以期读者对工作流有一个基本的认 识。 什么是工作流? 不同的研究者对工作流分别提出了不同的定义，他们分别从 不同的角度对工作流概念进行了描述。这里采用w f m c 发布的工作流参考模型中 的定义来描述什么是工作流系统。“工作流干预过程、业务程序的自动化处理， 文档、信息或者任务按照定义好的规则在参与者间传递，来完成整个业务目标或 者对整个业务目标的完成做贡献。”同时，工作流可能由手工组织，实际上，多 数工作流都在i t 系统中进行组织的，从而对过程自动化提供计算机支持，w f m c 把工作定位在这个方向上。 定义2 1 ：工作流：全部或者部分，由计算机支持或自动处理的业务过程。 工作流管理系统( w f m s ) 通过管理工作活动序列，调用与各种活动步骤相关 的人员、i t 资源，对业务过程提供自动化处理。 定义2 2 ：工作流管理系统：详细定义、管理并通过一些软件来执行工作流 的系统。这些软件的执行顺序由工作流逻辑的计算机表示形式( 计算机化的业务 规则过程定义) 驱动。 在最高层，所有的w f m s 都有相同的特性，即为下边的三个功能提供支持： ( 1 ) 建立时期功能，定义、模拟工作流过程，及其组成活动。 ( 2 ) 运行时期控制功能，在运行环境中管理工作流过程，管理不同活动执行 顺序。 9 时态工作流模型研究 ( 3 ) 运行时期与用户、i t 应用程序( 工具) 的交互，来处理各种活动的执行。 图2 1 描述了w f m s 的基本特性，以及上述功能间的关系： 图2 - 1w f _ s 中各功能之间的关系 建立时期的功能负责产生业务的计算机化定义。在这个阶段，通过使用一个 或多个分析、建模和系统定义工作，把实际中的业务过程转变成形式的、计算机 可处理的定义。通常把定义的结果称为过程定义。 定义2 3 ：过程定义：过程的计算机化表示，包括手工定义和工作流定义。 过程定义由一系列的分散的活动、相关的计算机、人员操作、活动间控制过 程进程的规则构成。可以用文本、图形或者语言符号来表示过程定义。这部分正 是本论文研究的重点。 工作流的概念被明确提出并得到重视的同时，人们就认识到了“标准化”在 其中的重要性，驱使实现工作流重要功能接口的标准化主要有以下两个原因： 1 继续支持过程重组和操作的灵活性 业务过程重组与相应的工作流实现是有战略意义的，从而要求工作流产品要 有足够的灵活性来处理不停变化的业务过程，这是采用工作流技术的主要动机。 有时，用不同工作流产品实现的几个单独的业务过程，后来业务过程重组为一个 1 0 时态工作流模型研究 单一的复合过程。这种需求可能由于组织的合并、立法的变化、业务对象的改变 等引起。在这种情况下，非常希望在不同的组织或者部门间使用不同的产品，而 那些不能用于协调工作的产品，在过程变化时会产生十分严重的潜在问题。 2 满足产品专业性与市场变化的需要 市场中很多的工作流产品都针对不同方面的应用和不同的数据应用程序集 成。协同标准的制定，将使得我们可以选择每一应用领域的产品中最好的来满足 要求。例如可以从一个开发商处选择过程分析、定义产品，而从另一开发商处选 择工作流引擎软件，然后从第三个开发商处购买客户端任务表处理程序与前两个 产品集成。此外，许多工作流程序需要与其他已有的或者将要出现的系统集成， 标准化的接口可以支持这种集成并减少产品的复杂度。 正是由于标准化的重要性，一些公司才联合到一起成立了工作流管理联盟， 为工作流产品的实现制定适当的规范。w f m c 成立于1 9 9 3 年8 月。目前该组织 的成员已经超过2 0 0 个，成员包括工作流产品的供应者、应用者，有关大学和研 究机构及个人，是一个国际性的非赢利组织。1 9 9 4 年1 1 月2 9 日，w f m c 发布 工作流系统参考模型，参考模型是w f m c 发布的工作流标准的一部分，更多的 细节可以参考标准文档。工作流参考模型删r o f k f l o wr e f e r c i l c cm o d e l ) 详细描述了 工作流系统的有关概念，并在此基础上，给出w f m s 的主要组成部分、各部分 的功能及相互之间的接口，如图2 2 所示。 圈2 _ 2 肝参考模型 在w f m c 参考模型中，工作流执行服务是工作流管理系统的核心部分。在 时态工作流模型研究 其外部定义了五个接口： 接口1 ：工作流定义转换 接口2 ：工作流客户端应用程序接口 l 接口3 ：应用程序调用接口 接口4 ：不同工作流系统间协同工作接口 接口5 ：管理和监视接口 工作流引擎基于一个或多个工作流定义。在工作流的参考模型中，用来构造 它们的工具被称作过程定义工具，也就是接口1 。原则上可以将工具分为三类： 过程定义工具、资源分类工具、分析工具。本论文主要研究对象为过程定义工具 和资源分类工具。【2 3 】 有许多不同的工具可以用来分析、建模、描述业务过程。其中一些技术是非 形式化的，原因在于使用的图没有形式化定义的语义。这些模型通常是非常直观 的，其解释依赖于建模者、应用领域和身边的业务过程的特性。非形式化的技术 有i s a c 、d f d 、s a d t 和i d e f 等。目前有许多形式化的过程建模技术，如有限 状态机、标记转移系统、状态图、p e t r i 网和进程代数( 如a c p 、c s p 和c c s 等) 。 在各种建模技术中，p e t r i 网以其充分的模拟能力和严谨、丰富的分析方法，逐 渐成为工作流建模理论中的一种主流技术。 2 2 p e t r i 网基础理论 本文所提出的时态工作流过程模型是在p c t r i 网理论的基础之上发展而来的。 因此，本章将对p c t r i 网的基本概念、术语与标记进行简要的介绍。阻l 2 2 1 p e t r i 网形式化定义 p e t f i 网是由德国的c a la d a mp 训教授于1 9 6 2 年在他的博士论文中提出的。 7 0 年代以后p e t r i 网理论得到了迅速的发展，并被广泛应用于计算机科学技术、 自动控制等领域。 时态工作流模型研究 p e 打i 网是一种信息处理系统的描述与分析工具，能够表示系统中并行、同步、 冲突及因果依赖等关系。p e 仃i 网具备坚实的数学基础，这为形式化分析提供了良 好的条件：同时，p c t r i 网又以网图的形式简洁、直观地模拟离散事件系统，使复 杂的系统形象化，从丽降低了建模的难度，提高了模型的易读性。 从结构上看，p e t r i 网是一类特殊的有向图，它有两种结点：库所( p l a c e ) 和 变迁( a n s i t i o n ) 。通常库所用圆圈表示，变迁用矩形表示。有向弧可以从库所 指向变迁，也可以从变迁指向库所，但相同类型的结点之间不能出现有向弧。也 可以认为，p e t r i 网是个二元图( b i p a n i t eg r a p h ) ，其库所与变迁交替地出现在 由弧线连接而成的路径上，每条弧在其起点与终点处各有一个结点。 每条有向弧上标明了对应的权( 正整数) ，一条权为k 的有向弧可以理解成k 条权为1 的平行弧。权重为1 的弧上通常可以省略标记。 下面给出p e t r i 网的形式化定义： 定义2 - 4 一个p e t r i 网是一个四元组：p n = ( p t ，f ，w ) ，其中 ( 1 ) p 是库所的有限集合； ( 2 ) t 是变迁的有限集合，并且满足p n t = 中，p u t 巾； ( 3 ) f 口1 ) u 口p ) ，它是一组有向弧的集合，称为流关系； ( 4 ) w ：卜z + ，其中z + 指正整数的集合，w 为p n 的每一条弧赋予一个权， 称为权函数。 库所丽笨做变迁啪输入库所，当且仅当存在一个从硎的有向弧。库所西尔 做变迁啪输出库所，当且仅当存在一个从垤0 p 的有向弧。我们使用壤示变迁 的输入库所集合，符号抽、瘌p 有类似的意义，即p 是共享腓为输入库所的 变迁集合。 任何时刻，库所当中包含零个或者多个标记，标记用一个黑点表示。状态m ， 也称为标识，是标记在库所上的分布，即m p j i n 。我们将一个状态表现如下： p 1 + 劲2 + 1 p 3 + 印4 是这样一个状态，库所p l 中有一个标记，库所p 2 中有两个标记， p 3 中有一个标记，m 中没有标记，当然也可以表示为l p l + z 阮+ 1 舶。为了比较状态， 时态工作流模型研究 我们定义了一个偏序关系，对于任意两个状态m l 和m 2 ，m 1 m 2 ，当且仅当v p p ：m 1 ( p ) m 2 0 ) ，这里m p ) 表示在状态m 下库历p 中标记的个数。 一个带有初始标识m o 的p e 仃i 网可以用( p n ，m o ) 表示，称为p e t r j 网系统。在不 引起混淆的情况下，也可以称( p n ，m 0 ) 为p c 仃i 网。 如果一个网中每一条有向弧的权重都是1 ，即是说权函数w ；1 ，那么称这个 网为平凡( o r d i n a r y ) 的p e 仃i 网，也称为标识网( m a r k e dn e t ) 。值得一提的是， 平凡的p c t r i 网与非平凡的p e t r i 网拥有相同的建模能力，两者的差异仅仅在于建模 的效率。 许多系统的行为能够用状态以及状态的改变进行描述。为了模拟一个系统的 动态行为，p e t r i 网的标识可以使用以下的变迁触发规则进行改变： 定义2 - 5 令p n = 口，t ，f ，w ) 为一个p e t r i 网，则有 ( 1 ) 对于v x p u t ，x ： yl ( y ，x ) f ，y p u t ，x 称为x 的前集； ( 2 ) 对于v x p u t ，x = y l ( x ，y ) f ，y e p u t ) ，x 称为x 的后集； ( 3 ) 对于v fet ，在标识m 下，如果对于f 中的任意元青如，均有m 0 ) w ( p ，o ，贝| i 称疰标识m 下是使能的( e 响b l e d ) 或可动的； ( 4 ) 若庄标识m 下使能，则河以被触发( 觚) 。触发之后，m 变成如下 定义的新标识m ：对于，p p ，有 i m 0 ) = m ( p ) - w p ，d ，p e 吖。； “m o ，) = m p ) + w g 们，pe 扣； i i i m o ) = m 0 ) + w o ，p ) j w ( p ，0 ，p e f p e 扣： i v m 0 ) = m ( p ) ，其他。 把触发f 导致标识m 变成m 记作m l m ，m 称为m 的后继标识。 上述的变迁触发规则可以从图2 3 中得到阐明，它通过p c 仃i 网描述了化学反 应2 h 2 + 0 2 _ ，2 h 2 0 。图2 3 ( a ) 中表明各有2 个单位的h 2 与0 2 ，变迁f 是使能的。通过 1 4 时态工作流模型研究 触发f ，标识变为图2 - 3 ( b ) 中所示的样子，在2 - 3 ( b ) 中f 不再是使能的。 2 2 2 行为特性 ( b ) 田2 _ 3 化学反应2 h 2 加z 一2 h 2 0 的p e t ri 网描述 根据是否与初始标识有关的原则，p e 岫网的性质可以分为两种类型：与初始 标识相关的性质称为行为特性；与初始标识无关的性质称为结构特性。接下来我 们对p e t r i 网的几种重要的行为特性一一包括可达性( r c a c h a b i l i t v ) 、有界性 ( b o u n d c d n e 豁) 以及活性( 1 i v e n e s s ) 进行定义。 1 可达性 可达性是最基本的行为特性。触发一个使能的变迁将会使得p e t r i 网的标识发 生改变，一个触发序列将会产生一个标识的序列。因此，可以对可达性进行如下 的定义： 定义2 - 6 在p e 仃i 网系统( p n m 0 ) 中，当存在触发序列仃= t l t 2 t n 可以使得标 识m o 变成m 。时，贝q 称m n 是从m 0 可达的( r e a c h a b l e ) ，用m d 鱼一m 。表示。所有 从m o 可达的标识称为m o 的可达集合，用r ( p n ，m o ) 或r ( m 0 ) 表示。而所有能够从 时态工作流模型研究 m o 启动的变迁序列则记为i 删，m 0 ) 或l m o ) 。 p e t r i 网的可达性问题即是对于给定的m o 与m 。，确定m 。r ( m o ) 是否成立。可 达树可用来形象地描述从m o 出发所有可能的触发序列的集合，它是将r ( m o ) 中的 各个标识作为节点，从m o 到各个节点的触发序列为枝画成的树。在通常的情况 下，可达性问题是可解的，但至少必须耗费指数空间( 与时间) 才能够达到目的 【冽。 2 有界性 定义2 - 7 对于一个p e 砸网系统( p n ，m 0 )