（计算机软件与理论专业论文）基于着色petri网的工作流建模与分析研究.pdf

摘要 摘要 目前，工作流技术虽然已经得到了很大的发展，但尚还没有一种工作流产品或原型 系统能够在过程执行的可靠性和一致性方面达到与关系数据库管理系统同水平的功能， 究其原因主要是相应的工作流模型在理论和实践上存在模拟分析能力不足等问题，在建 模复杂性和性能提高上还有很大的空间。针对现存的问题，本文以着色p e t r i 网为建模 工具对工作流模型进行了一些研究。 工作流建模主要有两大目的：一是对系统进行模拟和分析，二是对系统进行成本和 预算分析。在模拟和分析方面现有的模型都存在过程建模与过程执行过度耦合的问题， 即在某个组织机构模型上建立的过程必须在同一个组织机构模型上才能执行。造成这种 耦合的原因在于，当前的业务过程管理技术和标准没有区分控制逻辑内部的差别。实际 上业务过程中的控制逻辑有两种：一种是路由逻辑，另外一类是资源管理逻辑。 资源建模正是基于以上目的提出来的。针对工作流中涉及到的资源问题，本文分析 了资源的重要属性和分类，重点研究了稀缺资源的分配和管理，提出了资源池的概念， 并采用着色p e t r i 网方法建立了工作流资源管理器，实现工作流的资源管理和分配。基于 着色p e t d 网的资源管理器模型为工作流系统进行定性和定量分析提供了一个形式化的 基础，同时也为提高工作流过程模型的健壮性提供了一个有效的方法。 而相应地在成本和预算分析方面，基于p e t f i 网的这方面的工作流模型研究还处于 起步阶段，且众多学者提出的模型也多是基于简单p e t r i 网的，这些模型是工作流建模 在成本和预算分析方面的初步的有益探索，但是这些模型摆脱不了p e t r i 网对于复杂的 业务流程和具有多案例的网结构的描述能力不足的弱点。基于实际应用中业务流程的复 杂性，本文提出扩展了价格信息的着色p e t r i 网，讨论了该模型的变迁规则，并针对状 态空间爆炸问题提出了最小成本可达算法。通过模型在业务流程管理中的应用和仿真实 验的分析可以看出，将扩展了价格信息的着色p e t r i 网运用于工作流建模是可行的、有 效的。 关键词：工作流、着色p e t r i 网、c p nt o o l s 、资源建模、资源管理器模型、成本预算分 析、价格着色p 硎网、最小成本可达问题 a b s t r a c t ，- _ - _ - i - 。_ - _ - 。_ _ _ _ - - _ _ _ - _ _ _ _ _ - _ _ _ - _ _ 。_ _ _ _ _ _ _ _ _ _ _ _ _ - _ - - 。1 。- _ _ _ - 。- 。o o 。o 。- _ _ l - - _ _ - 。i - _ _ _ _ - ab s t r a c t a tp r e s e n t , t h ew o r k f i o wt e c h n i q u eh a sb e e nd e v e lo p e dg r e a t l y , b u tt h e r ei sn ow o r k f l o w p r o d u c tn o rp r o t o t y p es y s t e my e tw h o s er e l i a b i l i t ya n dc o n s i s t e n c yi np r o c e d u r ee x e c u t i o n r e a c ht h ef u n c t i o no fr e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e m t h em a j o rc a u s ei st h a tt h e s i m u l a t i n ga n da n a l y z i n gf u c t i o no ft h ee x i s t i n gw o r k f l o wm o d e l sa r en o te n o u g hb o t hi n t h e o r ya n dp r a c t i c e t h e r ei ss t i hal o n gw a yt or e a c ht h ei d e a lm o d e li nc o m l e x i t ya n d p e r f o r m a n c e t om e e tt h ec u r r e n tp r o b l e m id i ds o m er e s e a r c ho nt h ew o r k _ f l o wm o d e l i n gb y u s i n gc o l o u r e dp e t i rn e ta st h em o d e l i n gt o o l si nt h i st h e s i s t h e r ea r et w op u r p o s e sf o rw o r k f l o wm o d e l i n g ：o n ei ss i m u l a t i n ga n da n a l y z i n gt h e s y s t e m ，a n dt h eo t h e ri sd o i n gc o s tb u d g e ta n a l y s i sf o rt h es y s t e m t h ec u r r e n tm o d e l sf o r s i m u l a t i n ga n da n a l y z i n ga leh e a v i l yc o u p l e db e t w e e np r o c e s sm o d e l i n ga n dp r o c e s s e x e c u t i n g t h a ti st os a y , t h ep r o c e s sb a s e do nt h ec e r t a i no r g a n i z a t i o nm o d e lm u s te x e c u t ei n t h es a m em o d e l t h er e a s o ni st h a tt h ec u r r e n tm a n a g e m e n tt e c h n i q u ea n ds t a n d a r do f b u s i n e s s p r o c e s sd on o ts u b d i v i d et h ec o n t r o ll o g i c i nf a c t t h e r ea r et w ok i n d so ft h ec o n t r o ll o g i ci n t h eb u s i n e s sp r o c e s s ：o n ei sr o u t i n gl o g i c ，t h eo t h e ri sr e s o u r c em a n a g e m e n tl o g i c r e s o u c em o d e l i n gi sb a s e do nt h ea b o v e t om e e tt h er e s o u e em a n a g e m e n ti n v o l v e di n t h ew o r k f l o w , t h ei m p o r t a n tp r o p e r t ya n dc l a s s i f i c a t i o no fr e s o u c ew e r ea n a l y z e d ，t h e n e m p h a s i sw a sl a i do nt h ed i s t r i b u t i o na n dm a n a g e m e n to fr a r er e s o u r c e t h er e s o u r c ep o o lw a s p r o p o s e da n dt h ew o r k f l o wr e s o u r c em a n a g e rw a sb u i l tb yu s i n gt h ec o l o u r e dp e t r in e tt o i m p l e m e n tt h er e s o u r c em a n a g e m e n ta n dd i s t r i b u t i o no ft h ew o r k f l o w t h er e s o u r c em a n a g e r m o d e lb a s e do nt h ee o l o u r e dp e t r in e tp r o v i d e saf o r m a lt o o lf o r t h eq u a l i t a t i v ea n d q u a n t i t a t i v ea n a l y s i so ft h ew o r k f l o ws y s t e m w h i l ei t i sav a l i dm e t h o dt od e v e l o pt h e r o b u s t n e s so ft h ew o r k f l o wp r o c e s sm o d e l i nt h ec o s tb u d g nt h ew o r k f l o wm o d e l i n gr e s e a r c hb a s e do np e t r in e ti si nt h e e l e m e n t a r ys t e p s o m em o d e l sw e r eb u i l tb yn u m e r o u ss c h o l a r s ，b u tm o s to ft h e m w e r eb a s e d o nt h ep e t r in e t , t h e ya ls oc a nn o tw d lm o d e lt h ec o m p l e xb u s i n e s sp r o c e s sa n dd e s c r i b et h e n e ts t r u c t u r ew i t hm u l t ic a s e s t om e e tt h ec o m p l e x i t yi nt h ep r a c t i c a lb u s i n e s sp r o c e s s a c o l o u r e dp e t r in e te x t e n d e dw i t hp r i c ei n f o r m a t i o nw a sp r o p o s e d a n dt l l et r a n s i t i o nr u l e so f t h em o d e lw e r ed i s c u s s e d a i s ot om e e tt h es t a t es p a c ee x p l o s i o np r o b l e m ，t h em i n i m u mc o s t g e n e r a t i n ga l g o r i t h mw a sp r o p o s e d i nt h ee n d ，ab u s i n e s sp r o c e s sc a s ei sd e m o n s t r a t e da sa a p p l i c a t i o no ft h em o d e l t h ec o n c l u s i o ni st h a tp r i c ec o i o u r e dp e t r in e ti sag o o dm o d e lt o s o l v et h ec o s t sa n db u d g e ta n a l y s i sp r o b l e mi nt h eb u s i n e s sp r o c e s sm o d e l i n ga n dt h e m i n i m u mc o s t sg e n e r a t i o na l g o r i t h mi sv a l i d k e y w o r d s ：w o r k f o w , c o l o u r e dp e t r in e t s ，c p nt o o l s ，r e s o u r c em o d e l i n g ，r e s o u r c em a n a g e r m o d e l ，c o s tb u d g e t ，p r i c ec o l o u r e dp e t r in e t s ，r e a c h a b i l i t yo fm i n i m u m c o s t s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名： 日 期： 趔翌：z ：! l 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名： 蓟噬 导师签名： 到一一日 期2 笾置驰 第一章绪论 1 1 研究背景 第一章绪论 伴随着社会信息化的发展，现代企业的集团化规模日益扩大，需要处理的信息资源 也随之飞速增长，企业的经营业务过程也越来越复杂。在计算机软件没有成为主要业务 支持工具之前，通常是使用纸张作为信息载体在不同的业务部门之间传递，这种方式效 率很低，处理方式繁琐，不但要耗费大量的人力和物力，而且也容易造成信息的丢失或 者某个流程的脱节，因此对客户的需要不能及时响应和反馈，给企业的生产经营带来不 利的影响。在计算机得到广泛应用，企业信息化水平不断提高的情况下，公司和企业迫 切需要用无纸化的和计算机自动响应的方式来取代以前落后的信息运转方式。通常的业 务处理流程有：销售订单处理流程、物资采购处理流程、库存管理流程和公文审批流程 等，这些信息处理流程构成了公司、企业以及各行政单位的决策活动。如何方便和高效 的进行信息传递是各个业务主体和计算机软件开发人员十分关心的问题【1 儿2 。 因此在这个领域内产生了工作流的概念，它是针对日常工作中具有固定程序的活动 而提出的一个概念，目的是通过将工作分解成定义良好的任务、角色，按照一定的规则 和过程来执行这些任务并对它们进行监控，达到提高办事效率、降低生产成本、提高企 业生产管理水平和企业竞争力的效果。工作流技术一出现就得到了广泛的重视和研究， 并得到了迅速的推广，由最初的公司和企业，延伸到了银行、保险、行政管理和工业制 造等众多领域。进入2 0 世纪9 0 年代以后，随着计算机与网络技术的迅速发展，特别是 i n t e r n e t 应用日益普及的情况下，集中式信息处理的时代已成为过去，取而代之的是大 规模的异构分布式信息处理与应用执行环境。在这种技术背景下，工作流管理系统也由 最初的创建无纸办公环境，开始转变为同化企业复杂信息环境，实现业务流程自动执行 的必要工具。这样的一个转变，把工作流技术带入了一个崭新的发展阶段，使得人们从 更深的层次和更广阔的领域对工作流展开研列3 1 。 在这种深层次的研究过程中，工作流技术开始与其他各种技术相结合。其中就把p e t r i 网这种计算机建模技术应用到了工作流中来，丰富了工作流的建模手段和分析方法，在 图形化建模和数学分析方面提供了一个新的研究课题。这些新技术的集成和融合，不但 极大地提高了工作流产品的性能，而且使得工作流技术不断完善，取得了显著的成果。 1 2 研究现状 1 2 1 工作流管理系统 按照工作流管理联盟的定义，工作流管理系统是软件系统，它完成工作流的定义和 管理，并按照在计算机中预先定义好的工作流逻辑推进工作流实例的执行1 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 ，简称w 蹦c ) 于1 9 9 3 年成立了，这是由多家公司联合成立的国际标准组织，其目的是通过制定工作 流技术及其标准，提高不同工作流产品之间的连通性和协同工作能力。通过使用标准可 以使不同的产品之间协同工作，也可以改善工作流产品与其他i t 服务( 电子邮件、文 档管理) 之间的集成。 目前，w f m c 参考模型给出的只是工作流管理系统的各个功能部分，而没有给出任 何的实现细节。实际构造一个工作流管理系统时有许多具体的技术细节需要仔细加以考 虑，以便满足工作流管理系统向大规模工作流管理方向发展所需的高度的灵活性、可用 性、可伸缩性、可靠性以及互操作性等方面的要求。围绕这些要求，目前关于工作流管 理系统的研究主要集中在以下几个方面【4 j ： ( 1 ) 更为灵活的过程模型 人们对于w f m c 批评最多的莫过于其“僵硬 的过程模型，这使得用户在某些情况 下不得不越过w f m c 而用其它方法( 如手工方式) 来完成有关的工作。这一点主要是由 于目前已有的系统中建立时的过程定义与运行时的过程执行脱节，而致使预定义的过程 模型不能很好地反应实际的业务流程。由于对过程定义及过程实例动态修改将会带来一 系列的困难，因此需要寻找更为灵活的工作流过程形式化表示方法及过程的执行策略。 ( 2 ) 面向对象的w f m s 面向对象( o o ) 的思想反映了人类思维的一般特征。进入9 0 年代，基于这一思想而 发展起来的各种技术在计算机领域得到了广泛的应用。随着w f m c 研究的不断深入，o o 思想也被引入进来，逐渐形成了面向对象的w f m s ( o o w f m s ) 。关于o o w f m s 的研究 有两个不同的层面。其一是指w f m c 本身的实现使用了o o p 的方法，即将w f m s 系统中 2 第一章绪论 的各种元素以对象的形式加以描述，并在某种环境下加以实现；另一个方面是关于面向 对象的过程模型，即使用面向对象的方法来完成业务过程的分析建模，并得到相应的对 象表示，此种模型在通用的分布式对象技术环境下实现起来比较容易。 ( 3 ) 智能化的w f m s 就w f m s 系统业务过程的建模而言，由于许多参数需要到过程开始被执行时才能确 定，或者需要根据实际情况的变化而动态地变化，同时由于建模者不可能考虑到所有的 情况，因此静态建模得到的过程模型也必然是不完善的。另外要求建模者对所有的业务 过程逐个建模也是一项繁重的工作，因此可能通过实例学习的方法完成业务过程的自动 建模。这要求w f m s 系统本身具有学习的功能，能够从各用户的实际工作中提取出各种 参数而得出相应的过程定义。 ( 4 ) 对同步协作的支持 w f m s 的基本功能是对异步的结构化协作的支持，即将一个用户工作完之后生成的 结果数据自动传递给下一个环节的用户进行处理。而同步协作则是各参与者实时地交流 思想，最终得到某个结果的过程。在一些比较大型的工作流管理中，某些环节的任务可 能需要多个用户实时协作才能更好的完成，此种支持能力又是目前的w f m s 所缺乏的。 ( 5 ) 对移动用户的支持 商业社会的激烈竞争要求企业具有良好的反应能力，移动办公正是为满足此种要求 而出现的一种新的工作方式，它使得员工能够随时随地地处理他们的业务。为了支持此 种功能，需要在w f m s 客户程序与工作流引擎之间定义相应的协议。对该协议的基本要 求是在尽可能增加移动用户自主性( 能够在断开同系统的连接的情况下继续对其工作项 进行处理) 的同时保证不会有多个用户同时对同一个工作项进行处理。 ( 6 ) 基于w e b 的w f m s w e b 技术因其界面的一致、简单及与平台的无关性而在其出现之后就得到了迅猛发 展。i n t e r a c t 的发展及企业i n t r a n e t 的构建为人们提供了一个理想的协同工作环境，同时也 使得基于w e b 建立工作流系统成为可能。这方面的研究是最近几年才刚刚开始的，而 j a v a 技术的成熟提供了更强大的技术支持。 ( 7 ) 分布式w f m s 为了支持跨企业的异构计算环境下大规模工作流管理，现有的w 搦s 的能力必须从多 个不同的方面加以扩展，以提高系统的可靠性、可伸缩性及容错能力等。关于这方面的 研究目前主要包括分布式的体系结构和分布式的数据管理两种。 ( 8 ) 事务型w f m s 这方面的研究主要是试图将一些高级事务模型应用到工作流系统的过程实例的执行 中，以提高w f m s 的可靠性，如保证过程实例中各活动执行的完整性和一致性。但到目 前为止，事务处理中的许多概念，如事务的a c i d 属性、失败语义等在w f m s 中的定义仍 然是不明确的。 ( 9 ) 工作流系统之间的互连 随着大量各具特色的w f m s 产品涌入市场，不同的企业或企业内的不同部门可能会 3 江南大学硕士学位论文 选用不同厂家的产品。而跨企业及企业间大型工作流应用需求的增强要求能够将这些异 质的w f m s 互连起来( 即在两个多个w f m s 之间传递工作项和执行控制) 以协同完成复 杂的业务过程。分布式结构的w f m s 本身就有一个如何将各工作流引擎( 同质的) 互连 起来的问题。w f m s 互连的关键性问题包括三个不同的方面：首先是互操作模型的确定， 其次，对不同的互操作模型，需要确定所需的互操作一致性级别，最后可定义一组操作 集来实现该操作模型。 另外，在工作流管理系统的实施上也存在非常多的问题需要研究，如分布式工作流 机的实施、异常处理和错误恢复和事务管理等。而这些问题的解决对于提高工作流管理 系统的性能具有重要意义。 1 2 2 工作流模型 在实际应用中，由于现代企业的信息系统的分布性、异构性和自治性变得越来越显 著，为适应这种环境，工作流系统的性能和可靠性需要得到进一步提高，这其中对工作 流系统进行良好的建模是关键。 工作流模型是对工作流的抽象表示，也就是对企业经营过程的抽象表示。工作流管 理建立阶段的功能主要是完成经营过程的计算机化的定义，也就是完成过程建模的任 务。一个完善的工作流模型应该完整地提出支持工作流定义的概念，为建模用户提供工 作流定义所需要的组件或元素。理想的工作流模型能够清楚地定义任意情况下的工作 流，能够适应用户在建模过程中所提出的各种要求。然而，到目前为止，虽然人们提出 不少有意义、有见解的工作流模型，但从模型的能力上看，距离理想情况还有一定的差 距【卯。 由于工作流系统必须清楚地描述一个经营过程是如何进行的，因此，许多工作流模 型都是从过程定义入手，比如流程图、状态图、活动网络图等等。这一类基于有向图的 模型的优点是比较直观，容易理解。但其缺点是比较简单，不能处理复杂的过程逻辑， 缺乏柔性p j 。 p e t r i 网是在本世纪6 0 年代由c a r l a d a m p e t r i 博士发明的，适合于描述异步的、并发 的计算机系统模型。利用p e t r i 网进行系统建模，不仅有图形的直观性、结构的层次性， 而且还有一套理论方法支持系统的性质分析和品质分析。p e t r i 网作为系统模拟与分析的 一种有效工具已得到广泛的应用，特别是在并发系统的应用中更体现了p e t r i 网的优势。 这是由于p e t r i 网擅长描述并发、冲突、异步和同步等重要现象，以形式的步骤和严格的 理论作为系统分析的基础，从而使得p e t r i 网成为越来越受人们重视的一种建模工具，在 多个领域得到了广泛的应用睁1 0 1 。荷兰学者v a nd e ra a l s t 于1 9 9 8 年在文献 11 中首次提出 了工作流网( w fn e t ) 的概念，工作流网运用p e t r i 网极强的表达过程的能力，以系统的 状态和变化来描述业务流程。p e t a l 网描述过程具有简单清晰的特点，但是对于复杂的业 务流程和具有多案例的网结构的描述能力不足。 而着色p e t f i 网( c o l o u r e dp e t r in e t ，简称c p n ) 是高级p e t r i 网，具有很强的表达过程 的能力和很强的数学建模能力。现在已经证明c p n 与p n 是等价的，c p n 还具有表达简练 灵活的特点，能够满足更复杂业务流程的表达，因此基于c p n 建模的方法完全具有工作 4 第一章绪论 流建模的能力，并能适应现代企业业务流程复杂多变的特点。以k u r tj e n s e n 教授为首的 丹麦奥胡斯大学( a a r h u su n i v e r s i t y ) c p ng r o u p 对着色p e t r i l 网进行了长期深入的研究， 在基础理论和实践应用上都取得了一系列成果，并和美国宇航局合作开发推出了基于着 色p e t r i 网的仿真软件c p n t o o l s 。c p n t o o l s 的出现为基于c p n 的工作流模型提供了可靠、 易用的仿真平台支撑，使模型研究不仅仅局限于理论层面【1 2 】【1 3 】。基于p e t f i 网及着色p e t r i 网的工作流模型及其产品的研发基本还处于研究和理论探索阶段，虽然国内外的专家学 者不断提出新的模型【1 牝1 1 ，其中也包括很多基于c p n 的工作流建模的研究，但是都存在 一定的局限性和不足，并没有一个很好的通用的基于c p n 的工作流模型。且已有的这些 基于p e t r i 网和c p n 的工作流模型都侧重对系统的模拟和分析，而对系统的成本和预算分 析就没有考虑到。 1 3 本文的研究工作及其意义 工作流建模主要有两大目的：一是对系统进行模拟和分析，二是对系统进行成本和 预算分析。在模拟和分析方面v a i ld e ra a l s t 和r e i j e r s 等人用扩展了时间信息的p e t r i 网成功 地解决了这一问题1 2 2 1 1 2 3 l ，在k u r tj e n s e n 教授的c p n 理论中也提出了赋时c p n 用来进行工 作流建模对系统进行模拟和分析，但是这些模型都存在过程建模与过程执行过度耦合的 问题，即在某个组织机构模型上建立的过程必须在同一个组织机构模型上才能执行。造 成这种耦合的原因在于，当前的业务过程管理技术和标准没有区分控制逻辑内部的差 别。实际上业务过程中的控制逻辑有两种：一种是描述工作环节之间按照业务规则形成 的顺序并发、竞争等关系，被称为路由逻辑；另外一类是描述工作的指派、资源的组织、 责权利的分配，被称为资源管理逻辑。 按照路由逻辑与资源管理逻辑分离的原则，本文将工作流管理系统分为描述路由逻 辑的路由管理层与描述资源管理逻辑的资源管理层。资源建模正是基于以上目的提出来 的。针对工作流中涉及到的资源问题，本文分析了资源的重要属性和分类。在此基础上， 采用着色p e t r i 网方法建立了工作流资源管理器，实现工作流的资源管理和分配。基于着 色p e t r i 网的资源管理器模型为工作流系统进行定性和定量分析提供了一个形式化的基 础。 而相应地在成本和预算分析方面，基于p e t r i 网的这方面的工作流模型研究还处于起 步阶段，且众多学者提出的模型也多是基于简单p e 斫网的，比如刘卫东及林闯提出的 面向网格用户应用的价格时间p e t r i 网以及刘显明等人提出的扩展了价格信息的时间 p e t r i 网1 2 4 l 【2 5 l ，这些模型是工作流建模在成本和预算分析方面的初步的有益探索，但是 这些模型摆脱不了p e l r i 网对于复杂的业务流程和具有多案例的网结构的描述能力不足 的弱点。基于实际应用中业务流程的复杂性，本文提出扩展了价格信息的着色p e t r i 网， 讨论了该模型的变迁规则，并针对状态空间爆炸问题提出了最小成本可达算法。 工作流技术的核心就是工作流建模，只有建立起好的工作流模型才能在其基础上开 发出功能强大、可靠性高的工作流管理系统。由于p e t r i 网和着色p e t r i 网在系统建模方面 有着巨大的优势，基于p e t r i 网和着色p e t r i 网的工作流模型已经成为近几年工作流建模的 江南大学硕士学位论文 主流方向。而已有的这方面的模型大都在系统模拟和分析方面很成功，但都不具备资源 建模能力且在系统成本和预算分析方面无能为力，而在实际应用中对系统建模是全方位 考虑的，不仅要考虑至i z 艮好地实现系统功能，还要考虑到相应的资源约束以及实现成本。 所以从这两方面对工作流建模是非常有必要的，不仅可以丰富工作流建模技术，还可以 为开发工作流管理系统打下良好的理论基础，即该课题研究具有学术和应用双重价值。 1 4 本文基本结构 本文基于着色p e t f i 网对工作流的建模与分析进行了一些针对性、探索性的研究，全 文由以下三部分组成： 第一部分：引言部分 该部分由前两章组成。第一章介绍了研究背景以及国内外的研究现状，并阐述了本 文的主要研究工作及其意义。第二章主要介绍了几种传统的工作流模型和基于p e t f i 网的 工作流网，并比较了它们的优缺点。 第二部分：基于着色p e t f i 网的工作流资源建模和价格建模 该部分是本文的重点，由第三、四章组成。第三章详细阐述了基于着色p e 们网的资 源建模，针对工作流中涉及到的资源问题，分析了资源的重要属性和分类；在此基础上， 采用着色p e t r i 网方法建立了工作流资源管理器，实现工作流的资源管理和分配。第四章 则是基于着色p e t r i 网的价格建模，提出了价格着色p e t f i 网，讨论了该模型的变迁规则； 并针对状态空间爆炸问题提出了最小成本可达算法，最后以业务实例演示了该模型在工 作流成本预算分析方面的应用。 第三部分：结束语 该部分对全文进行了总结，综述了论文的研究工作，并评价了基于着色p e t r i 网的资 源模型和价格模型的优点与不足，最后探讨了基于着色p e t r i 网的工作流建模进一步的 研究方向。 6 第二章工作流模型概述 第二章工作流模型概述 工作流模型是w f m s 的执行和管理核心。这一章将详细阐述一些传统的工作流模型， 以及基于p e t r i 网的工作流模型，对各种模型给出相关的定义，并分析比较了各自的优 缺点。本章第一节主要介绍了传统工作流模型中的f l o w m a r k 模型、e p c 模型、 a e t i o n w o r k f l o w 模型；第二节主要介绍了基于p e t r i 网的工作流模型；第三节是本章小 厶士 缃o 2 1 传统工作流模型 工作流模型是对工作流的抽象表示，也就是对经营过程的抽象表示。工作流管理建 立阶段( b u i l d t i m e ) 的功能主要是完成经营过程的计算机化的定义，也就是完成过程 建模的任务。在这个阶段，利用一个或多个建模方法及其相应的建模工具，完成实际的 经营过程到计算机可处理的形式化定义的转化。所得到的定义通常可称为过程模型、过 程模板、过程元数据或过程定义。由于需要在计算机环境下运行，所以工作流模型不仅 仅要让人读懂，更要让计算机能够理解所定义的工作流过程。也正是因为如此，简单的 业务过程通过语言或文字就可以表达完全，无需建立明确的模型，而描述企业业务经营 过程的工作流则必须建立相应的工作流模型，才能实现企业业务流程的工作流管理，尤 其是对那些实现许多复杂的并行执行流程的业务过程，只有建立它们的计算机化的模型 才可能对流程的执行情况进行有效的监控。 工作流模型除了应该支持完整的工作流概念定义，为建模用户提供定义工作流所需 要的组件或元素等主要特性外，理想的工作流模型还应该能够清楚地描述任意业务情况 下的工作流，适应用户在建模过程中所提出的各种要求，即工作流描述能力要强，可以 描述清楚几乎所有的业务流程类型。然而，到目前为止，人们虽然提出了不少有意义、 有见解的工作流模型，但从模型的能力上看，距离这一理想情况尚很遥远。 对概念模型进行评价的四条标准为【5 】： ( 1 ) 表达能力丰富：模型提供丰富的建模概念，使得由大量约束集合而成的元素能够 在模型中被直接表达出来； ( 2 ) 容易理解：不论是领域专家还是普通用户，都能够比较容易地理解模型含义； ( 3 ) 最小化：模型中的概念不重叠，每一个基本概念都有它特定的意义； ( 4 ) 形式化：模型定义能够作为现实对象的形式化描述。 在大多数情况下，概念模型都提供相应的图例表示，因此，我们认为还应该再附加 上对图例的要求，如易读性、完整性。 在进入九十年代以后，市场上已经出现了许多的工作流产品，人们开始对工作流模 型进行深入的研究。许多工作流模型来自于不同的工作流产品，有些模型则来自于专门 的研究项目或者直接由某位学者提出。以下将着重介绍几种有代表性的工作流模型，它一 们都具有比较突出的特点，并代表了一种较为普遍的观点，对于今后开展工作流建模问 7 江南大学硕士学位论文 题的研究有着一定的参考价值。 2 1 1 基于活动网络的过程建模一f i o w m a r k 工作流模型【5 】 f l o w m a r k 是m m 公司在2 0 世纪9 0 年代中期推出的工作流产品，其目标是实现企 业的文档路由( d o c u m e n tr o u t i n g ) 和过程自动化( p r o c e s sa u t o m a t i o n ) ，这也是传统的 工作流产品的典型特点。 在f l o w m a r k 中，一个完整的经营过程( 工作流过程) 由一个无自环的有向图构成。 有向图中的节点元素表示可执行的步骤或任务，节点间的连接弧代表了过程中的控制流 与数据流。组成模型的元素包括过程( p r o c e s s ) 、活动( a c t i v i t y ) 、模块( b l o c k ) 、控制 连接弧( c o n t r o lc o n n e c t o r ) 、数据连接弧( d a t ac o n n e c t o r ) 和条件( c o n d i t i o n s ) 。 f l o w m a r k 的工作流模型是一种典型的基于活动的i p o ( 输入一处理一输出) 模型， 以活动作为构成过程的基本单元，以连接弧体现过程逻辑，活动的输入数据箱与输出数 据箱成为活动输入输出的接口，再辅以条件的设置，就能够比较简单、灵活地实现企业 经营过程的建模。 从模型的语义上，f l o w m a r k 明确地将控制流与数据流进行了分离，这样，一个工作 流过程可以被看成是由控制流图与数据流图叠加而成的。f l o w m a r k 的这一特点，将会 带来如下好处： ( 1 ) 从系统分析的角度来看，有利于通过过程建模来提取建立功能视图与信息视图模 型所需要的相关信息，便于对企业这一复杂系统进行深入的分析，过程模型中提 取信息并输入到i d e f o 、i d e f l x 建模工具中，辅助功能模型与信息模型的建立； ( 2 ) 从系统实现的角度看，这种分离直接对应于控制流管理与数据流管理的相互分离， 从而实现两种不同性质的流管理上的独立。在f l o w m a r k 的系统实现上，m m e x o f f c a f m q m 实现了分布式工作流的控制流管理，相应的，基于l o t u sn o t e s 的 文档系统则实现了分布式工作流的数据流管理。在这样的分布式工作流执行环境 中，逻辑上控制节点与数据节点( 在物理上二者可能位于同一个内存空间中) 的 分离将带来如下好处：有利于保护原有的数据系统，不必强迫企业改变原有的 数据管理方案；有利于数据节点能够自主地、柔性地、高性能地处理复杂结构 的数据而不会影响整个工作流系统的效率，特别是对多媒体数据的处理，这是唯 一可行的方法；有利于增强系统的可扩展性，可靠性以及容错性等分布式性能。 除了m 的f l o w m a r k 所提出的这种基于活动网络的工作流模型以外，还有其他的 工作流产品( 如i n c o n c e r t ) 或原型系统( 如m e t e o r 2 ) 也推出了类似的模型。这些模 型在宏观含义上是一致的，都明确地反映出基于活动网络的过程模型所应该具有的特 点，而仅仅在细微之处有所不同，比如模型元素的类型、模型元素的语义等等。总的说 来，这一类模型所共有的特点是简单、直观、便于理解，适合于流程较为固定、异常情 况较少的生产型工作流的建立，有利于企业规范自身内部流程；但这类模型往往缺乏柔 性，对紧急情况的应变能力不足，显得比较死板。 2 1 2 事件驱动的过程链模型( e p c ) 1 5 1 一种应用比较广泛、用来描述企业事件与经营过程的传统方法就是事件驱动的过程 8 第二章工作流模型概述 链模型( e v e n t - d r i v e np r o c e s sc h a i n ) ，简称为e p c 模型。它主要被用于企业的经营过程 重组( b p r ) 、工作流的定义与控制、软件的配置与开发、基于活动的成本( a b e ) 分 析以及符合i s o9 0 0 x 认证标准的质量文档的规范。世界范围内已经有数千家公司、企 业使用e p c 对自己的经营过程建立了模型，一些软件供应商( 如a s p ) 还提供了相应 的软件工具来支持e p c 的建模过程，这些软件工具通常都提供一些标准的通用e p c 模 型用以支持企业用户对过程的定制。 e p c 是由k e l l e r 提出的。e p c 的主要元素就是功能和事件；功能被事件触发，功能 也能产生相应的事件。经营过程的控制流就这样由交替出现的功能和事件彼此连接而构 成，控制流的分之选择、汇合连接以及并发进行则通过逻辑操作符( 比如与、或、异或) 或者更复杂的表达式来完成。 e p c 模型的一个很大的优点就在于它兼顾了模型描述能力强与模型易读性这两个方 面。因此，e p c 经常被用于在与未受过专业建模训练的普通用户讨论经营过程的场合； 同时，e p c 模型经过改进、提炼后，也同样可以作为一个企业信息系统的需求定义。这 也正是许多企业与公司利用e p c 来进行过程建模的原因。为了进一步提高建模的质量 与效率，不少研究人员试图把已有的建模方法( 如e r 图、面向对象方法) 与e p c 相 结合，成为一种集成的建模方法，能够更有针对性地面向某一领域，如信息系统开发、 企业经营过程建模等。t h o m a sa l i w e y e r 就把e p c 与u m l 相结合，用于面向对象的经 营过程建模当中。 2 1 3 基于语言行为理论的工作流模型- - a c t i o n w o r k f l o w i 纠 一百年前，f r e d e r i c kt a y l o r 在科学管理一书中详细阐述了科学管理的主要原则， 他把一个组织的工作描述成为一系列的任务，每个任务都是工人们具体的、严谨的活 动过程；而管理就是使这些任务在一定的计划下以最优的方式进行。这种管理的概念一 直被延续下来，即使是在计算机出现并发展了多年的今天，我们依然能够找到它的影 子一一在许多计算机管理系统中，人被当作了一种功能实体而建立模型，能够对输入进 行处理并产生相应的输出。这也造成了人们普遍认同的一种对企业经营过程的看法一 i p o 模型；即过程中的每一个基本活动都由输入( i ) 、处理( p ) 、输出( o ) 这三部分 组成。尽管i p o 模型在二十世纪大规模的生产活动中得到了广泛的应用并取得了令人满 意的成果，但正如f l o r e s 所说，在以遍布全球的互联网络为通讯基础的今天，人们必须 要重新考虑对“工作这一概念的理解问题以便能实现更为有效的组织管理，而有效的 行为协作不失为一种好的观念模式，因为通过透视协作联系中的“语言行为( s p e e c h a c t s