Petri Net Induced Heuristic Search for Resource Constrained Scheduling

2026-05-18 · Source: cs.AI updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences, Robotics & Autonomous Systems · Depth: Expert, long

Summary

A new approach formulates the Resource-Constrained Project Scheduling Problem (RCPSP) as an optimal search over the reachability graph of a Timed Transition Petri Net with Resources (TTPNR). This method uses relative-delay tokens, where scheduling decisions correspond to transition firings in the induced state space. The problem is solved using an A* search algorithm guided by a consistent heuristic that combines Critical Path and resource-based lower bounds. Experiments on the PSPLIB benchmarks (J30, J60, J90 sets) demonstrate that this TTPNR-based A* approach outperforms strong exact Mixed-Integer Linear Programming (MIP) baselines, SCIP and CBC, in both success rate and solve time. The analysis indicates that A* performance degrades with resource tightness, while MIP performance degrades with formulation size, with resource strength mediating which solver benefits from scale.

Key takeaway

For Machine Learning Engineers and AI Scientists working on complex scheduling problems, consider adopting the Timed Transition Petri Net with Resources (TTPNR) and A* search approach. This method offers superior performance over traditional MIP solvers, especially for instances with lower resource tightness, by enabling consistent heuristics and efficient state pruning. Your team should evaluate this approach for project management, robotic task coordination, or multiprocessor scheduling to achieve better success rates and faster solutions.

Key insights

RCPSP can be optimally solved via A* search on a TTPNR reachability graph using consistent combined heuristics.

Principles

• Petri nets can model complex scheduling problems.
• Consistent heuristics enable optimal A* search with safe pruning.
• Resource tightness impacts A* more than MIP.

Method

Formulate RCPSP as optimal search over a TTPNR reachability graph, using relative-delay tokens. Solve with A* search guided by a combined Critical Path and resource-based heuristic, ensuring consistency for optimal pruning.

In practice

• Apply TTPNR to other scheduling problems.
• Use combined heuristics for complex search spaces.
• Consider A* for resource-abundant RCPSP instances.

Topics

• Resource-Constrained Project Scheduling
• Timed Transition Petri Net
• A* Search Algorithm
• Consistent Heuristics
• Mixed-Integer Linear Programming

Best for: AI Scientist, Research Scientist, Machine Learning Engineer

Related on AIssential

• Petri Net Induced Heuristic Search for Resource Constrained Scheduling — RCPSP can be effectively solved via A* search on a Petri Net reachability graph using a consistent combined heuristic.
• Petri Net Relaxation for Infeasibility Explanation and Sequential Task Planning — Petri net relaxation improves planning by detecting infeasibilities and supporting dynamic plan updates.
• Scheduling in a changing world: Maximizing throughput with time-varying capacity — New algorithms optimize non-preemptive job scheduling in dynamic cloud environments with fluctuating machine capacity.
• Two Scheduling Examples — Explicitly modeling shift order and cumulative state within a solver's network is crucial for complex temporal scheduling constraints like mandatory breaks.
• UC-Search: Risk-Aware Test-Time Search for Delayed Constrained Time-Series Control — UC-Search provides a risk-aware test-time search framework for delayed, constrained time-series control decisions.
• Scheduling That Speaks: An Interpretable Programmatic Reinforcement Learning Framework — ProRL offers interpretable, programmatic reinforcement learning for scheduling, combining heuristics with Bayesian optimization.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.