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.
arXiv cs.AI files mainly under ai research. We currently carry 1,128 of its stories.
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
