EUVIMEDEUVIMED entdecken
Crossref

State Transfer Graph and Its Generating Methods for Place-Timed Petri Nets-Based Scheduling

Jiazhong Zhou, Jiliang Luo

IEEE Transactions on Automation Science and Engineering · 2026 · 23 · 9293-9306

DOI: 10.1109/tase.2026.3689952 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Automation Science and Engineering, 2026. Verfasst von Jiazhong Zhou und 1 weiteren Autor:innen. Gefördert von: Natural Science Foundation of Xiamen, China,, Fujian Provincial Natural Science Foundation of China, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A state transfer graph and its generation algorithm are introduced to represent the state space of the place-timed Petri net model for a specific discrete event system. For a bounded place-timed Petri net possessing infinite states, it is proven that the state transfer graph comprises a set of finite nodes and an optimal schedule leading the net from an initial state to a target state in the minimal time. However, the size of a state transfer graph grows quite quickly with the net size and the total amount of tokens in the initial marking, which complicates the efficient calculation of an optimal schedule, particularly for real-world systems. To address this issue, two advanced rules are proposed to judge whether a state node is old and cut off when generating a state transfer graph. As a result, two variants of a state transfer graph are obtained, and it is proven that they all contain optimal schedules and are smaller than the state transfer graph, allowing more efficient solutions to scheduling issues. The state transfer graph provides a theoretic foundation for graph search algorithms, such as the Dijkstra, greedy-first, and A* algorithms, for scheduling problems of Petri nets. The proposed approach is demonstrated and verified through a flexible manufacturing benchmark system. The experimental results indicate that the state transfer graphs contain optimal schedules. Additionally, the old-state node judgment rules are effective in significantly reducing the computational burden of graph search algorithms for Petri nets. Note to Practitioners—This paper addresses the optimal scheduling problem in discrete event systems, such as flexible manufacturing systems. Although timed Petri nets are a common formalism for modeling such systems, the resulting “state explosion” frequently renders the search for an optimal schedule with minimal makespan computationally prohibitive or even infeasible in practical applications. We propose a refined approach to generate a state transfer graph using pruning rules that identify and remove redundant state nodes. This approach reduces the size of the graph while guaranteeing that the optimal schedule is preserved. For practitioners, this method provides a high-efficiency graph foundation for implementing search algorithms such as Dijkstra or A*. The proposed method is suitable for practical systems with complex timing behavior and limited resources. The case study on a flexible manufacturing system demonstrates that the state transfer graphs retain optimal solutions and lower computational effort, making the approach practical for real-world scheduling problems.

Förderung

  • Natural Science Foundation of Xiamen, China,
  • Fujian Provincial Natural Science Foundation of China
  • National Natural Science Foundation of China
  • Foundation of Huaqiao University

Zitieren

APA

Zhou, J., & Luo, J. (2026). State Transfer Graph and Its Generating Methods for Place-Timed Petri Nets-Based Scheduling. IEEE Transactions on Automation Science and Engineering, 23, 9293-9306. https://doi.org/10.1109/tase.2026.3689952

Vancouver

Zhou J, Luo J. State Transfer Graph and Its Generating Methods for Place-Timed Petri Nets-Based Scheduling. IEEE Transactions on Automation Science and Engineering. 2026;23:9293-9306. doi:10.1109/tase.2026.3689952

BibTeX
@article{Zhou2026,
  author = {Zhou, Jiazhong and Luo, Jiliang},
  title = {State Transfer Graph and Its Generating Methods for Place-Timed Petri Nets-Based Scheduling},
  journal = {IEEE Transactions on Automation Science and Engineering},
  year = {2026},
  volume = {23},
  pages = {9293--9306},
  doi = {10.1109/tase.2026.3689952}
}
Kostenlos starten →