基于邻接矩阵的工厂制造流程模型差别检测方法

摘要

本发明公开一种基于邻接矩阵的工厂制造流程模型差别检测方法。该方法包括以下几个步骤：两个用Petri网建模的工厂制造流程模型进行元素匹配(变迁匹配和库所匹配)，得到多种匹配方式；对于每一组匹配方式，将流程模型转换为对应的邻接矩阵，两个邻接矩阵相减得到差别矩阵；在所有的差别矩阵中，选择其中最优的差别矩阵来代表两个流程模型之间的差别。本发明的优点是：打破了只面向两个相似流程进行差别检测的局限性，将比较范围扩大到所有的流程模型，大大提高了实际的可用性。

说明书

技术领域

本发明属于业务流程管理领域，涉及流程模型间的差别检测方法，特别是一种基于邻接矩阵的工厂制造流程模型差别检测方法。

背景技术

随着业务流程模型管理(Business Process Management,BPM)技术的发展，越来越多的工厂开始创建自己的流程模型库。如一个模具工厂就拥有大量的流程模型，包括模具制造、质量检查、调度安排、车间加工、过程监控等流程。一个家电制造工厂涉及的流程模型有电视制造流程、冰箱制造流程、空调制造流程、电扇制造流程等。这些流程模型是工厂的重要资产，有效地管理可以为工厂提高效率、增加利润。流程模型差别检测作为一种流程模型管理技术在业务流程领域越来越重要：给定两个流程模型，通过比较得他们之间的差别，并将差别反馈给流程设计人员。流程分析人员可以通过该差别找到流程执行效率低下的原因并对流程进行重新设计等其他操作来改进流程模型的执行效率。传统上，人为地对两个流程模型进行比较并找出差别，然而该做法耗时长、效率低，差别的结果会因人而异。由此，迫切需要一种自动化的技术来检测两个流程模型间的差别。

发明内容

为了能够自动、高效、准确、快速地找出两个工厂制造流程模型间的差别，本发明提出一种基于邻接矩阵的差别检测算法。将流程模型转化成一个邻接矩阵并将流程模型间的差别检测转换为其对应的邻接矩阵之间的差别检测，打破了只面向两个相似流程进行差别检测的局限性，将比较范围扩大到所有的流程模型，大大提高了实际的可用性。

基于邻接矩阵的工厂制造流程模型差别检测方法，包括以下步骤：

(1)输入两个用Petri网建模的工厂制造流程模型，将流程模型中的变迁、库所节点和边解析出来；

(2)元素匹配，即找出第一个流程模型中与第二个流程模型中的对等元素；

(3)选取其中的一组元素匹配方式，基于该匹配方式建立两个流程模型对应的邻接矩阵，将两个邻接矩阵相减，得到该匹配方式对应的差别矩阵；

(4)判断是否还有其他的元素匹配方式，若有，则跳至步骤(3)，否则执行步骤(5)；

(5)N种匹配方式对应N个差别矩阵，选择其中的最优差别矩阵来表示两个流程模型的差别；

进一步，步骤(2)具体包括：

(2.1)变迁匹配，即找出两个流程模型中变迁标签相同的变迁节点对集合{(T₁,T₁’),(T₂,T₂’),…,(T_i,T_i’)}，其中T_i是第一个流程模型中的变迁节点，T_i’是第二个流程模型中的变迁节点；

(2.2)库所匹配，即找出两个流程模型中对等的库所节点对{(P₁,P₁’),(P₂,P₂’),…,(P_i,P_i’)}。一个库所的上下文环境由它的入变迁集合和出变迁集合组成：{{入变迁集合},{出变迁集合}}，即流入和流出该库所的变迁集合；两个库所节点能否映射由它们的入变迁交集集合和出变迁交集集合决定；

进一步，所述的步骤(2.2)具体包括：

(2.2.1)计算两个流程模型中所有可能匹配的库所对(P_i,P_j)的入变迁交集集合和出变迁交集集合：{{入变迁交集集合},{出变迁交集集合}}，其中P_i是第一个流程模型的一个库所节点，P_j是第二个流程模型的一个库所节点；

