标注Petri网的最小代价计划序列估计

周广瑞，徐淑琳，郭乙运，鲁法明，岳 昊+

1.青岛大学 复杂性科学研究所，山东 青岛 266071

2.山东省工业控制技术重点实验室，山东 青岛 266071

3.青岛港国际股份有限公司，山东 青岛 266011

4.山东科技大学 计算机科学与工程学院，山东 青岛 266590

离散事件系统是由事件序列驱动的一种动态系统，可以通过一组状态和一些驱动状态改变的事件来描述[1]。典型的离散事件系统有柔性制造系统、交通系统以及通信网络系统等。Petri 网[2-3]是系统建模和分析的工具，能够简便地描述系统的演化过程。Petri 网作为一种形式化工具被用于解决许多有价值的问题，例如，柔性装配系统的监督控制[4-5]、死锁控制[6-9]、业务流程管理[10-11]等。

文献[12-13]研究了基于变迁观测的Petri 网的标识估计问题，将观测信息来源于变迁发生的Petri 网称为标注Petri 网。在标注Petri 网中估计最小初始标识，可用于解决制造系统中已知制造流程求解最小资源消耗的最优化问题。在制造系统中，规划出以最小成本完成任务的制造流程，转化为标注Petri 网中的最小代价计划序列的估计问题[14-16]。文献[14]提出了一种用于计算最小代价变迁序列的动态规划算法，并证明了标识数目是关于标注序列长度k的多项式函数，最小代价变迁序列即为所求的最小代价计划序列。文献[16]提出在标注Petri 网中可通过构建一种特殊可达图的方法来寻找最小代价变迁发生序列。

在现有的文献中，回溯法作为一种系统化的搜索方法常用于最优解的求取问题，通过目标函数和约束条件来避免无效搜索，剔除冗余节点，减少搜索的节点数目[17]。文献[18]应用回溯法求解带时间窗和同时送取货的车辆最优路径问题。文献[19]解决无线传感器网络的确定性调度问题，基于回溯法能够获得近似最优调度解，有效降低计算复杂度。文献[20]应用回溯法解决云计算中多任务执行不协调的问题，节约了计算时间。文献[21]应用回溯法解决安全业务可行性的时间和空间失衡问题，付出的空间代价较小，且具有良好的时间性能。

在制造系统标注Petri 网模型中估计最小代价计划序列，有助于达到以最小成本完成生产任务的目的。本文应用回溯法对标注Petri 网的最小代价计划序列进行估计，达到减少计算量、提高工作效率的目标。应用本文方法，当观测到一个标注时，优先发生代价小的变迁，根据深度优先搜索的策略能够获得一个当前最小代价变迁序列。以其作为约束条件，在搜索其他路径时，能够避免一些不满足约束条件的变迁发生，并剔除搜索路径中的剩余标识，最终通过遍历解空间树获得系统的最小代价变迁序列。基于回溯法求解标注Petri 网的最小代价计划序列估计问题，能够剔除冗余标识，进而删除多余搜索标识路径。现有文献中的动态规划法仅能够合并相同标识，不能剔除标识，因此回溯法的计算量更小。针对同一实例分别采用回溯法与动态规划法进行运算，由实验运行结果可知，本文方法具有更高的工作效率。

1 基本概念

N=(P,T;A,W) 为一个Petri 网，其中P={p1,p2,…,pn} 是有限库所集，T={t1,t2,…,tm} 是有限变迁集，A⊆(P×T)⋃(T×P)是流关系集合，W:A→{1,2,…}是弧上的权重函数。在Petri 网模型示意图中，空心圆圈代表库所，库所中的托肯用实心圆点表示，黑色实线代表变迁，有向箭头代表流关系。

以图1 所示的标注Petri 网模型为例，库所集P={p1,p2,…,p9}；变迁集T={t1,t2,…,t7}；标注集Σ={a,b,c,d,e}；标注函数为L(t1)=a，L(t2)=L(t3)=b，L(t4)=L(t5)=c，L(t6)=d，L(t7)=e；变迁代价为C(t1)=C(t2)=C(t5)=C(t6)=C(t7)=1，C(t3)=2，C(t4)=3。p1与p9中的托肯分别表示待加工原材料和成品，p2～p8中的托肯表示半成品，变迁t1与t7分别表示拆卸和组装。变迁t2～t8表示半成品的加工，其中一个加工过程表示为p2t2p4t4p6t6p8。

