基于着色Petri网的工作流模型研究与应用

高德平, 周国祥

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)

工作流技术起源于20世纪70年代的“办公自动化”和“任务批处理”思想,但受当时计算机技术和网络技术发展水平的制约,一直未有较大的发展[1,2]。直至90年代,随着计算机技术的迅速发展,制约工作流技术发展的技术枷锁逐渐被打破,同时伴随着经济的发展,原有的信息管理系统已经不能满足企业的需要,人们迫切需要开发出的系统能够迅速地反应需求的变化,这也直接促进了工作流管理系统(WfMS)的发展,目前已经有许 多 WfMS,如 Action Workflow、Visual Workflo和 Flow Mark等。工作流管理的主要目标是:通过调用有关的信息资源与人力资源来协调业务过程中的各个环节,使之按照一定的顺序依次执行,从而实现业务过程的自动化[1,3]。

1993年成立的工作流管理联盟(Workflow Management Coalition,简称WfMC)给出了工作流和工作流管理系统的定义:①工作流是一个业务过程全部或部分地用计算机自动执行。②工作流管理系统是一个完全定义、管理和执行工作流的系统,它通过计算机表示的工作流逻辑来驱动软件的有序执行。

1 工作流建模技术

1.1 工作流技术简述

目前,工作流建模技术方面还处于百家争鸣时代,并没有统一的标准。比较流行的几种建模方法为:基于描述语言、基于图和网的方法(如有向图和 Petri-Nets)以及基于规则的方法等形式[2,3]。

在众多的工作流建模方法中,Petri网是一种比较有应用前景的技术。经典Petri网是在20世纪60年代由德国学者C.A.Petri提出,它是一种由库所(Place)和变迁(Transition)2种元素构成的有向图。它具有图形化表达的形式化语义、基于状态的流程描述方式和丰富的模型分析方法等优点,同时它可以方便地通过计算机表示,在工作流建模中有着先天的优势[4,5]。此外,Petri网具有很多扩展的高级Petri网(如时间Petri网、着色Petri网和层次Petri网等),它们非常适合用于描述和分析复杂的过程,是当前工作流建模技术研究的热点。

1.2 工作流网的结构

通过对企业流程的分析,总结出企业的流程可以归纳为4类,分别为:串行、并行、选择和循环。工作流网络应该能准确描述这4类流程,即工作流网的路由结构主要有:串行结构、并行结构、选择结构和循环结构[6],如图1所示。

图1 工作流网的4种路由结构

(1)串行结构。各个变迁按照顺序串行执行的流程,如图1a所示。

(2)并行结构。变迁B、C可以同时执行,且执行的顺序不受限制的流程,如图1b所示。

(3)选择结构。在某个流程中,变迁B、C执行一个即可,如图1c所示。

(4)循环结构。某些变迁B、C需要反复执行多次的流程,如图1d所示。

2 基于着色Petri网的工作流网模型

在基于Petri网的工作流建模中,常存在着托肯语义的不确定性和网络冲突等问题,着色Petri网能够较好地克服这些问题,本文将对Petri网进行颜色扩展,并在着色Petri网的基础上设计着色工作流网(CWF-nets)模型。

2.1 着色Petri网的定义

经典Petri网在工作流建模领域中有着巨大的优势,它可以用计算机进行形式化表示,同时又具有丰富的数学基础和模型分析方法,这使其在工作流模型的分析设计中有着广泛的应用。

着色Petri网对经典Petri网的扩展主要体现在增加了托肯颜色、弧表达式函数和守卫函数3个方面。它对托肯进行着色以达到客服经典Petri网的二义性问题,具体是利用着色托肯来解决不同托肯案例的不同处理,而弧表达式函数和守卫函数则控制着色托肯在工作流网中的路由。其定义如下:

定义1 着色Petri网(CPN)是一个多元组CPN=(Σ,P,T,A,C,G,E,I),其中Σ为颜色集;P为库所;T为变迁;A是有向弧集合;C为着色函数;G为守卫函数;E为弧表达式函数;I是初始化函数,具体定义见文献[7]。

2.2 CWF-nets的定义

着色工作流网 CWF-nets是一个 8元组:CWF-nets=(Σ,P,T,F,G,B,K,W),其详细定义见参考文献[8,9]。CWF-nets是以CPN为基础来建立工作流网模型,通过CPN对Petri网的扩展来加强模型的描述能力,主要体现在颜色扩展、增加弧表达式函数和守卫函数3个方面。对库所中的资源进行着色,使不同颜色的托肯得到不同的处理,解决了普通工作流网中的路由冲突问题;利用增加的弧表达式函数和守卫函数来精确控制着色托肯的流向。

CWF-nets使得模型的描述能力和对数据流的控制能力得到了较大的提高,适合于描述较为复杂的系统,本文将通过实例介绍CWF-nets。

2.3 正确性分析

定理 正确的CWF-nets应该保证起点库所中的每一个案例托肯经过传递能够流动到一个终点库所,而且与冲突消解方式无关[8]。

