基于Petri网的离散事件系统初始资源优化配置

郝真鸣,孙丹丹，郝晋渊,陈凡，葛卫华,李兵兵,冉宁

(1.河北大学 电子信息工程学院，河北 保定 071002；2.河北大学 中央兰开夏传媒与创意学院，河北 保定 071002)

离散事件系统(discrete event system，DES)是由不规则时间间隔出现的事件(离散事件)序列驱动，并按照一定的运行规则相互作用导致状态演化的一种动态系统[1].大部分人造系统从逻辑层面都可抽象为DES，例如柔性制造系统、通信网络系统、交通控制系统等.DES初始资源优化配置问题是指使用最少资源成本完成系统生产要求，对于降低生产成本、提高经济效益具有重要意义[2].因此，DES资源优化配置成为近年来的研究热门问题.

Petri网自20世纪60年代被提出以来，由于具有强大的建模分析能力以及图形和数学双重表示、高效分析离散事件系统等优点[3]，而被应用于故障诊断[4-8]、监控器综合[9-12]、资源优化配置的研究.曹蕊等[13]利用Petri网提出了基于业务流程模型抽象的流程配置优化，对抽象模型添加配置信息，实现了配置优化分析.杨欣等[14]以资源配置混杂Petri网为研究模型，提出了一种适用于混杂系统动态生产调度的模型以及优化方法，增强了混杂生产过程应对突发事件的能力.廖敏等[15]基于工作流活动，利用在传统Petri网的基础上的扩展Petri网建立了工作流模型，对制造资源的调度过程进行了仿真，提高了资源的共享效率以及企业协作性.宋海翔等[16]基于传统Petri网改进定义了一种带有资源约束的Petri网，对业务流程进行了建模和优化，对资源配置进行了优化.Li等[17]提出了一种在已知标识Petri网中估计最小初始标识的递归算法，并进一步讨论了具有低复杂度的启发式算法，该算法能有效确定初始化时执行指定任务所需的最小资源.

经过上述分析可发现，虽然Petri网适合于DES资源优化配置问题，但是几乎所有基于Petri网的方法都需要计算系统状态空间，导致复杂度较高，难以满足实际要求.为了避免计算系统的状态空间，本文基于Petri网提出一种将DES初始资源优化配置问题转化为整数线性规划(integer linear programming,ILP)问题[18]的方法.首先，基于Petri网对DES建立数学模型，并利用Petri网的结构特性和状态方程将初始资源优化配置问题转化为ILP问题；其次，利用Lingo求解ILP问题；最后，通过实例验证提出方法的有效性.实验结果表明，提出的算法简单高效，具有较强的实用性.

1 Petri网基础

1.1 基本概念

Petri网的结构表示为N=(P,T,F,W)，其中P={p1,p2,…,pn}表示库所集合；S={t1,t2,…,tm}表示变迁集合；F⊆(P×T)∪(T×P)表示流关系，即库所与变迁之间的连接关系；W为权值函数，为每一条弧赋予1个正整数权值.

令x∈P∪S为一个Petri网的节点.它的输入集定义为·x={y∈P∪S|(y,x)∈F}；它的输出集定义为x·={y∈P∪S|(x,y)∈F}.

一个Petri网N的关联矩阵A是以|P|×|S|为序标的整数矩阵,定义为

A(p,t)=W(t,p)-W(p,t)

,

(1)

其物理意义是变迁t发生后库所p中托肯数的变化量.库所p对应的行向量称为p的关联向量，记作A(p,·)，变迁t对应的列向量称为t的关联向量，记作A(·,t).

一个Petri网的标识是一个向量M∶P→B，其中B表示自然数集合.库所中的标识称为托肯(token)，M(p)表示库所p中的托肯数.(N,M0)称为一个网系统，其中N是Petri网结构，M0是初始标识.

一个变迁t∈S在标识M下是使能的(enabled)当且仅当

∀p∈·t,M(p)≥W(p,t),

(2)

