论文部分内容阅读
一、工作流模型概念到Petri网的映射
Aalst在Petri网的基础上定义了WF-net，即工作流网。在工作流网中库所对应过程中的条件，变迁对应过程中的可执行活动，库所中的托肯代表一个过程实例。
定义2.1（工作流网WF-net）:一个Petri网WF=(P,T;F)是一个工作流网当且仅当满足如下两个条件:
(1)WF-net中存在两个特殊库所:库所i是输入库所，即·i=○,库所o是输出库所，即o·=○;
(2)如果在库所o和i之间增加一个变迁t*（即t*·={o}且·t*={i}）,则得到的Petri网WF’是强连通的。
从上面两个约束条件可以看出一个工件流网必须有一个起始库所和一个终止库所，进入起始库所的托肯代表着一个过程实例的开始，而到达终止库所的托肯则意味着一个过程的结束。所有的活动与条件都位于起始点到终点的有向路上，不存在处于孤立状态的活动和条件。
二、工作流网的正确性分析方法
为了实现预期的业务目标，再定义了基于Petri网的工作流模型后，还要在被工作流管理系统执行之前对其进行分析。在对工作流网分析时，首先是如何判定一个工作流网在结构上是正确的。
工作流网的可靠性描述的是工作流网的动态性质，保证对于任何工作流实例，在没有异常的情况下，处理过程都能够正确终止。下面我们介绍一种借助Petri网的可达树，来对工作流网的可靠性进行分析的方法。
可达树分析算法:
对于一个Petri网PN=(P,T;F,M0），它的可达树是由标识M（标识值可以为ω,ω∈N且趋于无穷)作为节点构成的树，结点之间用T元素标注。
(1)根节点r由M0标注。
(2)一个标注为M的节点x是一个叶子节点当且仅当不存在t∈T:t在M是可实施的或者在从r到x的路上存在一个节点y≠x且节点y也是由M标注的。
(3)如果一个标注M的节点x不是一个叶子节点，那么对于所有t∈T使得在M下可实施的t实施而产生一个新的节点y且在从x到y新产生的弧上标注t。y节点标注的标识M’计算方式如下:
对于M’存在两种情况:
在从o到y的路上，如果存在标注为M’’的节点z≠y且
那么
其他情况，M’=M1’’
如果存在M(p)=ω，就意味着位置p中的标记（token）数在接下来的变迁中将会一直增大，直至趋于无穷，因此是错误的，转到(5)，否则转到(2)直至生成一个完整的树。
(4)设L为所有叶子节点的集合。进行如下判断:
如果说明该系统可以正常终止
如果说明该系统会出现死锁，死锁发生在位置P:M(p)≠0
如果说明该系统存在多余的位置，无法正常终止。
(5)算法结束。这种方法虽然能很好地对工作流网的可靠性进行分析，然而依然存在问题。我们知道一个含有m个元素的Petri网模型的状态空间有2m个,试图通过分析可达标树来研究其性质时间和空间的复杂度非常大,因此我们将在下节讨论解决的方法。
三、层次化建模及性质分析
细化理论的基本思想就是由已知或容易分析的简单网（这一简单Petri网的活性、有界性和可达性等比较容易验证）开始，逐步地用更加详细的子网代替初始简单网中的变迁或库所，而新加进去的子网并不改变原先网的某些性质。这种“自顶向下”、“逐步求精”的过程可重复进行到建模人员想要的细化程度。
在本文中用一个子网代替层次Petri网中非基本受迁/库所的过程称之为细化，根据细化元素的不同可分为变迁细化和库所细化;用一个非基本变迁/库所代替层次Petri网中一个子网的过程称之为抽象。
以变迁细化为例，用□表示基本变迁，表示非基本变迁，○表示基本库所，◎表示非基本库所,如图所示。
用基于层次Petri网建立复杂系统的工作流模型时，采用从上到下逐层细化的方法首先在最高层次上建立模型，然后再在下一层次上对系统的各个复合任务进行单独模拟，建立一个相对独立的子工作流系统，完成层次化的工作流模型，做到把握整体结构基础的同时又不丢失一个子系统的细节信息。对于常用的基本业务单元，可以建立Petri网模型库，直接引用这些模型库完成层次工作流网。
层次概念也可以用来判定一个工作流网的可靠性。给定一个复杂的层次化的工作流模型，通过单独分析每一个子工作流网来验证其可靠性是可能的，这可通过下面的定理和推论来进行。
定理3.1:工作流网WF1=（P1,T1;F1），WF2=（P2,T2;F2），WF3=（P3,T3;F3）=若WF1和WF2都是可靠的，且（WF1，i1）是安全的，则WF3也必然满足可靠性。
类似的，对库所细化我们也可以得到同样的结论:
定理3.2:工作流网WF1=（P1,T1;F1），WF2=（P2,T2;F2），WF3=（P3,T3;F3）=若WF1和WF2都是可靠的，且（WF1,i1）是安全的，则WF3也必然满足可靠性。
四、 结论
本文通过对我国电子商务的实际需求分析发现，跨部门流程的形成、跨部门流程的描述和跨部门流程的重组是跨部门流程管理的主要内容。通过对工作流模型和建模技术深入研究和学习，介绍了一种基于Petri网的工作流模型——工作流网，提出了一种支持电子商务的层次化建模方法。针对一些大型、复杂的系统，利用细化理论，包括变迁细化和库所细化，对其进行层次化建模和可靠性分析。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
Aalst在Petri网的基础上定义了WF-net，即工作流网。在工作流网中库所对应过程中的条件，变迁对应过程中的可执行活动，库所中的托肯代表一个过程实例。
定义2.1（工作流网WF-net）:一个Petri网WF=(P,T;F)是一个工作流网当且仅当满足如下两个条件:
(1)WF-net中存在两个特殊库所:库所i是输入库所，即·i=○,库所o是输出库所，即o·=○;
(2)如果在库所o和i之间增加一个变迁t*（即t*·={o}且·t*={i}）,则得到的Petri网WF’是强连通的。
从上面两个约束条件可以看出一个工件流网必须有一个起始库所和一个终止库所，进入起始库所的托肯代表着一个过程实例的开始，而到达终止库所的托肯则意味着一个过程的结束。所有的活动与条件都位于起始点到终点的有向路上，不存在处于孤立状态的活动和条件。
二、工作流网的正确性分析方法
为了实现预期的业务目标，再定义了基于Petri网的工作流模型后，还要在被工作流管理系统执行之前对其进行分析。在对工作流网分析时，首先是如何判定一个工作流网在结构上是正确的。
工作流网的可靠性描述的是工作流网的动态性质，保证对于任何工作流实例，在没有异常的情况下，处理过程都能够正确终止。下面我们介绍一种借助Petri网的可达树，来对工作流网的可靠性进行分析的方法。
可达树分析算法:
对于一个Petri网PN=(P,T;F,M0），它的可达树是由标识M（标识值可以为ω,ω∈N且趋于无穷)作为节点构成的树，结点之间用T元素标注。
(1)根节点r由M0标注。
(2)一个标注为M的节点x是一个叶子节点当且仅当不存在t∈T:t在M是可实施的或者在从r到x的路上存在一个节点y≠x且节点y也是由M标注的。
(3)如果一个标注M的节点x不是一个叶子节点，那么对于所有t∈T使得在M下可实施的t实施而产生一个新的节点y且在从x到y新产生的弧上标注t。y节点标注的标识M’计算方式如下:
对于M’存在两种情况:
在从o到y的路上，如果存在标注为M’’的节点z≠y且
那么
其他情况，M’=M1’’
如果存在M(p)=ω，就意味着位置p中的标记（token）数在接下来的变迁中将会一直增大，直至趋于无穷，因此是错误的，转到(5)，否则转到(2)直至生成一个完整的树。
(4)设L为所有叶子节点的集合。进行如下判断:
如果说明该系统可以正常终止
如果说明该系统会出现死锁，死锁发生在位置P:M(p)≠0
如果说明该系统存在多余的位置，无法正常终止。
(5)算法结束。这种方法虽然能很好地对工作流网的可靠性进行分析，然而依然存在问题。我们知道一个含有m个元素的Petri网模型的状态空间有2m个,试图通过分析可达标树来研究其性质时间和空间的复杂度非常大,因此我们将在下节讨论解决的方法。
三、层次化建模及性质分析
细化理论的基本思想就是由已知或容易分析的简单网（这一简单Petri网的活性、有界性和可达性等比较容易验证）开始，逐步地用更加详细的子网代替初始简单网中的变迁或库所，而新加进去的子网并不改变原先网的某些性质。这种“自顶向下”、“逐步求精”的过程可重复进行到建模人员想要的细化程度。
在本文中用一个子网代替层次Petri网中非基本受迁/库所的过程称之为细化，根据细化元素的不同可分为变迁细化和库所细化;用一个非基本变迁/库所代替层次Petri网中一个子网的过程称之为抽象。
以变迁细化为例，用□表示基本变迁，表示非基本变迁，○表示基本库所，◎表示非基本库所,如图所示。
用基于层次Petri网建立复杂系统的工作流模型时，采用从上到下逐层细化的方法首先在最高层次上建立模型，然后再在下一层次上对系统的各个复合任务进行单独模拟，建立一个相对独立的子工作流系统，完成层次化的工作流模型，做到把握整体结构基础的同时又不丢失一个子系统的细节信息。对于常用的基本业务单元，可以建立Petri网模型库，直接引用这些模型库完成层次工作流网。
层次概念也可以用来判定一个工作流网的可靠性。给定一个复杂的层次化的工作流模型，通过单独分析每一个子工作流网来验证其可靠性是可能的，这可通过下面的定理和推论来进行。
定理3.1:工作流网WF1=（P1,T1;F1），WF2=（P2,T2;F2），WF3=（P3,T3;F3）=若WF1和WF2都是可靠的，且（WF1，i1）是安全的，则WF3也必然满足可靠性。
类似的，对库所细化我们也可以得到同样的结论:
定理3.2:工作流网WF1=（P1,T1;F1），WF2=（P2,T2;F2），WF3=（P3,T3;F3）=若WF1和WF2都是可靠的，且（WF1,i1）是安全的，则WF3也必然满足可靠性。
四、 结论
本文通过对我国电子商务的实际需求分析发现，跨部门流程的形成、跨部门流程的描述和跨部门流程的重组是跨部门流程管理的主要内容。通过对工作流模型和建模技术深入研究和学习，介绍了一种基于Petri网的工作流模型——工作流网，提出了一种支持电子商务的层次化建模方法。针对一些大型、复杂的系统，利用细化理论，包括变迁细化和库所细化，对其进行层次化建模和可靠性分析。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。