（管理科学与工程专业论文）基于Petri网的工作流建模技术的应用研究.pdf

浙江理工大学硕士学位论文 摘要 工作流的概念起源于生产组织和办公自动化领域 是人们为了提高生产和办公效率 针对工作中具有固定程序的常规活动提出的 其目的是通过将业务分解成定义良好的任 务 角色 并按照一定的规则和过程来执行这些任务并对它们进行监控 以提高办事效率 降低生产成本 提高企业生产经营管理水平和企业竞争力 工作流模型在提交给工作流引擎之前 应该首先验证模型的正确性 测试工作流是否 能实现预期的业务目标 获得相关性能指标 找出模型中存在的死锁 瓶颈以及冗余部分 从而修改模型使其达到最优的性能 模型的正确性验证和性能评价是工作流系统当前一个 主要的研究和应用领域 p e t r i 网作为一种从过程的角度出发描述和分析复杂系统的模拟工具 具有形式化的 语义定义 直观的图形表达 严格的数学基础以及基于状态的描述等优点 非常适合于业 务过程建模和流程优化 本文结合浙江省高级人民法院o a 系统 把扩展p e t r i 网应用于工作流的建模和评价 过程中 对公文的收发过程进行建模 使用合理性验证规则对模型进行验证并加以改进 根据广义随机p e t r i 网理论对工作流系统的性能 平均服务时间和资源利用率进行了定量 分析 本文针对经典p e t r i 网的死锁定义过于宽泛的问题进行了探讨 引入了严格死锁和可 控死锁概念 因为在实际的p e t r i 网模型中往往存在死锁 但是可控的 这就为给实际问 题的正确描述带来了方便 文中引入了虚变迁的概念 虚变迁指的是不消耗时间和资源 能够将输入库所状态转 移到输出库所状态的变迁 通过引入虚变迁可以将两个或多个相互独立的具有相同状态的 库所经过或汇集 o r j o i n 后合并为单一库所 从而可以使某些存有缺陷的工作流子网消 除缺陷 在本文的写作过程中作者参阅和引用了多个文献资料 为方便阅读和相互印证 作者 对p e t r i 网的部分符号和术语作了规范统一 使用p r e v x 和n e x t x 分别表示节点x 的前集 和后集 扬弃了在x 左右加上标 的表示方法 关键词 公文流转p e t r i 网时间约束工作流网性能分析 浙江理工大学硕士学位论文 r e s e a r c ho na p p l i c a t i o no fw o r k f l o w m o d e l i n gt e c h n o l o g y b a s e do np e t r in e t a b s t r a c t t h ec o n c e p t i o no fw o r k f i o wo r i g i n a t e sf r o mp r o d u c t i v eo r g a n i z a t i o na n do a o f f i c ea u t o m a t i o n p e o p l e b r i n gf o r w a r di tb e c a u s ei ti sa l l i e dt or e g u l a rp r o g r a mo fr o u t i n ea c t i v i t yd u r i n gw o r k w h i c hc a ni m p r o v et h e e f f i c i e n c yo fp r o d u c t i v eo r g a n i z a t i o na n do f f i c i a lb u s i n e s s t h ep u r p o s eo fw h i c hi st h r o u g hd e c o m p o s i n g b u s i n e s si n t ow e l ld e f i n e dt a s k s r o l e s a n da c c o r d i n gt oc e r t a i nr u l e sa n dc o u r s et oe x e c u t et h e s et a s k sa n d m o n i t o rt h e m s ot h a tw ec a ne n h a n c ew o r ke f f i c i e n c y r e d u c ep r o d u c t i o nc o s t i m p r o v ec o r p o r a t i o n s p r o d u c t i o na n do p e r a t i o nm a n a g e m e n tl e v e la n dc o m p e t i t i v ep o w e r b e f o r es u b m i t t i n gw o r k f l o wm o d e lt ow o r k f l o we n g i n e a b o v ea l l w es h o u l dv a l i d a t em o d e l s c o r r e c t n e s s t e s tw h e t h e rw o r k f l o wc a nr e a l i z ep r o s p e c t i v eg o a l g a i nr e l e v a n tp e r f o r m a n c ei n d e x a n df i n d e x i s t i n gd e a d l o c k s b o t t l e n e c ka n dr e d u n d a n c yi nt h em o d e l s ot h a tw ec a na m e n dm o d e lt om a k ei tr e a c h o p t i m a lp e r f o r m a n c e t h em o d e lv e r i f i c a t i o na n dp e r f o r m a n c ee v a l u a t i o ni st h em a i nr e s e a r c ha n da p p l i c a t i o n f i e l di nt h ew o r k f l o ws y s t e m p e t r in e ta sas i m u l a t i o nt o o lw h i c hi sf r o mt h ep e r s p e c t i v eo f p r o c e s st od e s c r i b ea n da n a l y z ec o m p l e x s y s t e m w h i c hh a sm a n ya d v a n t a g e s s u c ha sf o r m a ls e m a n t i c v i s u a lg r a p h i c a le x p r e s s i o n s t r i c tm a t h e m a t i c s b a s i ca n dd e s c r i p t i o nb a s e do ns t a t e s oi ti sw e l lf i tf o rm o d e l i n gb u s i n e s sp r o c e s sa n do p t i m i z i n gp r o c e s s t h i st h e s i sc o m b i n e dw i t hz h e j i a n gh i g h e rc o u r to a s y s t e m a p p l y i n ge x t e n d e dp e t r in e tt ow o r k f l o wm o d e l a n de v a l u a t i o np r o c e s s m o d e l i n gd o c u m e n t sr e c e i v i n ga n ds e n d i n gp r o c e s s u s i n gr a t i o n a l i t yv e r i f i c a t i o n r u l e st ov a l i d a t ea n di m p r o v et h em o d e l a c c o r d i n gt og s p nt h e o r y id oq u a n t i t a t i v ea n a l y s i sf o rw o r k f l o w s y s t e m sp e r f o r m a n c ea v e r a g es e r v i c et i m ea n dr e s o u r c eu s a g e b e c a u s eo fc l a s s i c a lp e t r in e t sd e a d l o c kd e f i n i t i o ni st o og e n e r a l t h i st h e s i si n t r o d u c et h ec o n c e p t i o no f s t r i c td e a d l o c ka n dc o n t r o l l a b l ed e a d l o c k s i n c ed e a d l o c ki sa l w a y si nt h ea c t u a lp 硎n e tm o d e l w h e r e a si ti s c o n t r o l l a b l e w h i c hp r o v i d ec o n v e n i e n c ef o ra c t u a lp r o b l e m sc o r r e c td e s c r i p t i o n t h i st h e s i si n t r o d u c et h ec o n c e p t i o no fv i r t u a lt r a n s i t i o n v i r t u a lt r a n s i t i o nr e f e r r e dt ot r a n s i t i o nw h i c hd o n o tc o n s u m et i m ea n dr e s o u r c e a n dc a nt r a n s f e ri n p u tp l a c e st oo u t p u tp l a c e s i n t r o d u c i n go f v i r t u a lt r a n s i t i o n c a nm a k et w oo rs e v e r a ls e p a r a t e dw i t ht h es a m es t a t ep l a c e sb yo r j o i nt oi n c o r p o r a t ei no n ep l a c e w h i c h c a nm a k ew o r k f l o ws u b n e tw j t hd e f e c t sa v o i dd e f e c t s 浙江理工大学硕士学位论文 t h e r ea r ep l e n t yl i t e r a t u r ec o n s u l t e da n dc i t e di nt h ec o u r s eo f c o m p o s i t i o no f t h i st h e s i s i no r d e rt or e a d e x p e d i e n t l ya n dc o r r o b o r a t i o nw i t he a c ho t h e r a u t h o ru n i f yp a r t i a ls y m b o la n dt e r mo fp e t r in e t t h ep r e y x a n dn e x t x a r el a b e l e da st h ep r e s e t sa n dp o s t s e t so fn o d ex b ya u t h o r a n dt h em e t h o dt h a ti te m p l o y s u p e r s c r i p ta r o u n dxw a s a b a n d o n e d k e y w o r d s d o c u m e n tt r a n s i t i o n p e t r in e t t c w f p e r f o r m a n c ea n a l y s i s 浙江理工大学学位论文原创性声明 本人郑重声明 我恪守学术道德 崇尚严谨学风 所呈交的学位论文 是本人在导师 的指导下 独立进行研究工作所取得的成果 除文中已明确注明和引用的内容外 本论文 不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容 论文为本人亲自撰 写 我对所写的内容负责 并完全意识到本声明的法律结果由本人承担 学位论文作者签名 醵亚蠕 日期 瑚 年 月 日 浙江理工大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版 允许论文被查阅或借阅 本人授权浙江理工 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印 或扫描等复制手段保存和汇编本学位论文 本学位论文属于 保密口 在 不保密口 学位论文作者签名 缘亚岛 日期 坳 年 月7 日 年解密后使用本版权书 指导教师签名 乏 召缪 醐 7 刖朋 浙江理工大学硕士学位论文 1 1 工作流研究的形成与发展 1 绪论 工作流技术起源于二十世纪七十年代中期办公自动化领域的研究 它是针对日常工作 中具有固定程序的活动而提出的一个概念 提出的目的是通过将工作分解成定义良好的任 务 角色 按照一定的规则和过程来执行这些任务并对它们进行监控 达到提高办事效率 降低生产成本 提高企业生产经营管理水平和企业竞争力的目标 由于当时计算机尚未普 及 网络技术水平还很低以及理论基础匮乏 这项新技术并未取得成功 1 9 9 3 年8 月 第 一个工作流技术标准化的工业组织 工作流管理联盟 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 成立 1 9 9 4 年 工作流管理联盟发布了用于工作流管理系统之间互操作的 工作流参考模型 并相继制定了一系列工业标准 与此同时 关于工作流技术的学术研究 也十分活跃 许多原型系统在实验室里被开发出来 如i b m 的m q s e r i e sw o r k f l o w a c t i o n t e c h n o l o g i e s 公司的m e t r o f i l e n e t 公司的v i s u a lw o r k f l o j e t f o r m 公司的i n t e m p o 和 p a v o n e 公司的g r o u p f l o w 和p a v o n e 公司的e s e p r e s s o 等等 这些工作流产品都具有独立的 一套工作流模型 工作流定义语言以及a p i 函数 因为不同的系统之间缺乏互操作的接口 一旦用户选定一种产品之后 很难再过渡到其他同类产品上 目前在工作流建模方面还没 有形成一套比较成熟的理论和方法 特别是模型验证方面 严格的理论上的分析还几乎处 于空白 1 1 1 工作流定义与相关概念 不同的研究者和工作流产品供应商从不同的角度给出了工作流的定义 下面给出几个 具有代表性的定义 工作流联盟给出的工作流定义是 1 9 9 6 工作流是一类能够完全或者部分自动执行的 经营过程 它根据一系列过程规则 文档 信息或者任务能够在不同的执行者之间进行传 递与执行 g e o r g a k o p o u l o s 1 9 9 5 给出的工作流定义是 工作流是将一组任务组织起来完成某个经 营过程 在工作流定义中定义了任务的触发顺序和触发件 每个任务可以由一个或者多个 浙江理工大学硕士学位论文 软件系统完成 也可以由一个或一组人完成 还可以是由一个或多个软件系统协作完成 任务的触发顺序和触发条件用来定义并实现任务的触发 任务的同步和信息流的传递 a mi ts h e t h 1 9 9 5 的定义 工作流是涉及到多任务协调执行的活动 这些任务分别由 不同的处理实体来完成 一项任务定义了需要做的某些工作 它可用各种形式来进行定义 包括在文件或电子邮件中的文本描述 一张表格 一条消息以及一个计算机程序 用来执 行任务的处理实体可以是人 也可以是计算机系统 比如一个应用程序 一个数据库管理系 统 w m p v a nd e ra a l s t 1 9 9 6 的定义 工作流是一系列工作的偏序集 工作的序列可以有 多种方式 比如工作x 与y 满足x c o d f x e p u t i j y p u t y x f p 叫做库所 p l a c e 集 t 叫做变迁 t r a l l s i t i o n 集 f 叫做流关系 f l o wr e l a t i o n 集 p 中的元 素叫库所或p 元素 t 中的元素叫变迁或t 元素 f 是由一个p 元素和一个t 元素组成的 有序偶的集合 d o m f 是f 所含有序偶的第一个元素的集合 c o d f 是第二个元素的集合 称d o m f 和c o d f 分别是f 的定义域和值域 用图形来表示一个网时 使用o 来表示库所 使用口来表示变迁 每个库所代表一种 资源 资源的流动由流关系规定 所以变迁只能与库所有直接的流关系 如表达式 3 所 定义 变迁和库所之间共有两种类型的流关系 从库所到变迁 从变迁到库所 从库所到 库所 或从变迁到变迁的流关系是不允许的 网就是一个有向图 它将节点分为两类 库所和变迁 同类节点间不能相连 流关系 就是有向孤 定义2 2 设n p t f 为一个网 对于x e p ut 本文采用p r e v 及n e x t 分别记节 点 集 的前集及后集 浙江理工大学硕士学位论文 p r e v x y l yeputn y x f n e x t x 2 y l y eput n x y f 称 p r e v x 为x 的前集或输入集 n e x t x 为x 的后集或输出集 称p r e v x u n e x t x 为 原素x 的外延 托肯 t o k e n 是p e t r i 网的一个重要概念 它是p e t r i 网的使能机制 托肯的状态 取值 是决定变迁发生与否的主要外部环境 原因 定义2 一 3 设n p t f 为一个网 映射m p 0 1 2 称为网n 的一个托肯 t o k e n 二元组 n m 也即四元组 p t f m 称为一个p e t r i 网 经典p e t r i 网 托肯网 为了叙述的方便与清晰 本文将托肯m 在单个库所p e p 的映射值m p 称为令牌 用 图形来表示一个p e t r i 网时 若m p k 则在表示库所p 的小圆圈内加k 个小黑点 当数值 很大时也可以直接写上数字k 并说令牌值为k 在不引起混淆时 单色网 也称库 所p 中有k 个令牌 定义2 一 4 一个p e t r i 网系统具有下面的变迁发生规则 对于变迁t e t 如果v p e p p c p r e v t m p 1 则说变迁t 在托肯m 有发生权 记为m t 若m t 则在托肯m 下 变迁t 可以发生 从托肯m 发生变迁t 得到一个新 的托肯m 记为m t m 对任意的p e p l m p 一1 若pep r e y t n e x t t m p m p 1 若p e n e x t t 一p r e v t m 0 其它 上述抽象定义含义如下 只有变迁t 的每个输入库所都至少含有一个托肯 变迁才有 发生权 变迁一旦发生 便从它的每个输入库所中取走一个令牌 令牌值减1 并往它的 每个输出库所增加一个令牌 令牌值加1 2 2 2 高级p e t r i 网 由于传统p e t r i 网在描述一些问题时会变得庞大而且难以理解 或者不能对某些活动进 行建模 因此产生了对基本网的扩展 成为高级网 这些扩展包括 颜色扩展 时间扩展 层次扩展等 1 颜色扩展 浙江理工大学硕士学位论文 传统的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 网的出发点是对于系统中类 似的要素合并 并用经典p e t r i 网的模型要素 库所 变迁 弧 来表示 用这些模型要素的 属性来区分同一系统中不同的个体 在颜色p e t r i 网中称这些属性为色彩 c o l o r 在变迁实 施时所产生的托肯 取决于实施时被消耗的托肯的值 生产出的托肯的值也可以依赖于那 些被消耗的托肯的值 定义 2 5 j 一个简单的 带k 种颜色的 颜色p e t r i 网是一个五元组n p t f w m 其中 p t f 是一个网 在颜色p e t r i 网中 w f o 1 2 k m p 一 0 1 2 k 对于t t 如果p p r e v t 一m p 也w p t 那么变迁t 在托肯m 下有发生权 m t 在托肯m 下发生变迁t 产生一个新的托肯m m t m f m p w p t 若p p r e v t n e x t t im p w t p 若p n e x t t p r e v t m p im p w p o w t p 若p p r e v t n n e x t t m p 其它 2 时间扩展 通常当希望对一个过程的预期性能进行判断时 就需要对经典p e t r i 网进行时间扩展 经典的的p e t r i 网不允许对 时间 建模 即使进行了颜色扩展 对过程时间进行建模仍然很 困难 采用时间扩展通常的做法是 把时间戳作为托肯值 该时间戳指明托肯自何时可用 一个时间戳为t 的托肯只有在时刻t 之后才能被变迁消耗 变迁要想就绪 当且仅当每个 要被消耗的托肯的时间戳早于当前时间 也就是说 变迁的就绪时刻是它的输入库所包含 足够的可用托肯的最早时刻 托肯的消耗按照先进先出 f i f o 规则 拥有最早时间戳的托 肯首先被消耗 此外 具有最早就绪时刻的变迁首先实施 如果一个变迁实施并产生托肯 那么每个托肯都被赋予一个不早于实施时刻的时间戳 实施的变迁可以确定产生的托肯的 延时 产生的托肯的时间戳等于实施时刻加上时延 延时的长短可以依赖于其消耗的托肯 浙江理工大学硕士学位论文 的值 延时可能是一个固定值 如5 5 个时间单位 也可能是一个位于某一个区间内的 随机值 根据这种固定值和区间值的划分 时间p e t r i 网又可以分为固定延迟网和不固定延 迟时间网 由于不固定延时时间网更具有一般性 所以很多研究都是基于它之上的 时间p e t r i 网 t i m ep e t r in e t t p n 的定义最早是由p m e r l i n 1 9 7 4 提出的 后人在 他的基础上做了一些修改 下面是时间p e t r i 网的一般性定义 定义2 一 6 时间p e t r i 网是一个五元组n p t f m i 其中 p t f m 是一个经典p e t r i 网 i 是定义在变迁集上的时间区间函数i t 一心 凡u 这里凡表示非负实数集 对于t e t 若i t 0 p 那么当变迁t 在托肯m 在经典p e t r i 网意义下 有发生权时 至少要经过q 个单位时间才能发生 如果在此期间没有别的变迁发生使t 失去发生权 那么 变迁t 最晚在p 个时间单位内必然发生 i t 0 l p 俗称点火时段或触发时段 一般常取a 0 即在变迁t 使能后可以立即触发 最迟也在p 时能触发 时延p e t r i 网 t i m e dp e t r in e t t d p n 的定义是r a m c h a n d a n i 19 7 4 最先提出的 后人在 他的基础上做过一些非本质的修改 下面是时延p e t r i 网的一般性定义 吴哲辉 2 0 0 6 p 2 1 7 2 1 8 定义2 一 7 时延p e t r i 网是一个五元组n p t f m d i 其中 p t f m 是一个经典p e t r i 网 d i 是定义在变迁集t 上的时间函数 即d ht 对于t t d i t a 表示变迁t 的发生需要a 个单位时间来完成 即当一个托肯m 满足m t 时 变迁t 立刻就可以发生 但要经过a 个时间单位 t 的发生才结束 由t p n 和t d p n 定义易见 一个同时具备触发时刻及执行时间的变迁应该更能反映实 际情况 关于时间扩展p e t r i 网的更多讨论和具体应用在本文第3 5 和6 章 2 3 p e t r i 网动态性质 2 3 1 p e t r i 网行为特性 1 直达性和可达性 定义2 一 8 设n p t f m 为一个p e t r i 网 如果存在t t 使m t m 则称m 为从m 直接可达的 如果存在变迁序列t l t 2 t k 和托肯序列m l m 2 m k 使得 浙江理工大学硕士学位论文 m h m i t 2 m 2 m k 1 k m k 则称m k 为从m 可达的 从m 可达的一切托肯序列的集合 记为r m 约定m r m 吴哲辉 p 2 7 定义2 一 9 设n p t f m o 为一个p e t r i 网 其中 m o 是n 的初始托肯 网n 的可达 托肯集r m o 定义为满足下面两条件的最小集合 吴哲辉 p 2 7 1 m o r m o 2 若m r m o 且存在t t 使得m t m 则m e r m o 第一个条件表明被称作为p e t r i 网的可达托肯集至少要包括初始托肯 第二个条件则 要求可达托肯集的元素对直接可达托肯是封闭的 p e t r i 网的可达托肯集可以直观地用可 达托肯图表示 本文第5 章将作具体介绍和应用 2 有界性和安全性 p e t r i 网的有界性反映被模拟系统运行过程中对所有资源的容量要求 只有库所的资 源不小于库所的界 才能保证系统的正常运行 1 有界库所和安全库所 设n p t f m o 为一个p e t r i 网 对某一库所p e p 若存在正整 数b 使得对可达托肯集r m o 的任一托肯m 都有m p 1 则称变迁t 为活的 如果每个t t 都是活的 则称网n 为活的p e t r i 网 4 死锁与陷阱 下面是抄自吴哲辉 2 0 0 6 p 8 8 对死锁与陷阱定义 定义2 一 1 1 设n p t f 为一个网 p i g p 如果p r e v p 1 n e x t p 0 则称p l 为网 的一个死锁 如果n e x t p 1 ep r e y p 1 则称p 1 为网的一个陷阱 浙江理工大学硕士学位论文 在网系统运行过程中 一个不含有托肯的死锁永远不会得到托肯 一个含有托肯的陷 阱永远不会失去托肯 2 3 2 对p e t r i 网死锁定义的探讨 图2 1 死锁实例图 在上面图2 1 中 p r e v p 0 p 1 p r e v p 0 up r e y p 1 2 t o t 1 n e x t p 0 p 1 n e x t p 0 un e x t p 1 2 t o t 1 t 2 由于p r e v p 0 p 1 c n e x t p 0 p 1 所以 p 0 p 1 构成死锁 由死锁的定义2 一 1 1 和死锁实例可看出 只要相应的库所和变迁存在循环就存在死 锁 一般存在两种类型的循环 即死循环和活循环 所谓死循环指的是永无止境的进行下 去的循环 活循环指的是通过添加限定条件可以跳出去的循环 如果相应的库所和变迁存 在死循环 则此p e t r i 网存在死锁 如果相应的库所和变迁存在活循环 则此p e t r i 网只是 存在死锁的可能性 因此我们有必要对循环加以区别 上小节关于经典p e t r i 网死锁的定义过于宽泛 如果严格按照上节所给出的死锁定义 在实际的p e t r i 网模型中往往存在死锁 这就给实际问题的描述带来不便 本文在吴哲辉对 死锁定义的基础上 引入严格死锁和可控死锁的概念 设n p t f m 为经典p e t r i 网 p 1 是库所集p 的子集p i c p 记p l 中的所有元素p 的 输入集的并为p r e v p i 这是一个变迁子集 所有的输出集的并为n e x t p 0 这也是一个变 迁子集 浙江理工大学硕士学位论文 1 严格死锁 如果p r e v p 1 n e x t p 0 则称p l 为网的一个严格死锁 2 可控死锁 如果p r e v p 1 cn e x t p 1 则称p l 为网的一个可控死锁 改进后的定义能够很好地对死锁进行区分 如果满足严格死锁的定义 则该库所肯定 会产生死锁 这时就需要对p e t r i 网模型加以改进 如果满足可控死锁的定义 此时可以通 过添加限制条件来控制死锁的产生 图2 2 严格死锁与n i 控死锁实例 在图2 2 中 p r e v p 0 p 1 c n e x t p 0 p 1 即 p 0 p 1 满足可控死锁的条件 p o p 1 是此p e t r i 网模型的可控死锁库所集 进一步观察图2 2 因p r e v p 4 n e x t p 4 t 3 即 p 4 满足严格死锁集的条件 显然 此p e t r i 网模型既存在可控死锁又存在严格死锁 对于因可 控死锁而导致的死锁只需添加限制条件来限制死锁的产生 而对于因严格死锁而导致的死 锁则需要对有关库所和变迁加以改进 1 6 浙江理工大学硕士学位论文 3 基于p e t r i 网的工作流建模 过程建模的目的是为了支持处理过程的定义 执行 注册和监控 需要为工作流提供 一个抽象表达的参考性的框架环境 在这个阶段 利用一个或多个建模方法 完成实际的 工作流程到形式化定义的转化 得到相应的过程定义是需要考虑的首要问题 3 1 基于p e t r i 网工作流建模的可行性 3 1 1 过程建模方法的评价标准 工作流是对业务流程的抽象表示 因此建立相应的工作流模型是必不可少的 为了评 价过程建模方法 必须首先给出确定过程模型的标准或者说是功能特征 针对过程建模的 特点 过程建模方法必须满以下的基本条件 1 支持面向过程的建模 过程建模的对象是过程 是以过程为中心的 建模方法只有支 持以过程为对象 才可以进行过程建模 2 同时支持静态分析和动态分析 过程建模的目的是为了模拟现实 现实是动态多变的 因此建模方法必须具有动态的模拟功能 3 具有各种复杂的逻辑关系的表达能力 各种过程的逻辑关系是复杂的 过程中的各个 实体的关系也是复杂的 因此建模方法必须具有表达这些复杂逻辑关系的能力 4 具有形式化的能力 过程模型需要通过形式化的语言进行表达 5 具有抽象能力 能够分层次表达 必须有一定的抽象机制 采用分层的表达方式才可以 清楚的建模 6 简单 容易理解和掌握 只有具备这个特点 建模方法才可以在过程管理中真正的发 挥作用 3 1 2 工作流建模方法的选取 由于工作流描述的是企业的业务流程是如何进行的 因此 许多工作流模型都是从过 程定义入手 比如状态图和活动网络图等 常用于工作流建模的方法有 i d e f 族方法 e p c 方法 r a d 方法 d f d 方法 u m l 方法和p e t r i 网 1 7 浙江理工大学硕士学位论文 1 i d e f 族方法 i d e f 族利用图形符号和自然语言 简单准确 容易理解和掌握 同时采用层次化的建 模方法 过程的自身规律得到分解 能够清楚的描述过程及过程间的关系 i d e f 族的方法 基本上是静态建模 缺少动态的功能 由于其主要是图形化的表达方式 在表达复杂的逻 辑关系和非确定的信息方面有所缺陷 2 基于事件驱动的过程建模方法e p c e v e n t d r i v e np r o c e s sc h a i n 是由k e l l e r k n o l m a y e r 等人提出的它的主要元素是功能和事件 功能被时间触发 功能也能产生相应的事件 它最大的优点在于它兼顾了模型描述能力强与模型易读性这两 个方面 可被未受过专业训练的普通用户使用 3 角色活动图方法r a d r o l ea c t i v i t yd i a g r a m r a d 从角色 目的和规则方面来描述过程 其主要特点是可以很好的描述活动之间的 关系 但r a d 只是静态的分析了活动间的相互关系 缺少动态的模拟能力 同时其在复 杂逻辑关系建模和对不确定信息建模方面也有一定的缺陷 4 数据流图方法d f d d a t af l o wd i a g r a m d f d 是一种结构化图示方法 是以一定格式的图形来描述和分析数据的运动 处理功 能和支持技术文件的相互作用 相互连续的流程图 其特点主要是 直观 简便 准确 具有很好地描述数据处理功能和数据运动特性 可以采用自顶向下 逐层分解的方法来描 述一个企业过程 着重于数据分析 5 p e t r i 网方法 p e t r i 网是一种图形化 数学化的建模方法 作为一种图形化工具 可以把p e t r i 网看 作与数据流图和网络相似的方法来描述系统模型 作为一种数学化工具 p e t r i 网可以建立 各种状态方程 代数方程和其它描述系统行为的数学模型 因此 它非常适合工作流的建 模 具体叙述如下 1 很强的表达能力 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 图形化表现基础上的形式化语意 p e t r i 网的形式化语义使得用p e t r i 网说明的工作流具有清晰准确的定义 不存在二义 性 可以成为互相交流的基础 也有利于推理 分析工作流的各种属性 3 丰富的分析技术 通过对p e t r i 网的研究 人们找到了许多基于p e t r i 网的分析技术 p e t r i 网建模的形式化 语义和丰富的分析技术为工作流模型的各种特性的分析提供了可能 这些分析技术可以用 来验证安全性 不变性 合理性以及死锁等属性 也可以用来计算各种性能参数如响应时 间 等待时间 评价执行时间和资源利用率等 用这些分析技术可以从多方面来评价工作 流 4 易于计算机化 p e t r i 网是一种独立于任何具体软件工具的建模和分析框架 是一种具有普遍适用性的 建模方法 它以较少的元素库所 变迁和连接弧实现了对复杂模型的建模 通过对托肯着 色 给变迁加上时间属性 容易实现对模型的控制流建模和模型的时间性能分析 通过层 次建模可以很容易实现面向对象的特性 因此 易于用计算机程序实现基于p e t r i 网的工作 流建模的工作流管理系统 5 具有良好的抽象性 一方面 工作流的控制流可以通过托肯着色和变迁点火条件等方法加以解决 能够将 控制流作为模型的一部分在建模过程中得以实现 这样 工作流的控制流和程序能够实现 分离 程序中不需要对控制流进行处理 有利于工作流结构的改变 另一方面 p e t r i 网能够 通过分层技术实现自顶向下的建模 可以实现子系统之间的复用 易于抽象分离子系统 使系统容易获得面向对象的特性 这些都使得基于p e t r i 网的工作流建模具有良好的抽象特 性 6 动态特性 因为p e t r i 网是基于状态的 这就使得过程定义具有更多的柔性特征 对于工作流管理 系统而言 具备一定的柔性是必不可少的 比如 能够动态地修改过程实例 可以实现与 其它工作流管理系统的交互 对异常情况做出响应 对于p e t r i 网而言 只需对网中的托肯 与点火做相应的处理 就能够比较容易地实现上述功能 7 可理解性 浙江理工大学硕士学位论文 p e t r i 网具有严密的数学背景 因此对于不了解p e t r i 网的人来讲 要想真正读懂p e t r i 网所表示的语义不是那么容易 表3 1 建模方法的综合比较 过程建模方法 d f d鼬m i d e f 系列 e p cp e t r i 网 对比 过程特点智能型智能型智能型跨职能跨职能 是否抽象机制无无有无有 可理解性 较好 需严密支持一般一般一般 计算机化能力可以可以可以较弱 可以 形式化能力弱弱弱强强 是否动态是否否是是 综合比较认为p e t r i 网除了可理解性比其它方法稍微逊色外 在其它方面都有较好的表 现 它在描述并发 冲突 同步等重要行为现象上所表现出的优势 以及具有形式化步骤 与数学图论相支持的理论严密性 特别是其图形表达的直观性和便于编程实现的技术特 点 适合工作流领域的建模需求 6 统一建模语言u m l u m l 活动图和状态图是可以用于描述工作流系统动态行为建模的两个图形工具 u m l 活动图实质上也是一种流程图 表现的是从活动到活动的控制流 它描述活动序列 并且 支持对并发行为和条件选择行为的表述 还支持职责分布和数据流描述 其特点主要是 图形化描述 支持信息流表示 丰富的表达能力 但不够细腻一般适合对高层业务流程的 描述 在业务流程重组 b p r 领域有着广泛应用 u m l 状态图可以细腻表述工作流系统状态 s t a t e 和变迁 t r a n s i t i o n 图形元素平行条 s y n c h r o n i z a t i o n 支持对并发行为的表述 u m l 状态图与p e t r i 图的差别主要在是否把变迁从 控制 流中分离出来 其实只要对状态图中变迁和平行条的语义稍作调整 给平行条赋予 变迁的语义 原变迁元素只保留控制语义 那么u m l 状态图从形式到语义就与p e t r i 图完全 一致了 因此本文认为 1 p e t r i 网的发展历史较u m l 悠久 u m l 无意去涵盖和取代p e t r i 网 尽管是完全可以的 例如对u m l 状态图中状态定义托肯或令牌之类也是轻而易举的事 2 把变迁从控制流中分离出来是否必要也不能一概而论 在许多简单的p e t r i 网中可以发 现独立出来的变迁的语义内涵很贫乏 对这种情况用p e t r i 网还不如用u m l 状态图 3 建立在坚实图论理论基础上的p e t r i 网应该擅长于对网结构和性能的解析 因此要开展 2 0 浙江理工大学硕七学位论文 解析工作最好还是应用p e t r i 网 3 2 基于p e t r i 的工作流建模 工作流管理联盟定义了一个描述工作流模型的模型 即工作流元模型 该模型描述了 工作流模型内在联系 可用于描述工作流模型内部包含的各个对象 对象之间的关系及对 象之间的属性 3 2 1 工作流元模型 工作流模型是对工作流的抽象表示 需要保证流程含义的正确 数据一致性和流程的 可靠性 建立的模型不仅有正确的含义 而且能提供一个由分析模型到投入实际实施模型 的转换接口 从而使该模型能够被企业应用的工作流管理系统执行 为此 工作流管理联 盟定义了描述工作流模型的模型 即工作流元模型 定义工作流模型首先需要对工作流程 进行定义 这个模型需要反映企业中业务过程的目的 完成这个业务需要哪些功能操作 过程的执行转换条件 即规定业务规则和操作的顺序 所需资源和相关数据 对于一个可 执行的工作流模型还需要指出该模型需要激活的应用程序 下图所示的过程定义元模型的组成核心是活动 工作流定义与活动 工作流相关数据 之间是一对多的关系 即一个工作流定义由多个活动与多个工作流相关数据组成 活动 资源 工作流相关数据 需要激活的应用程序 转换条件之间是多对多的关系 图3 1 过程定义元模型 此外 工作流实例需要某种启动条件才能够启动和终止 一般情况下称他们为启动活 动和结束活动 在工作流模型中 活动作为结点通过连接弧连接在一起 在这里解释成是 2 1 浙江理工大学硕士学位论文 对工作流活动转移的控制连接 通过控制连接可以定义活动执行的先后顺序 当需要决定 后继活动是否能执行 当一个活动后面有多个后继活动可以执行时 实际的路径选择就是 由活动开始条件 活动终止条件和转移条件三个附加的路径选择条件决定 这些条件可以决定如下图所示的路径选择 1 并分离 a n d s p l i t 如图3 2 a 当流程需要并行执行两个或多个活动时 一个控制 连接被分成两条或多条 2 并汇集 a n d j o i n 如图3 2 b 将多个并行执行的活动所发出的控制连接汇集成一条 3 或分离 o r s p l i t 如图3 2 c 当一个活动的后继活动需要通过路径转移条件来决定 应该执行哪条分支时 一个控制连接被分成几条需要选择的分支 4 或汇集 o r j o i n 如图3 2 d 当两个或多个活动物理连接或汇集到一个活动时 或 汇集被用来将这两个或多个活动汇集到一个活动上去 c o r s p l i t 移l 力 移2 砖 移n 移l 力 杉2 p 移n 岭 移 转移 一一搏强 国 a n d j o i n 图3 2 工作流的四种基本结构 3 2 2 元模型到基本p e t r i 网的映射 d o r j o i n 通过对控制连接 活动和四种选择结构建模就可以实现对工作流的建模要求 过程建 模如下 粤碰 浙江理工大学硕士学位论文 1 通过用变迁来表示活动 库所表示活动的开始状态和活动终止状态来建立工作流的 p e t r i 网模型 而且某个活动终止后的状态和另一个活动的开始条件是重合的 如图3 3 a 所示 2 对于过程的启动条件相连的活动 活动的开始状态也是过程的启动条件 用一个特别 的库所i 来表示 如图3 3 b 所示 3 对于过程的终止条件相连的活动 活动终止后的状态也是过程终止后的状态 用一个