基于Petri网的医用材料采购流程工作流建模分析

陈郁韩

①南通大学附属医院设备科 江苏 南通 226001

医用材料采购是一项复杂的活动，是一个多任务、多角色参与的流程化执行过程，具体活动涉及生产商、配送商、政府集中招标采购管理办公室、临床业务科室、采购中心、财务科及审计部门等诸多环节，需要协作完成。工作流是多个参与者之间按照某种预定义的规则传递文档、信息和任务的自动进行过程，以实现其预期的目标[1]。医用材料采购流程工作流建模的主要任务是将其采购流程分为诸多任务单元，按照定制的流转过程的定义，安全、可靠地在各种任务执行者之间传递，完成预期执行目的。工作流建模的内容主要包括工作处理过程的抽象描述、管理过程中信息的流转路径、参与信息处理人员的权限分配和任务指定以及流程中需要共享的业务数据等信息对象，从而建立完整的、可动态变化的管理系统。基于Petri网的建模方法是主要的工作流建模技术之一，其可用图形化方式描述工作流，与其他非形式化的框图技术相比，Petri网具有规范而明确的语义和丰富的分析技术，避免了模糊性、不确定性和矛盾性。

1 Petri网概念

Petri网是一种适用于多种系统的图形化、数学化建模工具，为描述和研究具有并行、异步、分布式和随机性等特征的复杂系统提供了强有力的手段[2]。Petri网用图形表示的组合模型具有直观、易懂和易用的优点，对描述和分析并发现象有独到的优越之处；Petri网又是严格定义的数学对象，借助数学开发的Petri网分析方法和技术，既可用于静态的结构分析，又可用于动态的行为分析[3]。Petri网采用可视化图形描述，但却被形式化的数学方法所支持，表达系统的静态结构和动态变化，成为描述、分析和控制系统最有效的方法[4]。

1.1 Petri网的发展历程

Petri网的概念于1962年由德国学者Carl Adam Petri在其博士论文中提出。1970-1975年，麻省理工学院的计算结构研究小组积极参与了Petri网的研究，并于1975年举行了第一次Petri网及相关方法研讨会。1980年召开了第一次Petri网理论和应用国际研讨会，之后每年举办一届。1981年Peterson出版了第一本关于Petri网方面的书。在数十年的发展过程中，Petri网的抽象研究和描述能力不断地向纵横两个方向扩展。其纵向扩展表现为从基本的条件/事件网(Condition/Event Net，C/E)，经过位置变迁网(Place/Transition Net，P/T)，发展到高级网(High Level Network，HLN)(包括谓词/变迁网和着色网)；横向扩展表现为从没有参数的网发展到时间Petri网和随机Petri网；从一般有向弧发展到禁止弧和可变弧；从自然数标记个数到概率标记个数；从原子变迁发展到谓词变迁和子网变迁[5-8]。

1.2 Petri网定义

一个三元组N=(S,T；F)是一个Petri网，当且仅当：

其中，dom(F)={x∈S∪T｜ y∈S∪T:(x,y)∈F}；cod(F)={x∈S∪T｜ y∈S∪T:(y,x)∈F}；S为N的库所集，T为变迁集，F叫做流关系。x=S∪T叫做N的元素集。S中元素为库所或S元素，T中元素为变迁或T元素。S={S1,S2……Sm}是一个有限库所(place)集，T={T1,T2……Tn}是一个有限变迁(translation)集。库所集和变迁集是Petri网的基本成分，流关系是从他们构造出来的。库所和变迁是两类不同的元素，所以S∪T≠Φ，而S∩T=Φ表示网中至少有一个元素。每一个位置表示一种资源，变迁是资源的流动，由流关系规定，所以变迁只能与位置有直接关系：F(S×T)∪(T×S)，dom(F)∪cod(F)=S∪T表示不存在不参加任何变迁的资源和不引起资源流动的变迁。通常用｜x｜表示集合S∪T的元素的个数。在图形上，库所用圆或椭圆表示，变迁用竖线或者小长方形表示；元素之间的流关系F用带箭头的弧(有向弧)表示,用从x到y的有向弧表示有序偶(x,y)，因而(x,y)∈F也叫有向弧。显然，有向弧只存在于小圆圈(椭圆)和小矩形(竖线或者小长方形)之间，任意两个小圆圈之间或任意两个小长方形之间均无有向弧的连接[9]。

2 Petri网路由模型

在工作流的过程定义中，控制流是对执行业务过程所经过的活动和连接的时序排列描述，各活动之间通过控制流相关联，且十分重要。而Petri网作为图形处理工具可直观地表达活动之间的逻辑关系。在通用工作流规范的基础上，结合医用材料采购管理中的流程特点，形成了基于Petri网的工作流路由模型。在流程化管理模式中分类提取了数种路由模型，根据不同的业务特点，可选择相应的路由模型进行业务的流程化处理。任务可选择，即可能有仅为某些案例执行的任务。案例不同其任务执行的顺序也不相同，通过确定案例的任务执行路由而确定任务的执行情况[10]。

