Admissible Heuristic Design for Optimally Scheduling Resource Allocation Systems With Generalized Timed Petri Nets

Yuanzheng Xiao; Yangqing Gao; Haoran Wu; Bo Huang

doi:10.1109/JAS.2025.125777

Volume 13 Issue 7

Jul. 2026

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 18.3, Top 1 (SCI Q1)

CiteScore: 28.2, Top 1% (Q1)
Google Scholar h5-index: 95， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2026 > 13(7): 1572-1583

Y. Xiao, Y. Gao, H. Wu, and B. Huang, “Admissible heuristic design for optimally scheduling resource allocation systems with generalized timed petri nets,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 7, pp. 1572–1583, Jul. 2026. doi: 10.1109/JAS.2025.125777

Citation:

Y. Xiao, Y. Gao, H. Wu, and B. Huang, “Admissible heuristic design for optimally scheduling resource allocation systems with generalized timed petri nets,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 7, pp. 1572–1583, Jul. 2026. doi: 10.1109/JAS.2025.125777

Citation:

PDF( 3171 KB)

Admissible Heuristic Design for Optimally Scheduling Resource Allocation Systems With Generalized Timed Petri Nets

doi: 10.1109/JAS.2025.125777

Funds: This work was in part supported by the Special Foundation of Jiangsu Province of China for the Transformation of Scientific and Technological Achievements (BA2023022)

More Information

Author Bio:
Yuanzheng Xiao (Student Member, IEEE) received her B.S. degree in computer science and technology from Nanjing University of Science and Technology in 2025. She is currently pursuing her M.S. degree at the University of Science and Technology of China. Her research interests include Petri nets, intelligent search algorithms, and manufacturing systems

Yangqing Gao received her B.S. degree in computer science and technology from Nanjing University of Science and Technology in 2025. She is now pursuing her M.S. degree at Tongji University. Her research interests include discrete event systems, Petri nets, and intelligent manufacturing systems

Haoran Wu received his B.S. degree in computer science and technology from Nanjing University of Science and Technology (NUST) in 2025. He is currently pursuing his M.S. degree at Fudan University. His research interests include reinforcement learning, Petri nets, and multi-agent systems

Bo Huang (Senior Member, IEEE) received his B.S. and Ph.D. degrees from Nanjing University of Science and Technology (NUST) in 2002 and 2006, respectively. He joined NUST in 2007 and is currently a Professor at the School of Computer Science and Engineering. He was a Visiting Scholar at the University of Missouri – Kansas City (UMKC), MO, USA, in 2013, and at the New Jersey Institute of Technology (NJIT), Newark, NJ, USA, from 2014 to 2015 and again from 2019 to 2020. His research interests include discrete event systems, Petri nets, intelligent manufacturing, and applications in transportation and robotic systems. He has led more than 10 research projects, authored one book, and published over 70 papers in these fields. He has also served as a reviewer for over 10 international journals and as a Publication Chair, Session Chair, or Program Committee member for more than 10 academic conferences
Corresponding author: Bo Huang, e-mail: huangbo@njust.edu.cn
Received Date: 2025-05-07
Accepted Date: 2025-08-05

Available Online: 2026-07-21

Abstract

Abstract

The heuristic function in Petri-net-based A^* search directly influences both the search efficiency and solution quality for scheduling resource allocation systems (RASs). In the literature, some heuristic functions have been proposed, but most of them fail to consider key aspects such as token remaining time, alternative routes, weighted arcs, multiple resource copies, and batch processing ability, which are common in the place-timed Petri nets (PNs) for RASs. This paper proposes two novel heuristic functions. Both are admissible, guaranteeing the optimality of the obtained schedules. In addition, they are designed not only for ordinary PNs but also for generalized ones, which may have arc weights greater than one. They can effectively handle RAS PNs with alternative routes, weighted arcs, multiple resource copies, and batch processing capability. Most importantly, the new heuristics, especially the second one, are highly informed, leading to faster searches for optimal schedules compared to existing heuristics for generalized PNs. Experiments on several benchmark PNs of RASs have been conducted to demonstrate the effectiveness and efficiency of our methods.
- A^* search,
- heuristic function,
- resource allocation system,
- scheduling,
- timed Petri net

