Journal of Frontiers of Computer Science and Technology ›› 2021, Vol. 15 ›› Issue (7): 1350-1358.DOI: 10.3778/j.issn.1673-9418.2011035

• Theory and Algorithm • Previous Articles    

Estimation of Least-Cost Planning Sequence for Labeled Petri Nets

ZHOU Guangrui, XU Shulin, GUO Yiyun, LU Faming, YUE Hao   

  1. 1. Institute of Complexity Science, Qingdao University, Qingdao, Shandong 266071, China
    2. Shandong Key Laboratory of Industrial Control Technology, Qingdao, Shandong 266071, China
    3. Qingdao Port International Co., Ltd., Qingdao, Shandong 266011, China
    4. College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong 266590, China
  • Online:2021-07-01 Published:2021-07-09

标注Petri网的最小代价计划序列估计

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

  1. 1. 青岛大学 复杂性科学研究所,山东 青岛 266071
    2. 山东省工业控制技术重点实验室,山东 青岛 266071
    3. 青岛港国际股份有限公司,山东 青岛 266011
    4. 山东科技大学 计算机科学与工程学院,山东 青岛 266590

Abstract:

To solve the least-cost planning sequence problem of a manufacturing system which is modeled by labeled Petri nets, an algorithm based on backtracking method is proposed. Given a labeled Petri net with its structure and an initial marking, the searching stages are divided into parts according to the given labeled sequence. In each stage, the transition with the minimal cost fires at first. With the observation of all the labels following this rule, the sum of the costs of transitions in the firing sequence is the minimum total cost. The least-cost planning sequence and the corresponding total cost are stored. The proposed method traverses the solution space tree according to the depth-first strategy. By taking the current minimum total cost as the constraint condition, the markings and the sequence of transitions that do not need to be searched can be eliminated in other paths. Therefore, the searching space is reduced. An illustrative example shows the feasibility of the method. Compared with the execution of dynamic programming method, the proposed method needs a smaller amount of calculation and achieves higher work efficiency.

Key words: discrete event systems, labeled Petri nets, backtracking method, least-cost planning sequences

摘要:

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

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