基于Petri网的工作流模型合理性验证
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Petri网的工作流模型合理性验证范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:工作流管理系统具有实时性、同步和异步操作等特点,其建模方法是成功实施工作流管理的关键,而工作流模型应该完整地支持工作流定义的概念,正确、高效地反应企业的经营组织过程,为确保工作流的正确运行,必须对工作流模型的合理性进行分析和研究,因此工作流的模型分析和优化成为工作流研究的一个重点[7]。该文从各种研究资料出发,利用工作流模型的合理性定义,给出基于petri网的工作流模型的验证步骤和方法。
关键词:工作流;工作流模型;Petri网;模型验证
中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)11-2603-02
Reasonable Verification of Petri-net Based Workflow Model
WANG Yu1, LI Ceng 2
(1.Anhui Radio and Television University, Hefei 230022, China; 2.Anhui China-Australia Technical and Vocational College, Hefei 230031, China)
Abstract: Workflow management system with real-time, synchronous and asynchronous operation of the characteristics of the successful implementation of their modeling approach is the key to workflow management and workflow model should be complete to support the concept of workflow definition, correct and efficient response to business operations organizational processes, to ensure the correct functioning of the workflow to be the workflow model is reasonable to conduct analysis and research, the workflow modeling and workflow optimization to become a focus of the study. This departure from a variety of research data, using the workflow model’s reasonable definitions given Petri net-based workflow model verification steps and methods.
Key words: workflow;petri-net;model of workflow; model verification
1 工作流模型验证的意义
应用Petri网的分析技术对工作流模型进行验证的目的是在过程设计中检验工作流的正确性,避免执行时出现异常,过程异常包括死锁、死任务和活锁等。工作流建模是开发工作流管理系统的先行任务,所以在工作流投入使用之前就要进行很好的分析验证。如果一个工作流过程定义模型在其正确性、合理性没有得到充分验证时就投入使用,在工作流管理系统运行后再去进行修改,代价将远远高于前期的修改。因此在工作流模型实际实施之前,对其进行合理性分析,探索其中可能存在的各种过程异常,可以大大降低工作流运行时停产、检查和修复的成本,具有重大的意义[1]。
2 工作流网的合理性定义
工作流网的合理性定义是[1,3]:
一个工作流网PN=(P,T,F)建模的过程是合理的,当且仅当满足下面的三个条件:
1) 对于每一个状态i可达的状态M,存在一个实施序列,从状态M肘通往状态o,形式化表示为:M(iM)MO;
2) 状态o是从状态i可达的唯一最终状态,且结束时其中至少会有一个标记,形式化表示为:;
3) 在(PN,i)中没有死活动(不可能执行到的活动),形式化表示为:?坌t∈T?埚M,Mi'MM'。
其中条件一是规定了从初始库所总能到达终止库所;第二个条件规定了当托肯转移到终止库所时,其他所有库所都要是空的,也就意味这整个工作流的结束;第三个条件是规定不能有死活动,即所有的活动都能得到执行。
3 工作流网模型的合理性验证算法
在研究分析各种文献的工作流网的合理性验证理论和方法的基础上,对原有的算法进行综合改编,使算法更容易被人所理解,总结出合理性算法的基本思路和验证步骤[1-2,5]。
算法的基本思路是:根据工作流网模型建立矩阵,用矩阵表示每个活动的前后顺序;根据模型表示出每个活动的前后库所,用来确定托肯转移时的向量表示规则;从初始库所出发,根据活动的前后库所和矩阵判断后续触发的活动,并重复此工作,直到没有活动变迁可以发生;如果终状态是形如(0,0,…,1)的终止状态(此时托肯存放在最后一个库所,其余所有库所中都没有托肯存在),并且所有的活动都触发过,托肯也经历了所有的库所,这时可以说改模型是合理的、正确的,否则模型中就存在错误。
在算法中要描述出状态从(1,0,0,…)到状态(0,0,…,1)的推算过程,并且要用另一个集合表示所执行的活动,最终检查是否合理的依据就是a、状态向量是否变成(0,0,…,1);b、表示活动的集合是否包含所有的活动。算法的具体描述为:
(1) 用矩阵表示各个活动之间的前后顺序,方法如下:
(2) 根据矩阵构造各个活动的输入库所集合和输出库所集合,用・t表示活动t的输入库所集合,用t・表示活动t的输出库所集合。构造方法是,矩阵t列中所有为1的元素的行号的前驱库所即t的输出库所集合;t行中所有为1的元素的列标的前驱库所即t的输入库所集合;没有前驱活动的活动的输入库所集合为起始库所i,没有后续活动的活动的输出库所集合为终止库所o。
(3) 构造初始条件,初始条件有一个向量和一个集合,向量P0=(1,0,0,…),具体向量的维数是库所的个数,表示托肯在第一个库所内;集合T0为空,表示没有执行任何活动。
(4) 根据活动t的输入库所集合・t和输出库所集合t・,更改向量P,并把活动t添加到集合T中,并根据矩阵判断下一个活动。
(5) 反复进行执行步骤(4),直到没有活动可以执行且执行一遍所有活动。
4 总结
通过矩阵列举出活动序列,说明所有的活动都处于起始库所和终止库所之间,满足了合理性条件一;由于在列举活动序列时,序列中包含了所有活动,说明没有活动是死活动,满足了合理性条件三;演算的结果中向量P={0,0,0,0,0,0,0,0,0,1},证明在工作流结束时,托肯只存在于终止库所中,其他所有的库所中均不存在托肯,满足了合理性条件二。通过以上演算,证明了模型能够满足合理性定义中的三个条件,所以可以得出结论,此工作流模型是正确、合理的。[6]
参考文献:
[1] 郝文,王道平.基于Petri网的工作流建模合理性验证算法[J].计算机工程与应用,2008,44(13).
[2] van der Aalst W M P.The application of Petri nets to Workflow Management[J].The Journal of Circuits,Systems,and Computers,1998,8(1).
[3] 袁崇义.Petri网原理[M].北京:电子工业出版社,1998.
[4] van der Aalst,W M P.Workflow Management: Models, Methods, and Systems[M].Boston:MIT Press,2002.
[5] 周福明.基于Petri网的工作流建模与正确性分析[J].计算机科学,2005,32(2).
[6] 李.基于Petri网的工作流模型应用研究[D].合肥:安徽大学硕士论文,2008,28-29.
[7] 庞善臣.petri网在工作流系统建模和分析中的应用[J].系统仿真学报,2005(17).