记M[t〉.M[σ〉表示变迁序列σ=t1t2…tk在标识M下是使能的.在初始标识M0下使能的所有变迁序列定义为L(N,M0)，即

L(N,M0)={σ∈S*|M0[σ〉}.

(3)

一个Petri网的节点序列x1x2…xn称为一条路径,如果xi+1∈xi·，其中xi∈P∪S,i∈{1,2,…,n-1}.如果从节点xi到节点xj之间存在一条路径，则称xj可由xi进入.如果一条路径的首节点就是尾节点，则该路径称为回路.无回路的Petri网称为无环Petri网.

1.2 状态方程

在一个Petri网中，变迁t发生后，网系统跃迁到另一个状态,产生一个新标识M′,使得∀p∈P，M′(p)=M(p)+A(p,t),表示在标识M下发生变迁t到达标识M′,记为M[t〉M′.在Petri网N中从标识M出发能够到达的全部标识的集合称为(N,M)的可达标识集，表示为R(N,M).

M′=M0+A·y，

(4)

满足上述状态方程的标识集合称为潜在的可达标识集，记作PR(N,M0).然而，任何一个可达标识都满足状态方程(4)，但满足方程(4)的标识并不一定是可达的，即R(N,M0)⊆PR(N,M0).因此状态方程仅提供了一个标识可由初始标识到达的必要条件.

定理1[19]令N是一个无环Petri网.

2)标识M′从M0处可达当且仅当存在一个非负整数解y满足状态方程M′=M0+A·y，即R(N,M0)=PR(N,M0).

为了避免计算系统状态空间，本文利用状态方程法求解初始资源优化配置问题，因此根据定理1做出如下假设：

假设1Petri网是无环的.

2 初始资源优化配置算法

本文考虑的初始资源优化配置问题可描述为问题1.

问题1给定一个Petri网模型，计算初始标识M0满足以下2个条件：

1) 变迁ti发生ki次，其中ki≥0，i=1,2,…，|S|.

例1一个Petri网模型如图1所示，其中库所集P={p1,p2,p3,p4}，变迁集S={t1,t2,t3}.

图1 Petri网模型Fig.1 Model of Petri net

其关联矩阵为

现根据问题1考虑图1所示Petri网的初始资源优化配置问题.计算初始标识M0满足以下2个条件：

1)t1、t2各发生1次，t3无发生次数限制.

令xi为库所pi中的托肯数，即M0=(x1,x2,x3,x4)T；无发生次数限制变迁t3的发生次数表示为z3，即y=(1,1,z3)T.根据条件1)以及Petri网的固有属性，上述问题包含如下4个约束条件：

2)对于任意p∈P，满足M0(p)≥0.

(5)

(6)

综上所述，问题1可由算法1求解.虽然求解ILP的复杂度在理论上是不确定的，但大量实验结果表明现有的Gurobi、Lingo等软件在求解这类问题上具有良好的计算效率，本文利用Lingo求解ILP问题.命题1证明了算法1的正确性.

算法1

输入：Petri网N、问题1.

输出：初始资源优化配置结果.

步骤1:判断Petri网是否无环；若不是，退出算法；若是，执行步骤2.

步骤2:令M0=(x1,x2，…,x|P|)T.

步骤3:写出问题1的目标函数：

步骤4:写出问题1的约束条件集合：

步骤5:求解上述ILP问题，输出计算结果.

命题1算法1所求的解是问题1的解.

3 实例分析

图2 Petri网模型Fig.2 Model of Petri net

图2为某自动制造系统的Petri网模型，其中库所集P={p1,p2,p3,p4,p5,p6,p7,p8}，变迁集S={t1,t2,t3,t4,t5,t6,t7}.

其关联矩阵

现根据问题1考虑该模型的初始资源优化配置问题：计算初始标识M0满足以下2个条件：

1) 变迁t1、t2、t3各发生1次，t4、t5各发生2次，其余变迁无发生次数限制.

(7)

(8)

图3 Lingo代码Fig.3 Code of Lingo

图4 Lingo计算结果Fig.4 Results of Lingo

4 结论

基于Petri网提出了一种DES初始资源优化配置方法.根据Petri网的结构化特性和状态方程，将初始资源优化配置问题转化为ILP问题，并利用Lingo软件求解.实验结果表明，提出的算法简单高效,具有较强的实用性，可为现实中DES资源优化配置提供理论借鉴.

本文只考虑了可观事件存在的情况，然而DES中还可能存在不可观事件.因此，在可观事件与不可观事件同时存在的情况下进行资源配置则是未来的研究方向.