（计算机应用技术专业论文）基于赋时着色petri网的工作流建模技术研究.pdf

基于赋时着色p e t r i 网的工作流建模技术研究 河海大学硕士学位论文 摘要 近几年来，工作流管理技术被业界广泛采用并得到了迅速发展。它的主要特 点是根据一系列过程规则，采用计算机技术，使得业务流程完全或者部分地自动 执行。工作流管理系统最重要的功能之一就是工作流建模。这些预定义的过程模 型必须能很好的反映实际业务流程，因此需要找寻更为灵活的工作流过程形式化 表示方法及过程的执行策略。为了判定新的业务过程模型是否正确，就必须对其 进行分析。因此，需要研究使用仿真和形式化验证技术。a a l s t 的工作流网技术 就是一个典型代表。 a a l s t 的工作流网已被众多研究人员所认同，它是基于经典p e t r i 网所建立的。 因此，它能精确地描述事件的顺序、并发和冲突关系，使系统形象化，有利于理 解。但是，传统p e t r i 网具有一些固有的缺陷：难以实现流程控制，不能描述时 间性活动。因此，本文对经典p e t r i 网进行颜色扩展、时间扩展，在a a l s t 的工作 流网基础上提出了基于赋时着色p e t r i 网的工作流网，以及从业务流程到工作流 网的映射算法。 模型的正确性验证一直是工作流过程定义阶段的难点问题。一些学者提出了 基于图规约法的验证算法，这些算法研究主要集中在时间p e t r i 网的验证简化上， 很少有对赋时着色p e t r i 网进行研究的，并且这些研究也局限于对简单控制结构 的规约，对一些复杂结构( 如：a n d a n d 嵌套结构、o r o r 嵌套结构) 仍然 束手无策。本文在这些算法的研究基础上对赋时着色p e t r i 网的各种结构进行详 细的研究，提出了针对基于赋时着色p e t r i 网的工作流网的图规约验证算法。 最后，本文设计了一个用于进行模型元数据输出的建模工具。它采用x p d l 标准，支持可视化操作，支持业务流程模型重现，并实现了从业务流程到工作流 网的映射算法。 关键词：工作流，过程定义，赋时着色p e t r i 网，工作流网，类邻接表，x p d l 挞干赋时着色p e t f i 触的工作流建模投术研究 河海大学硕士学位论文 a b s t r a c t r e c e n t l y , 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 , ar a p i d l yd e v e l o p i n gt e c h n o l o g y , h a sb e e n a p p l i e dt om a n y t r a d e s t h em a i nc h a r a c t e r i s t i ci st h a ti tc a l lm a k eb u s i n e s s p r o c e s sa u t o m a t e di nw h o l eo rp a r t ，a c c o r d i n g t oas e r i e so fr u l e s ，u s i n gc o m p u t e r i n f o r m a t i o n t e c h n o l o g y t h e m o s t i m p o r t a n t f u n c t i o no fw o r k f l o wm a n a g e m e n t s y s t e mi sm o d e l i n g t i l em o d e lm u s t r e f l e c tb u s i n e s sp r o c e s s ，a n di t sn e c e s s a r yt o f i n daw a yt o e x p r e s sw o r k f l o wp r o c e s s 。t h em o d e lm u s tb ea n a l y z e dt o c o n f i r m w h e t h e ri ti ss o u n d t h ew o r k f l o w - n e tw h i c hp u tf o r w a r db ya a l s ti sat y p i c a l r e p r e s e n t a t i o n m o r en u m e r o u ss c h o l a r sa n ds p e c i a l i s t sh a v ei d e n t i f i e dw i t hw o r k f l o wn e tb a s e d o i lc l a s s i c a lp e t r in e t i t ，t h e r e f o r e ，c a nd e s c r i b es e q u e n c e ，c o n c u r r e n ta n dc o n f l i c t a n di tm a k e s s y s t e m v i s u a la n du n d e r s t a n d a b l e 。t h e r e , h o w e v e r , a r es o m el i m i t a t i o n s ： i ti sd i f f i c u l tt oc o n t r o lf l o wo fb u s i n e s s ，a n di tc a l l td e s c r i b et i m e l i n e s sa c t i v i t y s o t h ep a p e re x t e n d sc l a s s i c a lp e t r in e tb yt i m ea n dc o l o r t h e ni tp u t sf o r w a r dw o r k f l o w n e tb a s e do nt i m e - c o l o r - p e t a ln e ta n dm a p p i n ga r i t h m e t i cf r o mb u s i n e s sp r o c e s st o w o r k f l o wn e t 。 s o u n d n e s sv e r i f i c a t i o no fm o d e li s a l w a y s ad i f f i c u l t q u e s t i o n o fp r o c e s s d e f i n i t i o n s o m es c h o l a r s p u t f o r w a r dav e r i f i c a t i o na r i t h m e t i cb a s e do ng r a p h r e d u c t i o n 。t h e s ea r i t h m e t i c s p a y a t t e n t i o nt or e d u c t i o no ft i m e p e t r i n e t ，n o t t i m e - c o l o r p e t r in e t a n di tc a nr e d u c e s i m p l e c o n t r o l s t r u c t u r e ，n o tc o m p l e x s t r u c t u r e b a s e do nt h e s ea r i t h m e t i c s ，t h ep a p e rb r i n g sf o r w a r dag r a p hr e d u c t i o n a r i t h i n e r i cf o rw o r k f i o wn e tb a s e do nt i m e ( 、o l o r - p c t r in e t a tl a s t ，t h ep a p e rd e s i g n sa m o d e l i n gt o o l f o rm e t a d a t ao u t p u to fw o r k f l o w m o d e l t h et o o l a p p l i e s s t a n d a r d o fx p d lr e l e a s e d b yw f m c ，b a c k u p sv i s u a l o p e r a t i o na n dm o d e lr e d i s p l a y a n di t r e a l i z e sm a p p i n ga r i t h m e t i cf r o mb u s i n e s s p r o c e s st ow o r k f l o w n e t k e y w o r d s ：w o r k f l o w , p r o c e s sd e f i n i t i o n ，t i m e c o l o r - p e t r in e t ，w o r k f i o wn e t ， a d j l i s t ，x p d l 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成柒。尽我所知，除了文中特别加潋标注和致谢的地方外，论 l 文中不包含萁能人已经发表或撰写过熬研究成果。与我一丽工作麴露事 对本硬究所做的任何烫献均已在论文中作了明确的说明并表示了谢意。 如不实，本人负全部责任。 论文作豢( 签名) ：2 0 0 5 年3 月1 0 窭 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家圈书馆、中国学术期刊 光擞叛) 电子杂志毒主鸯投保甓本人爨送交学壁论文懿复印铎或电子文 档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档麴蠹 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被 查阅和借阅。论文全部或部分内枣的公布( 包括刊登) 授权河海大学研究 生院办理。 论文作者( 签名) ：2 0 0 5 年3 月1 0 日 基于赋时菪色p c t r l 蒯的工作流建模技术研究 河海大学硕士掌位论文 1 1 研究背景 第一章绪论 工作流技术的历史可以追溯到7 0 年代末的办公自动化和任务批处理1 1 】操 体系统中的j c l 语言o o b c o n t r o ll a n g u a g e ) 就带有原始的工作流思想。8 0 年代初 人们第一次使髑工作流术语1 2 】，但怒那个鼹候还没有真正戆工作滚系统出瑷。 随着计算机技术和网络的飞速发展，计算机的处理模式发生了臣大的变化， 飘集中式处理融分布协作式处理发腥。在这种新的处理模式中，人们可戬更加精 确地对意层的系统行为进行建模，瑷开发的系统g 够更快建对疲用嚣袋懿交伲做 出反应。因此，应用系统不仅仅要处理单个的任务，还要能够控制、监视和支持 处理过程的逻辩，帮管理组缆机构内部的工作流。许多内部具有复杂处理过程的 组织枫构认为鸯必要建立一熬套橛念、技术穗王疑来支持工终滤簧毽。在这耱应 用需求下，工作流管理的术语就应运而生了4 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 ，w f m c ) 的成立标 志璜工终浚技术开始遴入耱黔成熟瓣除段。必了安现不周工作浚产鑫之阙麴互操 作，w f m c 在工作流管理系统的相关术语、体系结构及应用编程接口( w a p l ) 等方面制定了一系列稀准。 不围瓣硬突老昶王传淡产最供应囊扶不露戆焦度绘交了工蠖滚粒定义。 w f m c 给出的工作流定义是：工作流是一类能够完全或者部分自动执行的经蒋过 程，它根据一系剐过程溉则，文档、信息或任务能够在不同的执行者之间进行传 递与执行。震溪渤及滔动之阕交诬懿过程袭示静妲务滚稷裁是工终浚l 弱。 工作流管理技术的发展，对业务流程自动化带来了不少帮助，但其效果仍然 不能令入满意，其不魑主要表现在： 1 、建模王暴对鼹户建立靛模蘩缺乏验涯支持哆这镬褥王终淀鬻理系统在 运行时可能发生数命性的错谈，从1 搿导致系统崩溃，损失巨大； 2 、 多个工作流引擎之间缺乏淑好的协同工作能力； 3 、疯子不愿厂蠹瓣建攘王其与王终滚弓| 擎乏润疑乏统一搂盈，经褥元数据 在两者之间不能很好的被解丰斥凡 基于赋时着色p c t r i 网的工作流建模技术研究 河海大学硕士学位论文 为了各个工作流管理系统能有一个统一的标准，w f m c 提出了一个参考模 型，如图1 - 1 ： 图1 - 1w f m c 提出的参考模型 w f m c 的参考模型定义了工作流的五大接口：接口1 ：过程定义数据，以及 过程定义数据的转换规范接口；接口2 ：支持不同工作流系统间协同工作的接口； 接口3 ：支持与各种不同r r 应用程序交互的接口；接口4 ：支持与用户交互的接 口；接口5 ：提供系统监视，以及标准功能来简化复合工作流应用环境管理的接 口。参考模型的提出有利于各软件厂商利用自身的技术优势，集中精力研究工作 流管理系统中的某一方面，从而促进工作流技术的发展。 本文主要对接口1 进行研究，即过程定义接口。 过程定义由各种活动以及相互之间的网状关系组成，标识了过程的开始和终 止，并且包含了个体行为的信息，比如各个参与者、与i t 相关的应用程序和数 据，等等。过程定义可能会涉及到子流程，子流程是单独定义的，是整个过程的 组成部分。 过程定义的导入导出接口，是建模或定义工具与运行时期工作流管理软件 间的接口。在此接口中需要实现工作流过程建模，把实际的业务流程转变成工作 流系统运行阶段可以解释的计算机化表示。工作流建模直接影响到整个工作流管 理系统的正确性与执行效率等关键问题 ”。同时，工作流建模是用户使用工作流系 统的第一步，一个高质量的工作流建模工具会方便用户的操作、能充分的描述实 际的业务过程，提高过程模型建立的准确性，最终影响整个系统的运行。接口1 基于赋时蒜毡p e t f i 弼匏工雩# 遽建摸技术蛩 究 # g 海火学颈：e 学健论文 是实现工作流定义与工作流运行阶段的分离。按照w f m c 的接口1 规范实现的 工 乍流建模= ： 具，可以与其它的符合w f m c 规范的王馋渡系统集成，从 甄实现建 模工具败遭照性。 1 。2 研究现状 目前工作流镗理技术已经进入飞速发展时娥，世界上有趣过二吾家软传供应 逝提供工l 乍波管理软件。除了专门黪工传流管理系统，大多数e r p 系统，妇s a p 、 b a a n 程j de d w a r d s 帮已把工柞流雩 攀雩 入刭自琵豹系统中。在夫部分情况下， 这些工俸流零 擎不能被当作独立的工作流管疆系统使用。 当前，裔关工作流管理系统的研究与开发主溪集中在一下几个方面： 建模；工作流管理系统的最羹要的功能之一就是工作流建模。这些预定义的 过程模型必须能很好的反映实际业务流穰，能够对过程定义以及过程实例方便地 进行动态修改 8 j ，因此需耍找寻熨为灵活的工作流过程形式化表示方法及过程的 执行策略1 9 j 。这方面的主要成果可参见文献：【l o 】f 1 3 】等等。 分据：为了判定毅的业务过程是否在定量和定性方露灌怒要浆，靛必须辩其 进行分掇。在现鸯过程被改遴之螽，瞧应该奁改变实施嚣对修改嚣静过程送行分 橱。为了迸行分攒，需要僮焉仿粪和一些形式仡验证技术。就仿粪而吉，市场上 港经蕊现了徽多髂模叛工其，在形式化方面，也融经有了不少的分析方法，这些 方法主要针对l e t r i 阙，与其体的业务过程结构无关。但是这些分析方法仍不够 完善，需爱进一步的研究发展。主要见文献：【1 4 】【1 7 】等等。 枣务管理：一般工作流管理系统在执行中缺芝并发和失败语义的一致性和可 靠性的能力。为了提糍此熊力，将一些高级事务模型施用到工l 乍流系统过程实例 的执行中，即事务型工作渡管理系统。蛩 究翅侮实现舞级搴务处瑗技术与王黪流 蛰理技术瓣结合，建宠义良好的楼型港义与恢复撬制采提舞工作流系统静正确性 与可靠往，扶嚣能够援好缝支持众韭复杂的馥务过程。 甄操作毪：不同工作流之间的互操律和通讯虽有w f m s 的参考模型作为基 础，但目前除了e m a i l 这种松散藕合的连接方式外没有具体实现支持。其研究 重点在于那些单独描述却需要互相支持的工作流之间的交互作用和并发问题【1 8 】。 同步协作：在些较大型的工作流管理中，某些环节的任务可能嚣要多个用 基于燃时着色p e t r l 两的工作流建模授术研究河海大学硕士学位论文 户的实时协作才髓更有效的完成f 捌，诧种支持能力正是黼前的w f m s 所缺乏的。 为掇供这琴孛能力，可以扶两个不囿的方厦入手：首先可以提供搜多个溺户能够按 同步协作的方式究成工作流形式化窳义的能力；另一方面允许柱活动执行时f i ! ；i 多 个用户同时协作究成豳l 。 对予以主阅题，一魑学者秘谚究人员在蒺些方嚣取褥了重大戆硬究成果。龙 其在建模方面，备种建模技术、建模工具发展非常迅速。g a r c i a m o l i n a 等人在 文献【2 l 】中借鉴数据库的事务处理技术，首次对工作流管理系统提出了事务补偿 弱橛念，以疆媛定义良虹约模型语义与滚复极铡来提毫工 乍滚模型戆蠹! 确性与可 靠性。m o h a n 在文献【2 2 】中列举了大型工你流管理系统设计时的一些关键问题： 错误处理、实用髓、导航机制、复制和并行处理。h o f s t e d e 与n i e u w l a n d 在文献 【2 3 1 中提枣了任务结稳熬壤念，在工作流蓉璎系绞中， 壬务结擒可以毂看终一耪 很好的模型描述与控制语言。荷兰e i n d h o v e n 大学的w m ，p v a nd e r a a l s t 在文献 【2 4 】中提出了基于经典p e t r i 网的工作流网概念，这使得p e t r i 网的众多分析技术 与王其可骇在工作滚警壤系统中褥鲮瘟羁，滋憩王佟滚翳弱概念已披众多磅巍人 员所认同，本文的研究也是基于工作流网的。 1 。4 研究内容积成果 1 4 。1 本文秘主要磋究表客 ( 1 ) 盈务流程到工作流羽静转纯。 建摸工具中用户的输入应该是隧机的、非专业的，亦即他们的输入仅仅是表 示业务流程的有向图。而工具的分析应该建立在一定的理论模型之上，如工作流 阏。所醣浠要寻我合适辩算法将有向黼映射掏工佟流网，并置裔尚图审的相威信 息必须褥以俣存。 ( 2 ) 高级p e t r i 网的特性研究。 p e t r i 阏作为稀窝形纯静数学王其，能深刻、简涪婊分析系统的渤态遥程， 精确地接述事件的顺序、并发和冲突关系，使系统形象化，有利于理髂。它不担 可以进行结构建模，又可以进行定性和定量的分析，这然特性使得p e t r i 网投术 在离散事件动态系统( d e d s ) 分析中的备受关注圜。但是，传统p e t r i 阏其 一4 - 基于赋时着色p e t d 嗣的工作流建模技术研究河海大学硕士学位论文 有一些固有的缺陷：难以实现流程控制，不能描述时间性活动，因此，本文在经 典p e t r i 鹣基秣上，对其进行颜色扩震、辩洒扩震，邵所谓馥赋辩蕾氆p e t r i 丽 ( t i m e c o l o r - p e t r in e t ，t c p n ) ，并对t c p n 的行为特性进行研究，努力使建摸 工县建立出来的模型简洁、精确，扩展性好。 ( 3 ) ： 髂流蠲静正确浚验 芷。 近年来，市场上已经出现了众多粒基予不固遐论黪工作凉产基，但这些产品 都存在一个很大的问题忽略了工作流模型的验证，几乎没有任何工具提供验 证支持秘。簸算法鹣魏窿讲，缺乏这静支持楚因为工作流验证狠复杂淄，丽它 的质果则是在工作滤篱理系绕运行孵可熊发生致命性的错误，从藤蹲致系统裁 溃，损失巨大。本文针对p e t r i 验证所碰到的难点，以简化原网为主囊思想，在 文激【2 7 】【2 朝的基础主提蹬了一种基予瞬巍约方式的验证方法。 ( 4 ) 存储网的数据结构。 用户输入的信息类型，信息内容大小怒随机的，不确定的。对于每一次建模， 璃户有可麓使稻不两的方式表示库所、变迁的不同信息，如何有效豹袭示这擅信 息，应当使用怎样的数据结梅，著将库赝、变迁键接成一个飚以便避纾验涯，这 些都是值得研究的问题。 1 4 2 本文的主螫研究成果 ( i ) 在a a l s t 的任务结构映射算法的綦础上，结合高级p e t r i 网技术提嫩了 一种基于链表遍历方式的业务流程到工作流网的l ! 兜射算法，该算法先纷出基本结 稳瓣映菇滚粼，然惹遍历整务流程甏有囊甏，对潮中豹每一个袄态节点应嗣辐应 的映肘规则进行p e t r i 网映射，此映射算法能实现籀级p e t r i 网建模； ( i i ) 针对p e t r i 网传统验证法一可达树验证法中可达状态节点过多，甚至 童瑷无疆状态节点豹阉逶，农文献【2 8 】【2 9 】鹣基确土提出了一稀基于潮麓约憨想 的赋时着色工作流网的验证算法，该算法先绘出基本结构及一些复合结构的嫂约 规则，随厢对网中的各种结构按规则进行规约，蓿网能舰约为一特定结构，则模 型建立芷麓； ( i i i ) 设计了基于炎邻接袭的建摸工具，该工具中设计了一穗类似邻接焱的 数据结构用于表示网系统，此种数据结构易于实现元数据输出。 基于赋时着热p e t t i 网的t 作漉建模技术研究渐海大学硕士学谊论文 1 5 论文结构 本文凼以下六章和参考文献组成。 第一章绪论。介绍论文酌研究背景秘磷究内容。 第二鬻介绍p e t r i 潮和工作流网的相关知识。 第三章论述了一种从业务流程到工作流网的映射算法。该算法先针对不同 的鏊本绪梅，先给出各螽的酸辩规羽，其次遍历裔淘图，对毒一个节点萃l 霄映射 靓则将表示业务漩程的育囱图映射成赋时麓色p e t f i 网，然后再姆该p e t f i 网转化 成工作流网。 第霞犟论述了一种基予蕊约思想的蕊时着包工俸流鞠的验证算法。传统的 p c t r i 网验涯算法存在饕可达状态节点过多的闻题，刊髑越化熊思想可实现对赋 时着色工作流网的验证。 第五肇基于类邻搂表的建模工搽的实壤。在与本文耜对皮的模黧定义工其 软 牛熬实现过程中，设计了一糖类似邻接袭豹数搀结构髑以存储刚系统、输如模 型元数据，并利用类邻接表实现了从业务流程到工作流网的映射算法。 第六牵总结与展鬻。总络全文工作，并给出下一步工作的展望。 基于赋时着色p c t r l 网的工作流建模技术研究河海大学硕士学位论文 2 。1p e t r i 网概述 第二章p e t r i 网与工作流网 1 9 6 2 年联邦德国的c a da d a mp e t f i 在他的博士论文用自动机通信中首 次使用网状结构模拟通讯系统f 6 】，该结构不久就被认为是描述和分析同步通讯和 并发进程资源共享的最适合可靠的建模语言。这种系统模型后来以p e t r i 网为名 流传，现在的p e t r i 网一词既是指这种模型，又指以这种模型为基础发展起来的 理论。但是在实际应用中，p e t r i 网出现了两个严重不足：一是无数据概念：二 是无层次概念【3 。这些限制使之只能进行小系统的建模。 7 0 年代后期高级网和8 0 年代后期高级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 网应用已经涉及计算机科学的各个领域，如软件工程、人工智能、并 行编译、网络协议、操作系统等等。 2 2 经典p e t r l 网与高级p e t r i 网 2 2 1 经典p e t r i 网 经典p e t r i 网是一个具有两类结点的有向图，这两类结点叫做库所( p l a c e ) 和 变i 王_ ( t r a n s i t i o n ) 。结点之间由有向弧( d i r e c t e da r c ) 连接，并且同类结点之间的连 接是不允许的。通常库所由圆形( o ) 表示，变迁由矩形( 口) 表示。库所中可以包 含托肯( t o k e n ) ，t o k e n 通常用黑点( ) 表示。 ( 1 ) 静态特性： 定义i ( p n 定义1 三元组p n = ( p ，t f ) 称为p e t d 网，当且仅当： i ) p n t = g ； 照于蜮时着色p e t r i 搏匏工作瀛遗摸技术秘究 辫海大学硕士学臻论文 i i ) p u t g ； i i i ) f _ c p x t o t x p ； i v ) d o m ( f ) uc o d ( f ) = p u t ， 其中d o r a ( f ) = x l | y ：( x ，y ) f k c o d ( f ) = y l 3 x ：x ，y ) e f 分别为f 的定义域 秘蕊域。 秘t 势鬃稼为p n 煞疼掰q l a c e ) 集移交迂( t r a n s i t i o n ) 集，f 为滚关系( 渤w r e l a t i o n ) 。库所和变迁又分别称为t 元素和t _ 元素，或p 一元和t 元。x = p u t 称为p n 熬元素集。 为了叙述方便，需豢定义库所绒交迁韵前集和后集。设x e p u t 中的任一元 素，令 4 x = y l ( y ，x ) e f ；x 8 = y l ( x ，y ) e f + x 称为x 的前集或输入集，x * 称为x 的后集或输出集。猩p n = ( p ，t i f ) 中， 如果对所有x p u t ，都商* x n x + = 彩，则称p n 为纯网，如果对所有x ，y p u t ， 帮有( 8 x = s y ) a ( x2 = y4 ) 缔x = y ，簧| j 称p n 为篱擎潮。 ( 2 ) 动态特性： 作为系统建模工具，p e t r i 网除其商以上描述的静态结构外，还应包括位鼹 容量_ 帮转移寝动对链登嚣爨豹影响信惑。有疆容羹可蘑大予零豹整数表示。转移 启动对位鬣中标记数的辩响用弧上的黢数表示，于魑具有动态特性的p e t r i 网可 表示为六元组= ( p 置e k w m 0 ) ，其中浞t ；f ) 含义同藏。 k ：p n + u ，麓使置上戆容激爱数，“= l ，2 3 。 ，若i 潍) = ，表示彼 置p 的容墩为无穷。 w ：f n + ，是弧集会上的权函数 m ：p - n o ，是上静标谖( m r k i n g ) ，m o 为初始标识。显然应该霄m l 潍) 。 ( 3 ) 转移启动规则： p e t r i 刚的动态行为憝通过转移启动从而引起标识改变来体瑷瓣，下西楚转 移有效( 转移可戳痘动) 瓣条俘帮启动溪黉| j 。 转移t 有效的条件 若在标识m 下，v p l ，p 2 e + t = 争m ( p 1 ) w 1 ，t ) ，且v p 2 ，p 2 e t t 醚q 2 - 8 - 基于赋时着色p e t r i 网的工作流建模技术研究河海大学硕士学位论文 w ( t ，p 2 ) k ( p 2 ) ，此时称t 在m 下有效，记为m 【t 。 转移t 启动的结果 若t 在m 下有效，t 就可以启动，启动后将m 变成新表示m ，记为m t m ， 并称m 为m 的后继标识。v p e p ，有： m p ) = m 0 ) - w ( p ，t )当p 4 t t 8 m ( p ) + w ( t ，p )当p t + - 8 t m ( p ) 一w q ，t ) + w ( t ，p ) 当p 4 t f q t + m )当p 圣t4 u 8 t 下面，给出一个经典p e t r i 网的实例，该模型的起始状态如图2 - 1 p lt 1p 2 p 3t 2 p 4 图2 1 经典p e t r i 网示例 图中的静态特性数学描述表示如下： n = f p , t ；f ) p = p l ，p 2 ，p 3 ，p 4 t = t l ，t 2 f = 0 1 ，t 1 ) ，( t l ，p 2 ) ，( t l ，p 3 ) ，( p 3 ，t 2 ) ，( t 2 ，p 4 ) ) 动态特性描述如下： m 0 = ( 2 ，0 ，0 ，o ) w ( p l ，t 1 ) = w ( p 3 ，t 2 ) = w ( t l ，p 3 ) = 2w ( t l ，p 2 ) = 4 w ( t 2 ，p 4 ) = 3 初始状态时，库所p l 中有两个t o k e n ，根据转移启动规则，有m o t ， 。令 m o h m 1 ，则根据变迁启动转移公式有，m 1 = ( 0 ，4 ，2 ，o ) 。此时，】m l t 1 ，而 有 m i t 2 m 2 ，并有m 2 = ( 0 ，4 ，0 ，3 ) 。状态标识序列m o 、m l 、m 2 描述了此p e t r i 网 的t o k e n 动态转移过程。此过程形象直观，易于理解。 2 2 2 高级p e t r i 网 经典p e t r i 网中对t o k e n 含义和变迁发生条件的定义比较简单，不利于对系统 基于赋时着色p c t r l 硝韵工作流建模技术研究 河海大学硕士学位论文 的理解。为了丰富模黧的表达能力，人们对经典p e t r i 网在颜色、时间、鼷次三 个方瑟邀萄二了扩展。 ( 1 ) 着色p e t r i 网 着包网也称为有识p e t r i 阐，就鼹在经典p e t r i 嗣的藻础上引入了颜色的概念， 对躔蟹奁疼所中靛t o k e n 个体赋予簇色 3 1 l 。在这爨，颜色表示豹楚它熬一个或一 组值。t o k e n 由予其值的不同而具有不问的颜色。这样，一个库所中就可以包含 几个不同颜色酌t o k e n 。一个变迁蒯表示一个复台条件，交迁器能够被激发就要 求与进入变迁黪煮肉弧据连瓣涯露获中含套要求瓣t o k e n ，软不弱疼溪遴入懿 t o k e n 在变迁中拟合，如果满足变迁袭示的复合条件，变迁激发，产生的新的t o k e n 遴副变迁的目标库所中。着甑p e t r i 网特剐适合于对通信协议、分布式系统、自 动生残系统、王撂滚稼进行分辑弱建摸器z l 。 对着色p e t r i 网的形式化定义如下： 网系统= ( p ，t - f ，c ，l 一，1 + ，m o ) 称为着色p e t r i 暖 ( c o l o r - p e t f in e t ) ，当 置仅当： i ) ( p ，t ；f ) 为商向网，称为的基网。 i i ) c ：p u t f ( d ) ，f ( d ) 为颜色集d 之幂集合，使得： 对p p ，c 国) 是瘁所p 土所有可能的托肯色( 资源类) 之集台。 对l 霉，e g ) 是交趱t 上黔毒可煞懿出瑷色之集合。 i i i ) i - 和i + 分别是p t 上的负函数和正函数，并且：使得对所有( p ，t ) e p t ： v p p ，3 t e t ：i - ( p ，0 辩0ub ( t ，力o ； v t e t ，3 p e p ：i - ( p ，1 ) 婶0gl ( t ，妨0 。 m o ：p d m s ，称为e 的初始标识，它必须满足条件v p p ：娲0 o p ) m s ， 即m o 是p 的托肯色集合上的多敷集。 ( 2 ) 赋露p e t r i 辩 通常当希望对一个过程的预期性能进行判断时，就鼹要对经典p e t r i 嘲进霉亍 时间扩展【3 3 1 。传统的p e t r i 网不允许对“时间”建模，即使进行了颜色扩展，对 过程辩藏避手亍建模仍然缀困滚 辩t 。 甚干赋时着色p e t f i 脚的工作流建模技术研究河海大学硕士学位论文 采用时间扩展时通常的做法是：标记将时间戳作为个值【3 5 】。该时间戳指明 标记舀侮时可蠲，令时滴戳为t 豹标记只有在时亥lt 之后方能被变迁消耗。变 迁要想就绪，当且仅当每个要被消耗的标记的时间戳旱予当蘸时闽。也就怒说， 变迁的就绪时刻是它的输入库所包含足够的可用标记的最早时刻。标记的消耗按 黧先避先岛( f i f o ) 窥捌f 3 3 l 。穗有最早时溺戳的标记蓠先被消耗。诧矫，具有 最早就绪时刻的变迁蕾先实髓。如果一个变迁实施著产生标记，那么每令拣记邦 被赋予一个不早于实施时刻的时间戳。实施的变迁可以确定产生的标记的獗时。 产生的标记静时闻戳等于实施对袤l 鸯日上对延。延时的长短可以依赖予其消耗的标 记的值。延时霹能是一个固定值( 翔1 0 s ) ，也霹越是一个位予菜一令区阕肉戆 随机值。根据这种固定值和区间值的划分，赋时p e t r i 网又可以分为固定延迟网 和不固定延迟辩闻网，由于不固定延时时阅两更舆有一般性，所以狠多研究都是 基予它之上的，本文也是以它为硬究对象。下嚣绘出不固定熊迟对瓣您网懿 形式化定义： z = 留，t ；f ，i ，o ，m o ，t ) 称为不固定延时网，当且仅当： i ) ( p ，t ，l ，o ，m 玉必荣标识蛇基本网； i i ) a t ：t a p ，其中a p 的元索为递增非负实数对a p = ( a 曲，a m 醒) ，其中 o a m i n a r r t a x 。 在这葶孛时闯网中，对每个转移t e t ，均毒一个a p e a p 与之稳对痰，馨表示 转移t 的启动要考虑延迟时间。假设t 在时钟为u 时有效，则它可在区间 u + a m i 。， u + a 。嗣内执行。也就慧说，当t 有效时，在输入位置p 中的标记至少霪保留a 。i n 秒，立至这些檬记虫予t 豹囊凄露移出。继t 必缓在珏+ 。内痿动，器委将不秀 能扁动。 ( 3 ) 多层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 网中，每一个结点不再是一个原子结点，可能其中的某一个结 点代表着一个子网，这个子网也是一个带裔库所、变迁、更深层次子网的p c t r i 牲于赋时着色p e t r i 刚的工作流建模技术研究 河海大学硕士学位论文 剃。掰墩可以鑫底瑟上或囊顼聪下层次化地构造p e t r i 网。自感疆土的方法是嚣 先然竣瘾避开始，详缨地攘遮基本缀终，这些组传波缀合减过程，众多豹予过糕 褥缀合成受大的过程，最终褥到过程浆详尽描述。囊顶预下的方法则正好桷反， 从最蓬屡次齐始，过稷不鞭地被分鼹为予过程，嶷到最底层只包挺变迁秘露所。 反复麓分解激褥剽层次讫豹援遮。 2 3p e t r i 网作为理论工具的理由 目前存程着多种理论对业务流程建模，基于脚本的建模方法过于复杂，而熬 予肖向图的建模方法又可能导致语义模糊不清，并且没有很好的模塑分析算法。 u m l 作为一种面阿对象的建横语富，髓很好的反映对象系统缀绞结构单元之间 的相互作用，但它不适合描述糕体的控制流程，对于工作流管理系统中随着进程 流动的资源来说，u m l 中没有与之相对应的元素，因此它并不能完整娩擒述熬 个企业的嬗务过程f 辅。有浆于此，本文采用高级p e t r i 网进行工作流建模，箕瑗 由如下： ( 1 ) 具脊精确的语义 基于p e t r i 网建立的模澄具有精确的语义，园为p c t r i 黼自身就楚一个拥有精 确定义的数学模型印1 1 3 甜，可以从语义学、矩阵论的角度对模型进行分析验诞【3 蚋。 ( 2 ) 图形化描述 p e t r i 网本身就是一种图形语言，因此，p e t r i 网其有直观瀚掌的将点，也有 利予和最终用户之间的交流【矧，同时p e t r i 网易于形式化表示，有利于专业人员 避杼研究与分析f 4 0 1 。 ( 3 ) 强大的表达携力 对予所有的工作流建模过程中的结构，都可以用p e t r i 网谶行描述f 2 韭。同时， p e t r i 网述可以明确表达整个流程的状态【埘。 ( 4 ) 基于状态丽不怒基予事件 目前大部分的过程定义技术，不论是非形式化方法还是形式化方法都悬基于 事件的，在这些技术中任努被明确地描述，但任务之间的状态却怒隐含的，必须 出工作流管璐系统的代码潦完成工佟流中的控制流，造成系统实现比较复杂，功 能不易扩充。而p e t r i 网是基于状态的，它可以消楚地描述案例的状态【4 1 】，只霈 基于赋时着色p e t t l 网的工作流建模技术研究河海大学硕士学位论文 要根据t o k e n 的分布状态就可以判断出任务是否被授权，是否可以被启动，是否 正在执行，这一特性可以使得工作流引擎的实现变得简单。 ( 5 ) 丰富的分析技术 经过三十年的发展，人们找到了许多基于p e t r i 网的分析技术。这些分析技 术可以用来验证安全性( s a f e t y ) 、不变性( i n v a f i a n c e ) 、合理性( s o u n d n e s s ) 以 及死锁( d e a d l o c k ) 等属性，也可以用来计算各种性能参数，如响应时间( r e s p o n s e t i m e ) 、等待时间( w a i t i n gt i m e ) 、占有率( o c c u p a t i o nr a t e s ) 等等。这些分析方 法也同样适用于工作流分析【2 5 】。 2 4 工作流网对p e t r i 网的扩展 工作流网是荷兰e i n d h o v e n 大学的w m p v a nd e r a a l s t 提出来的，他在工作 流过程建模中引入p e t r i 网技术并加以扩展，形成了如下的工作流网定义： ( w f n e t ) ：p e t r i 网p n = ( p ，t ；f ) 是工作流网( w f - n e t ，w o r k f l o wn e t ) ， 当且仅当： i ) 存在一个源库所i e p ，使得+ i = d ； i i ) 存在一个汇结库所o p ，使得o + = a ； j i ) 每一个节点x e p u t 都位于从i 到。的一条路径上。 根据以上定义，很容易得出w f - n e t 的一些性质： 令p n = ( p ，t ；f ) 是一个p e t r i 网，则： ( 1 ) 如果p n 是一个拥有源库所i 的w f n e t ，那么对于任何库所p e p ：+ 口 a 或p = i ，即i 是唯一的源库所； ( 2 ) 如果p n 是一个拥有汇结库所o 的w f - n e t ，那么对于任何库所p e p ： p + a 或p = o ，即。是唯一的汇结库所； ( 3 ) 如果p n 是一个w f n e t ，添加一个变迁t 到p n ，用来连接汇结库所。 和源库所i ( 即”t = o ) 八t ”= i ) ) ，则所获得的p e t r i 网是强连通的。 ( 4 ) 如果p n 有一个源库所i 和一个汇结库所o ，并且添加一个变迁t ，来连 接汇结库所。和源库所i ，产生一个强连接的网，那么对于每一个节点x e p u t ， x 都位于从i 到。的一条路径上，而且p n 是一个w f n e t 。 基于赋时着色p e t r i 喇的工作流建横技术研究河海大学硕士学位论立 第三章一种基于链表遍历方式的业务流程映射算法 3 。1 概述 本文采用p e t r i 网对工作流模型进行分析，为此需要寻找相应的映射算法， 将期户建立的表示业务流穰的有向图映射戚p e t r i 网，从而进一步将其映射为工 馆滚鼹。 工作流管理系统的原始任务有多种驱动方式。对于用户来说，照然最终建立 的模型都是简单有向图，儇不同的模型定义工具会提供不同的任务驱动形式。遗 今为止， 壬务鹣驱动方式烹婪有戳下尼辩 镩：( 1 ) 蔽涮滚方式：黻辩任务静滚獠 控制为主要目标，控制任努的执行顺序，根据不同的任务路由执行不同的工作； ( 2 ) 资源流方式：业务漉程的组织结构与角色( r o l e ) 和组( g r o u p ) 紧密相关， 任务的藏嚣楚出资源拥寄久的农隘确定滟；( 3 ) 羧掇漉方式；以辩数据熬控稍 ( c o n t r 0 1 ) 和制造( p r o d u c t i o n ) 为主露目标，数据题主要的信息炭体，它的存 在与否不依赖于工作流管理系统；( 4 ) 业务流方式：镞一个元素郝是一个可执行 零件。本文中的监务溅程滚述淤及褶应模整定义工具鹣实现都是潋控稍流方式淹 基础的。工作流网同样以掩制流方式为熬础。 a a l s t 在文献【2 4 】中曾对任务结构的工 乍流嘲映射蠢过较为详尽的撼述，但饿 懿浃辩算法童簧是钎瑟经典p e t r i 网，鑫于经典p e t r i 黼存在穗晕牵缺陪，不巅予辩 系统的理解，所以本章第三节将在a a l s t 工作流网映射算法的基础上进行扩展， 讨论基于赋对整色高级p e t r i 网靛工作流潮映射算法。第四节将绘幽该算法的具 体实例。 3 2a a i s t 的任务结构映射算法 a a l s t 的任务结构到置作流网的映射算法已被众多学者所认同，为了便于叙 述a a l s t 的任务结构映射算法，先给出几个