(2.2.2)对于入变迁交集集合和出变迁交集集合都不为空的库所对，按入变迁交集数乘以出变迁交集数的值从大到小进行匹配，已匹配过的库所节点不能再次进行匹配；

(2.2.3)对于入变迁交集集合和出变迁交集集合其中有一个为空的库所对，按不为空的集合中变迁数目从大到小进行匹配，已匹配过的库所节点不能再次进行匹配；

(2.2.4)将匹配的变迁对集合与库所对集合进行并集操作，得到元素匹配集合；

(2.2.5)重复(2.2.2)至(2.2.4)找出N(N≥1)种元素匹配方式；

进一步，步骤(2.2.5)会得到N(N>＝1)种元素匹配方式。这是因为在(2.2.2)中可能会存在相同的入变迁交集数目乘以出变迁交集数目对应多个库所对的情况，此时选择那个库所对进行匹配是随机的。同样，在(2.2.3)中同样可能出现存在相同的不为0的变迁交集数目对应多个库所对的情况。虽然优先选择哪个库所对进行匹配是随机的，但是本发明会把所有的匹配情况都找出来。

进一步，在步骤(3)中，假设两个工厂制造流程模型分别为P₁(拥有n个库所节点和m个变迁节点)和P₂(拥有x个库所节点和y个变迁节点)，P₁与P₂的匹配库所对数为a，匹配变迁数为b，则它们对应的邻接矩阵是(n+x-a+m+y-b)×(n+x-a+m+y-b)的矩阵。n+x-a+m+y-b表示{匹配的库所对集合}∪{两个流程模型中未匹配的库所集合}∪{匹配的变迁集合}∪{两个流程模型中未匹配的变迁集合}。邻接矩阵中的内容A[i][j]表示第i个节点和第j个节点之间是否存在有向边，若存在有向边则A[i][j]＝1，否则A[i][j]＝0。为了得到P₁与P₂对应的邻接矩阵A₁，A₂，需要分别填充邻接矩阵中的内容A₁[i][j]和A₂[i][j]。将两个流程模型对应的邻接矩阵A₁，A₂相减，得到表示两者差别的邻接矩阵A，A中的元素共有-1、0、1三种情况，-1表示插入边，即A₂中对应两个节点之间有边而A₁没有，0表示A₁、A₂中对应两个节点之间都有边，1表示删除边，即A₁种对应两个节点之间有边而A₂没有。

进一步，所述的步骤(5)具体包括：

(5.1)分别计算N个差别矩阵中的元素绝对值之和；

(5.2)选择和最小的差别矩阵。

本发明的技术构思是：在计算两个工厂制造流程模型的差别之前，先找到流程模型间的匹配元素，保证匹配元素的准确性。由于该步骤是流程比较的首要步骤，因此该步骤的准确率直接影响后面的差别检测准确率。在计算两个流程模型的差别时，将流程模型转换为对应的邻接矩阵，这样的方式适用于计算任意两个流程模型之间的差别而非只适用于两个相似流程模型，使得本发明的使用范围更广。

本发明的优点是：打破了只面向两个相似流程进行差别检测的局限性，将比较范围扩大到所有的流程模型，大大提高了实际的可用性。

附图说明

图1为本发明的总的流程图

图2为两个工厂制造流程模型间库所匹配案例图

图3为图2中两个工厂制造流程模型所有可能的匹配情况图

图4为图2中两个工厂制造流程模型间差别计算案例图，图4a～图4d分别是基于匹配1～4的邻接矩阵。

具体实施方式

实施例一

参考附图1

基于邻接矩阵的工厂制造流程模型差别检测方法，包括以下几个步骤：

(1)输入两个用Petri网建模的工厂制造流程模型，将流程模型中的变迁、库所节点和边解析出来；

(2)元素匹配，即找出第一个流程模型中与第二个流程模型中的对等元素，具体包括：

