基于带权时间Petri网的工作流建模研究及应用

周望平,黎湖广

(长沙航空职业技术学院,湖南 长沙 410124)

目前，工作流技术已经日益普及应用，它具有流程集中实现、开发简单快速、风险低等特点。工作流的建模方式有很多种，如基于活动网络、基于形式化表示、基于状态与活动图、基于事务模型的建模方式等[1]。工作流系统本质上大部分基于Petri网构建。Petri网的图形化表示方式使得模型具有良好的直观能力，因此Petri网非常适合用于对工作流技术进行建模和分析。

2000年，W.M.P.Van der Aalst提出了基于Petri网的建模技术[2]。Khodakaram 等人在此基础上提出了如何利用基于Petri网的工作流对建模过程中的文件进行审查和分类[3]。Mor Peleg等人利用Petri网建模技术，结合生物学，开发出了生物过程的图形化知识模型的定性推理方法，给出了一个生物概念模型TAMBIS，并将其映射到工作流模型[4]。

但是传统Petri网不能反映时间等方面的内容，无法对大型复杂的结构提供模型支持等，因此，近些年研究人员对Petri网进行了扩充，应用得最广泛的方案有三种：基于时间、基于颜色和基于层次的扩展。Injun Choi等人提出了一种基于有色Petri网的事务工作流模型，给出了对该工作流模型的一个实现，对该实现进行了仿真[5]。Berthomieu B.等人提出了一种基于时间Petri网的工作流模型，该模型支持时间变化的通信系统，并采用枚举法对该时间Petri网进行了验证，证明了该模型是可靠的[6]。Rainer Fehling则根据实际工作经验，提出了一种层次化的Petri网工作流模型，作者给出了Petri网分层结构的接口，并将该思想用于编辑器的层次化界面设计中[7]。

基于时间对Petri网进行扩充是目前较为主流的工作流实现方法。但时间属性对工作流模型中的资源、案例和过程具有不同的重要性，因此引入加权的思想，构建基于带权时间的工作流模型，并以此模型开发了某企业的物资管理系统，实际运行情况表明该工作流模型效果良好。

1 Petri网

1.1 Petri网简介

Petri网于1962年由Carl Adam Petri博士提出，作为一种图形化描述过程的工具，Petri网被广泛用于建模与分析上。既拥有严格的数学定义又能形式化表示的Petri网被认为是所有流程定义语言之母。Carl Adam Petri为Petri网给出了一些基本的术语，简单分析如下[8]。

(1)资源(resource)：系统发生变化包括的人员、工具、设备、数据等与系统状态有关的因素。

(2)库所(place，又称P元素)：每一类资源存放的地方，既表示存放资源的场所又表示该类资源。库所是一个抽象概念，将资源按其在系统中的作用进行分类。

(3)变迁(translation，又称为T元素)：自动化过程会使用和消耗资源，从而可能引发库所变化。

(4)连接弧(directed arc)：连接库所和变迁，表示库所与变迁之间可能存在的逻辑关系。

(5)托肯(token)：表示系统的动态特性。在Petri网中，托肯位于库所之中，用黑色的小圆点表示，其在库所中的动态变化过程代表系统的状态改变(又叫标记、标识)。

在上述定义中，库所、变迁和有向弧为Petri网的必须结构，表示系统的静态功能，托肯的动态变化表示系统的动态功能。

1.2 工作流概念到Petri网的映射

工作流业务过程中的案例、任务、条件、过程、触发等可以由Petri网中的构成元素如库所、变迁、托肯、连接弧等进行映射。其中，Petri网中的变迁描述任务，库所对应条件，且库所表示任务的执行次序以及案例的状态。库所中的托肯则表示案例的个数和执行状态[9]。

(1)过程：工作流的业务过程中定义了哪些任务需要被执行，执行这些任务需要哪些条件，以及这些被执行的任务之间的次序关系，因此，可以采用Petri网来定义工作流中的过程及其子过程。在Petri网中，只有一个入口和一个出口，分别表示过程的进入和过程的结束，变迁描述任务，库所对应条件。变迁描述的任务为主动元素，库所描述的条件为被动元素。

