（计算机软件与理论专业论文）面向虚拟企业的工作流建模与正确性验证.pdf

山东大学硕士学位论文 面向虚拟企业的工作流建模与正确性验证 研究生于庚 指导教师王海洋教授 摘要 虚拟企业是建立在现代科学技术水平基础之上的新型竞争性组织，能对激烈 的市场竞争做出及时响应，是种新的企业发展组织形式。从生产经营角度出发， 制造企业可视为由多个相互关联的不同层次流程组成的活动流程。使用工作流技 术可以对企业的生产经营活动进行有效管理。 工作流技术是当前i t 领域的一个研究热点。工作流模型是业务过程的计算机 化形式表示，工作流管理建立阶段的功能主要是完成过程建模的任务。对于工作 流模型的正确性研究亦是一个重要且须得到很好解决的问题。 本文即论述了将工作流技术应用到虚拟企业的方法及其正确性验证问题。文 章首先综述了虚拟企业与工作流管理系统的概念及发展历程，着重介绍了当前工 作流模型及其验证方法。然后介绍了p e t r i 网与工作流网( w f - n e t ) 的概念及性 质。基于p e t r i 网进行的建模与分析，具有严格的过程形式化体系，避免了模糊 性、不确定性和矛盾性。工作流网是p e t r i 网的分析方法在工作流系统中的应用。 在此基础上，荷兰学者w i lv a nd e ra a l s t 提出了跨组织工作流模型。对于虚拟 企业，跨组织工作流具有良好的适应性与必要性。接下来，本文对跨组织工作流 进行着色扩充，通过给p e t r i 网中的标记赋值，就好比给它们涂上了不同的颜色， 从而使对象特性与对应标记紧密结合，更加真实地反映虚拟企业内各成员间的交 互与协作。工作流模型正确性验证是工作流研究领域的一个重要问题，工作流管 理系统可能建立错误的模型，导致工作流的执行出现异常以a a l s t 的方法为基 础，本文最后着重对经过着色扩展的跨组织工作流网进行正确性的验证。 将工作流技术应用到虚拟企业具有广泛意义，它可以实现后者的业务过程自 山东大学硕士学位论文 动化，业务动态调整，控制、监视与警告等目的。本文给出的形式化建模方法及 正确性验证，使该应用得以更加严谨地实现在本文最后，举例模拟了这种建模 与验证方法的实际应用 关键字：工作流虚拟企业正确性p e r r y 网工作流网跨组织工作流着色跨组 织工作流 l l 山东大学硕士学位论文 m o d e l l n ga n dv e r l f l c a t l 0 no fw o r k f l o wl nv i r t u a l e n t e r p r is e s p o s t g r a d u a t e ： y ug e n g t u t o r ：p r o f w a n gn a i y a n g a b s t r a c t v i r t u a l e n t e r p r i s e s a r en e w 孵r i v a l r o u so r g a n i z a t i o n sb a s e do nt h em o d e r n t e c i l i l o l o g ya n dc a nr e s p o n dt os c v c i em a r k e tc o m p e t eq u i c k l y f r o mt h ep o i n to f p r o d u c t i o na n dm a n a g e m e n t , e n t e r p r i s e sc a nb er e g a r d e da sa c t i v ep r o c e s s e sm a k i n g u po fs e v e r a lp r o c e s s e sa s s o c i a t e de a c ho t h e rw i t hd i f f e r e n tl e v e l s t h ea c d v i t i e so f p r o d u c t i o na n dm a n a g e m e n ti ne n t e r p r i s e sc a nb em a n a g e dm o l q e f f i c i e n t l yw i t ht h e w o r k _ f l o wt e c h n o l o g y w o r k f l o wh a sb e e nb e c o m i n gah o tt o p i ci n 盯r e s e a r c hr i d & a n dm a n yw o r k f l o w s y s t e m sa n dp r o t o t y p e sh a v eb e e nd e v e l o p e dc u r r e n t l y w o r k f l o wm o d e l i st h ep r o c g s s r e p r e s e n t e db yc o m p u t e r o n eo f t h et a s k so f w f l v l si st oc r e n t et h ew o r k f l o wm o d e l s t h er e s e a r c h0 1 1t h es o u n d n e s so fw o r k m o wm o d e li sa ni m p o r t a n ta n ds h o u l db ew e l l s o l v e d t h i st h e s i si sr i g h td i s c u s s i n gt h et o p i co ft h em e ! t h o da n di t ss o u n d n e s sw h e n w o r k _ f l o wt e c h n o l o g yi su s o di nv i r t u a le n t e r p r i s e s i nt h i st h e s i s ，f i r s t l y , w es u m m a r i z e t h ec o n c e p ta n dd e v e l o p m e n to f v i r t u a le n t e r p r i s e sa n dw o r k f l o wm a n a g e m e n ts y s t e m s ， e m p h a s i z i n go nt h en o w a d a y sw o r k f l o wm o d e l sa n dt h e v e r i f i c a t i o nm e t h o d s ；t h e nw e t a l ka b o u tt h ec o n c e p ta n da t t r i b u t eo fp e t r i - n e ta n dw f - n e t b a s e do np e t r i - n e t m o d e l i n ga n da n a l y s i sh a v e s t r i c ts y s t e mo ff o r m a l i z a t i o n , t h e nc a na v o i dt h e i l l e g i b i l i t y , u n c e r t a i n t ya n di l l o g i c a l i t y w f - n e ti st h ea p p l i c a t i o no fp e t r i - n e ta n a l y s i s 山东大学硕士学位论文 m e t h o di nw o r k f l o wa r e a b a s e do nw f - n c t n e = t b e r l a n d i s hs c h o l a rw i lv a nd c ra a l s t p r o p o s e dt h ei n t e r o r g a n i z a t i o n a l w o r k f l o w sm o d e l f o rv i r t u a le n t e r p r i s e s ，t h e i n t e r o r g a n i z a i o n a lw o r k f l o w sh a v eg o o da d a p t a b i l i t ya n dn e c e s s a r y i nt h i st h e s i s ，w e a d dc o l o ra t t r i b u t et oi n t e r o r g a n i z a t i o n a lw o r k f l o w ss ot h a tw ec a nd e s c r i b em o r e c o m p l e xi n t e r a c to b j e c t sa m o n g s e v e r a lo r g a n i z a t i o n s v a r i o u sc o l o r sc a nd i f f e r e n t i a t e a n dr e f l e c tb u s i n e s sp r o c e s s e sl i v e l i l y v e r i f i c a t i o no fw o r k f l o ws o u n d n e s si sa n i m p o r t a n tp r o b l e mi nt h ec u r r e n tw o r k f l o wr e s e a r c ha 吼m a n yw f m s sp r o b a b l y c r e a t ew r o n gw o r k f l o wm o d e l s , s ot h er u n n i n go fw o r k f l o ww i l lb ea b n o r m a l s o m e r e s e a r c h e r si n t r o d u c et h et h e o r e mo fe v e n tb a l a n c e 。an e c e s s a r yc o n d i t i o nt ov e r i 母 w o r k f l o wl o g i c a ls o u n d n e s si sp r o p o s e db ya n a l y z i n gt h es o u n d n e s so fl o c a lw o r k f l o w b u th o wt ov e r i f yt h es o u n d n e s so faw h o l ew o r k f l o wi sn o ti n t r o d u c e d b a s e do nt h e m e t h o do fa s l s t , w ee m p h a s i z eo nt h es o u n d n e s so fc o l o r e d i n t e r o r g a n i z a t i o n a l w o r k f l o w si nt h er e s to f t l l e s i s u s i n gw o r k f l o wt e c h n o l o g yt ov i r t u a le n t 铒, r i s e sh a v es i g n i f i c a n tm e a n i n g t h i su s i n g 锄h e l ps o m ed e m a n d so ft h el a t t e rt oc o m et r u e s u c ha sa u t o m a t i z a t i o no fb u s i n e s s p r o c e s s ，d y n a m i cb u s i n e s sa d j u s t m e n ta n dc o n t r o l ，w a t c h i n ga n dw a r n i n ge 1 【c t h e f o r m a l i z e dm o d e l i n ga n dv a l i d i t ym e t h o dm a k et h i si m p l e m e n tm o r ep r e c i s e i nt h e l a s to ft h i st h e s i s w eg i v ea ne x a m p l et os i m u l a t et h ep r a c t i c a lu s eo ft h i sm o d e l i n g a n d v a l i d i t ym e t h o d k e y w o r d s ：w o r k f l o w , v i r t u a le n t e r p r i s e ，s o u n d n e s s ，p c t r in e t , w f - n c t , i o 骶 c 1 0 、 下 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均已在文中以明确方式标 明。本声明的法律责任由本人承担。 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有 关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学 可以将本! 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者虢纽l 翩繇脚日期：型业： 山东大学硕士学位论文 第一章绪论 1 1 虚拟企业的概念 虚拟企业是建立在现代科学技术水平基础之上的新型竞争性组织，能对激烈的 市场竞争做出及时响应，是企业发展的种新的组织形式虚拟企业通过网络联 结形成，网络信息处理是其运营的基础，其组织结构具有无形化特征。信息技术 的高度发展，改变了信息的传递方式和处理方式，信息的网络化改变了企业运营 的外在条件，加强了企业的自我控制能力，同时也加强了企业间的联盟合作关系。 另外，企业生存环境的改变，迫使企业改变经营方略，企业间的战略联盟、业务 重组、协同工作等方法得到了广泛的运用，联盟成为企业求生存的最佳方式之一， 传统企业的工作模式在虚拟企业中因信息技术的应用而改变，因而虚拟企业的产 生便成了自然。一般认为虚拟企业是多个生产小组为了一个共同的目标而组织起 来的分布式小组集，这种小组集合是随任务( 目标的分解) 变化而变化，随任务 的终结而消失。无论是信息处理、战略制定、联盟协调，还是整体运行控制，虚 拟企业都具有很强的可操作性。过程任务机制、过程的每一个环节都可以用目标 管理来实现。 目标管理是传统企业经常使用的一种管理方法。它是根据企业发展的总体目 标，向下分层、分级分解总目标形成分目标，在明确任务和职权的基础上，企业 内各部门或人员积极主动地为各自的分目标努力，从而实现企业的总目标。虚拟 企业目标明确，过程任务具体，适合于使用目标管理方法。目前，对虚拟企业的 研究主要是集中于机制和虚拟企业的组建方式上过程控制是信息技术应用于虚 拟企业运营管理的切入点i ” 虚拟企业的产生和发展并非偶然，由于虚拟企业比传统企业更强调资源的有效 整合和配置，其中资源不仅包括自然资源，还包括人力资源和技术资源等，从这 个意义上说，虚拟企业比传统企业更有利于社会生产效率的提高。从另一个方面 讲，在高科技蓬勃发展的今天，市场竞争更加激烈，顾客的需求日益多样化和个 性化在某些行业，人们对大批量生产的产品需求已不占多数，企业要想在市场 上立于不败之地，将在很大程度上取决于企业是否具有快速的市场应变能力。而 山东大学硕士学位论文 网络时代的到来与信息等技术的发展极大地促进了虚拟企业的产生，并为虚拟企 业组织与管理模式的实际推广提供了现实可能性综上所述，有专家预测，虚拟 企业将是2 1 世纪的主流企业形式1 2 】。 1 2 虚拟企业的发展历程 2 0 世纪幻年代以后，日本处于经济萧条时期，制造业陷于困境。丰田汽车公司 的丰田英二和大野耐一认识到美国当时传统的大批量生产方式不适合日本的国 情，于是，他们结合自身的特点，另辟蹊径，开创了“精良生产”( l e a n p ，- o d u c t i o n ) 的生产方式。日本在其后的几十年中，利用这一生产方式在制造业方面超过了美 国，曾一度取代了美国在制造业方面的领先地位2 0 世纪8 0 年代后期，美国开始 想方设法夺回制造业的优势以保持其国际竞争力1 9 9 1 年，美国国会和国防部委 托里海( l e h i g h ) 大学的艾科卡( i a c o c c a ) 研究所进行一项旨在建立较长期的制 造技术规划基础结构的课题研究。该所的3 位学者在合作完成的一份名为 2 1 世 纪制造企业研究：一个工业主导的观点的研究报告中首次提出了虚拟企业的概 念。该报告指出：在市场变化加快、全球性竞争日益激烈的情况下。单个企业仅 仅依靠自己内部资源的整合已难以满足快速变化的市场需求为解决这一问题， 该报告提出了以虚拟企业为基础的敏捷制造模式，即以竞争能力和信誉度为依据， 选择合作伙伴，组成虚拟企业，以增强企业整体的竞争能力，在最大程度上满足 用户需求。这个报告主要以制造业为背景，其核心理念和出发点是“敏捷制造” 该报告具有非常巨大的影响，虚拟企业作为一种组织形态开始受到理论工作者的 重视。自2 0 世纪9 0 年代中期以来，关于虚拟企业的理论研究正在成为管理科学中 的一个研究前沿和热点。现阶段，作为一种新的组织与管理模式，虚拟企业已开 始在实际中得到广泛应用1 2 】。 1 3 工作流问题的起源与发展 工作流( w o r k p o w ) 的概念起源于生产和办公自动化领域。通过将一些具有固 定程序的工作分解成定义良好的任务、角色，并且按照预先定义好的规则和过程 来执行这些任务并对执行过程进行监控，从而可以达到提高办事效率、降低生产 山东大学硕士学位论文 成本、提高企业生产经营管理水平和竞争力的目的。 工作流技术的历史可以追溯到上个世纪7 0 年代末的办公自动化和任务批处 理。而第一次使用工作流术语则可以追溯到上世纪8 0 年代初，但那个时候还没有 真正的工作流管理系统出现。 2 0 世纪8 0 年代中期，f i l e n e t 和h e w s t a r 等公司率先开拓了工作流产品市场， 成为最早的一批工作流产品供应商。它们把图象扫描、复合文档、结构化路由 ( s t r u c t u r e d r o u t i n g ) 、实例跟踪、关键字索引以及光盘存储等功能结合在一起， 形成了一种全面支持某些有我流程的集成化软件( 包) ，这便是早期的工作流管理 系统。典型的有f z t e n e t 于1 9 8 4 年推出的w o r k f l o 商用系统，h e w s t a r 于1 9 8 8 年 推出的i r t e w s t a r ，i b m 于1 9 8 8 推出的l m a g e p l u s 。这种集成化的软件系统为企业 简化与重组自己的关键业务流程提供了一种非常好的方法。由此可见，工作流从 最初的诞生之日起就是作为一种面向过程的系统集成技术而出现的。只不过是限 于当时技术水平，它所集成的功能比较简单而已。 进入上个世纪9 0 年代，随着计算机与网络技术的迅速发展，特别是在i n t e r n e t 应用日益普及的情况下，现代企业信息系统的分布性、异构性和自治性的特征越 来越显著。c s ( 客户端朋匣务器) 体系结构和分布式处理技术( c 0 1 兄鲥、d d 的广泛应用说明集中式信息处理的时代即将成为过去，取而代之的将是大规模的 异构分布式信息处理与应用环境。这种新的处理模式和应用环境要求系统不仅仅 要处理单个任务，还要能够控制、监视和支持处理过程的逻辑，即实现处理过程 的自动化或者半自动化。在这种背景下，工作流管理系统由最初的无纸化办公环 境转而成为在企业复杂信息环境中实现业务流程自动执行的必要工具。这样的一 个转变，把工作流技术带入了一个崭新的发展阶段，使得人们从更深层次、更广 的领域对工作流展开研究例。 目前，在全球范围内，对工作流技术的研究以及相关的产品开发进入了更为 繁荣的阶段，更多更新的技术被集成进来，文件管理系统、数据库、电子邮件、 移动式计算、网格计算、i n t e r n e t 服务等都已经被容纳到工作流管理系统中来。同 时，工作流产品市场也得到了很大发展。目前市场上具有代表性的工作流产品有： i b m 的m q s e r i e sw o r k f l o w 、a c t i o n 技术公司的m e t r o 、f i l e n e t 公司的h s u a lw o r k f l o 、 j e t f o r m 公司的l n t e m p o 和p a v o n e 公司的e s p r e s s o 等。 山东大学硕士学位论文 1 4 工作流管理系统的基本概念和参考模型 19 9 3 年工作流管理联盟( 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 f m c ) 的成立标 志着工作流技术开始进入了相对成熟的阶段。为了实现不同工作流产品之间的互 操作性，w a t c 在工作流的相关术语、体系结构以及应用编程接口( w a p i ) 等方 面制定了一系列标准。 根据工作流管理联盟( w f m c ) 的相关文件 4 1 ，工作流和工作流管理系统的定 义如下： 工作流：工作流是一类能够完全或者部分自动执行的经营过程，在工作流中， 文档、信息或任务按照一定的程序规则在参与者之间传递，以完成相应工作 工作流管理系统( w f m s ) ：是一种能定义、创建和管理工作流执行的系统。 它可通过一个或多个工作流机来运行，并能解释过程定义、与工作流参与者交互， 在需要时还可以引用刀工具和应用。通常，工作流管理系统是指运行在一个或者 多个称为工作流机的用于定义、实现和管理工作流运行的一套软件系统，它和工 作流执行者交互，推进工作流实例的执行，并监控工作流的运行状态。在工作流 管理系统的支持下，通过集成具体的业务应用软件和操作人员的界面操作，才能 够良好的完成对企业经营过程运行的支持。 为了便于工作流管理系统的研究与开发，玎脚c 提出了一个工作流系统参考 模型，其体系结构、主要组成部分和接口如图1 1 所示。 4 山东大学硕士学位论文 隔蒸丽 i j 。过程定义j ：豆e ，f l* d 接n t 土 图1 - 1 工作流系统参考模型 工作流执行服务( w o r k f l o w e n a c t m e n t s e r v i c e ) 是参考模型的核心部分，围绕 它的外部接口包括工作流应用程序接口( w a p i ) 和交换格式等。通过这些接口可 以访问工作流系统服务，并控制工作流控制软件与其它的系统组件之间的交互 w a p i 是一个统一的服务接口，根据不同的功能范围分为五个接口，如图1 - 1 所示。 该参考模型在逻辑上把过程、活动控制逻辑与应用工具和最终参与者端的任 务分开。这样使得制定广泛的工业标准，或者将参与者专用的应用工具集成到特 殊的工作流应用程序中变得可能。 1 5 工作流管理系统的分类 根据所实现的业务，工作流管理系统可以分为四类： ( 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 cw o r k f l o w ) ：与管理型工作流类似，但一般用来处理 异常或发生机会比较小的情况，又是甚至是只出现一次的情况，这与参与的用户 有关。 山东大学硕士学位论文 ( 3 ) 协作型工作流( c o l l a b o r a t i v ew o r k f l o w ) , 参与者和协作的次数较多在一 个步骤上可能反复发生几次直到得到某种结果，甚至可能返回到前一个阶段，参 见文献【5 】。 ( 4 ) 生产型工作流( p r o d u c t i o nw o r k f l o w ) ：实现重要的业务过程的工作流，特别 是与业务组织的功能直接相关的工作流与管理型工作流相比，生产型工作流一 般应用在大规模、复杂的和异构的环境下，整个过程会涉及许多人和不同的组织。 根据底层实现技术，工作流管理系统分为三类： ( 1 ) 以通讯为中心：以电子邮件为底层的通讯机制这种类型的工作流管理系统 适合于协作型和不确定型工作流，而不适于生产型工作流。 ( 2 ) 以文档为中心；基于文档流转的思想，与外界应用交互有限。由于管理型工 作流很多都是基于表单处理的，可以用以文档为中心的工作流管理系统实现，适 用于电子政务工作流。缺点是系统不能主动的把任务提供给用户，往往依赖用户 连接并注册到w e b 服务器上。 ( 3 ) 以过程为中心：对应于生产工作流，它实现自己的通讯机制，在底层数据库 基础上，提供大量与新老应用系统交互的接口 1 6 工作流建模方法及正确性验证方法研究现状 工作流模型是业务过程计算机化的形式表示工作流管理建立阶段的功能主 要是完成过程建模的任务。不同的工作流管理系统所实现的工作流模型是各不相 同的；工作流正确性验证有其重要意义，由于工作流管理系统可能会建立错误的 工作流模型，从而会导致工作流的执行出现异常，因此，建立工作流模型的同时， 必须考虑其是否正确。目前，主要的建模方法有以下几种： ( 1 基于脚本语言的建模方法 脚本语言中有描述控制流和数据流的语句结构，它提供了一种简明的描述方 法，对于有经验的设计者来说更易于使用。它的主要缺点是缺乏流程本身的形式 化语义，同时并没有很好的方法对建立的工作流模型进行正确性验证。 ( 2 ) 基于网的建模方法 适合于流程的可视化建模，一般都使用状态变迁网，流程中的活动用结点表 示，控制流用边表示。使用状态变迁网的主要问题在于是否有形式化的语义，大 6 山东大学硕士学位论文 多数工作流产品的可视化建模方法都缺乏形式化语义在具有形式化语义的状态 变迁网中，使用最多的就是p e t r i 网和状态图( s t a t ec h a r t s ) 具有形式化语义的 基本网的方法可以转换成其他建模方法，如基于规则的、时序逻辑的和脚本语言 的方法等。传统的p e t r i 网具有直观的图形表示、明确的语义、丰富的分析技术等， 但它不能完全描述任务间的条件关系，不能表示外部事件及时序对工作流程的干 预( 即开放性) ，并且不支持动态性，而这些在应用中又是不可避免的文献6 提出了基于p e t r i 网的分析方法，通过某些限制提出了一个可以在多项式时间内验 证正确性的模型结构w f - n e t 。但由于模型本身所具有的描述能力上距离对工作流 过程本质的描述仍有差距，所以模型本身表达力具有一定的局限性。 ( 3 ) 基于规则的建模方法1 7 1 目前研究的较多的是基于e c 规则的建模。e c a ( e v e n t - c o n d i t i o n - a c t i o n ) 规则具有形式化基础，也可以转换成其它的建模方法，如p e t r i 网、时序逻辑等， 但是e c z 规则的可视化工作量比较大。 在m e t e o r 项目中，类似于e c a 的规则用来表示任务间的状态和值依赖关 系。状态依赖规定了一个可控制任务变迁如何依赖于其它任务的可观察状态。事 件是隐含的，表示任务变迁到某个状态。规则中的条件可能是任务输出数据、工 作流全局变量的表达式。根据规则，一个任务迁移到另一个新的任务，同时相应 的任务状态发生变化。 在w i d e 中，e c a 规则用来描述由时态事件、工作流内部事件和外部事件引 发的工作流例外处理。工作流内部事件指的是工作流变量更改、约束违例，任务 的取消或者拒绝、执行实体的不可用等。条件可能是有关工作流模型产量或产品 数据的表达式，也可以是时态表达式。动作可以是任务状态修改、例外处理例程。 e c a 规则不仅能够描述工作流模型中活动之间的协调关系，而且能够表达组 织、角色之间的约束关系。此外，基于规则的方法能够支持过程的动态修改，角 色的调整等，因而使模型具有一定的灵活性，能够描述a d - h o c 类型的工作流模型a 但e c a 规则作为一中底层实现机制，缺乏图示化的手段和结构化构造工作流模型 的方法。另外，当规则急剧增加时，对规则的处理将是一个很繁琐的任务e c a 规则也缺乏逐步求精的手段，就语言而言，e c a 规则本身必须就借助于其它方法 来表示，如上面提到的凡们网和时序逻辑。因此，很难对e c a 规则表示的工作 山东大学硕士学位论文 流模型进行形式化的验证 ( 4 ) 基于逻辑的建模方法 给予逻辑的方法适合于描述系统的动态性，其中时序逻辑是一种常用的方法， 它具有很好的形式化基础，验证工作流模型的属性比较方便但是时序逻辑的主 要缺点是很难实现可视化，不容易转换成其它的描述方法，描述业务流程的系统 行为太复杂。例如d a v u l e u 采用的并发事务逻辑c t r ( c o n c u r r e n tt r a n s i t i o nl o g i n ) 来表示工作流模型。在c t r 中，对经典的逻辑符号( 与、或、取反等) 进行了扩 展，引入新的逻辑连接符号，如并发、可能和单独执行。与基于图的方法相比， 采用逻辑的一个优点是，能够表达全局约束，这些全局约束也能构用逻辑来刻画， 从而使工作流模型的描述和验证在一个统一到框架中进行。但是，同样由于其设 计上的难度和缺乏方便的图示化手段，该方法并没有广泛使用 ( 5 ) 基于事务模型的建模方法i 引 事务的概念来源于数据库研究领域，用于解决数据的并发访问和出错恢复问 题。事务性在工作流管理系统中更为重要，因为工作流活动的持续时间有时很长， 工作流执行过程中出现错误的可能性更大因此，从提高工作流管理系统的可靠 性出发，建立基于事务的工作流具有很重要的意义在数据库事务模型基础上， 研究人员提出了许多高级事务模型，包括嵌套事务类型( n e s t e d t r a n s a c t i o n ) 唧、 开放嵌套事务模型( o p e nn e s t e dt r a n s a c t i o n ) 【堋、s a g a 模型【1 1 】、分布式事务管 理模型( d i s t r i b u t e d t r a n s a c t i o n m a n a g e m e n t m o d e l ) 1 2 】以及柔性事务模型( f l e x i b l e t r a n s a c t i o nm o d e l ) b 3 等。 ( 6 ) 基于代数的方法 进程代数是一种刻画并发计算的工具，目前在工作流研究领域中还没有得到 广泛的研究和足够的重视有的研究人员采用l o t o s 来进行软件过程的建模。 l o t o s 是一种描述通信的进程代数。由于软件过程和业务过程的相似性，进程代 数也可以用来描述工作流模型。同基于逻辑的建模方法一样，进程代数的方法具 有严格定义的形式化语义，容易验证，但缺点是缺乏图示化的手段。 总之，目前的工作流产品中采用心f r f 网和e c a 规则的方法比较多，p e t r i 网 具有图示化的手段和严格的语义定义，能够对建立的工作流模型进行形式化分析 和验证，因而被广泛采用。但n 州网的缺点也很明显：图形过于复杂，节点过多， 8 山东大学硕士学位论文 从而导致普通用户难以掌握。而互c 爿规则的方法是一种较为理想的底层方式，但 缺乏图示化的手段和逐步求精的手段。 工作流模型的正确执行是提高企业竞争力，改善企业服务质量的关键因素之 一。如何对工作流进行建模同时对模型的正确性( s o u n d n e s s ) 进行验证是当今工 作流研究的一个热点，文献 1 4 b i a t 正确性( s o u n d n e s s p r o p e r t y ) 的概念，一个 工作流是正确( s o u n d ) 的，当且仅当对于任何工作流实例，处理过程都能够正确 的终止。如果过程模型中存在错误的逻辑，会导致严重后果，并且需要额外的补 救措施。因而，在工作流模型正式运行之前，必须对工作流模型进行分析。目前， 主要的思路有三种： ( 1 ) 证实( v a l i d a t i o n ) ，通过工作流仿真执行，判断是否和规定的模型一致； ( 2 ) 性能分析( 凡咖r m a n c ea n a l y s i s ) 。也是通过工作流仿真执行，分析工作流 的运行时间、服务质量和资源利用情况： ( 3 ) 正确性验证( s o u n d n e s sv e r i f i c a t i o n ) ，证明工作流模型是正确的，或者说不 存在错误的逻辑。 前两种方法，需要设计大量的工作流实例，来检查工作流运行是否正常，而 第三种方法，则是在工作流执行之前，对模型进行形式化的验证因而，从代价 的角度讲，验证的方法优于前两种方法。但是，验证问题在大多数商品化工作流 产品中并没有涉及到 h o f s t e d e 首先谈到t - r 作流模型验证的复杂性问题，通过限制模型为无循环 和无同步元素，证明了终止性问题是个多项式复杂度问题。而w m pv a nd e r a a l s t 通过把工作流表示成一种p e t r i 网的扩展：w f - n e t ，从而利用经典p e t r i 网理论对 工作流模型进行了验证，证明了一个工作流是正确的当且仅当w f - n e t 是活的，有 界的，并且是可达的。同时他还提出了一些静态的限制，如自由选择( f r e e c h o i c e ) 和好的结构( w e l ls t r u c t u r e ) ，但是这种基于p e t r i 网的方法并没有考虑每个特定 任务的语义。 综上所述，一个比较理想的工作流建模方法应该满足下面的条件： ( 1 ) 具有图示化的建模界面，建模用户容易掌握： ( 2 ) 建模方法或者语言本身是可执行的，可以作为工作流引擎的实现机制，例如， 一般基于规则的方法都可以作为底层实现机制； 山东大学硕士学位论文 ( 3 ) 有形式化的语义，也就是说，其语义可以用n 州网、逻辑或者代数表示， 从而可以对模型进行验证和推理。 当今工作流建模的研究有一种混和的趋势：高层面向用户的客户端用图示化 的建模手段，而在底层采用一中或者多种便于实现或者具有严格语义、便于验证 的方法，从而可以讲高层描述方法转化为底层方法，便于验证模型和程序实现 n 乱 1 7 虚拟企业与工作流管理系统 从生产经营的角度出发，制造企业可视为由多个相互关联的不同层次流程组成 的活动流程。由订货、采购、设计、生产、交货组成主流程，每个主流程又可分 解为多个彼此相关的子流程，层层分解，直至分解到活动。因此可以使用工作流 技术对企业的生产经营活动进行有效管理对于有能力组成虚拟企业的企业，应 该实现了工作流管理，而这些企业中的工作流管理系统可以通过i n t o r n e t 进行无 缝连接。 虚拟企业使用工作流管理可以达到以下目的： ( 1 ) 业务过程自动化。工作流系统可以在正确的时间把工作动态分配给符合规定 的虚拟企业成员，从而使得整个业务流程实现自动化 ( 2 ) 业务的动态调整。工作流系统中的即席工作流针对重复性不是很强或没有重 复性的工作流程，关于这类流程执行所需的有关参数( 如参加者等) 事先无法确 定，而必须推迟到过程实例运行时才能确定，同时在执行过程中间还可能会发生 一些意外的情况。这种动态多变的特点为虚拟企业动态定义、调整业务流程提供 了很大的灵活性。 ( 3 ) 控制、监视和警告。工作流引擎可以为每一个过程定义最后的期限并进行监 视。可通过不同的方式避免超越最后的期限，如向管理者发出警告，改变优先权， 或者是改变过程内部的执行路径等。此外，通过工作流引擎中时间戳的记录，可 提供统计报表，从而既达到控制、监视的目的又为虚拟企业提供了管理的依据。 1 1 6 】 山东大学硕士学位论文 1 8 本文所做的工作 上文概述了虚拟企业和工作流的概念及相互关系，并列举了主要的工作流建 模和相应验证方法存在的问题，以及理想的工作流建模方法满足的条件在此基 础上，本文主要作了以下研究工作： ( 1 ) 介绍了基于n 州网的工作流模型及其着色扩展，并给出该模型的基本属性 及正确性验证方法； ( 2 ) 根据上述模型，提出应用于虚拟企业的跨组织工作流模型； ( 3 ) 对面向虚拟企业的跨组织工作流模型给出正确性验证方法。 1 9 本文的组织结构 结合本文所做的研究工作，整篇论文的章节是这样组织的。第一章为绪论部 分，介绍了虚拟企业及工作流的起源、发展和基本概念，以及工作流管理系统的 分类，综述了工作流建模和验证方法，介绍了本文所做的工作；第二章介绍了基 于p e t r i 网的工作流模型，包括p e t r i 网与工作流网( w f - n e t ) 的概念与基本属性， 工作流网的完全性( s o u n d n e s s ) 证明，以及着色p e t r i 网在工作流网中的应用； 第三章主要介绍了应用于虚拟企业的跨组织工作流的建模，包括跨组织工作流的 基本概念与属性，以及对其扩展颜色属性后的着色跨组织工作流定义；第四章介 绍了面向虚拟企业的工作流正确性验证，包括普通跨组织工作流的正确性( 完全 性s o u n d n e s s ) ，着色跨组织工作流的正确性等问题，并在验证过程中举例说明； 第五章为全文的结束语。 山东大学硕士学位论文 第二章基于p e t r i 网的工作流模型。 2 1 引言 凡f r f 网自二十世纪6 0 年代由德国学者c a n 州提出。经过四十多年的发展， 已被广泛应用于各个领域进行系统的建模、分析和控制。 古典 f r f 网是具有两类称作库所( p l a c e ) 和变迁( t r a n s i t i o n ) 节点的双重 有向图( d i r e c t e d b i p a r t i t e g r a p h ) 结点之间通过有向弧连接。同一类型的结点之 间不允许相连。库所和变迁分别用圆圈和方框表示。 本章介绍了p e t r i 网和w f - n e t 的基本概念以及基于p e t r i 网进行工作流建模及 扩展的方法。 2 2p e t r i 网的基本概念 定义2 1 ( p e t r i 网) n f r f 网是一个三元组( ，lf ) ： i p 是库所的有限集， i i r 是变迁的有限集( p n 丁= 妒) ， 1 1 1 f p r ) ur x 尸) 为弧的集合( 流关系) 。 我们称库所p 为变迁t 的输入库所当且仅当存在由p 至r 的有向弧。称库所p 为变迁t 的输出库所当且仅当存在由t 至p 的有向弧。我们用t 表示变迁f 的输 入库所集合。符号f ，p 和p 类似定义，如p 指所有将p 作为其输入库所的 变迁t 的集合。需要注意的是我们限定所有弧的权值为1 因为库所代表了条件， 所以在工作流处理中弧的权值为其他值没有意义 在任意时刻，库所中包含零个或多个托肯，托肯用一个黑圆点表示p e t r i 网 的状态肘，也称为标识，是托肯在库所上的分布，即m p _ 刀v 我们可以如 下描述一个状态：l p i + 2 p 2 + i p 3 + o p ，该状态中库所a 内有一个托肯，p 2 内 有两个，p s 内有一个，p 4 内没有托肯此状态可以用另外一种方法表示： p ，+ 2 p ：4 - p ，。我们定义了一个偏序关系来比较状态对于两个状态m 和 山东大学硕士学位论文 m ：，m s m ：当且仅当对于所有的库所p 户：m 。( p ) m ：d ) ，其中肼0 ) 表示在 状态膨下库所p 中托肯的个数。 网络运行过程中托肯的数量可能会变化变迁是p e t r i 网中的活动部分：它们 根掘如下“实施规则( f i r i n g r u l e ) ”改变网络的状态： ( 1 ) 就绪( e n a b l e d ) ：t 的每一个输入库所( t ) 中均包含至少一个托肯； ( 2 ) 实施修疗喀) ：一个被就绪的变迁有可能被实施。当变迁，实施时，需消 耗它每一个输入库所( t ) 中的一个托肯，同时给它的每一个输出托肯 ( t ) 中产生一个托肯 变迁是p p 们网中的主动元素。通过实施变迁，过程从一个状态转变到另一个状态。 因此变迁经常表示事件、操作、转换或传输库所是n 研网中的被动元素，它们 不能改变网的状态，库所通常表示媒介、缓冲器、地理位置、( 子) 状态、阶段或 条件。托肯通常表示对象。这些对象可能是具体的事务，也可能是抽象的信息。 给定一个p e t r i 网( 尸，l ，) 和状态m ，定义如下符号： a ) m i l 如：在状态m 。中t 是被就绪的，并且t 被实施后状态肘i 转化为状态 m 2 b ) m 1 m 2 ：存在一个变迁t ，使得m l j l 如 c )m 1 山鸩：存在一个实施序列o = t j t 2 t - l 使得从状态m 1 转化为状态 m 。酃m 1 山m l 山! t m 。 我们称状态 毛为从m l 可达(