(2.1)变迁匹配，即找出两个流程模型中变迁标签相同的变迁节点对集合{(T₁,T₁’),(T₂,T₂’),…,(T_i,T_i’)}，其中T_i是第一个流程模型中的变迁节点，T_i’是第二个流程模型中的变迁节点；

(2.2)库所匹配，即找出两个流程模型中对等的库所节点对{(P₁,P₁’),(P₂,P₂’),…,(P_i,P_i’)}。一个库所的上下文环境由它的入变迁集合和出变迁集合组成：{{入变迁集合},{出变迁集合}}，即流入和流出该库所的变迁集合；两个库所节点能否映射由它们的入变迁交集集合和出变迁交集集合决定；找到匹配的库所对需要执行以下步骤：

(2.2.1)计算两个流程模型中所有可能匹配的库所对(P_i,P_j)的入变迁交集集合和出变迁交集集合：{{入变迁交集集合},{出变迁交集集合}}，其中P_i是第一个流程模型的一个库所节点，P_j是第二个流程模型的一个库所节点；

(2.2.2)对于入变迁交集集合和出变迁交集集合都不为空的库所对，按入变迁交集数乘以出变迁交集数的值从大到小进行匹配，已匹配过的库所节点不能再次进行匹配；

(2.2.3)对于入变迁交集集合和出变迁交集集合其中有一个为空的库所对，按不为空的集合中变迁数目从大到小进行匹配，已匹配过的库所节点不能再次进行匹配；

(2.2.4)将匹配的变迁对集合与库所对集合进行并集操作，得到元素匹配集合；

(2.2.5)重复(2.2.2)至(2.2.4)找出N(N≥1)种元素匹配方式；

(3)选取其中的一组元素匹配方式，基于该匹配方式建立两个流程模型对应的邻接矩阵，将两个邻接矩阵相减，得到该匹配方式对应的差别矩阵；

(4)判断是否还有其他的元素匹配方式，若有，则跳至步骤(3)，否则执行步骤(5)；

(5)N种匹配方式对应N个差别矩阵，选择其中的最优差别矩阵来表示两个流程模型的差别，具体包括：

(5.1)分别计算N个差别矩阵中的元素绝对值之和；

(5.2)选择和最小的差别矩阵。

实施例二

参考附图2、3、4

图2表示两个工厂制造流程模型间库所匹配案例图。最上面是待计算差别的两个用Petri网建模的模具厂制造模具的流程模型：Process 1、Process 2。由于空间的限制，我们用字母和数字的组合来代表节点表示的意义：T1表示“材料准备”，T2表示“打磨”，T3表示“抛光”，T4表示“切割”，T5表示“组装”，S和S’表示开始，E和E’表示结束，P1表示“主体材料已准备好”，P2表示“主体材料已完成”，P3表示“配件材料已准备好”，P4表示“配件材料已准备好”，P1’表示“开始打造主体材料”，P2’表示“主体材料打造完毕”，P3’表示“开始打造配件材料”，P4’表示“配件材料打造完毕”。

为了得到这两个流程模型之间的差别，需要执行以下几个步骤：

(1)输入Process 1、Process 2，将它们的变迁、库所节点和边解析出来，得到Process 1的变迁节点集合为{T1,T2,T3,T4,T5}，库所节点集合为{S,P1,P2,P3,P4,E}，边的集合为{S→T1,T1→P1,T1→P3,P1→T2,P1→T3,T2→P2,T3→P2,P2→T5,P3→T4,T4→P4,P4→T5,T5→E}；Process 2的变迁节点集合为{T1,T2,T3,T4,T5}，库所节点集合为{S’,P1’,P2’,P3’,P4’,E’}，边的集合为{S’→T1，T1→P1’，T1→P3’，P1’→T2,P3’→T3,T2→P2’,T3→P4’,P2’→T5,P3’→T4,T4→P4’,P4’→T5,T5→E’}；

(2)元素匹配，即找出Process 1中与Process 2中的对等元素，具体还包括：

(2.1)变迁匹配，即找出Process 1、Process 2中变迁标签相同的变迁节点对集合，为{T1-T1,T2-T2,T3-T3,T4-T4,T5-T5}，其中“-”表示匹配的关系；