(2)路由：可执行的任务是可以选择的，采用Petri网库所的转移，确定案例中任务的执行路由，可以确定哪些任务需要执行。

(3)启动：工作流中的工作项映射为Petri网中一个就绪的变迁，即，只要触发条件满足，则该变迁立即执行。当变迁拥有一个额外的输入库所时，该输入库所中包含的托肯表示任务的触发条件。

2 基于带权时间的工作流模型设计

2.1 带权时间工作流概念模型

标准的工作流由三个维度元素组成，包括过程(process)、资源(resource)、案例(case)。引入时间属性到工作流空间，就可以使工作流的所有组成元素以及元素间的关联关系具备时间属性，显然时间属性对三个维度的重要性是不同的，因此，在此基础上，给出带权时间工作流的概念。而带权时间工作流则是在时间工作流网的基础上，除关注过程维外，还关注资源维以及案例维，如图1所示。

图1 工作流的四维模型

2.2 带权时间工作流的元模型

所谓元模型，就是关于模型的模型。工作流的元模型则用来描述工作流中各元素以及元素间关系的模型。一个扩展的带权时间工作流的元模型如图2所示，图中，Logic-Rule代表逻辑规则，表示工作流中的分支(Split)、汇聚(join)结构以及AND、OR、XOR等相关性约束，Derived Process继承了过程的定义，为Process的子过程，子过程可以具备自己的属性，不同的子过程可以进行组合，这样可以使得不同的逻辑层次上基本任务粒度可以进行灵活控制。

图2 元模型静态UML图

在元模型中，任务task具备角色(role)、工具(tool)以及案例(case)三要素。工具处理相应的数据，角色则使用工具。对任务进行实例化，由资源(发起者)触发后，任务被激活为活动，执行这些活动，形成过程，这些过程会拥有各种各样的状态。事件(event)既可以触发控制转移又可以导致状态转化。状态之间可以相互转化(类似于线程的就绪、挂起、运行等)。任务状态的变化由状态转换规则(state-transfer-rule)决定，任务转移的方式则由任务转移规则(task-transition-rule)决定，状态转换规则和任务转移规则统称为规则(Rule)。规则与规则之间由联系(conn)组成，联系则引用相关数据以及触发相应事件。

在元模型中，Activity(活动)被分解为task(任务)和Logic-Rule(逻辑规则)。task由WFMS(工作流管理系统)分配给资源完成，是为业务逻辑任务。而Logic-Rule则属于自动化任务，WFMS在其中充当执行者的角色，属于管理逻辑任务。从Activity的角度分析，Logic-Rule不但承担了选路控制的任务，同时也负责了案例数据的选路任务以及相应的数据处理任务。这种分解使得task中只需要定义状态转换规则，Logic-Rule只需要定义任务转移规则，两者这种低耦合关系，让业务任务定义只需要经过微小改变就可以重复利用，甚至达到完全复用。

在工作流中，作为任务的执行者，既可以是程序设备，也可以是人，这两者在元模型中被统一为角色(Role)。

在元模型中，case(案例)为被过程处理的业务对象。case关心的是数据，既包括业务对象中抽象出来的相关数据，又包括控制案例流转的控制数据。

2.3 带权时间工作流的过程模型

工作流过程模型是整个工作流管理系统的基础，同时也是整个工作流模型最重要的部分，可以说，工作流过程模型是整个工作流模型的核心部分。工作流过程模型是区分一个工作流模型好坏的关键所在，系统所支持的应用范围以及系统的灵活性很大程度上取决于模型描述能力的强弱。

过程模型的组成实体有三类：过程、活动和子过程。过程是对现实世界一个业务过程结构的抽象描述。过程包含很多属性，如过程名、时间限制、活动列表、起始活动、各个活动的优先级以及限制条件等等。活动则是对业务过程中一个具体的执行步骤的抽象描述，比如打开打印机，活动可以根绝应用语义分为不同的类型。子过程则类似于数据库中的外键，是对另外一个模型的引用，包括输入输出、结束条件、过程名、过程描述等。