Fig.1 A labeled Petri net model图1 一个标注Petri网模型

给定一个长度为2 的标注序列ω=a b，根据ω可获得变迁发生序列σ1=t1t2和σ2=t1t3，代价分别为C(σ1)=2 和C(σ2)=3。由C(σ1)

由图1 中的Petri 网实例可知，标注序列ω=a b对应的最小代价变迁发生序列为σ1=t1t2，标注序列ω=a b c对应的最小代价变迁发生序列为σ2=t1t3t5，即标注序列ω=a b c前两个标注对应的最小代价变迁发生序列将被替代。当标注序列发生改变时，其对应的最小代价变迁发生序列也可能发生改变，因此需要计算每条搜索路径中变迁发生序列的总代价。

2 基于回溯法求取最小代价变迁序列

2.1 解空间树的构建

复杂问题通常有较多的可行解，它们构成了问题的解空间。若没有确定正确的解空间就开始搜索，可能会产生较多满足约束条件的重复可行解或者错误解。解空间用如图2 所示的解空间树来表示。根节点作为初始状态位于解空间树的第一层，根据不同的约束条件对根节点做出选择后得到的叶子节点位于第二层。以此类推，解空间树的一个可行解为从树的根节点到叶子节点的路径[17]。

Fig.2 Model of solution-space tree图2 解空间树模型

2.2 最小代价变迁序列的获取

基于回溯法估计标注Petri 网的最小代价计划序列，剔除其他路径中不满足约束条件的标识，而非直接剪掉一条路径。设lc是当前最小总代价，当搜索到一个标识M后，满足，存在以下两种情况：

（1）若C(σ)≤lc，则该标识是构成搜索路径的部分解，且继续搜索下一个标识。

（2）若C(σ)>lc，则该标识不是构成搜索路径的部分解，结束该路径的搜索。

在图3 所示的标识路径搜索空间示意图中，给定标注序列ω=l1l2…lk，假设成立，且C(t1)lc，则回溯至祖先标识并搜索其他路径，反之继续搜索该路径。由于同一个标识可能出现在多条搜索路径上，为了清楚地显示每条路径的情况，因此不合并搜索路径中的相同标识。

Fig.3 Schematic diagram of evolution of marking paths图3 标识路径演化示意图

2.3 算法

给定一个长度为k的标注序列ω=l1l2…lk(lj∈Σ,j=1,2,…,k)，观测到标注lj，j∈{1,2,…,k}，集合Vj包含所有与标注lj相关的节点v。四元组节点v=(level,marking,sequence,cost)，其中level为节点层次的序号；marking为节点相关标识；sequence为对应的变迁发生序列；cost为变迁序列的代价。若后继需考虑节点v，则flag(v)=0；反之flag(v)=1。

算法1计算最小代价变迁序列

输入：一个标注Petri 网Nl=(N,M0,Σ,L)，一个长度为k的标注序列ω=l1l2…lk(lj∈Σ,j=1,2,…,k)。

输出：包含所有最小代价变迁序列的集合S和最小代价lc。

观测到标注lj，j∈{1,2,…,k}，若标注lj对应多个变迁，则选择代价较小的变迁优先发生。创建一个节点v之后，当v.cost≤lc时，若集合Vj中不存在节点v1，使得v1.marking=v.marking，则flag(v)=0，节点v进栈S，更新集合Vj=Vj∪{v}；若集合Vj中存在节点v1，使得v1.marking=v.marking，则需考虑以下三种情况：

（1）若v.cost

（2）若v.cost>v1.cost，则flag(v)=1，节点v不进栈S；

（3）若v.cost>v1.cost，则flag(v)=0，节点v进栈S，更新集合Vj=Vj∪{v}。

当j=k时，若v.cost

算法1 首先通过栈S获得节点ϑ，根据栈的性质，可以直接得到代价较小的变迁，避免发生代价较大的变迁。其次，通过比较发生节点变迁代价的大小，能够确保该节点通过最小代价变迁发生获得。最后，能够避免在搜索路径中出现大于当前最小总代价的变迁序列，从而使得算法1 能够避免无效搜索，减少搜索的节点数目。

3 应用实例与结果分析

3.1 应用实例