(2.2)库所匹配，即找出两个流程模型中对等的库所节点对{(P₁,P₁’),(P₂,P₂’),…,(P_i,P_i’)}；一个库所的上下文环境由它的入变迁集合和出变迁集合组成：{{入变迁集合},{出变迁集合}}，即流入和流出该库所的变迁集合；两个库所节点能否映射由它们的入变迁交集集合和出变迁交集集合决定；找到匹配的库所对需要执行以下步骤：

(2.2.1)计算Process 1、Process 2中所有可能匹配的库所对(P_i,P_j)的入变迁交集集合和出变迁交集集合：{{入变迁交集集合},{出变迁交集集合}}，其中P_i是第一个流程模型的一个库所节点，P_j是第二个流程模型的一个库所节点；如P1的上下文环境为{{T1},{T2,T3}}，P1’的上下文环境为{{T1},{T2}}，P1和P1’的入变迁交集集合为{T1}，出变迁交集集合为{T2}；为了两个流程模型中所有可能匹配的库所对，我们建立了一张表称为初始库所匹配表，如从上往下第二部分所示：第一列中，S、Pi(1≤i≤4)、E代表的是Process>

(2.2.2)对于入变迁集合交集和出变迁集合交集都不为空的库所对，按入变迁交集数目乘以出变迁数目的值从大到小进行匹配，已匹配过的库所节点不能再次进行匹配：可以先得到P1与P3’进行匹配，然后删除P1和P3’所出现过的所有单元格；接着得到P2和P4’进行匹配，再删除P2和P4’所出现过的所有单元格，由此，该阶段结束，因为此时不存在入变迁集合交集和出变迁集合交集都不为空的库所对；

(2.2.3)对于入变迁交集集合和出变迁交集集合其中有一个为空的库所对，按不为空的集合中变迁数目从大到小进行匹配，已匹配过的库所节点不能再次进行匹配：可以先得到匹配的库所对为P3-P1’、P4-P2’、S-S’、E-E’，至此，该阶段结束；

(2.2.4)将匹配的变迁对集合与库所对集合进行并集操作，得到所有的元素匹配集合：{T1-T1,T2-T2,T3-T3,T4-T4,T5-T5,P1-P3’,P2-P4’,P3-P1’,P4-P2’,S-S’,E-E’}；

(2.2.5)重复(2.2.2)至(2.2.4)找出4种元素匹配方式，如图3所示：匹配方式1({T1-T1,T2-T2,T3-T3,T4-T4,T5-T5,P1-P1’,P2-P2’,P3-P3’,P4-P4’,S-S’,E-E’})、匹配方式2({T1-T1,T2-T2,T3-T3,T4-T4,T5-T5,P1-P3’,P2-P2’,P3-P1’,P4-P4’,S-S’,E-E’})、匹配方式3({T1-T1,T2-T2,T3-T3,T4-T4,T5-T5,P1-P1’,P2-P4’,P3-P3’,P4-P2’,S-S’,E-E’})、匹配方式4({T1-T1,T2-T2,T3-T3,T4-T4,T5-T5,P1-P3’,P2-P4’,P3-P1’,P4-P2’,S-S’,E-E’})；

(3)选取其中的一组元素匹配方式：匹配方式1，基于该匹配方式建立两个流程模型对应的邻接矩阵，将两个邻接矩阵相减，得到该匹配方式对应的差别矩阵，如图4a所示；

(4)判断是否还有其他的元素匹配方式，若有，则跳至步骤(3)，否则执行步骤(5)：依次找到匹配方式2、匹配方式3、匹配方式4并得到对应的差别矩阵，如图4b，图4c，图4d所示；

(5)4种匹配方式对应4个差别矩阵，选择其中的最优差别矩阵来表示两个流程模型的差别，具体包括：

(5.1)计算4个差别矩阵中的元素绝对值之和分别为4、6、6、8；

(5.2)选择和最小的差别矩阵，即选择图4a中的差别矩阵来表示Process 1和Process 2的差别。