2.1 顺序路由模型

顺序路由是最基本的工作流路由方式，是最为容易理解的模型。当两个或更多任务间存在依赖关系时需用顺序模式—在上一任务完成之前本任务不能执行(调度)。工作流过程中的各个活动是按照固定的顺序串行执行，每个活动的执行都依赖于前一个活动的执行情况。如图1所示，A、B和C是3个串行的活动，要想执行活动B，必须先执行活动A，而要想执行活动C，必须先执行活动A和活动B。

图1 顺序路由的Petri网建模

2.2 并行路由模型

当多个任务要同时执行或以任意次序执行，称之为并行路由。工作流过程中各活动的执行没有严格的顺序，可同时进行。如图2所示，当活动A执行完，使得托肯转移到库所c2和c3中，使活动B和活动C同时满足执行条件，而活动B和活动C之间无制约关系，因此活动B和活动C可任意的执行，而活动D则用来同步这两个分支，以保证活动B和活动C都执行完后流程能继续向前执行。

图2 并行路由的Petri网建模

2.3 选择路由模型

一个过程可以决定某个案例的路由，但不同的案例之间的路由可能相同也可能不同，称在两个或多个任务中进行选择的路由为选择路由。一个工作流流程的执行可以在数个活动中选择，而无需执行每个活动。如图3所示，活动A执行完后托肯可转移到库所c2或c3中，使活动B或活动C被执行。当活动B或活动C执行完后活动D将被执行。

图3 选择路由的Petri网建模

2.4 循环路由模型

循环路由指某个任务的反复执行，通常一个案例的一个任务只需要执行一次，但当某项任务需要重复执行直至检测通过，这时该路由形式显得理所当然。在一个工作流流程的执行过程中，某一活动需要重复执行多次，才能满足条件继续执行下个活动。如图4所示，活动B需要执行多次，直到满足条件为止，活动C才能被执行。

图4 循环路由的Petri网建模

在工作流的过程定义中，Petri网路由模型是对执行业务过程所经过的活动和连接的时序排列描述，各活动之间是通过控制流关联的，而Petri网作为图形处理工具，可以直观地表达活动之间的逻辑关系[11]。

3 医用材料采购流程工作流建模

按照Petri网建模流程首先构建Petri网模型，根据医用材料采购的业务流程，得到医用材料采购业务的Petri网模型，Petri网模型由9个库所p和9个变迁t组成(如图5所示)。

医用材料采购流程的Petri网工作流程：①t1被执行→临床科室根据需要提出医用耗材和低值器具的采购需求；②变迁t2表示审批科室申请→审批完成后token进入库所p3确认采购方式，如属于低值器具则token从库所p3转移到变迁t4直接采购，如属于医用耗材则token从库所p3转移到变迁t3按招标目录进行订货采购；③低值器具在等待采购完成后直接入库t8，如为医用耗材，订货采购完成后需要转移到变迁t5签订合同→由token转移到库所p6等待到货；④在收到货物后token转移到变迁t6进行验收→由token转移到库所p7等待验收结果；⑤如验收不合格由token转移到变迁t7与供应商交涉→由token转移到库所p8等待交涉结果，如交涉成功，供应商重新供货→由token转移到变迁t6重新验收，如交涉不成功，根据合同的相关规定，token转移到变迁t9终止合同；⑥如果验收合格，token转移到变迁t8办理入库手续→结束整个工作流程→token转移到结束库所p8中→流程进入结束的稳定状态[12-13]。

4 模型合理性验证算法

(1)变量初始化。P为工作流网中的所有库所集合{i，p1，…，pn，o}；HP为所经历过的库所集合，初始值为{i}；T为工作流网中的所有变迁集合{t1，…，tm}；HT为所经历过的变迁集合，初始值为{t1}；E为工作流网中存在托肯(Token)的库所集合，初始值为{p0}；工作流网中的所有库所状态为公式1：式中，M(pk)为库所pk的三维矢量(mi，mo，mo)，其中mi为库所pk前置条件，mo为库所的后置条件；mo’为库所的后置变迁触发时能到达的新库所数目。

(2)让托肯按照工作流的过程图遍历所有库所和变迁。对于所遍历过的库所和变迁分别加入集合HP和HT；对于每个遍历过的库所pk，记录M(pk)；并实时更新E集合。

(3)如发现以下情况，即可中止遍历：①某个库所的mo=0；②存在死变迁；③S存在矢量(1，1，0)，否则继续(2)中的内容。

(4)检查遍历结果。

图5 医用材料采购流程的Petri网模型

If[S中矢量(0，1，1)个数＞1]，then提示“开始库所不唯一”；

If[S中矢量(1，0，0)个数＞1]，then提示“汇结库所不唯一”；

If[S中矢量(1，0，0)个数=0]，then提示“无汇结库所”；

