A Faster Heuristic Scheduling Search for Robotic Cellular Manufacturing Systems with Generalized and Timed Petri Nets

The design of the heuristic function in Petri-net-based <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$A^{\ast}$</tex> search significantly impacts the efficiency and result quality of scheduling robotic cellular manufacturing (RCM) systems. Previous work in such designs lacks consideration of some key features such as token remaining time, alternative routes, weighted arcs, multiple resource copies, and batch-processing ability. This paper proposes a novel admissible heuristic function tailored to address these challenges. It is designed from the perspective of maximal time usage of each part token. In addition, it is admissible, which guarantees that its obtained schedules are optimal. Most importantly, it is highly informative, enabling efficient scheduling of generalized Petri nets (PNs) of RCM systems. Experimental simulations on benchmark PN models demonstrate the efficacy and efficiency of our method. Codes are available at https://github.com/PNOptimizer/NewHDesign.