（计算机应用技术专业论文）基于着色petri网的工作流系统性能评价研究.pdf

摘要 工作流技术是目前计算机应用领域的研究热点，在项目管理、制造领域以及业务流 程重组中有着广泛的应用。工作流就是工作流程的计算模型，即将工作流程中的工作如 何前后组织在一起的逻辑和规则在计算机中以恰当的模型进行表示并对其实施计算。 工作流模型应该完整、正确的反映工作流程，并支持模型验证和性能评价，使相关 人员能够基于模型对工作流系统结构和流程的正确性和主要性能指标有初步了解，并根 据分析结果在具体实施前进行系统的调整和改造，保证工作流系统成功运行。性能评价 的方法主要有模型分析和仿真两种。目前，对工作流系统研究主要集中在对具体应用的 建模以及建模仿真工具的研究方面，对性能评价的研究相对比较少。 本文以典型的工作流系统产品开发制造系统的工作流程作为参照实例，利用着 色p e t r i 网进行建模，并对模型验证与性能评价进行了系统的研究，针对模型分析方法 提出了建立在结构约简基础上的模型验证与性能分析方法。首先对结构约简方式进行改 进，在简化结构的同时保留模型原有的表达能力，使原本复杂的验证与分析过程变得相 对简单可行。并通过变迁的时间参数绑定，将广义随机p e 仃i 网的有关评价方法引入着 色工作流网，利用马尔可夫链对相关性能指标进行评价与定量分析，得出优化配置方案。 在对基于着色p 喇网建立的产品开发制造系统工作流模型进行仿真分析时，实现 了流程正确性和系统瓶颈的检测，并根据仿真结果提出产品开发制造流程的改进和优化 措施。 关键词：着色p “网，工作流，模型验证，性能评价 r e a r c ho np e r f o r m a n c ee v a l u a “o no fw o r k n o ws y s t e m b a s e do nc o l o 陀dp e t r in e t l i uz h i p e n g ( c o m p u 锨a p p l i c a t i 伽t e c l l l l o l 9 9 y ) d i 删b y p z h u l i 狮吐锄g a b s t l a c t w 6 r k n o wt ec _ h n o l o g yi sm er e s e a rc _ h 仃e n d si n 廿l e6 e l do fc o m p l u t e ra p p l i c a t i o n ，a n dt l a s b e e n 、) l ，i d e l y 印p l i e dt 0m 锄ya r e 嬲s u c h 粕p 删e c tm a n a g e m e n t 、m 锄u 州n gs y s t e m 觚d b u s i n e s sp r o c e s sr e e n 画n e c f i n g w 6 n m o wi sm em o d e io fw o r ：i ( i n gp r o c e s s i tr e p r e s e m sm e o 唱a i l i 砑t i o nl o g i c s 觚d “e so fw m k si i l 吐l ew o 她p r o c e s sp r o p e d yb ym o d e li i lc o m p u t 瓯 w 6 d m o wm o d e ls h o u l dr c j f i e c tm ew o r k i i l gp r o c e s sc c 唧【p l e t e l y 锄dc o r 把c t l y 髂w e l l 舔 p r o v i d es u p p o r tf 0 rm o d e lv 2 l l i 捌o n 趾dp e r f 0 n l l a n c ee v m 嘣o n l e tm er e l e v a n tp e o p l eg e t t 0k n o w 缸l ev a l i d i 哆锄dp c 缸0 m a n c eo f 吐l ew o r k n o ws y s t e mb yt l l ei n o d e l ，瓤dd 0 m o d i f i c a t i o nb e f 0 聆c o n c r c t ei m p l 锄1 e i 妇t i o nt 0e 璐u r e l es u c c e s s 如lo p e r a t i o no ft l l es y s t 锄 t h e 聆h 嬲抑oe v 面u a t i o nm e l d d so fp c 咖a 球冷：m o d c l 趾a l y z i i l g 锄ds i i l l u l a t i o n a t p r c s e n t ，s t u d i e s0 nw o r k n o ws y s t 锄a 聆栅l l l yc e 曲m i z e do n 舔p e c t so fm o d e l i n ga c c o r d i n g t 0s 】p e c i f i c 印p l i c a t i o na n di i n p r o v e m e n to fm o d e l i n gt o o l s ，p e r f 0 n i l a i l c ee v a l 嘶o nw 笛 f c 、e rs t i l d i e d t 1 1 i sp a p e rh 舾s y s t e m a t i c a l l yg n j d i e do nm o d c lv a l i 拙i o na n dp e 面r n l a n c ee v a l u a t i o n o fw o r | m o ws y s t e mb 勰e do nc o l o r e dp “瞅， a n dc h o o s i l l gat y p i c a lw o r k n o w s y s t e m - p r o d l l c tm i v e l o p m e n t 觚dm 鲫删k i 伽r es y s t 咖嬲a ne x 锄p l e am e m o do f m o d e l v a j i 眦i o n 觚dp e r f b n n 锄c ce v 甜u a d o ni sp r o p o s e da c c o r d i l l gt 0m o d e la n 尔y s i sm e t l l o d f i r 巩 i i i l p r o v cn l em o d co f 蛐r u c t u 坞r e d u 嫩o n ，s 证l p l i f i e dt l l e m o d e ls 饥l c t u r ea n dm e 鲫w l l i l e r e s e e dt l l ee x p r e s s i o na b i l 时o ft h em o d e l i i lt l l i sw a y ，t l l ec o n l p l e xp r o c e s s e so fv a l i d a t i o n 锄dc v 以僦i o nb e c o m es i m p l e 觚df c 硒i b l e a r l di i l 臼0 d u | t t l ee v a l u a t i o nm e t l l o do f 咖c h a s t i cp e t r in e tt 0c o l o r e dw f - n e t ，i m p l e i n e n tp e r f - 0 功：瑚n c ee v a l u a t i o n 跚dq 咖t i 僦v e a i l a l y s i so f 坞l 砷e dp e 柙d r m 觚c ei n d e x 骼b ym 酬k 0 vc h a i n ，锄dg i v e 廿l eo p t i m i z a t i o ns c h e m e b ys i m u l a t i o n 锄a l y s i so fw o r k f l o w m o d e lo ft i l ep r o d u c td e v e l o p m e n t 锄dm a n u f i a c 懈 s y s 钯mb 勰e d0 nc o l o r e dp e 仃in e t d e t e c t i o no fp m c c s sv a l i d i 够a n ds y 妣mb o t t l e n e c l 【sh 髂 b e e nr c a l i z e d a n dt h eo p t i m i z a t i o n 觚dm l p r o v e dn l e a s u 豫so fm ep r o c e s sa c c o r d i n gt 0 s i n l u l a t i o nr e s u n si sp 1 0 p o s e d k e y w o r d s ：c o l o r e dp e t r in c t ，w 甜阻o w m o d e lv a l i d a t i o n ，p e r f 0 鼬a n c ee v a l u 撕o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：边圭蝗 日期：矿年r 月7 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名j 主= i 盘园睦 指导教师签名；7 乐兰磊乙一 日甄；口笤年 是n 的有穷变迁集合；p 和t 称为p e 台i 网的库所集( p l a c es c t ) 和变迁集( b 如s i t i o ns e t ) ： 库所和变迁分别成为p 囊素和t 元素，或p _ 元和t 一- 元；x = p u t 成为p e t r i 网的元素 集；f 是由n 中的一个p 元素和一个t 元素组成的有序偶的集合，被称为流关系( f i o w r e l a t i o n ) 。 p n t = 乃表示p j 素与t 一元素是两类没有交集的元素；p u t 囝表示网中至少 要有一个元素。 为了方便表述，还需要定义库所或变迁的前集和后集。定义如下： 定义2 2 ；设x p u t x = yi ( y ，x ) f ，；x = yl ( x ，y ) f ) 那么，x 被称为x 的前集( 也称输入集) ，x 成为x 的后集( 也称输出集) 。 有向网通常用来描述静态p e t r i 网，静态p 硎网的一个典型事例如图2 1 ： 图2 1p e t r i 网示例图 f i 9 2 lt h e 锄m p l eo fp e t r in e 协 附注l ：t l 用粗线表示，代表瞬时变迁；t 2 用矩形表示，代表时间变迁。 8 中国石油大学( 华东) 硕士学位论文 定义2 3 一个六元组= ( p ，t ；f ，k ，w ，m o ) 是一个p 玎系统，当且仅当： 1 ) t f ) 是一个网，p 中元素代表位置，t 中元素代表变迁，f 为弧元素； 2 ) k ：p 哼n + u o o ) 是位置容量函数； 3 ) w ：f n + 为弧权函数； 4 ) m o ：p 寸n 是初始标识，且满足：v p p ：m o ( p ) k ( p ) ，当k ( p ) = 时，通常省 略k ( p ) 的标注。 定义2 4 ：变迁发生条件： 1 ) t = t u t 称为t 的外延； 2 ) t 有发生权的条件是：v p t ：m ( p ) w ( p ，t ) 八v p t ：m ( p ) + w ( p ，t ) sk ( p ) ，t 在 m 有发生权记作m 【t ，即t 在m 的授权下发生。 若t 在m 下启动，则启动后m 变为新标识m ，记为m 【t m ，m 被称为m 的后 继标识，对于v p p ，有： m ( p ) = m ( p ) 一w ( p ，t ) 当p t t m u ) = m ( p ) + w ( t ，p ) 当p t 一t m ( p ) = m ( p ) + w ( t ，p ) 一w ( p ，t ) 当p t n t m t ( p ) = m ( p ) 当p t u t 通常用p 厂r 系统表示具有动态特性的p e t r i 网，图2 2 是一个动态p e t r i 网实例： p l t lp 2 其动态特性描述如下： 图2 - 2 动态p e t r i 网示倒 f i 垂2 t h ed y n a m | co f p e t r in g 纽 9 第二章p 附i 网基础知识与理论 m o2 ( 2 ，o ，o ，0 ) w ( p l ，t 沪w 慨，t 3 ) = w ( t l ，p 3 ) 2 w ( t l ，p 2 产4 w ( t 2 ，p 4 ) = 3 初始状态时，库所p i 有两个托肯，令m o 【t i m l ，根据发生规则有m 。= ( o ，4 ，2 ，o ) ； m i 【t 2 m 2 ，则有m 2 = ( 0 ，4 ，o ，3 ) 。状态标识序列m o 、m l 、m 2 描述了托肯的转移过程， 非常直观易懂。 2 2 高级p 嘶网 经典p 耐网对托肯的表达涵义以及变迁的发生条件规定的非常简单，在应用到具 体实例中时会受到各个方面的限制【2 4 】，出于实际应用需求的考虑，人们在经典p e 仃i 网 中增加了时间和颜色元素，并发展出分层机制，下面分别从这三个方面进行说明。 2 2 1 时间p e t r i 网 早期的p 面网主要用于系统逻辑行为的描述和逻辑性质的研究，即系统定性时态性 质的研究并未引入显式时间的概念。但是，人们在分析动态系统时不仅关心系统的定性 时态性质，还关心系统的定量时态性质，如系统与时间有关的各项性能指标，包括系统 的信息流通率及信息传输的平均时延等。因此，在7 0 年代后期，许多学者将显式时间引 入p e t r i 网，这类p e t r i 网被称为时间p e t r i 网( 1 p 。当引入的时间为随机变量时，时间 p 硎网就成为随机p e t r i 网( s p n ，s t 0 h 出挝i cp 耐n e t ) ，又可分为时间连续p 谢网和时问 离散p e t r i 网【2 卯。 定义2 5 ：时间连续p e t r i 网被定义为s p n = ( p ，t ，f ，w ，m o ，k ) 。其中p 为位置，t 为转移，f 为输入、输出有向弧，w 为权函数，m o 为初始标识，k = k 。，k ：，k m 是 各个转移的发生率( 转移平均点火速率) 。各个转移的发生时间( 点火延时) 服从负指数分 布。 定义2 6 ：时间离散随机p e t r i 网被定义为s p n = ( p ，t ，f ，w ，m o ，q ) ，其中p 、t 、f 、 w 、m o 的含义同上；q = q 。，q ：，q 。 是各个转移在下一采样时刻发生的条件概率( 假 设其他转移不发生) ，转移的发生时间服从几何分布。 1 0 中国石油大学( 华东) 硕士学位论文 s p n 模型继承了p e t r i 网的描述能力，由于它和马尔可夫过程同构，可以借助马尔可 夫链的有关理论分析系统的性能指标，如：每个可达标识的稳定概率、在每个标识m i 中的逗留时间、标记概率密度函数、在一个位置中的平均托肯数、每个转移的利用率、 系统的平均延时时间、吞吐量等参数，扩展了p “网的分析能力【2 们。 2 2 2 分层p e t r i 网 利用经典p e t r i 网得到的模型虽然能够语义明确地反映了业务流程，但往往由于实 际的企业业务工作流是复杂交联的，对于设计者而言，一次性的建立整个工作流模型过 于复杂和庞大，即使能够建立出模型，用户也无法清楚的看清它的结构关系，无法观察 到p 嘶网建模的过程层次结构。将流程进行层次扩展符合人类的思维模式，可以帮助 克服上述缺陷。 在层次p 确网中，每一个结点不再是一个原子结点，可能其中的某一个结点代表 着一个子网，这个子网也是一个带有库所、变迁、更深层次子网的p “网。在层次p e t r i 网中引入网模块( n e tm o d u l e ) 和模块变迁( m o d u l e 仃a i l s i t i o n ) 的概念【2 7 】：模块变迁是网 模块的抽象，标识低一级层次的网模块；网模块是模块变迁的细化；任务可以视为不可 细化的原子模块变迁。 在利用层次p 嘶网进行工作流设计时，可以首先描述出一个整体轮廓模型，其中 可以细化的变迁使用模块变迁标识，再对模块变迁细化生成低一级的网模块，在低一级 的网模块中还可以再包含更低一级的模块变迁，层层细化，从理论上来说，层次工作流 模型的层次数目是不受限制的。但实际操作时，并非越多越好，过多的层次也会增加用 户使用的复杂度。这种方法类似于软件工程中自顶向下( 伯p d o w n ) 的设计方法。 还有一种自底而上( d o 、 | r 1 1 1 o p ) 的方法是首先从最底层开始描述基本组件，再将这些 组件组合成为过程，若干子过程还可以组合成更大的过程，最终得到过程的详尽描述。 2 2 3 着色p e 仃i 网 着色p 确网( c o l o r c dp “n e t ，c 踟的概念是由丹麦学者k 陬j e n s e n 首先提出的 网。是高级p e t r i 网中应用最为广泛的模型语言，也叫颜色p 硎网或有色p 硎网，它 把p 硎网的图形表示和编程语言相结合，降低了模型复杂度，提高了灵活性。 不同于一般p e 仃i 网仅有一种标记阳k e n ) 并通过一个整数来描述位置的状态，c p n 的每个标记被附加上一个称为标记颜色的数据值。在c p n 中对给定的位置，所有标记 必须拥有同属于某一特定类型的标记颜色，所有这些类型构成位置的颜色集。c p n 中 第二章p e t r i 网基础知识与理论 的每条弧都有一个弧表达式( a r c i r 毽c r i p t i o n ) ，定义各条弧上可通过的标记类型和通过条 件。类似地，变迁也有一个守卫( 函数，包含各个变迁的可实施条件，守卫函数在 缺省状态下为空，意味着变迁的实施没有特殊条件。因此，变迁是否使能不仅依赖于输 入位置中的标记变量，也决定于弧表达式和守卫函数。 着色p e t r i 网的形式化定义如下【2 9 】： 定义2 7 一个着色p e 仃i 网是一个多元组c p n = ( ，p ，t a ，n ，c ，g ，e ，i ) ，其中： 1 ) 是类型( c ) ，p e s ) 的非空有限集，也称为颜色集( c o l o r 蛐) ； 2 ) p p 。，p 2 ，p m ) 是库所q i a c e s ) 的有限集，m 表示系统中库所的数目； 3 ) t 三 t l ，t 2 ，t 。) 是变迁i t i o 衄) 的有限集，n 表示系统中变迁的数目； 4 ) a 是弧( a r c s ) 的有限集，满足p n t = p na = i t n a - 囝； 5 ) n 是结点( n o d e ) 函数，定义为n ：a p t u t p ； 6 ) c 是颜色( c o l o r ) 函数，定义为c ：p 一； 7 ) g 是守卫( 删) 函数，也可以称为变迁表达式函数，定义为g ：t 专e x p f e s s i o 璐， 满足：v t t ：【t y p e ( g ( t ) ) = b a t y p e ( v 孤( g ( t ) ) ) sz 】。其中，聊e ( v ) 表示变量的类型竹 p co fav 撕a b l e ) ，畎e x p r ) 表示表达式e x p r 的变量集。 8 ) e 为弧表达式( a r ce x p r e s s i o n ) 函数，定义为e ：a _ e x p r e s s i o 粥，满足： v a a ：【聊e ( e ( a ) ) = c ( p ) 人聊e ( ( e ( a ) ) ) 冬】。其中，p 为n ( a ) 中的位置，c ( p ) m 表示居于c 之上的所有多重集的集合。 9 ) i 是初始化( i n i t i a l i z a t i o n ) 函数，定义为i ：p c l o s e d e x p r e s s i o 地，满足 v p p ：【t y p e ( i ( p ) ) = c ( p ) m s 】 其中，弧的颜色集决定了c p n 中标记的类型，颜色函数c 把每个库所都映射到一 个颜色集c ，即p 中的每个标记都属于颜色类型c ( 1 ) ) 。守卫函数g 把每个变迁t 都 映射到一个布尔表达式b ，并且g ( t ) 中所有变量的类型必须包含于颜色集中。当采用 形式为【e x p r l ，e x p r 2 ，e x p m 】的布尔表达式表示守卫函数时，意味着 e x 矿l n e x p r 2 n n e x p m 。当变迁上的守卫函数值恒为真时，缺省表示。弧表达式函 1 2 中国石油大学( 华东) 硕士学位论文 数e 把每一条弧a 都映射到一个类型为( p ( a ) ) m s 的表达式，表示e ( a ) 的每次求值都生成 一个依赖于相邻库所颜色集的多重集合，通常弧表达式不能缺省。初始化函数i 把每个 位置p 映射为不包含变量的表达式，其类型为c ( p ) m ，初始化表达式的类型也可为空。 下面是着色p 砌网中涉及到的几个概念： 定义2 8 变迁的绑定( b i n d i n go f 缸锄s i t i o nt ) ：变迁t 的一个绑定是定义在、协( t ) 之 上的一个函数b ，满足： 1 ) v v v a r ( t ) ：b ( v ) t y p e ( v ) ； 2 ) g ( t ) 。 即指定每个类型的颜色，并使绑定b 中的守卫表达式g ( t ) 的值为真。变迁t 的所有 绑定的集合用b ( t ) 表示。直观上，变迁t 的绑定是一种取代。用颜色代替t 的每个变量。 要求每个颜色拥有正确的类型，守卫函数求值结果为真。 定义2 ，9 标记元素( t o k e ne l e m e n t ) ：一个标记元素是指元素序偶p a i r ( p ，c ) ，其中 p p ，c c ( p ) ，所有标记元素的集合表示为t e 。 定义2 1 0 绑定元素( b i n d i n ge l e m e n t ) ：一个绑定元素是指元素序偶p a i r ( t ，b ) ，其中 t t ，b b ( t ) ，所有绑定元素的集合表示为b e 。 定义2 1 l 状态标识( 础m ( i i l d ：一个状态标识是当步骤( s t 印) 为非空时，定义在t e 上的一个多元集，也是b e 上的一个多元集。其中，初始状态标识m o 是通过求解初始 化表达式而得到的一个状态标识：v ( p ，c ) t e ：m 。( p ，c ) = ( i ( p 以c ) 。所有状态标识和步 骤( s t c p ) 的集合分别用m 和y 表示。 定义2 1 2 使能步( e n a b l e ds t e p ) ：当满足v p p ：e ( p ，t ) m ( p ) 时，称与状态 标识m 相关的步( s t e p ) y 是使能的。 当对应状态标识m l 存在使能步时，它可以实旌，从而将状态标识m l 转化为另一 个状态标识m 2 ，满足： v p p ：m 2 ( p ) = ( m 1 ( p ) 一e ( p ，t ) ) + e ( t ，p ) 。 ( t b ) e y( t b ) e y 如果m 2 从m l 直接可达，则记为：m l 【y m 2 。 c p n 模型的构建可以与时间相关，也可以与时间无关。非时间c p n 模型通常用于 1 3 第一ip e 目基础知m 与m 论 验证一个系统的功能或逻辑正确性，而时间c p n 模型则主要用于系统性能的评价。有 许多其他的模型语言可用来系统的功能或逻辑正确性，或者进行系统性能评价，然而， 很少有模型语言能够同时适于两方面的研究。同时，c p n 有比较正式的形式化定义及 其解释，还包括一系列动态行为属性。c p nt o o l s 作为c p n 的一种描述和分析工具 能够方便地描述和分析c p n ，并用于系统模拟和状态空间分析统计结果的生成。 2 3 着色p e 啊网的分层结构 分层着色p e 廿i 网( h i e i a r _ 咖c mc p n 妒。1 是将分层机制融入着色p 出i 网，它由若干页 ( 也称为模块) 组成，每页都包含由若干位置、变迁和弧组成的网络。如同高级程序语言 一样，模块之间通过定义良好的接口来交互操作，其图形化表示使得很容易明白复杂c p n 模型的基本结构，利于复杂系统建模与分析。分层着色p e 啊网在实际的应用中有2 种分层方式：一种是以变迁为核心的分层方式叫变迁替代( s u b n h t i o n1 协s i t i o n ) i 另一 种是以库所为核心的分层方式叫库所联合( f 岫i o n 升a c c s ) 。 23 1 变迁替代 变迁替代允许用户将变迁同其周围的库所和相关弧关联起来，形成独立的c p n 子 网，以便给出同那个变迁相关行为的更详细描述。替代变迁称为顶层节点或超节点( s u p 盯n o d e ) 拥有变迁替代的c p n 网称为顶层页或超页( s “p e p a g e ) ，同替代变迁相连接 的c p n 子网称为分页( s u b p a g e ) 。通过使用替代变迁，可在超页级隐藏替代变迁行为的 复杂描述这使我们能更为灵活的得到一个复杂c p n 的概要。 匾牙运蔓匾哥包。 图2 d 分层着色p 曲1 网的顶层页面圈 n 9 2 - 3t b e s 叩e p p l 俨o f h k 憎仲h i 姐l c p n 中国石油大学( 华束) 磺学位论立 圈2 一瞢代变迁s e m 子页 n 9 2 _ 4t h e s u b _ h g e o f s u h n h t l o n l h n s i 咖ns r 图2 _ 3 、2 4 在c p nt o o l s 中展示了分层c p n 的一个简单例子。图中库所和变迁的 名字可以清楚的表示其行为。替代变迁被两个矩形框来表示，其下浅蓝色文本为分层说 明，指明与超节点相关子页的名字。在例子中可以看到变迁s e e r 有一个同名分页( 图 2 4 ) ，每个分页都有许多标以i n 、0 u t 或u 0 标志的位置，这些位置即称为端口结点( p o n n o d c ) ，它们是分页与其他分页之间相互通信的接口。i n 对应输入端口，负责从周围分 页中接收标记。同理0 u t 端口是向周围分页输送标记的输出端口，有u o 标记的位置可 同时作为输入和输出端口。在图2 4 中的端口结点q u c u e 和c o m p l d e d 分别被作为输入 和输出端口。 在图2 3 中，还给出了c p n 中所用到的颜色集，也就是数据类型。一般地，c p n 模型中的各个标记和表达式通过称之为“颜色”的这种数据类型来加以区分，而经典 p e 订i 网的标记是不可区分的，没有数据类型的概念，一律标记为“黑色”的。c p n 的 颜色类型可复杂化，每个域对应不同数据类型，例如图2 - 4 中的记录( r v e f - j o b ) ，其 中s e r v 盯是s e r v e r 类型，而i o b 则是j o b 类型。因此，颜色集是颜色的闭集，而不是 诸如红、绿、蓝等颜色的离散值。 232 库所联合 库所联合的目的是指出被认为是相同的库所集合中的各个库所，即某些库所虽然被 分别独立的描述，但是它们表示的含义相同。如果集台中某个库所增加或减少某一标记， 则集合中的其他库所也增加或减少同样的标记。库所联合可能处于单独页或不同页。当 库所联合集中所有成员同属于一页，并且该页只包含一个页实例时，库所联合只不过是 提供了一种构造上的便利，避免使用过多的交叉弧。然而，当库所联合集的成员分属于 不同页或者同属于一个包含多个不同实例的页时，库所联合集允许指定行为方式，如果 第二章p 嘶j 网基础知识与理论 没有库所联合集，这种行为将可能导致麻烦。 2 4 工具软件c p nt 0 0 l s 简介 c p nt 0 0 l s 【3 1 】是一种用于着色p e 仃i 网建模、模拟和分析的工具。它能够提供与环 境相关的信息反馈，指出网中各元素之间的依赖关系。能够在构建过程中进行语法检查 以及代码生成，快速仿真模拟器能够有效处理非时间和时间关联的着色p 硎网。c p n t o o l s 工具还能够自动地生成并分析完全的和部分的状态空间【3 2 】，生成的标准状态空间 报告包含有界性、活属性等动态属性信息。 在c p nt 0 0 l s 中编辑着色p e t r i 网，经常有多种方式来执行同一特殊任务，因而显 容易、快捷并且灵活。c p nt 0 0 l s 可以以多种方式协助用户，例如：提供多种关于网的 语法和工具状态的图形反馈，自动对准绘制各个项目对象。菜单中的工具能够应用于单 个变迁或者是某个页，如果相关的页包含多个使能变迁，则从中随机选择一个变迁进行 实施。c p nt 0 0 l s 工具仿真运行机理在于基于网结构和文本表达式将网编译成机器语言 ( m a c t l i n el 觚图均g e ) 代码，这样，在编辑时就可以随时校验在运行过程中可能会导致语 法和运行时错误。对于分层c p n ，如果错误不是出现在顶层页中，则会在任何有错误 的页面标签上显示出提示出错的标识。 通过c p n1 砷l s 工具来进行状态空间分析，可以有两种模式：交互模式( 砷e m c t i v e m o d e ) 和自动模式o m o m a t i cm o d e ) 。在交互模式下，用户指定一个状态，c p nt 0 0 l s 计算该状态的使能绑定元素，根据每个使能绑定元素的实施状况来生成其后继状态。交 互模式主要应用于绘制部分状态空间，其原理类似于单步调试。 在大多数情形，交互模式不能生成比较完整的状态空间，但自动模式不同，自动模 式可以生成完整的状态空间，用户还可以通过停止选项( s t o p 叫i o n s ) 和分支选项( b 砌c i l i n go p t i o 璐) 来对自动生成过程进行控制【3 3 】。停止选项允许用户指定条件，来控制状态 空间计算应该在哪里停止，例如指定应该生成的结点数目的上界。分支选项让用户可以 局部地控制后继状态的生成，仅仅指定应该生成的结点后继状态的某一个子网。停止和 分支选项使得获取部分状态空间结果成为可能。 2 5 小结 本章首先从p e t r i 网的产生与发展、定义、类型等几个方面系统介绍了p c t r i 网及其 扩展网的有关知识和基本理论，并在此基础上着重对着色p 钉i 网及其分层机制做了阐 述。其次对建模工具c p nt 0 0 l s 的特点及应用做了详细的介绍与分析，为后面的建模、 1 6 中国石油大学( 华东) 硕士学位论文 验证与性能分析工作提供了坚实的理论基础。 1 7 第三章基于着色p c t r i 网的工作流系统建模 第三章基于着色p e t ri 网的工作流系统建模 工作流管理联盟定义了一个描述工作流模型的模型，即工作流元模型【3 4 1 ，该元模型 描述了工作流模型内在联系，可用于描述工作流模型内部包含的各个对象、对象之间的 关系及对象的属性。在本节中我们将使用着色p 砌建立工作流模型。 3 1 工作流基础知识 3 1 1 相关概念 w f m c 给出的工作流及相关定义如下【3 5 1 ： 定义3 1 工作流：工作流是一类能够完全或者部分自动执行的经营过程，它根据一 系列过程规则、文档、信息或任务能够在不同的执行者之间进行传递与执行。 从上述定义可知工作流的3 个要点： 1 ) 有多个参与者。 2 ) 按照一定的规则进行活动( 传递文档、信息、任务等) 。 3 ) 活动的推进是自动的或部分自动的。 定义3 2 业务流程( b 瑚i 鹏s sp r o c e s s ) ：业务流程是指在功能确定的组织结构中，能 够实现业务目标和策略的相互连接的过程和活动集。 定义3 3 活动( a c t i v 时) ：活动是工作流中的一个逻辑步骤或称环节。包括开始和结 束条件、可参与到此环节中的用户、完成此活动所需的应用程序和数据以及关于此活动 应如何完成的一些限制条件等信息。 定义3 4 过程定义( p r o c e s sd e f i l l i t i o n ) ：业务过程的计算机形式表示，定义过程运行 中的各种参数，如业务过程的开始和终止条件、各个工作环节及相互之间的控制流动与 数据流动关系等。 定义3 5 过程活动实例( p r o c e s s ，a c t i v 埘i l l ：睫a n c e s ) ：指某个工作流过程的一次具体 执行。工作流管理系统解释相应的过程定义，生成有关的活动并根据过程定义中的控制 规则协调这些活动实例之间的顺序关系，同时根据预定义的数据流动关系完成活动实例 间的数据传送。 通常情况下，活动实例表现为工作项，它由某个或某组用户负责完成，其负责的所 有工作项将构成其工作项列表。从用户的角度来看，实例的执行实际上是由用户调用相 应程序对他所涉及的那个环节有关的数据进行处理，处理完成后由工作流管理系统根据 相应的结果激活后续环节并生成相应的工作项，并通知相关用户，直至整个过程的完成。 中国石油大学( 华东) 硕士学位论文 3 1 2 基本构造 定义工作流模型首先需要对工作流程进行定义，模型中需要反映出业务过程的目 的、所需的功能操作、过程的执行转换条件( 即业务规则和操作顺序) 、所需资源和相关 数据，对于一个可以执行的工作流模型来说，还需要指出该模型需要激活因素。如图 3 一l 所示【3 6 】： 图3 l 工作流过程定义 m 9 3 一l t h ed e 行n i 廿o no f w o r k n 仃p i 心c 黜s 一个工作流定义由多个活动与相关数据组成。活动、资源、工作流相关数据、激活 因素之间是多对多的对应关系。活动是模型的组成核心，活动可以细分为自动活动和手 工活动，由工作流流程通过程序调用或消息触发机制完成的活动被成为自动活动；由人 工输入或工作流系统以外的外界活动触发完成的活动被称为手工活动。活动作为结点通 过弧( 也称控制连接) 进行连接，在工作流网中不允许有孤立的活动。通过弧可以定义活 动执行的顺序：例如，有从结点a 到结点b 的连接弧，则a 必须在b 开始之前启动完 成。一个活动可以受多个其他活动的制约。 一个工作流实例必须符合特定的条件才能启动和终止，符合这种条件的活动称之为 启动活动和终止活动。因此，一个工作流可以视为由启动活动、终止活动和分解完成工 作流任务的其他活动组成的活动序列。 当一个活动后面有多个后继活动可以执行时，实际的路径选择就要由活动开始条 件、活动终止条件和转移条件等三个附加的路径选择条件决定。其中，活动开始条件、 活动终止条件是每个活动都具有的，转移条件与控制连接相关联。 活动开始条件根据输入数据的状态决定该活动是立即执行、延迟执行( 进入等待状 态) ，还是跳过( 如由于某种原因被意外终止) 。 1 9 第三章基于着色p e t r i 网的工作流系统建模 活动终止条件用于在执行过程中检查退出条件的值，为假则继续执行；为真时退出 执行。 转移条件与每一个控制连接相联系，它检查前面执行活动的输出数据并判断选择路 径、是否可执行状态和数据再传递给该路径上活动的开始条件，只有对与某个活动相连 的所有控制连接的转移条件为真时，该活动方可启动。 通过活动、活动的启动和终止条件、控制连接的条件，可以构成工作流元模型四种 不同的选择结构： 或分离或汇集并分离并汇集 图3 2 工作流基本路径结构 f i 9 3 - 2 t h eb a s t cs t 加c t l l 他o f w o r 如o w 3 2 基本工作流网 3 2 1 工作流元模型到基本p e t r i 网的映射 利用上述四种基本路径结构结合启动活动和终止活动，就可以构建完整的工作流模 型，所有的工作流模型都可以用以下几种基本结构来表示【3 7 】： 顺序结构 条件结构 并行结构 循环结构 图3 3 工作流模型基本结构 f i 9 3 3 t h eb a s i co t m c t i l 心o fw b r k n o wm o d e i 基于工作流基本结构定义可以构造p e t r i 网的工作流模型，也称工作流网。由变迁 中国石油大学( 华东) 硕士学位论文 表示活动，库所表示活动的开始、执行和终止状态，托肯表示示例来建立工作流的p e t f i 网模型。图3 4 是工作流的基本结构与对应的p e t r i 网模型： 并分离映射 井汇集映射 图3 4 工作流元模型到p e t r i 网的定义 f i 9 3 - 4t h e m p p i 醒f m m w o r 如呷m e t a m o d e i t op e 们n e 侮 通过上述映射可将、肝m c 定义的工作流映射为p e t r i 网，被成为工作流网( w f n e t ， w 砌o wn 鳓。工作流网定义如下： 定义3 6 ：p “网w = ( p ，t ；f ) 是工作流网，当且仅当： 1 ) p 、t 、f 符合p e t r i 网定义； w 中存在2 个特殊的库所：输入库所i ，i 劫，库所。是输出库所，o = 0 ； 3 ) 为使工作流模型是一个具有连续输入的模型并方便问题的求解，在映射后的 网中，在库所。和i 之间增加一个变迁t 即t ，= i 并且t 7 = o ) ) ，最终得到一个强连通 的p e t r i 网。 3 2 2 资源建模 上述过程建模体现了工作流网的任务逻辑，在工作流中还有另外一种体现组织结构 及其关系的组织逻辑，组织逻辑资源是任务的执行实体，资源建模是对资源信息的静态 管理，是工作流运行过程中资源分配的基础。对资源属性的分析，有利于对资源建模。 在产品开发过程模型中，需要指出什么任务需要什么资源( 资源组合) 去完成。因而需要 对资源进行形式化描述。在有色p e 仃i 网中，可以用不同的颜色集合来表示。资源的比 较典型形式化描述表示为： t y p er 气i d ，n 锄e ，c a 讲i o n ，f e a n 鹏，s t a t e ，d e s “p t i o n ) 其中：i d 是资源的标识号；n a n l e 是资源的名称；c a p t i o n 是资源的能力，是该资 2 l 第三章基于着色p c t r i 网的工作流系统建模 源可以实现的功能描述：s t a ：t e 是资源所处的状态，即是否可用等；f e a n 玳是资源的使 用特征，如可重用性、共享性等；d e r i p t i o n 是对资源的备注描述。 以上的例子中，资源描述形式属于比较复杂，在实际应用中可以进行必要的简化， 如直接简化为资源凡，r 2 ，r 3 ，简化方法视具体需要而定。 不同的资源可以进行组合，在有色p e t r i 网中利用多元集合表示。例如：任务t a s k 需要3 个资源r l 和2 个资源r 2 才能完成，其资源组合可以表示为3 r l + 2 r 2 。 在资源的分配和使用方面，采用简化的资源管理器方式。当接到资源需求申请时， 如果资源管理器中有相应的资源就分配给该任务，如果没有该资源或者没有足够的该类 资源，该任务只能等待其他的任务执行完毕释放资源后才可以执行。 严格来说，时间也应视为一种资源，但显然时间资源具有特殊性，不能作为一种独 立的资源和其它资源一样进行分配，在建模与仿真过程中，通过变迁绑定的方式来实现 时间资源的分配。 3 2 3 工作流网的触发机制 工作流网对活动的使能状态与执行状态做了明确的区分。令被使能的活动被执行的 外部条件称为触发机制。触发机制通常被分为四种： 1 ) 自动触发：活动在被使能的同时就被触发。这种机制一般用于那些通过应用 程序来自动执行、不需要与人进行交互的自动型活动，在触发的同时就开始执行。 2 ) 人工触发：由执行者从工作流任务管理器提供的工作流任务表中选择工作项 来触发活动。在工作流系统中，每个执行者都有自己的工作流任务表，表中列出了该执 行者可以执行( 已被使能) 的活动实例。当执行者选中某一工作项执行时，活动就被触发。 3 ) 消息触发：由系统外部的消息( 事件) 来触发活动的执行。 4 ) 时间触发：由定时器来触发使能的活动。这种机制适用于那些需要在特定时 间或给定的时间间隔内执行的活动。例如银行的结算业务必须在下午4 点3 0 分进行。 在工作流网中，每个活动( 变迁) 的上方，都标有相应的触发标记，以指明该活动是 通过哪种触发机制来执行的。