If[S中矢量(1，1，0)个数≠0]，then提示“存在死锁”；

If(P≠HP)，then提示“存在不可达库所”；

If(T≠HT)，then提示“存在不可达变迁”；

If(E集合中存在库所M矢量中mo=1)，then提示“存在具有托肯的非汇结库所”；

否则，该工作流是合理的[14]。

5 模型优化

模型优化的目标是在不破坏工作流原本运行过程的前提下，大幅提高工作流的整体指标，如平均完成时间、资源利用效率等。基于工作流的两种过程优化方法(并行优化和合并优化)，工作流优化的算法基本思想具体描述如下：①变量初始化，对于工作流图中每个变迁tk，用三维矢量M(tk)对他进行描述，M(tk)=(s，time，tp)，其中s表示tk所使用的资源，time表示变迁tk的执行时间，tp表示变迁tk的必要前置条件；②让托肯按照工作流的过程图遍历所有库所和变迁；③如果发现变迁节点ti和tj为相邻的顺序结构，并且ti和tj并不是相互之间的必要前置条件，则改顺序执行为并行执行；④如发现变迁节点ti和tj为相邻的顺序结构，并且ti和tj使用相同的资源s，则将其合并优化；⑤重复②的内容，直到工作流图未发生新的变化为止。在工作流的执行过程中t1、t2、t3及t5虽然他们之间为顺序结构，但由于相互之间存在前置关系，且使用不同的资源，不满足优化的条件，因此不能优化。通过对各个环节员工的资源利用率进行计算，发现在整个流程中采购员资源利用率最高，是整个流程的瓶颈，因此在采购员的相关执行环节无法继续优化的情况下可考虑增加资源(增加采购员人数、网上采购等)[15-16]。

6 结语

本研究构建医用材料采购流程的Petri网模型，对采购流程进行模拟优化分析，为医用材料采购的业务模式选择提供了建模仿真的思路，医院可动态、连续地监测内部采购变动情况、平均执行时间的大小和运作效率的高低，为管理决策提供技术支持，对于效率较低的环节可以考虑改变管理模式、改进工作流程以提高运作效率。Petri网是简化模型，如何真正求解复杂的采购业务模式系统指标尚需进一步研究和探索[14-18]。

[1]Workflow Management Coalition.Workflow management coalition terminology and glossary[S].Technical Report,Brussels:Workflow Management Coalition,1996.

[2]袁崇义.Petri网原理与应用[M].北京:电子工业出版社,2005:1-20.

[3]Vander WM Aalst P.Verification of workflow nets[C].Proceedings of the 18th International Conference on Application and Theory of Petri Nets,Heidelberg:Springer Verlag,1997,407-426.

[4]Zhou MC.Parallel and sequential mutual exclusions for petri net modeling for manufacturing system[J].IEEE Trans on Robotics and Automation,1991,7(3):515-527.

[5]Lee J,Liu KR,Chiang W,Modeling uncertainty reasoning with possibilistic Petri nets[J].IEEE Trans Syst Man Cybern B Cybern,2003,33(2):214-224.

[6]Shen VL.Reinforcement learning for highlevel fuzzy Petri nets[J].IEEE Trans Syst Man Cybern B Cybern,2003,33(2):351-362.

[7]Adamyan A,He D.Sequential failure analysis using counters of petri net models[J].IEEE Trans Syst Man Cybern,2003,33(1):56-58.

[8]Zhang Zhiming,Wang Yue,Tao Ran,et al.Resource allocation using timed petri nets and heuristic search[J].Journal of Beijing Institute of Technology,2000(9):148-154.

[9]李文敬,廖伟志,王汝凉.Petri网系统的功能划分及其并行算法[J].计算机工程,2009,35(21):48-50.

[10]宋晓勇.基于工作流技术的医疗过程管理系统[D].长春:吉林大学硕士学位论文,2009:12-18.

[11]邹海,储德新,高顺利.基于Petri网的工作流建模与分析[J].安徽大学学报,2011,35(2):33-36.

[12]陈郁韩.医用耗材安全使用体系的构建[J].中国医疗设备,2010,25(4):4-7.

[13]陈郁韩.医院医疗设备全寿命周期研究[J].中国医学装备,2013,10(3):52-55.

[14]童吉.基于Petri网的高校设备采购工作流建模分析和优化[J].实验室研究与探索,2012,31(4):188-191.

[15]文俊浩,秦佳,赵瑞峰.基于WDAG的工作流模型优化分析[J].计算机工程,2010,36(1):30-32.

[16]傅作为,乐晓波.基于Petri网的工作流模型优化[J].长沙理工大学学报,2012,9(2):81-86.

[17]胥慧一,刘丽华,周丹.医疗设备信息数据集成与应用设计[J].中国医疗设备,2008,23(4):9-12.

[18]尹军,陈维平,刘福彬.医院医疗设备评估探讨[J].中国药物警戒,2011,8(7):416-418.