计算机科学与探索

作者：周广瑞, 徐淑琳, 郭乙运, 鲁法明, 岳昊

单位：1. 青岛大学 复杂性科学研究所，山东 青岛 2660712. 山东省工业控制技术重点实验室，山东 青岛 2660713. 青岛港国际股份有限公司，山东 青岛 2660114. 山东科技大学 计算机科学与工程学院，山东 青岛 266590

关键词：离散事件系统,标注Petri网,回溯法,最小代价计划序列

针对制造系统的标注Petri网模型，提出一种基于回溯法估计系统最小代价计划序列的算法。已知标注Petri网模型的网结构与初始标识，根据给定的标注序列划分搜索阶段，每个标注对应的代价较小的变迁优先发生。按此规则观测到所有的标注后，对应的变迁发生序列代价的加和为最小总代价，并储存最小代价计划序列及总代价。按照深度优先策略遍历解空间树，以当前最小总代价为约束条件，剔除其他路径中不必搜索的标识以及变迁发生序列，缩小搜索空间。通过实例验证了该方法的可行性，与动态规划法执行结果相比，提出的方法能够实现更少的计算量和更高的工作效率。

来源：2021年第7期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2021年第7期