如果一个CWF-nets是正确的,则无论在任何情况下,案例托肯都能顺利地处理完毕,流到结束库所,不会在流程中发生丢失或停滞的情况。当一个案例托肯在CWF-nets发生流转时,它所经过的一系列的变迁即为一个变迁序列,若某变迁序列L不是其他变迁序列的前缀,则称L为极大变迁序列。假设CWF-nets的初始库所为MPS,终点库所为 MPE,若CWF-nets是正确的,则任何一个变迁T都属于一个极大变迁序列中,并且存在一个极大变迁序列L,使得:MPS[L＞MPE。关于工作流模型的分析可参考文献[10,11]。

3 实例与分析

3.1 实 例

目前,工作流技术正在逐步应用于企业的关键业务中,如企业的财务和人力资源管理等。在此,采用着色Petri网,对财务管理中的项目金额申报流程进行抽象并建立着色 Petri网模型,如图2所示。

该流程描述信息如下:通常企业内部会对不同金额的项目采用不同的处理过程,因此将企业内部项目金额申报处理流程设计为2类:一般项目和重大项目的申报处理。对一般项目的处理步骤为:调研项目信息—项目金额申报—部门审核—信息整理;对重大项目的处理步骤为:调研项目信息—项目金额申报—部门审核—领导审核—信息整理;在建立的着色工作流网模型中,采用库所来表示状态信息,变迁表示处理步骤。

图2 项目金额申报的着色Petri网模型

对库所进行标记,以确定其意义。PS为起始库所;P1为调研项目信息完毕;P2为项目金额申报完毕;P3为部门审核完毕;P4为部门审核完毕;P5为领导审核完毕;PE为结束库所;R为资源库所。对变迁进行标记,以确定其意义。T1为调研项目信息;T2为项目金额申报;T3为部门审核;T4为领导审核;T5为信息整理。(注:针对一般项目和重大项目,P3和P4为2个不同的状态)。

图2中定义了颜色集:Color T=N|I;Color U=E|D|L。其中,T表示项目类型;N为一般项目;I为重大项目;U表示人员;E为普通员工;D为部门负责人;L为领导。该模型的初始状态为2′E+1′D+1′L 和1′N+1′I,表示此时的“资源”有2名普通员工、1名部门负责人和1名领导,而“任务”有一般项目和重大项目各1个。在各库所附近有颜色集标记T或U,即对该库所进行颜色标记,表示流经该库所的托肯只能为属于对应的颜色集。

此外,还定义了弧表达式函数,如有向弧(R,T1),(T3,P4)等,表示对不同颜色的托肯执行不同的处理。以(R,T1)为例,case x of:N:1′E,I:2′E,代表如果处理1个一般项目,则只需要启用1名普通员工,而处理1个重大项目,则需要启用2名员工。同时,变迁T4附近的[x=I]为守卫函数,表示只有守卫函数的值为“True”,变迁才可以执行,即T4变迁只处理重大项目。

整个着色工作流网模型描述了一个完整的项目金额申报流程,对不同类型的项目采用不同的处理,且明确了资源的占用情况,为企业建立财务相关的工作流管理系统提供了技术支持。

3.2 分 析

采用本文所述的方法简要分析该模型,模型中的极大变迁序列L1:T1→T2→T3→T4→T5和L2:T1→T2→T3→T5。对重大项目,托肯从初始库所PS经过极大变迁序列L1最终到达终点库所PE;对一般项目,托肯从初始库所PS经过极大变迁序列L2最终到达终点库所PE,该模型中没有不可达库所或者死锁。

4 结束语

在众多工作流建模方法中,基于Petri网的工作流建模是一种有巨大优势的建模方式。Petri网具有严密的数学基础和方便通过计算机处理等优点,但其对复杂模型的描述和处理能力不足则是业界一直努力克服的问题,基于高级Petri网的工作流建模可以较好地解决这些问题。CPN通过对Petri网进行颜色扩展,具有以下优点:它能够描述负责的工作流程,具有很好的实际处理能力;它以Petri网为基础,继承了Petri网所具有的优点。

本文在介绍CWF-nets的基础上,建立了一个企业中应用比较多的项目金额申报流程的CWF-nets模型。在该模型中,通过CPN成功地避免了因为托肯含义不确定引起的二义性,通过弧表达式函数和守卫函数准确引导托肯的流向,使整个模型可以安全、正确的运行。后期的研究工作主要集中在对CWF-nets的分析以及设计基于CWF-nets的工作流管理系统。

[1] 史美林,杨光信,向 勇,等.WfMS:工作流管理系统[J].软件学报,1999,22(3):326-332.

[2] 曾 炜,阎保平.工作流模型研究综述[J].计算机应用研究,2005,(5):11-13.

[3] Nichols J,Demirkan H,Goul M,et al.Autonomic workflow execution in the grid[J].IEEE Trans Syst,M an Cybern C,Appl Rev,2006,36(3):353-364.

[4] 李建强,范玉顺.一种工作流模型的性能分析方法[J].计算机学报,2003,26(5):513-522.

[5] Gubala T,Herezlak D,Bubak M,et al.Semantic composition of scientific workflows based on the Petri nets formalism[C]//Proc of the Second IEEE International Conference on e-Science and G rid Computing(e-Science'06),2006.ftp://ftp.Computer.org/press/outgoing/proceedings/deeber/patrick/,2009-03-10.

[6] 潘启澍,姜 兵.基于Petri网的工作流建模技术及应用[J].清华大学学报(自然科学版),2000,40(9):86-89.

[7] 刘 峰,张 伟.一种扩展了价格信息的着色Petri网及其应用[J].计算机应用,2007,20(10):2501-2503.

[8] 姚 昱,陈莘萌,刘金硕.一种基于有色Petri网的工作流网模型[J].武汉理工大学学报,2007,29(3):134-137.

[9] 程建军.基于Petri网的研究生培养工作流模型[J].合肥工业大学学报(自然科学版),2009,32(1):78-81.

[10] 李 涛,钟诗胜.基于着色时间Petri网的工作流模型及其性能分析[J].计算机辅助设计与图形学学报,2006,18(6):824-830.

[11] 王 远,范玉顺.工作流时序约束模型分析与验证方法[J].软件学报,2007,18(9):2153-2161.