Petri Net Induced Heuristic Search for Resource Constrained Scheduling
The article presents a new approach to the Resource-Constrained Project Scheduling Problem (RCPSP) using a Timed Transition Petri Net. The authors demonstrate that their heuristic search method outperforms traditional Mixed-Integer Linear Programming baselines in both success rate and solve time. This research was accepted at the International Symposium on Combinatorial Search in 2026.
- ▪The study formulates RCPSP as optimal search over the reachability graph of a Timed Transition Petri Net.
- ▪The proposed method uses A* guided by a heuristic that combines Critical Path and resource-based lower bounds.
- ▪Experiments show that the approach outperforms strong exact MIP baselines in success rate and solve time.
Opening excerpt (first ~120 words) tap to expand
Computer Science > Artificial Intelligence arXiv:2605.15983 (cs) [Submitted on 15 May 2026] Title:Petri Net Induced Heuristic Search for Resource Constrained Scheduling Authors:Ido Lublin, Dor Atzmon, Izack Cohen View a PDF of the paper titled Petri Net Induced Heuristic Search for Resource Constrained Scheduling, by Ido Lublin and 2 other authors View PDF HTML (experimental) Abstract:We formulate the Resource-Constrained Project Scheduling Problem (RCPSP) as optimal search over the reachability graph of a Timed Transition Petri Net with Resources, using relative-delay tokens so that scheduling decisions correspond to transition firings in the induced state space.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at arXiv cs.AI.
Discussion
0 commentsMore from arXiv cs.AI
