徐淑琳，周广瑞，岳 昊，2

（1.青岛大学自动化学院，山东青岛 266071；2.青岛大学复杂性科学研究所，山东青岛 266071）

0 概述

Petri 网是一种用于离散事件系统建模、分析和控制的工具，具有图形和数学的双重表现形式且可有效描述系统行为。近年来，Petri 网被应用于交通系统［1］和柔性装配制造系统［2］等多种实际系统中，且在系统安全及可靠性分析［3-4］、业务流程分析［5-6］、交互控制［7］以及Web 服务分析和替代［8］中也有广泛应用。随着实际系统规模的增大，标识估计对离散事件系统的诊断［9］和控制器设计［10-11］等具有重要的作用。

关于Petri 网中标识估计问题的研究已经取得显著成果［12-13］。文献［12］基于对标注序列的观察，讨论了初始标识已知的Petri 网中的标识估计问题，并指出标识集可用一组具有固定结构的线性不等式来描述。文献［13］也研究了标识估计问题，并证明所有可能的标识数目是关于k的函数。最小初始标识的估计成为当今研究的热点之一，例如文献［14］讨论了含有可观测变迁的标注Petri 网中的最小初始标识估计问题，并提出一种最小初始标识估计算法。文献［15］将文献［14］中的结果扩展到含有不可观测变迁的标注Petri 网中。文献［16］提出一种用于估计由标注Petri 网中的最小代价计划序列的算法。文献［17］通过使用基可达图寻找标注Petri 网中最小代价变迁序列。

针对不可观测变迁的存在给求解标注Petri 网建模制造系统中的最小资源带来困难的问题，本文放宽对不可观测变迁发生个数的限制，且允许可观测在变迁前至多有2 个不可观测变迁发生。……