Petri Net Heuristic Search for Resource Constrained Scheduling

A novel method for addressing the Resource-Constrained Project Scheduling Problem (RCPSP) conceptualizes it as an optimal search within the reachability graph of a Timed Transition Petri Net that incorporates Resources, utilizing relative-delay tokens. The solution employs A*, guided by a heuristic that integrates Critical Path and resource-based lower bounds, which has been shown to be consistent with token-based time semantics. Testing on PSPLIB benchmarks indicates that this technique surpasses robust exact Mixed-Integer Linear Programming (MIP) benchmarks (SCIP, CBC) in terms of both success rate and solving time. Analysis of individual instances demonstrates that heuristic search and MIP deteriorate along different dimensions: A* is affected by resource tightness, while MIP is influenced by formulation size, with resource strength determining which solver benefits from increased scale.