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

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]。……