# Petri Net Induced Heuristic Search for Resource Constrained Scheduling

arXiv: https://arxiv.org/abs/2605.15983 · HTML: https://mlsanity.com/paper/2605.15983/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 20 references that are in the map.
- First posted on arXiv 15 May 2026.

## Abstract (arXiv)

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. We solve the resulting problem with A^* guided by a heuristic that combines Critical Path and resource-based lower bounds, and prove that it is consistent under our token-based time semantics. Experiments on the PSPLIB benchmarks show that the approach outperforms strong exact Mixed-Integer Linear Programming (MIP) baselines (SCIP, CBC) in both success rate and solve time. Per-instance analysis shows that heuristic search and MIP degrade along independent axes, resource tightness for A^* and formulation size for MIP, with resource strength mediating which solver benefits from scale.