过程模型包括五种关系，分别是先序关系、继承关系、组成关系、引用关系和调用关系。先序关系即第二章中提到的WFMC的四种控制结构。每一种结构中前后的元素间存在着先序关系。继承关系，在三种实体中，子过程与过程间便存在着继承关系。组成关系，连接过程和活动，表示一个过程由一个或多个活动组成。引用关系，在一个过程执行中引用其他过程的对象或者实体。调用关系，一个过程或者活动执行过程中需要调用其他应用程序来处理本活动中的对象。

根据1.2节所述方法将元模型映射到Petri网，通过Petri网形成WF-Net，再将元模型相关概念映射为Petri网的相应角色，在此基础上进行适当的扩展，形成带权时间工作流模网(WTPWF-Net)。WTPWF-net引入时间工作流网和基本工作流网的相关思想，采用带权的时间属性对托肯进行扩充，用扩充后的托肯表示案例数据的时间性约束。变迁的属性则采用资源以及附加其上的时间属性进行映射。

2.4 工作流概念到模型元素的映射

工作流管理系统中要处理的业务对象由案例表示，在基本工作流网以及时间工作流网中，案例映射为Petri网的托肯，表示前一个任务已经完成。Alast在Petri网的扩展方式中提出了一种可能的时间扩展，并为托肯扩展了时间戳属性，时间戳属性主要用于处理两个任务间的时间延迟，代表拥有该属性的托肯何时能被引用。在其他情况下，托肯同样作为一个信号使用，其不具备自身的独立属性。

WTPWF-net中，赋予托肯独立的带权时间属性(Weighted Time Attribute)，该时间属性包括三个值：案例创建时间(Case Created Time)、案例有效时间(Case Valid Time)、时间权重(Time Weight)，其中，时间权重值越大，案例的优先级就越高，该案例重要性越大(即可能包含关键数据等情况)，这三个值可以完整的表述所有案例的时间信息。

在基本工作流定义中，只要过程不结束，案例数据永远有效，意味着案例的生命周期为贯穿过程始终，但在实际的工作流管理系统中，这不可能。因此，在WTPWF-Net中，给予托肯的带权时间属性中，CVT为独立值，代表在业务对象中，案例数据的有效时间。CVT大，则案例数据的有效期长，反之则短。这样，当用户需要对案例的处理进行时间性约束时，可以直接修改CVT的值，而不用去修改过程定义中任务的间隔时间。同样，当由案例映射成的托肯相对重要时，给予TW一个比较大的值，当案例为一次性或者相对不重要的案例时，给予TW一个相对较轻的值。

在基本工作流定义中，Petri网中的变迁由活动的执行映射而来，库所则由活动执行的条件映射而成，只有库所拥有托肯时，活动执行的条件才视为满足。但在WTPWF-net中，将任务分为了两种，分别是管理逻辑任务和业务逻辑任务，两者都需要映射，同时，在各种状态下以及状态的转换间会存在一定的时间延迟。

WTPWF-net中，在加入带权的时间因素后，任务状态转换图如图3所示(采用操作系统中的时间片分片思想)。

图3 活动状态转化图

其中，S0为等待状态，S1为就绪状态，S2为运行状态，S3为完成态，S4为异常态，S5为终止状态，S6为挂起状态，终止状态与挂起状态均为人工干预导致(参考了操作系统中进程模型)。

S3、S4、S5为终止态，S0为起始态，S0经过调度到S1，S1经过点火到S2，当S1的时间片用完时，跳转到终止态S4，当S1终止时，跳转到S5，当S1取消执行时，跳回到起始态S0.当S2取消时，回退到S1。当S0时间片用完时，跳到终止态S4。S0中断时，跳到S5。

在图3中，业务逻辑任务的状态分为等待、就绪、执行三个状态，分别由S0，S1和S2表示。当业务逻辑任务处于S0时，WFMS拥有控制权，当业务逻辑任务分配完成后，业务逻辑任务形成工作项，进入用户的工作项列表，此时业务逻辑任务处于S1，相应的控制权也从WFMS上转移到执行任务的资源。

