Abstract: In order to obtain the minimum resources required for initialization of manufacturing systems and realize the optimal resource allocation, these systems are modeled by labeled Petri nets, and this paper offers the study of the estimation problem of the minimum initial marking in labeled Petri nets. Given a labeled Petri net, a new algorithm for estimating the minimum initial marking is proposed based on dynamic programming when the unobservable transitions form an acyclic subnet. After a given sequence of labels is observed, the limit of the number of unobservable transitions is relaxed, and the schematic diagram of node evolution is constructed according to the proposed algorithm. When the same firing vector appears, only the current minimal initial marking estimation is retained, and the total number of tokens of the minimal initial marking estimation is compared based on the process of node evolution. An example of the labeled Petri net model of the manufacturing system is given to test the effectiveness of the algorithm. The minimum initial marking is[1000]^T, and the corresponding transition sequence is t₁t₃t₄t₆,which meets the structural requirements of the given labeled Petri nets. Compared with the existing algorithm using dynamic programming, the proposed algorithm can obtain the minimum initial marking estimatation with a smaller total number of tokens.

Key words: discrete event systems, estimation of initial marking, Petri nets, unobservable transitions, dynamic programming

摘要： 为获得制造系统初始化时的最小资源以实现最优资源分配，利用标注Petri网对系统进行建模，并研究标注Petri网的最小初始标识估计问题。给定一个标注Petri网，在不可观测变迁组成无环子网的情况下，基于动态规划提出一种新的最小初始标识估计算法。在观察到给定的标注序列后，放宽不可观测变迁发生个数的限制，并根据该算法构建节点的演化过程。当出现相同的发生数向量时，仅保留当前极小的初始标识估计，并通过节点的演化过程对极小初始标识估计的托肯总数进行对比。为验证算法的有效性，给出一个制造系统的标注Petri网模型实例，最终得到的最小初始标识为［1000］^T，且对应的变迁发生序列为t₁t₃t₄t₆，满足给定标注Petri网的结构要求。实验结果表明，与传统基于动态规划的算法相比，该算法获得的最小初始标识估计具有更小的托肯总数。

关键词: 离散事件系统, 初始标识估计, Petri网, 不可观测变迁, 动态规划

CLC Number: 

• TP393