以图4 所示文献[14]中的一个包含两台并联机器的制造系统标注Petri 网模型为例，标注集Σ={a,b,c,d,e,f,g,h} ；库所集P={p1,p2,…,p10} ；变迁集T={t1,t2,…,t12} ；初始标识为M0=[1 1 0 2 0 0 2 0 0 0]T；标注函数为L(t3)=L(t5)=a，L(t4)=L(t6)=b，L(t7)=L(t9)=c，L(t8)=L(t10)=d，L(t1)=e，L(t2)=f，L(t11)=g，L(t12)=h；变迁代价为C(t1)=C(t2)=C(t4)=C(t5)=C(t9)=5，C(t3)=C(t7)=C(t8)=C(t10)=10，C(t6)=C(t11)=C(t12)=15。

Fig.4 Labeled Petri net model for manufacturing system图4 一个制造系统的标注Petri网模型

给定长度为10 的标注序列ω=e e f f a a b c c d，根据这个序列，可得图5 所示的Petri网模型的标识解空间示意图。应用算法1，基于回溯法求取最小代价计划序列的标识路径搜索空间如图6 所示。表1 总结了每条标识路径中变迁发生的信息，每条路径的标识序列和标识剔除情况如表2 所示。在图6 所示的标识路径搜索空间中，路径①的标识集合Z(ω)={M1,M2,M3,M4,M51,M61,M71,M81,M91,M10}，最小代价为lc=55。图5 所示的标识解空间中存在多条路径，回溯至祖先标识M51并搜索路径②。路径②的标识集合为Z(ω)={M1,M2,M3,M4,M51,M62,M72,M82,M91,M10}，当变迁发生序列为σ2=t1t1t2t2t5t3t4t9t7时，C(σ2)=55，若继续发生变迁t8，则C(σ2)=65，由于C(σ2)>lc，标注d对应的变迁t8不应发生，此时剔除标识M10。以同样的方式搜索剩余路径，获得最小代价变迁序列集合S={t1t1t2t2t5t5t4t9t9t8}，最小代价为lc=55。

Table 1 Information about firing of transitions in marking paths表1 标识路径上的变迁发生信息

Fig.5 Marking solution space established according to labeled sequence ω=eeffa a b ccd图5 根据标注序列ω=eeffa a b ccd 构建的标识解空间

Table 2 Marking sequences and the number of eliminated markings表2 标识序列与标识剔除数目

3.2 结果分析

在上述包含两台并联机器的制造系统标注Petri网模型中，基于回溯法与动态规划法构建的标识解空间规模相同，因此仅给出基于回溯法构建的标识解空间。在标识路径搜索空间中不合并相同的标识，由表2 可知，应用回溯法搜索的标识数目比应用动态规划法搜索的标识数目减少约17%。对于给定的标注序列ω=e e f f a a b c c d，当观测到的标注序列长度小于等于4 时，标注e和f仅对应一个变迁，即只存在一条搜索路径，因此应用回溯法与动态规划法搜索的标识数目相同；当标注序列长度大于4时，可以剔除路径中不满足约束条件的标识，合并相同的标识后，回溯法比动态规划法减少搜索的标识数目由表3 给出。根据两种方法处理该实例的结果可知，基于回溯法估计标注Petri 网的最小代价计划序列可以减少计算量。

本文提出一种方法，基于回溯法估计标注Petri网的最小代价计划序列。虽然没有从理论上降低蛮力穷举方法与文献[14]所提方法的计算复杂度，但是本文方法在搜索标识的过程中，通过深度优先策略可以避免不满足约束条件的变迁发生，从而减少了搜索的标识数目，提高了工作效率。

Fig.6 Searching-space of marking paths图6 标识路径搜索空间

Table 3 Comparative analysis of number of markings表3 标识数目对比分析

4 结束语

本文研究制造系统标注Petri 网模型的最小代价计划序列估计问题，提出了一种基于回溯法求取最小代价变迁序列的算法。根据深度优先搜索策略可以获得标注Petri 网的一个当前最小代价变迁序列，以该序列的代价作为其他路径搜索部分解的约束条件，满足约束条件的一条完整路径即对应问题的一个解。实例结果表明，本文算法能够剔除冗余标识，缩小搜索空间规模，提高工作效率。后续工作将结合本文方法，在含有不可观测变迁的标注Petri 网中估计最小代价计划序列。