WTPWF-net中，将等待状态下的业务逻辑任务映射为库所，将就绪和执行状态下的业务工作项映射为变迁。同时，业务逻辑任务和业务工作项也包含自己的时间属性，包括任务分配延迟时间(DDT)、分配有效时间(DVT)、条件触发延迟时间(FDT)、条件触发有效时间(FVT)、执行延迟时间(EDT)、执行有效时间(EVT)，映射后，DDT和DVT为库所的时间属性，FDT、FVT、EDT、EVT为变迁的时间属性。

在管理逻辑任务中，就绪状态到执行状态可以拥有多条可选路径，执行状态到就绪状态也有多种方式，因此，这是一种不同于普通变迁定义的多入口多出口方式，这里，将之定义为查找变迁。

查找变迁Tr(I,O,W,(i,o,w))，其中，*t=I，t*=O，即I为变迁t的前置集，O为变迁t的后置集。(i,o,w)代表时间属性(变迁起始时间、变迁结束时间、变迁执行权重)，在起始时间相同的情况下，w大的变迁首先被触发。

查找变迁与普通变迁的区别为，普通变迁只有一个输入库所和输出库所，查找变迁不受此限制，而且，查找变迁没有时延，即DDT、FDT、EDT的值恒为0。

WTPWF-net中，Petri网中的弧由任务间的依赖关系映射而成，且弧的权值为一个常量值1，该数字不具备任何定量意义，仅仅是表示相邻任务间具备时序关系，这与基本工作流网一致。

WTPWF-net中最后一个是关于资源的映射，由于资源是任务的发起者和执行者，是任务以及活动的组成要素，往往与两者绑定在一起，因此，将资源及其时间属性同样映射为Petri网中变迁的属性。

3 基于WTPWF-net的物资管理系统实现

应用WTPWF-net对某公司物资管理系统进行流程分析，将物资管理系统的相关审批流程应用本方法编程开发实现。首先将物资管理系统中的有关工作流与Petri网进行相应映射，然后由Petri网与WTPWF-net进行映射。图4为所涉及物资管理系统的主功能界面图，图中，左边的树形菜单为物资管理系统中的主要功能，可以点击每个功能查看该功能的流程图。

图4 主功能界面图

图5为后台管理截图，后台管理人员可见，管理人员查看诸如订单等信息后将之传送给领导，以便领导审阅。

图5 后台管理

4 结论

在分析传统工作流局限性的基础上，提出了一种带权的时间工作流概念，将过程、资源、案例三维空间扩展到过程、资源、案例、时间四维模型，同时，针对传统工作流只关心过程而不关心资源和案例的情况，提出了时间属性对三个维度的重要性不一致的概念，并给出了带权的时间工作流模型，并对该模型的元模型、过程模型给予了详细说明。最后将提出的工作流模型实际应用于某公司物资管理系统，良好的实际应用效果验证了方法的可行性和有效性。

[1] 李炜, 曾广周, 王晓琳.一种基于时间Petri网的工作流模型[J]．软件学报，2002,13(9):1666-1672.

[2] 张亮, 姚淑珍.基于Petri网化简技术的工作流模型正确性研究[J]．计算机工程, 2007,33(9):60-61.

[3] 陆中，孙有朝，吴海桥．基于着色随机时间Petri网的维修性建模方法[J]．机械工程学报，2011,47(10): 231-237.

[4] 刘铭，张国印，姚爱红．基于层次实时有色Petri网的实时系统建模与分析方法研究[J]．电子与信息学报，2011,33(3): 24-32.

[5] 余阳，汤庸．时态工作流过程模型及其合理性验证[J]．软件学报，2010,21(6):1233-1253.

[6] 陈伟，文东戈，王昊．层次颜色工作流Petri网建模与应用[J]．计算机技术与发展，2009,1(1): 49-52.

[7] 潘理，丁志军，郭观七．混合语义时间Petri网模型[J]．软件学报，2011,22(6): 221-233.

[8] 周建涛，叶新铭．一种构造Petri网可达图的方法[J]．内蒙古大学学报(自然科学版)，1999,30(3):392-395.

[9] 周建涛，叶新铭．Petri网的可达图与可达树的比较[J]．内蒙古大学学报(自然科学版),2000,31(1):117-120.

[10] 罗海滨，范玉顺，吴澄．工作流管理技术综述[J]．软件学报，2000, 11(7): 89-97.