FullText(HTML)

References(28)

References

[1]	B. Huang, M. C. Zhou, X. S. Lu, and A. Abusorrah, “Scheduling of resource allocation systems with timed Petri nets: A Survey,” ACM Comput. Surv., vol. 55, no. 11, pp. 1–27, Feb. 2023. doi: 10.1145/3570326
[2]	Y. Dong, N. Wu, and Z. Li, “State-based opacity verification of networked discrete event systems using labeled Petri nets,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 5, pp. 1274–1291, May 2024. doi: 10.1109/JAS.2023.124128
[3]	Q. Zhu, B. Li, Y. Hou, H. Li, and N. Wu, “Scheduling dual-arm multi-cluster tools with regulation of post-processing time,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 8, pp. 1730–1742, Aug. 2023. doi: 10.1109/JAS.2023.123189
[4]	D. Y. Lee and F. DiCesare, “Scheduling flexible manufacturing systems using Petri nets and heuristic search,” IEEE Trans. Robot. Autom., vol. 10, no. 2, pp. 123–132, Apr. 1994. doi: 10.1109/70.282537
[5]	H. H. Xiong and M. C. Zhou, “Scheduling of semiconductor test facility via Petri nets and hybrid heuristic search,” IEEE Trans. Semicond. Manuf., vol. 11, no. 3, pp. 384–393, Aug. 1998. doi: 10.1109/66.705373
[6]	B. Huang, Y. Sun, Y.-M Sun, and C.-X Zhao, “A hybrid heuristic search algorithm for scheduling FMS based on Petri net model,” Int. J. Adv. Manuf. Technol., vol. 48, no. 9, pp. 925–933, Jun. 2010. doi: 10.1007/s00170-009-2329-8
[7]	O. T. Baruwa and M. A. Piera, “Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach,” J. Manuf. Syst., vol. 35, pp. 120–135, Apr. 2015. doi: 10.1016/j.jmsy.2014.11.009
[8]	G. Mejía, “An intelligent agent-based architecture for flexible manufacturing systems having error recovery capability,” Doctoral dissertation, Lehigh University, Bethlehem, PA, USA, 2003.
[9]	G. Mejía and N. G. Odrey, “An approach using Petri nets and improved heuristic search for manufacturing system scheduling,” J. Manuf. Syst., vol. 24, no. 2, pp. 79–92, Feb. 2005. doi: 10.1016/S0278-6125(05)80009-3
[10]	J. Luo, K. Xing, M. C. Zhou, X. Li, and X. Wang, “Deadlock-free scheduling of automated manufacturing systems using Petri nets and hybrid heuristic search,” IEEE Trans. Syst. Man Cybern.: Syst., vol. 45, no. 3, pp. 530–541, Mar. 2015. doi: 10.1109/TSMC.2014.2351375
[11]	X. Wang, K. Xing, Y. Feng, and Y. Wu, “Scheduling of flexible manufacturing systems subject to no-wait constraints via Petri nets and heuristic search,” IEEE Trans. Syst. Man Cybern.: Syst., vol. 51, no. 10, pp. 6122–6133, Oct. 2021. doi: 10.1109/TSMC.2019.2958494
[12]	G. Mejía, J. P. Caballero-Villalobos, and C. Montoya, “Petri nets and deadlock-free scheduling of open shop manufacturing systems,” IEEE Trans. Syst. Man Cybern.: Syst., vol. 48, no. 6, pp. 1017–1028, Jun. 2018. doi: 10.1109/TSMC.2017.2707494
[13]	D. Lefebvre and F. Basile, “An approach based on timed Petri nets and tree encoding to implement search algorithms for a class of scheduling problems,” Inform. Sciences, vol. 559, pp. 314–335, Jun. 2021. doi: 10.1016/j.ins.2020.12.087
[14]	O. T. Baruwa, M. A. Piera, and A. Guasch, “Deadlock-free scheduling method for flexible manufacturing systems based on timed colored Petri nets and anytime heuristic search,” IEEE Trans. Syst. Man, Cybern. Syst., vol. 45, no. 5, pp. 831–846, May 2015. doi: 10.1109/TSMC.2014.2376471
[15]	J. Luo, M. Zhou, and J.-Q. Wang, “AB&B: An anytime branch and bound algorithm for scheduling of deadlock-prone flexible manufacturing systems,” IEEE Trans. Autom. Sci. Eng., vol. 18, no. 4, pp. 2011–2021, Oct. 2021. doi: 10.1109/TASE.2020.3029737
[16]	J. Lv and B. Huang, “A Petri-net-based anytime A* search for scheduling resource allocation systems,” IEEE Trans. Ind. Inform., vol. 20, no. 2, pp. 2865–2872, Feb. 2024. doi: 10.1109/TII.2023.3296909
[17]	K. Xing, L. Han, M. C. Zhou, and F. Wang, “Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy,” IEEE Trans. Syst., Man, Cybern. B, vol. 42, no. 3, pp. 603–615, Jun. 2012. doi: 10.1109/TSMCB.2011.2170678
[18]	X. M. Liu, L. Pan, and H. Zheng, “Schedule optimization of time Petri nets based on ant colony systems,” Appl. Mech. Mater., vol. 263–266, pp. 1733–1739, Dec. 2012. doi: 10.4028/www.scientific.net/amm.263-266.1733
[19]	Z. Zhao, S. Liu, M. Zhou, D. You, and X. Guo, “Heuristic scheduling of batch production processes based on Petri nets and iterated greedy algorithms,” IEEE Trans. Autom. Sci. Eng., vol. 19, no. 1, pp. 251–261, Jan. 2022. doi: 10.1109/TASE.2020.3027532
[20]	F. Yuan, B. Huang, J. Lv, and M. Cui, “Scheduling AMSs with generalized Petri nets and highly informed heuristic search,” Comput. Oper. Res., vol. 175, Art. no. 106912, Mar. 2025. doi: 10.1016/j.cor.2024.106912
[21]	B. Huang and M. C. Zhou, Supervisory Control and Scheduling of Resource Allocation Systems: Reachability Graph Perspective. Hoboken, NJ, USA: John Wiley & Sons, 2020.
[22]	B. Huang, X.-X Shi, and N. Xu, “Scheduling FMS with alternative routings using Petri nets and near admissible heuristic search,” Int. J. Adv. Manuf. Technol., vol. 63, no. 9, pp. 1131–1136, Dec. 2012. doi: 10.1007/s00170-012-3958-x
[23]	B. Huang, M. C. Zhou, A. Abusorrah, and K. Sedraoui, “Scheduling robotic cellular manufacturing systems with timed Petri net, A* search, and admissible heuristic function,” IEEE Trans. Autom. Sci. Eng., vol. 19, no. 1, pp. 243–250, Jan. 2022. doi: 10.1109/TASE.2020.3026351
[24]	Y. Chen and Z. Li, “Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems,” Automatica, vol. 47, no. 5, pp. 1028–1034, May 2011. doi: 10.1016/j.automatica.2011.01.070
[25]	B. Huang, M. C. Zhou, G. Zhang, A. C. Ammari, A. Alabdulwahab, and A. G. Fayoumi, “Lexicographic multiobjective integer programming for optimal and structurally minimal Petri net supervisors of automated manufacturing systems,” IEEE Trans. Syst. Man Cybern.: Syst., vol. 45, no. 11, pp. 1459–1470, Nov. 2015. doi: 10.1109/TSMC.2015.2415765
[26]	X. Li, M. C. Zhou, K. Xing, and Q. Lu, “State space-based hybrid heuristic search algorithm for scheduling deadlock-prone automated manufacturing systems,” IEEE Trans. Autom. Sci. Eng., vol. 21, no. 3, pp. 4790–4807, Jul. 2024. doi: 10.1109/TASE.2023.3302333
[27]	P. Yin and J. Luo, “Deadlock-free scheduling of flexible manufacturing systems subject to no-wait constraints,” in Int. Conf. on Control, Automation and Robotics (ICCAR), Beijing, China, 2023, pp. 130−135.
[28]	B. Huang and M. C. Zhou, “Symbolic scheduling of robotic cellular manufacturing systems with timed Petri nets,” IEEE Trans. Control Syst. Technol., vol. 30, no. 5, pp. 1876–1887, Sep. 2022. doi: 10.1109/TCST.2021.3123963