（计算机软件与理论专业论文）基于信牌驱动模型的工作流动态仿真和模型分析.pdf

摘要 目前，为企业业务流程提供建模、管理和集成、仿真分析与优化的工作流管理技术 受到了广泛的关注和应用。但是，很少有工作流产品为建模人员提供全面的工作流仿真 分析功能来验证、诊断和优化过程模型，从而为企业业务流程重组和优化提供更有效的 支持。 工作流模型的能力分析以及正确性验证的方式可分为静态分析和动态仿真两种。其 中工作流动态仿真由于实用性，在工作流管理技术的研究与实践中受到越来越多的关 注。本文系统地介绍了工作流动态仿真的基本概念与基本理论，侧重研究通过动态仿真 手段对业务流程进行测试与分析，验证流程在适当的时间，由适当的参与者做适当的工 作。针对仿真过程中的几个关键问题设置仿真环境、事件表的生成及活动仿真时间 的计算做了较为深入的研究，并提出了工作流模型仿真系统的体系结构和工作流模型综 合分析、评价指标。通过设定仿真参数，仿真引擎自动模拟活动的执行，并在最后为用 户提供所需的仿真报表。用户在这些统计数据的基础上进一步分析和评价工作流过程模 型的各项性能，进而通过改进得到一个较优的过程模型，从而为企业业务过程持续改进 提供支持。 “面向流程管理的软件生产线 是一个国家“8 6 3 重点项目，我所在实验室承担了 其中一部分的工作，而我所参与的项目团队负责设计并实现一个基于信牌驱动模型的工 作流仿真系统，这也是这篇论文的基础和依据。 关键词：工作流仿真，信牌驱动工作流模型，仿真环境，模型分析 a b s t r a c t n o w a d a y s ，w o r k f l o wm a n a g e m e n tt e c h n o l o g y , w h i c hs u p p o r t s b u s i n e s s p r o c e s s m o d e l i n g ，m a n a g e m e n t ，i n t e g r a t i o n ，s i m u l a t i o na n a l y s i sa n do p t i m i z a t i o n ，i sa p p l i e dw i d e l y h o w e v e r , f e ww o r k f l o wp r o d u c t sp r o v i d em o d e l i n ge n g i n e e rw i t h s i m u l a t i o n a n a l y s i s f u n c t i o nt ov e r i f y , d i a g n o s ea n do p t i m i z eb u s i n e s sp r o c e s sm o d e ls o a st os u s t a i nb u s i n e s s p r o c e s sr e e n g i n e e r i n ga n do p t i m i z i n g t h em o d et oa n a l y z i n gc a p a b i l i t ya n dv e r i f y i n gc o r r e c t n e s so fw o r k f l o wm o d e li sd i v i d e d i ns t a t i ci n s p e c t i o na n dd y n a m i cs i m u l a t i o n b e c a u s eo fi t sp r a c t i c a l i t y , w o r k f l o wd y n a m i c s i m u l a t i o ni s a t t r a c t i n gm o r ea n dm o r ea t t e n t i o n i nw o r k f l o wm a n a g e m e n tt e c h n o l o g y r e s e a r c ha n dp r a c t i c e t h et h e s i si n t r o d u c e st h eb a s i cc o n c e p ta n dt h et h e o r yo ft h ew o r k f l o w d y n a m i cs i m u l a t i o n ，f o c u s i n go nt h ea d o p t i o no fp r o c e s sb ym e a n s o fd y n a m i cs i m u l a t i o nf o r t e s t i n ga n da n a l y s i s ，v e r i f i c a t i o nb u s i n e s sp r o c e s s a tt h er i g h tt i m e ，b yt h ea p p r o p r i a t e p a r t i c i p a n t st od ot h er i g h tt h i n g e s p e c i a l l yt h ep a p e rs t u d ys e v e r a lk e yp r o b l e m si np r o c e s s s i m u l a t i o m s e n i n gu ps i m u l a t i o ne n v i r o n m e n t ，g e n e r a t i n ge v e n tt a b l e ，c a l c u l a t i n ga c t i v i t y s i m u l a t i o nt i m e w es t u d yw o r k f l o ws i m u l a t i o na n db r i n gf o r w a r da r c h i t e c t u r eo fw o r k f l o w m o d e ls i m u l a t i o ns y s t e ma n dw o r k f l o wm o d e la n a l y s i sa n de v a l u a t i o ni n d i c a t o r s s i m u l a t i o n e n g i n ea u t o m a t i c a l l ys i m u l a t e sa c t i v i t ye x e c u t i o na n dp u s h e ss i m u l a t i o nm o d e lu n d e rt h e s i m u l a t i o ne n v i r o n m e n ts e tb yu s e r s f i n a l l y , s e v e r a lk i n d so fs i m u l a t i o nr e p o r t sa r ep r o v i d e d f o ru s e r st oa n a l y z ep e r f o r m a n c ei n d e x e so ft h i sp r o c e s sm o d e l ，a n dt h e nt oh e l pu s e r sg e ta b e t t e rp r o c e s sm o d e ls oa st os u p p o r te n t e r p r i s eb u s i n e s sp r o c e s si m p r o v e m e n t p r o c e s sm a n a g e m e n to r i e n t e ds o f t w a r ep r o d u c t i o nl i n e ”i san a t i o n a l ”8 6 3 ”k e yp r o j e c t m yl a b o r a t o r yu n d e r t a k e sp a r to ft h ew o r k sa n dm yt e a mh a sr e s p o n s i b i l i t yt od e s i g na n d i m p l e m e n tw o r k f l o ws i m u l a t i o ns y s t e mb a s e do nx i n p a id r i v e nw o r k f l o wm o d e l ，t h i s i st h e f o u n d a t i o na n db a s i sf o rt h ep a p e r s k e y w o r d s ：w o r k f l o ws i m u l a t i o n , x i n p a id r i v e nw o r k f l o wm o d e l ，s i m u l a t i o ne n v i r o n m e n t ， m o d e la n a l y s i s 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许论 文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论文 收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：! 塾j 坠指导教师签名：学位论文作者签名： ! 竺一型指导教师签名： 孔矽9 年多月2 2 日加9 年多月2 z 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论 文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：酯、铷 炒弓年6 月2 2 日 西北人学硕_ ：学位论文 1 1 研究背景 第一章绪论 工作流管理技术是近几十年来学术界和企业界关注的热点研究领域。工作流技术的 标准化组织工作流管理联盟( w o r k f l o wm a n a g e m e n tc o a l i t i o n ) 于1 9 9 3 年成立。它 的成立标志着工作流技术在计算机应用领域作为一项独立的技术被大家认识和接受。 八十年代中期，工作流产品最早由f i l e n e t 、v i e w s t a r 公司率先开发。他们把实例跟 踪、关键字索引、图像扫描、结构化路6 ( s t r u c t u r e x tr o u t i n g ) 功能整合在一起，实现了计 算机化的文档处理，从而全面支持某些业务流程，这种集成化的软件便是早期的工作流 管理系统。由此可以看出，工作流从最开始就是作为一种面向过程的系统集成技术而出 现的【l l 。 工作流管理系统已由最初的无纸化办公环境，转而成为同化企业复杂信息环境、实 现业务流程自动化的必要工具。工作流管理系统在企业中发挥的主要的作用和意义： 规范化企业管理制度；缩短业务过程的处理时间，例如在办公自动化环境中，对工作 流程进行更好的规划，使相互独立的活动可以并行的执行，从而降低文档的传递时间； 更好地与上下游企业形成供应链网络，以达到快速响应市场变化的目的；提高工作 质量，如自动为工作人员提供完成某个任务所需要的相关信息。在客户服务中，能够快 速方便地访问所有工作流程和相关数据，从而提高客户服务质量等。 虽然工作流管理技术和相关软件不断迅速的发展，并在一些企业的实际应用中取得 了一定的成就，但是从总体上看来，工作流管理系统的实际应用情况还不能达到用户所 期待的水平。这种情况是因为工作流技术自身还不够成熟，而且现有的工作流产品在一 定程度上还存在不足。工作流仿真更是在最近几年才引起人们的关注和重视。工作流仿 真系统作为工作流管理系统的一个重要补充，在工作流模型定义中的评估、优化作用已 经越来越明显，但是由于发展时间短、技术比较新，与工作流建模和管理技术相比，工 作流模型仿真还是一个比较薄弱的环节。 1 2 论文研究的目的和意义 在工作流建模技术不断发展的大背景下，更复杂的业务流程建模成为可能，从而对 于工作流仿真的需求也更为迫切： 第一章绪论 ( 1 ) 将具有设计缺陷的复杂的工作流定义( w o r k f l o wp r o c e s sd e f i n i t i o n ) 投入使用 之后，一旦出现问题，对其进行的修改将花费模型设计人员很多的时间和精力； ( 2 ) 工作流仿真在仿真环境中模拟业务过程的变动和企业环境的变化，从而不会对 实际的业务过程运行产生影响，具有风险小、安全经济的特点，避免了改变实际的业务 流程所带来的不可挽回的影响； ( 3 ) 在一般情况下，实际业务流程的实施经常需要付出较高的代价，而对于那些正 在设计过程中的业务流程、未来流程等，甚至根本没有办法实际运行。于是，通过工作 流仿真的方式，利用工作流仿真模型在仿真环境中进行仿真运行，并根据仿真结果来评 估真实流程的性能，不失为一种经济可行的手段。 所以，工作流模型设计人员需要工作流动态仿真系统来对于设计好的过程模型进行 性能分析和优化。 1 3 工作流仿真概述 目前，工作流仿真分析法作为最常见和最有效的工作流模型分析方法，被广泛的关 注和应用。工作流的仿真分析法通过定性定量的分析企业业务流程的多种性能指标，为 查找业务过程的瓶颈、死锁因素和判断业务流程的运行性能优劣提供了很大的帮助。仿 真报表展示的统计数据可以作为业务流程的评价指标，同时，这些数据可以帮助企业决 策人员判断过程改进方案的可行性和有效性。 在基于离散事件驱动的仿真引擎的支持下，工作流仿真系统在仿真环境中模拟执行 各个工作流活动。经过多次的仿真运行，仿真系统统计工作流模型的运行数据，例如流 程周期时间、活动成本和活动等待时间等，然后，模型设计人员可以根据这些统计数据 进一步的分析和评估企业业务流程的各项性能。 工作流动态仿真分析法具有以下优点： ( 1 ) 节省运行时间、效率高。个业务流程在现实当中也许需要运行几天甚至几个 月才能完成，但是通过仿真也许只需要几个小时或者几分钟就能完成： ( 2 ) 安全性高、风险低。由于工作流模型仿真可以通过修改仿真环境的设置和修改 工作流仿真模型来体现业务流程的变化，这些改变不会影响真实的业务过程，所以即使 仿真失败也不会带来不可挽回的影响； ( 3 ) 经济实用，成本低。在工作流模型的仿真过程中，由于资源、参与者都是虚拟 产生的，所以除了仿真系统的运行消耗外，不需要消耗其他的资源，所以非常经济。 2 两北大学硕士学位论文 通过工作流模型仿真能够分析和计算企业经营过程的多项性能指标，它可以： ( 1 ) 为企业决策人员提供帮助。仿真数据从统计意义上反映了业务流程的性能，它 能够为企业决策提供可靠的依据，从而帮助决策人员做出决定； ( 2 ) 帮助企业管理人员制定资源计划，包括验证资源需求的合理性、评估增加或减 少资源对经营过程带来的影响： ( 3 ) 进行面向活动的成本分析，例如判断业务流程中哪些活动的成本偏高，哪些活 动带来的收益很少却占用了过多的资源。通过对活动成本的分析进一步寻求降低业务流 程成本的方法； ( 4 ) 验证工作流过程模型。可以参照真实业务流程运行环境，设置工作流仿真环境， 通过工作流仿真，将仿真结果与真实的业务流程运行结果相比较，可以验证设计的工作 流模型是否能够反映业务过程的主要特征，如果不能准确描述，就需要修改工作流模型； ( 5 ) 分析经营过程中可能存在的瓶颈因素。系统瓶颈经常与利用率非常高的资源或 者执行时间长的活动相关。通过分析工作流仿真得到的统计数据，可以掌握过程中哪些 资源的利用率偏高，哪些活动的执行时间过长等信息，从而找到过程中的瓶颈。 1 4 国内外相关的研究现状和发展 仿真作为一种有效的模型验证和分析的手段，己为多家厂商所接受和采用f 】。以下 对几个典型的工作流建模与仿真工具做出介绍： 1 、m i c r o g r a f x 公司的i g r a f x 建模工具： 作为一种应用比较广泛的支持仿真的建模工具，它通过给图形插入属性信息和脚本 注释，进行工作流过程的仿真。i g r a f x 工具的最大特点就是为用户提供了友好的界面和 灵活多样的仿真报表生成样式。利用i g r a f x 工具，模型设计人员可以方便地建立工作流 模型，并在之后对其进行仿真分析。 该工具对工作流模型的仿真步骤如下： 建模包括创建过程模型并对模型进行必要的静态检查。 设置仿真环境仿真环境的设置包括以下几个方面： 运行环境设置：例如设置仿真的开始时间、仿真结束时间等。 随机事件生成器设置：例如设置事件的发生概率、事件的总个数、事件的问隔时间 等。 仿真资源设置：例如设置员工工作时间表、活动所需的资源的数量、员工的正常工 3 第一章绪论 资、员工的加班工资等。 执行仿真该仿真工具支持仿真过程的同步动画显示，支持开始、挂起、恢复、 单步仿真等功能。 生成报表生成关于时间、成本、资源利用率等指标的仿真报表。仿真报表分 为以下几类： 事务统计表：事务数量、平均周期时间、平均阻塞时间、平均同步等待时间、平均 资源等待时间等。 活动队列统计表：总等待队列、平均等待队列、最大等待队列等。 活动时间统计表：活动的平均执行时间、执行次数、平均工作时间、平均等待时间 笙 寸o 2 、清华大学的c i m f l o ws i m u l a t o r 仿真工具 作为c i m f l o w 软件中的一个工作流仿真工具，c i m f i o ws i m u l a t o r 与工作流建模工 具c i m f l o wm o d e l e r 一起组成了一个完整的建模仿真系统。 c i m f i o ws i m u l a t o r 工具具有友好、容易使用的图形化用户界面，用户可以通过该界 面对工作流模型进行仿真。该工具对工作流过程模型的仿真分为以下几个步骤： 打开并解析一个工作流过程模型； 建立工作流仿真资源模型，即定义各类仿真资源的名称、数量、成本等； 为过程模型中的每一个活动设置仿真属性，其中包括：活动的类型、活动执行时 间、活动执行所需的仿真资源等； 执行工作流仿真； 生成仿真统计报表。 可以看出，c i m f i o ws i m u l a t o r 仿真工具与i g r a f x 建模仿真工具有非常多相似的地 方。只是i g r a f x 建模工具将建模与仿真功能集成在一起，而c i m f i o ws i m u l a t o r 仿真工 具是于建模工具分离的，可以单独使用。 纵观当前市面上的工作流仿真产品，我们可以发现很少有工作流产品为建模人员提 供全面的工作流仿真分析功能来验证、诊断和优化过程模型。例如，对于模型执行过程 的追踪和随机修改相关数据对于一个工作流仿真系统来说都是相当的重要的功能，本篇 论文的主要工作是针对信牌驱动工作流模型构造仿真系统，并补充这些功能，帮助模型 设计人员在模型投入使用之前找到模型中存在的问题，从而为企业业务流程重组和优化 提供更有效的支持。 4 西北大学硕i ：学位论文 1 5 论文的主要工作 作为国家“8 6 3 ”重点项目“面向流程管理的软件生产线 的其中一个子项目， 我们需要为s y n c h r o f l o w 工作流系统开发一个仿真子系统，s y n c h r o f l o w 工作流系统 包括工作流模型设计工具，组织结构建模工具，信牌驱动工作流引擎及其管理控制台， 但是缺少工作流仿真的相关功能。我们参考现有的工作流仿真产品和相关论文，给出了 仿真系统的体系结构，实现了一个b s 结构的工作流仿真系统，通过对工作流模型中的 各个活动的模拟执行，在仿真过程中分析和收集性能评价指标并生成仿真报表最终展示 给用户。工作流模型的仿真分为性能仿真、功能性仿真和结构性仿真三种。性能仿真分 析业务流程的运行时间、资源利用率等性能指标，功能性仿真验证工作流过程模型是否 实现了业务流程的指定功能，结构性仿真主要分析工作流模型执行时的执行路径。本文 主要对工作流的性能仿真做了深入研究。 1 6 论文组织结构 本文主要论述了工作流仿真和性能分析的关键技术及研究方法，重点讨论了基于信 牌驱动工作流模型仿真的内容。论文共分为六章，具体的组织结构如下：第一章为绪论， 介绍了论文的研究背景，研究目的和意义，及主要工作等内容；第二章介绍了工作流技 术、p e t r i 网及基于p e t r i 网的信牌驱动工作流模型的基本概念；第三章介绍了离散事件 动态仿真概念、原理和方法，给出了仿真控制流程；第四章具体讨论了信牌驱动工作流 仿真中的几个关键技术，其中包括仿真方式、仿真环境设置、活动仿真时问的计算、仿 真实体的识别，并给出了工作流仿真算法的步骤；第五章针对工作流仿真的仿真分析流 程，给出了工作流仿真的性能评价指标，并讨论了工作流仿真性能评价的基本原理和综 合评价方法；第六章简单介绍了信牌驱动工作流仿真系统的设计与实现，并给出了仿真 系统的体系结构、详细设计类图和数据库表设计；最后是工作总结与下一步的研究工作。 5 第二章p e t r i 网和信牌驱动t 作流模型 第二章p e t ri 网和信牌驱动工作流模型 2 1 工作流技术及工作流管理系统 2 1 1 工作流技术的起源与发展 八十年代初期，纸张作为信息的主要的载体，在各行各业的同常业务活动中所起到 了不可替代的作用。与企业业务活动密切相关的表单、文件、技术资料等文档，都是以 纸张的形式在各部门之间互相传递的。由于其低效性和资源浪费，于是人们希望出现一 种无纸化的、基于计算机办公的工作环境，用于实现同常表单处理的自动化和电子化。 这样的系统可以认为是工作流管理系统的雏形。 九十年代后，随着计算机的普及和网络的延伸，现代企业的信息资源越来越表现出 一种异构、分布、松散耦合的特点。这说明了集中式的信息处理方式已经不能满足现代 企业的要求，现代企业需要找到一种方式将大规模的、异构的、分布式的企业信息资源 整合在一起，以促进相关联的任务活动以更高的效率运转，并且在运行过程中接受密切 监控。最初，工作流管理系统的目标是创建无纸化办公环境，但是现在已经逐渐的转变 成为帮助企业实现业务流程自动化的必要工具。正是由于这样的一个转变，工作流技术 进入了一个崭新的发展阶段，触及到了前所未有的领域，科学工作者也从更深的层次、 更广的领域上对工作流展开研究【1 6 1 。 在1 9 9 3 成立的工作流技术的标准化组织一一工作流管理联盟( w o r k f l o w m a n a g e m e n tc o a l i t i o n ) 将工作流技术的研究推入了更为繁荣的时代。同时，许多工作流 相关产品出现，更多新兴技术被集成到工作流系统当中1 7 , 1 8 l 。数据库系统、w e b 服务、 分布式计算、电子邮件等都已被整合到工作流管理系统之中，市场上的工作流产品大大 的丰富，基本上可以分为三类： l 、基于文件的工作流系统这种工作流系统通过在相互之间共享文件的方式来帮 助完成任务。代表产品有f i l e n e t 的v i s u a lw o r k f l o w 、i b m 的f l o w m a r k 等； 2 、基于消息的工作流系统以电子邮件系统为支撑，文档信息通过电子邮件的方 式在用户之间相互传递，共享信息以协作完成任务。代表产品有n o v e l l 与f i l e n e t 合作 开发的e n s e m b l e 、j e t f o r m 、l n t e p p o 等； 3 、基于w e b 的工作流系统通过w w w 来实现任务的协作。代表产品有a c t i o n t e c h n o l o g i e s 的a c t i o nw o r k sm e t r o 等。 6 西北大学硕上学位论文 2 1 2 工作流定义 工作流是描述一个企业或组织的业务处理活动的模型。不同的工作流研究人员和工 作流产品生产厂商对于工作流给出了不同的定义： 工作流管理联盟的定义：工作流是一类能够完全或者部分自动执行的业务过程，根 据一系列过程规则，文档、信息或任务能够在不同的执行者之间传递、执行1 8 】。 i b m 的定义：工作流是业务过程中的种计算机化的表示模型，定义了完成整个过 程所需用的各种参数。这些参数包括对过程中每一个单独步骤的定义，步骤问的执行顺 序、条件以及数据流的建立、每一步骤由谁负责以及每个活动所需要的应用程序【2 0 1 。 w m p v a nd e ra a l s t 的定义：i 作流是一系列工作的偏序集。工作的序列可以有多 种方式，比如工作x 与y 满足x y ，当且仅当x 在y 开始之前就己经就绪【2 2 1 。 范玉顺的定义：工作流是一种反映业务流程的计算机化的模型，它是为了在先进计 算机环境支持下实现经营过程集成与经营过程自动化而建立的可由工作流管理系统执 行的业务模型【1 4 】。 虽然以上对于工作流的非形式化定义各有不同，但是从以上的定义中我们可以发现 研究工作流技术的学者都有一个共识，他们都认为工作流是业务过程的一个计算机化的 实现，业务过程需要转化为计算机可以执行的工作流模型。 在实际情况中可以更广泛地把凡是计算机软件系统( 工作流管理系统) 控制其执行 的过程都称为工作流。工作流系统首先定义好相关的规则，然后按照规则将文档、信息 或任务在参与者之间进行传递，以提高业务过程的自动化程度，从而帮助用户实现经营 目标。用一句话总结工作流的特点就是“在适当的时间把适当的信息传递给适当的人 。 2 1 3 工作流管理系统的定义 前面介绍了工作流的基本概念，以下将给出工作流管理系统的定义。w f m c 对于工 作流管理系统的定义是：工作流管理系统是一个软件系统，完成工作流的定义和管理， 并按照在计算机中预先定义好的工作流逻辑推进工作流实例的执行。 工作流管理系统并不属于企业的业务系统，它为企业业务系统的运行提供了一个软 件支撑环境，从某种程度上说，企业业务系统与工作流管理系统的关系非常类似于应用 软件与计算机操作系统之间的关系。不同的是工作流管理系统支撑的范围更大，运用的 环境更为复杂而已。所以也有人将工作流管理系统称作业务操作系统。 市面上不同的工作流管理系统具有不同的应用范围和部署方式，但是从较高的层次 7 第二章p e t r i 网和信牌驱动t 作流模型 来观察就会发现这些工作流系统还是具有一些共同的特征。可以发现所有的工作流管理 系统都具有三种功能： 工作流建模功能。通过一种或多种建模技术以及相应的工具，利用计算机可识别 处理的形式化定义描述实际的业务流程，从而生成工作流模型： 在工作流运行阶段的控制功能。在工作流引擎的支持之下，执行工作流过程，并 完成对工作流过程模型中各个活动的控制和调度功能； 在工作流运行阶段的人机交互功能。在工作流执行过程中，通过人机交互界面， 用户可以实现对各种活动的交互，例如挂起和恢复活动。 图l 描述了工作流管理系统的特征1 1 3 】。 图1 工作流管理系统的特征 2 1 4 工作流模型简介 工作流模型是对工作流的抽象表示，也就是对业务过程的抽象表示【1 4 】。工作流模型 是业务过程的计算机化的定义，通过建模工具使实际的业务过程转化为计算机可处理的 形式化定义，从而使工作流模型可以在计算机上运行，建模过程所得到的定义通常可称 为过程模型、过程定义、过程模板或过程元数据。 对于基本的工作流模型应该完整支持工作流的概念定义，而且需要为建模人员提供 定义工作流模型需要的元素和组件，而对于理想的工作流模型还应该能为任意业务流程 建模，并可以满足建模人员在创建模型过程中提出的各种要求。此外，为了能够完整描 r 西北大学硕上学位论文 述一个业务过程，工作流模型不仅需要明确地表达活动与活动之间的关系，还应该对活 动间传递的数据、活动的执行人、活动需要的资源等方面进行定义。工作流模型通常由 过程模型、组织模型、资源模型和工作流相关数据四个部分组成l i 刖。以下对四个部分分 别介绍： 过程模型用来定义和描述工作流的过程逻辑，工作流模型的其他三个部分均为过 程模型提供支持，以完整的描述整个业务流程，所以可以说过程模型是整个工作流模型 的基础与核心。业务流程中的所有活动以及活动之间的依赖关系组成过程模型。 组织模型为企业的组织结构建模，它表述工作流模型中有关人员的视图，其中包 括多种不同形式的组织元素和每种组织元素内部的层次关系，通常为一种树形结构。在 工作流建模环境中建立过程模型时，用户可以为活动节点设置有关组织的属性。 资源模型为企业资源的组织结构建模，与组织模型类似，它包括几种不同形式的 资源容器和容器内部的层次关系，直到最终的原子级资源个体。在工作流的执行过程中， 组织中的参与者必须得到相关资源才能够完成相应活动。 工作流相关数据用来定义工作流运行过程中需要用到的数据，它既包括简单的数 据类型也包括复杂的企业对象。当工作流需要对不同活动进行选择性路由时，相关数据 对各种条件的判断提供支持。 整个工作流模型的组成结构如图2 所示。 9 第二章p e t r i 网和信牌驱动t 作流模型 过程模型 工作流相关数据 图2 工作流模型的组成结构 工作流模型是模型仿真和模型改进的基础，过程模型是对业务过程的抽象表示。工 作流的过程模型用来定义工作流的过程逻辑，是整个工作流模型的基础与核心【2 3 1 。 2 2p e t ri 网概述 工作流模型应该以形式化方法作为基础。原因是：1 ) 形式化方法可以使模型清晰、 易懂、无二义性：2 ) 形式化方法可以使模型更容易分析【2 8 】。p e t r i 网是对工作流进行建 模和分析的最主要的形式化方法之一f 2 9 3 0 , 3 1 , 3 2 , 3 3 1 。经典的p e t r i 网是德国科学家c a r la d a m p e t r i 在上个世纪六十年代提出来的，随后对于p e t r i 网的相关的研究不断深入，许多科 学工作者也对p e t r i 网进行了补充和发展，例如t i m ep e t r in e t s l 3 4 1 、c o l o r e dp e t r in e t s t 3 熨、 o b j e c tp e t r in e t s | 3 6 l 、s t o c h a s t i cp e t r in e t s t 3 7 l 等。p e t r i 网在工作流建模、柔性制造系统、 业务处理等等许多领域都被广泛的应用。使用p e t r i 网描述业务过程主要有以下几个原 因1 3 8 】： ( 1 ) p e t r i 网是一种图形化语言，非常便于理解； ( 2 ) p e t r i 网( 包括各种高级网系统) 都有形式化的语义定义，一个p e t r i 网模型加 1 0 两北大学硕上学位论文 上相应的语义就能描述一个业务过程； ( 3 ) p e t r i 网能够同时显式地描述系统状态和事件，便于对系统的理解和分析： ( 4 ) p e t r i 网模型提供了丰富的系统分析技术，例如利用p e t r i 可以对系统的活性 ( 1 i v e n e s s ) 、有界性( b o u n d n e s s ) 、安全性( s a f e t y ) 等方面做出分析计算，也可以计算 系统的性能。荷兰学者w m pv a nd e ra a l s t 对基于p e t r i 网的工作流网做了很多重要 的研究【2 4 3 9 4 0 1 。 p e t r i 网模型是一个有向图，由两种节点组成，即库所和变迁。有向弧( a r c ) 可以从 库所指向变迁，或者从变迁指向库所。以下是对p e t r i 网的形式化定义： ( 1 ) p e t r i 网的基本术语 a 、资源( r e s o u r c e ) 系统中发生变化所涉及的与系统状态有关的因素，称为资源。 包括产品、人员、资金、原材料、信息等。 b 、库所( p l a c e ) ：将资源按其作用分成不同的种类，每一类存放在一个位置，则该 位置抽象为一个库所，或者称为p 元素，库所既是存放资源的场所，也可以表示该场所 中存放的资源。 c 、变迁( t r a n s i t i o n ) ：资源的消耗、使用及产生对应于库所的变化，在p e t r i 网理 论中称之为变迁，又称为t 元素。 ( 2 ) p e t r i 网的定义及其图形化表示 定义l ：一个p e t r i 网可表示为一个五元组刚= ( 尸，t ，a ，w ，m ) 其中： p 为库所集，是非空有限集尸= p i ，p 2 ，p m ) ； t 为变迁集，是非空有限集丁= t if 2 ，乙 ； a 是由一个p 元素和一个t 元素组成的序偶的集合。满足彳p x t u t p ，p 和 t 还需要满足尸nt = a ； w 是映射，即w ：a 一 1 ，2 ，3 ，) ，称为p n 的权函数，它对各弧线赋权值，用 ，( b ，t j ) 7 f ；i ld ( 只，t y ) 分别表示由库所b 到变迁和变迁0 到库所只的有向弧的权重； m 是p n 的一个标识，是p 到非负整数集n 的映射，即m ：尸兮 1 ，2 ，3 ， ，为 初始标识。 若用圆形表示库所，用矩形表示变迁，用有向弧表示库所和变迁的有序对，则构成 第_ 二章p e t r i 网和信牌驱动丁作流模型 了p e t r i 网的图形表示。标识( m a r k i n g ) 为每个库所指定了一个非负的整数，表示库所 内所含令牌( t o k e n ) 的数目。在图形中表现为库所内的黑点的个数。 定义2 ：一个p e t r i 网p n 的标识是一个函数向量m ：p _ n 。若m ( 只) = m ，则称 库所只含有m 个令牌。 ( 3 ) p e t r i 网的变迁规则( t r a n s i t i o nr o l e s ) p e t r i 网的运行由网中标识的数目和分布情况来控制。标识驻留在库所里，控制变迁 的运行。p e t r i 网是由变迁的引发( f i r i n g ) 来运行。变迁的引发是指从它的各个输入位 置移走标识，并将产生的新标识分配到它的某个输出位置中。一个变迁只有当它使能 ( e n a b l e d ) 时才可以引发。当一个变迁的每一个输入位置的标识的个数不少于从这个输 入位置到变迁的弧的权数，称这个变迁为使能的。 定义4 ：带有标识m 的p e t r i 网尸= ( p ，m ) ，若对于任意的b p 都有 m ( b ) w ( b ，t j ) ，其中，w ( 仍，0 ) 是b 到0 的连线的权重，则称变迁0 是使能的。 定义5 ：当p e t r i 网p n = ( p ，眠) 的变迁f ，使能时，则它可以引发产生一个新的标识 m ( 一且m ( 尸) = ( 尸) + d ( b ，0 ) 一，( 只，t j ) 。图3 表示的是常见的水的化学反应式： 2 吼+ d 2 = 2 d 。 h ，h 2 0 2 图3 水化学反应式的p e t r i 网表示 1 2 西北大学颤十学位论文 2 3 基于p a r ri 网的信牌驱动工作漉模型 西北大学软件工程研究所在工作流矗面进行了十余年的探索和研究，并提出了基于 p e 丽网的信牌驱动工作流计算模型。 “信牌”制是一种始于宋代的古代官府行政事务处理制度。我国古代官府在执行任 务时，用“信牌”作为凭证，只有当官员持有信牌时才能执行相应的任务。借用这一概 念，并在采用p e t r i 网对控制转移结构描述的基础上，将p e t r i 网中托肯( t o k e n ) 、库所 ( p l a c e ) 和变迁( t r a n s i t i o n ) 等专业术语用相对容易接受和理解的信牌、信牌箱和活动 等来描述，同时引入了相关数据、环境数据、转移条件等元素，建立了信牌驱动的工作 流模型。如图4 所示： 怍流过程定义 -0 面【= 匕 陌吲i 碗 臼回回 圆圈圆 静态活自 日 ：孽_ _ 蔓 i 6 f 瞥“鸭一了1 ! j ；i 髫缓彩筹 1 j一冉j m m f ， 。w l , j i f i 矿：葫、i _ 州m 瓤- ，i !f - - i “m 掣【兰! h 磐i，i “竹。 图4 信牌驱动工作流模型 静态描述、状态描述及动态执行规则三部分的内容完整地组成了信牌驱动式工作流 计算模型的形式化描述。这三部分共同定义了模型的静态结构、活动h j 的依赖关系及其 执行顺序等，定义了模型的计算过程h “。 2 31 信牌驱动工作流模型的静态描述 静态描述：对流程中各个基本元素及其之间关系的描述。 l3 胁制 礤 淼了身 甲 吣薹 龇 第二章p e t r i 网和信牌驱动工作流模型 定义1 ：我们称一个多元组m = ( x ，y ，丁，p ，p t ，彳，f ，缈，钿，删彳) 为一个信牌驱 动工作流模型。其中： x ：全局变量集合。全局变量是流程中参与处理或控制转移的相关数据。 v ：值域集合。值域代表相关变量的取值范围，反映数据在流程中各个时刻的状态。 t ：x 寸y ，x 到v 的映射，表示变量的类型。( 即：对于任一个x x ，丁( x ) y ) 。 p ：信牌箱集合。在流程执行中信牌箱的状态决定活动实例的控制转移。 p t ：终止信牌箱。p t p ，当厅中的信牌数大于0 时认为流程结束。 a ：活动集合。每个元素口彳表示一个活动实体，由i d 、类型、功能函数和后继 函数等属性构成。 f ：转移集。定义了信牌箱和活动的联系。f ( 彳x p ) u ( p x 彳) w ：f n 称为转移的权重。 盯：是a 的一个划分 以d ，4 珊) ，即以dn n 彳脚= 9 ， 彳月du 如ru 彳船r = 彳。 删彳：是a 的另一个划分 d 么，伽彳，黼彳) ，即彳d 彳n 伽彳n 黼彳= o ， 舢彳u 伽彳u 黼彳= 1 。 转移集可定义每个活动的前信牌箱集和后信牌箱集如下： 定义2 ：对每一个活动口彳，定义： 前信牌箱集：口= pi ( p ，口) f ，p 尸) 后信牌箱集：口= pl0 ，p ) f ，p p 定义3 ( 功能函数) ：z ( 五，毛) = 乃，其中五，乃z 。对每个活动q 彳有 一个功能函数z 与之对应，用来描述工作流执行过程中由活动引起的状态变化。彳- j 出i 参与人员操作执行，也可由软件自动执行。此功能函数的语义既可以在流程定义时严格 定义，也可以用非形式地方法描述，如“阅读并修改详细设计 等，在流程执行时由参 与者确定。 定义4 ( 后继函数) ：g ( x l ，) ：m 屹专g 1 4 西北人学硕十学位论文 其中，一丁( ) ，f = l ，n ，g 是口。的子集。此函数决定活动执行结束后可以向哪 些信牌箱中放置信牌。与功能函数一样，可以用非形式化的语言描述后继函数的语义， 而在运行时由参与者确定。后继函数并不需要与活动一一对应，若某活动的后继函数属 性为空，则表示在其功能函数执行结束后向其所有后信牌箱中放置信牌。 定义5 ( 路径和非循环路径) ：设m = ( x ，v ，t ，p ，p t ，a ，f ，w ，盯，删彳) 为信牌驱 动模型， 令l = a ia 2 ，a n 是一个序列，q p u a ( i = l ，2 ，刀) 。如果 ( a i ，a e + 1 ) f ( i = l ，2 ，n - 1 ) ，则口l ，口2 ，称是m 的一条路径l ，且称 q l ( i = l ，2 ，刀一1 ) ，l 的长度为f l 。v i ，j = l ，2 ，l 如果f jj a i 巳，则称 q ，a 2 ，a 一是m 的一条非循环路径。如果存在m 的一条路径三：a i 口2 ，口一，其中口l 是 开始信牌箱节点，则称为可达的。 定义6 ( 必经节点) ：设m = ( x ，v ，t ，p ，p t ，a ，f ，w ，盯，删彳) 为信牌驱动模型， v n a ，称y a 是的必经结点，当且仅当对任何从开始结点到结点的非循环路 径l ，y l 。 定义7 ( 两点之间的距离) ：设，n a ，则y 和n 之间所有路径中长度最短的路 径长度称为y 和n 之间的距离。 定义8 ( 聚焦点) ：设m = ( x ，矿，t ，p ，p t ，a ，f ，w ，仃，删么) 为信牌驱动模型， n 一d 彳，当y 为n 的必经结点中与n 的距离最短的结点，则称y 是n 的聚焦点。 从聚焦点的定义可以推论出：如果y 是n 的聚焦点，则从结点y 到结点n 的非循 环路径中都不再含有其它必经结点。 定理1 ( 聚焦点唯一性) ：设m = ( x ，v ，t ，p ，p t ，a ，f ，w ，仃，删彳) 为信牌驱动模 型，n 舢彳，如果了】，肭彳是n 的聚焦点，则y 是唯一的。 定义9 ( 同步区) ：设m = ( x ，v ，t ，p ，p t ，a ，f ，w ，缸，r ，删彳) 为信牌驱动模型， n 舢彳，y 是n 的聚焦点，则从y 出发到达n 的所有路径结点的集合称为结点n 的同步区。将过程定义中所有a n d j o i n 活动的同步区的总合称为过程同步区。 定义1 0 ：在流程执行的某时刻，当活动a 的所有前信牌箱都收到信牌时，我们称此 1s 第二章p e t r i 网和信牌驱动工作流模型 刻活动a 满足激发条件，或活动a 处于可执行状态，等待执行。活动a 经自动或手动启 动后进入执行状态。 信牌驱动模型静态结构中包含若干活动、信牌箱