• 理论与算法 •

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

1. 1. 青岛大学 复杂性科学研究所，山东 青岛 266071
2. 山东省工业控制技术重点实验室，山东 青岛 266071
3. 青岛港国际股份有限公司，山东 青岛 266011
4. 山东科技大学 计算机科学与工程学院，山东 青岛 266590
• 出版日期:2021-07-01 发布日期:2021-07-09

### 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

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.