Petri Net Induced Heuristic Search for Resource Constrained Scheduling

Dor Atzmon; Ido Lublin; Izack Cohen

arxiv: 2605.15983 · v1 · pith:ORJL3OSAnew · submitted 2026-05-15 · 💻 cs.AI

Petri Net Induced Heuristic Search for Resource Constrained Scheduling

Ido Lublin , Dor Atzmon , Izack Cohen This is my paper

Pith reviewed 2026-05-20 18:20 UTC · model grok-4.3

classification 💻 cs.AI

keywords Resource-Constrained Project SchedulingPetri NetsA* SearchHeuristic SearchTimed Petri NetsMixed-Integer Programming

0 comments

The pith

The Resource-Constrained Project Scheduling Problem can be solved by A* search over the reachability graph of a Timed Transition Petri Net with Resources, where relative-delay tokens make every valid schedule a path of transition firings.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper reformulates RCPSP as a shortest-path problem in the state space generated by firing transitions in a Petri net that tracks both time and resource usage. An A* algorithm guided by a heuristic that merges critical-path estimates with resource lower bounds then finds optimal schedules, and the authors establish that this heuristic remains consistent under the chosen token timing rules. On the PSPLIB benchmark set the resulting solver completes more instances to optimality and does so faster than established mixed-integer linear programming solvers such as SCIP and CBC. The two families of methods degrade along separate dimensions, with A* sensitive to resource tightness and MIP sensitive to model size, while resource strength influences which technique gains from larger instances.

Core claim

RCPSP instances map bijectively to paths in the reachability graph of a Timed Transition Petri Net with Resources that uses relative-delay tokens; therefore A* equipped with a consistent critical-path-plus-resource heuristic can return optimal schedules, and this procedure outperforms MIP solvers in success rate and runtime on PSPLIB data.

What carries the argument

The Timed Transition Petri Net with Resources using relative-delay tokens, which turns feasible schedules into paths through an induced state space so that A* can search for the minimum-time goal marking.

If this is right

More RCPSP instances reach proven optimality than with SCIP or CBC.
Average solve times drop compared with the same MIP baselines.
Resource tightness hurts A* performance while formulation size hurts MIP performance.
Resource strength determines which solver benefits when problem scale increases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same net construction could be reused for related problems such as job-shop scheduling with setup times.
Because the state space is explicitly generated, standard Petri-net reduction techniques might prune unreachable markings before search begins.
Parallel or bounded-memory variants of A* could be substituted without changing the modeling layer.

Load-bearing premise

The chosen Petri net construction produces a reachability graph that contains every feasible RCPSP schedule and no spurious states.

What would settle it

An instance from PSPLIB for which the search returns a schedule that violates a resource constraint or misses a known optimal makespan.

Figures

Figures reproduced from arXiv: 2605.15983 by Dor Atzmon, Ido Lublin, Izack Cohen.

read the original 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. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a Petri-net reachability model for RCPSP that supports A* with a consistent critical-path-plus-resource heuristic and reports better solve rates than SCIP or CBC on PSPLIB, but the claimed bijection between valid schedules and net paths is the part that still needs direct checking.

read the letter

The core contribution is a Timed Transition Petri Net with Resources that uses relative-delay tokens to turn RCPSP into a state-space search problem. Scheduling decisions become transition firings, and they run A* on the resulting graph with a heuristic that merges critical-path and resource-relaxation bounds. They also claim a consistency proof for that heuristic under the token timing rules and show, on the standard PSPLIB set, higher success rates and shorter run times than two established MIP solvers. Per-instance breakdowns indicate that A* and MIP fail for different reasons, which is useful to see. That combination of modeling choice, heuristic guarantee, and head-to-head numbers is what is actually new here. The work sits squarely inside operations research and gives practitioners another exact option when MIP formulations get large. The soft spot is the modeling step itself. The argument rests on every feasible RCPSP schedule corresponding exactly to a path in the net and vice versa, without extra states that violate precedence or resource limits. The abstract invokes this equivalence when it talks about transition firings and when it proves consistency, but supplies neither the proof steps nor small-instance verification that would let a reader confirm the mapping is tight. If that equivalence has gaps, the optimality and performance claims do not hold. The benchmarks are external and the lower bounds are drawn from standard ideas, so there is no obvious circularity. Readers who work on exact methods for resource-constrained scheduling will get the most out of it; the paper is narrow enough that it will not interest people outside that niche. It is worth sending to a serious referee because the empirical comparison is on accepted instances and the modeling angle is distinct, even if the equivalence needs careful scrutiny in review.

Referee Report

2 major / 2 minor

Summary. The paper formulates 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. It solves the problem with A* guided by a heuristic combining Critical Path and resource-based lower bounds, proves consistency under the token-based time semantics, and reports that the approach outperforms MIP baselines (SCIP, CBC) on PSPLIB benchmarks in success rate and solve time, with per-instance analysis showing degradation along independent axes (resource tightness for A*, formulation size for MIP).

Significance. If the claimed bijection between feasible RCPSP schedules and Petri-net paths holds without spurious states or omitted schedules, and the consistency proof is valid, the work offers a novel exact heuristic-search method for RCPSP that complements MIP solvers and supplies useful guidance on when each approach scales better. The reliance on standard lower bounds and external benchmarks is a positive feature.

major comments (2)

[Modeling / Petri Net Construction] The modeling equivalence (every valid RCPSP schedule maps to a path in the reachability graph and vice versa, without spurious firing sequences that violate precedence or resource limits) is invoked to justify that A* explores precisely the feasible state space and to support the consistency proof. No explicit verification via small-instance enumeration or counter-example checks is supplied to rule out spurious states under the relative-delay token semantics.
[Heuristic Consistency Proof] The abstract asserts a consistency proof for the heuristic under the token-based time semantics, yet the manuscript supplies neither the proof steps nor the intermediate lemmas establishing admissibility and consistency.

minor comments (2)

[Experiments] Per-instance data tables (success rates, solve times, and node expansions for each PSPLIB instance) are absent; only aggregate statistics are reported, which hinders reproduction and detailed comparison with SCIP/CBC.
[Notation and Definitions] The precise definition of relative-delay tokens and how they enforce the time semantics should be illustrated with a small worked example to clarify the state representation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We address each major comment below and describe the revisions we will incorporate to strengthen the presentation of the modeling equivalence and the consistency proof.

read point-by-point responses

Referee: [Modeling / Petri Net Construction] The modeling equivalence (every valid RCPSP schedule maps to a path in the reachability graph and vice versa, without spurious firing sequences that violate precedence or resource limits) is invoked to justify that A* explores precisely the feasible state space and to support the consistency proof. No explicit verification via small-instance enumeration or counter-example checks is supplied to rule out spurious states under the relative-delay token semantics.

Authors: We agree that an explicit verification step would make the modeling equivalence more robust. The construction of the Timed Transition Petri Net with Resources and relative-delay tokens is designed so that every firing sequence corresponds to a feasible schedule respecting precedence and resource constraints, with no spurious paths. However, the original manuscript did not include small-instance enumeration. In the revised version we will add a dedicated subsection that enumerates all feasible schedules for several small instances (5–10 activities) drawn from the PSPLIB family, confirms that every valid RCPSP schedule appears exactly once as a path in the reachability graph, and shows that no invalid firing sequences are generated. This verification will also serve as supporting evidence for the consistency argument. revision: yes
Referee: [Heuristic Consistency Proof] The abstract asserts a consistency proof for the heuristic under the token-based time semantics, yet the manuscript supplies neither the proof steps nor the intermediate lemmas establishing admissibility and consistency.

Authors: The manuscript states that the combined Critical-Path-plus-resource heuristic is consistent under the token-based time semantics, yet we acknowledge that the detailed proof steps and intermediate lemmas were not presented with sufficient clarity. In the revised manuscript we will expand the heuristic section to include the complete proof: first admissibility (h(s) ≤ true remaining cost from state s), then consistency (h(s) ≤ c(s,s′) + h(s′) for every successor s′), with all lemmas explicitly stated and proved for the relative-delay token semantics. The revised proof will be self-contained and will directly support the claim made in the abstract. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper reformulates RCPSP as reachability search in a Timed Transition Petri Net with Resources using relative-delay tokens, then applies A* with a heuristic that combines standard critical-path and resource-relaxation lower bounds while proving consistency under the token semantics. These lower bounds and the A* framework are drawn from established scheduling and heuristic-search literature rather than being fitted to the present data or defined in terms of the target result. The claimed bijection between feasible schedules and net paths is presented as a direct consequence of the net construction itself, not as a self-referential equation or a prediction that reduces to an input parameter. Experiments rely on the external PSPLIB benchmark set. No load-bearing step equates a derived quantity to its own definition or to a self-citation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the faithful embedding of RCPSP constraints into the Petri-net reachability graph and on the standard optimality guarantee of A* once consistency is established; no free parameters are introduced in the abstract description.

axioms (1)

standard math A* returns an optimal solution when the heuristic is consistent (never overestimates true cost).
Invoked when the authors state they prove consistency under their token-based time semantics.

invented entities (1)

relative-delay tokens no independent evidence
purpose: Carry time information so that transition firings correspond exactly to feasible scheduling decisions in the induced state space.
New modeling device introduced to handle continuous time within the discrete Petri-net framework.

pith-pipeline@v0.9.0 · 5662 in / 1496 out tokens · 88723 ms · 2026-05-20T18:20:16.753746+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery and orbit embedding unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

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
IndisputableMonolith/Foundation/ArrowOfTime.lean Berry-phase monotonicity and Z-complexity arrow unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that the combined Critical Path and resource-based heuristic is consistent under our token-based time semantics

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

Achterberg, T. 2009. SCIP: solving constraint integer pro- grams.Mathematical Programming Computation, 1: 1–41

work page 2009
[2]

Artigues, C.; Kon ´e, O.; Lopez, P.; and Mongeau, M. 2015. Mixed-integer linear programming formulations.Handbook on project management and scheduling vol. 1, 17–41

work page 2015
[3]

E.; and Park, K

Bell, C. E.; and Park, K. 1990. Solving resource constrained project scheduling problems by A* search.Naval Research Logistics (NRL), 37(1): 61–84

work page 1990
[4]

Blazewicz, J.; Lenstra, J.; and Kan, A. 1983. Scheduling subject to resource constraints: classification and complex- ity.Discrete Applied Mathematics, 5(1): 11–24

work page 1983
[5]

Pesch, E. 1999. Resource-constrained project scheduling: Notation, classification, models, and methods.European journal of operational research, 112(1): 3–41

work page 1999
[6]

Dechter, R.; and Pearl, J. 1985. Generalized best-first search strategies and the optimality of A*.J. ACM, 32(3): 505–536

work page 1985
[7]

Dorndorf, U.; Pesch, E.; and Phan-Huy, T. 2000. A branch- and-bound algorithm for the resource-constrained project scheduling problem.Mathematical Methods of Operations Research, 52: 413–439

work page 2000
[8]

Edelkamp, S.; and Jabbar, S. 2006. Action Planning for Di- rected Model Checking of Petri Nets.Electronic Notes in Theoretical Computer Science, 149(2): 3–18

work page 2006
[9]

Forrest, J.; and Lougee-Heimer, R. 2005. CBC User Guide. Technical report, COIN-OR Foundation

work page 2005
[10]

E.; Nilsson, N

Hart, P. E.; Nilsson, N. J.; and Raphael, B. 1968. A for- mal basis for the heuristic determination of minimum cost paths.IEEE transactions on Systems Science and Cybernet- ics, 4(2): 100–107

work page 1968
[11]

Hartmann, S.; and Briskorn, D. 2022. An updated survey of variants and extensions of the resource-constrained project scheduling problem.European Journal of operational re- search, 297(1): 1–14

work page 2022
[12]

Herroelen, W.; De Reyck, B.; and Demeulemeester, E. 1998. Resource-constrained project scheduling: A survey of recent developments.Computers & Operations Research, 25(4): 279–302

work page 1998
[13]

S.; and Abusorrah, A

Huang, B.; Zhou, M.; Lu, X. S.; and Abusorrah, A. 2023. Scheduling of resource allocation systems with timed Petri nets: A survey.ACM Computing Surveys, 55(11): 1–27

work page 2023
[14]

Kolisch, R.; and Sprecher, A. 1997. PSPLIB-a project scheduling problem library: OR software-ORSEP opera- tions research software exchange program.European Jour- nal of Operational Research, 96(1): 205–216. Kon´e, O.; Artigues, C.; Lopez, P.; and Mongeau, M. 2011. Event-based MILP models for resource-constrained project scheduling problems.Computers & Ope...

work page 1997
[15]

A.; Palacios, J.; and Amodeo, L

Mejia, G.; Nino, K.; Montoya, C.; Sanchez, M. A.; Palacios, J.; and Amodeo, L. 2016. A Petri Net-based framework for realistic project management and scheduling: An application in animation and videogames.Computers & Operations Re- search, 66: 190–198

work page 2016
[16]

Mejia, G.; and Odrey, N. G. 2005. An approach using Petri nets and improved heuristic search for manufacturing sys- tem scheduling.Journal of Manufacturing Systems, 24(2): 79–92

work page 2005
[17]

Pellerin, R.; Perrier, N.; and Berthaut, F. 2020. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem.European Journal of Operational Re- search, 280(2): 395–416

work page 2020
[18]

Petri, C. A. 1966. Communication with automata.Technical Report No. RADC-TR-65-377

work page 1966
[19]

2020.Artificial Intelligence: A Modern Approach

Russell, S.; and Norvig, P. 2020.Artificial Intelligence: A Modern Approach. Pearson, 4th edition

work page 2020
[20]

Sadhukhan, S. K. 2013. Bidirectional heuristic search based on error estimate.CSI Journal of Computing, 2(1-2): S1:57– S1:64

work page 2013
[21]

Wu, Y .; Zhuang, X.-c.; Song, G.-h.; Xu, X.-d.; and Li, C.-x. 2009. Solving resource-constrained multiple project scheduling problem using timed colored Petri nets.Journal of Shanghai Jiaotong University (Science), 14: 713–719

work page 2009
[22]

Zamani, R.; and Shue, L.-Y . 1998. Solving project schedul- ing problems with a heuristic learning algorithm.Journal of the Operational Research Society, 49(7): 709–716

work page 1998

[1] [1]

Achterberg, T. 2009. SCIP: solving constraint integer pro- grams.Mathematical Programming Computation, 1: 1–41

work page 2009

[2] [2]

Artigues, C.; Kon ´e, O.; Lopez, P.; and Mongeau, M. 2015. Mixed-integer linear programming formulations.Handbook on project management and scheduling vol. 1, 17–41

work page 2015

[3] [3]

E.; and Park, K

Bell, C. E.; and Park, K. 1990. Solving resource constrained project scheduling problems by A* search.Naval Research Logistics (NRL), 37(1): 61–84

work page 1990

[4] [4]

Blazewicz, J.; Lenstra, J.; and Kan, A. 1983. Scheduling subject to resource constraints: classification and complex- ity.Discrete Applied Mathematics, 5(1): 11–24

work page 1983

[5] [5]

Pesch, E. 1999. Resource-constrained project scheduling: Notation, classification, models, and methods.European journal of operational research, 112(1): 3–41

work page 1999

[6] [6]

Dechter, R.; and Pearl, J. 1985. Generalized best-first search strategies and the optimality of A*.J. ACM, 32(3): 505–536

work page 1985

[7] [7]

Dorndorf, U.; Pesch, E.; and Phan-Huy, T. 2000. A branch- and-bound algorithm for the resource-constrained project scheduling problem.Mathematical Methods of Operations Research, 52: 413–439

work page 2000

[8] [8]

Edelkamp, S.; and Jabbar, S. 2006. Action Planning for Di- rected Model Checking of Petri Nets.Electronic Notes in Theoretical Computer Science, 149(2): 3–18

work page 2006

[9] [9]

Forrest, J.; and Lougee-Heimer, R. 2005. CBC User Guide. Technical report, COIN-OR Foundation

work page 2005

[10] [10]

E.; Nilsson, N

Hart, P. E.; Nilsson, N. J.; and Raphael, B. 1968. A for- mal basis for the heuristic determination of minimum cost paths.IEEE transactions on Systems Science and Cybernet- ics, 4(2): 100–107

work page 1968

[11] [11]

Hartmann, S.; and Briskorn, D. 2022. An updated survey of variants and extensions of the resource-constrained project scheduling problem.European Journal of operational re- search, 297(1): 1–14

work page 2022

[12] [12]

Herroelen, W.; De Reyck, B.; and Demeulemeester, E. 1998. Resource-constrained project scheduling: A survey of recent developments.Computers & Operations Research, 25(4): 279–302

work page 1998

[13] [13]

S.; and Abusorrah, A

Huang, B.; Zhou, M.; Lu, X. S.; and Abusorrah, A. 2023. Scheduling of resource allocation systems with timed Petri nets: A survey.ACM Computing Surveys, 55(11): 1–27

work page 2023

[14] [14]

Kolisch, R.; and Sprecher, A. 1997. PSPLIB-a project scheduling problem library: OR software-ORSEP opera- tions research software exchange program.European Jour- nal of Operational Research, 96(1): 205–216. Kon´e, O.; Artigues, C.; Lopez, P.; and Mongeau, M. 2011. Event-based MILP models for resource-constrained project scheduling problems.Computers & Ope...

work page 1997

[15] [15]

A.; Palacios, J.; and Amodeo, L

Mejia, G.; Nino, K.; Montoya, C.; Sanchez, M. A.; Palacios, J.; and Amodeo, L. 2016. A Petri Net-based framework for realistic project management and scheduling: An application in animation and videogames.Computers & Operations Re- search, 66: 190–198

work page 2016

[16] [16]

Mejia, G.; and Odrey, N. G. 2005. An approach using Petri nets and improved heuristic search for manufacturing sys- tem scheduling.Journal of Manufacturing Systems, 24(2): 79–92

work page 2005

[17] [17]

Pellerin, R.; Perrier, N.; and Berthaut, F. 2020. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem.European Journal of Operational Re- search, 280(2): 395–416

work page 2020

[18] [18]

Petri, C. A. 1966. Communication with automata.Technical Report No. RADC-TR-65-377

work page 1966

[19] [19]

2020.Artificial Intelligence: A Modern Approach

Russell, S.; and Norvig, P. 2020.Artificial Intelligence: A Modern Approach. Pearson, 4th edition

work page 2020

[20] [20]

Sadhukhan, S. K. 2013. Bidirectional heuristic search based on error estimate.CSI Journal of Computing, 2(1-2): S1:57– S1:64

work page 2013

[21] [21]

Wu, Y .; Zhuang, X.-c.; Song, G.-h.; Xu, X.-d.; and Li, C.-x. 2009. Solving resource-constrained multiple project scheduling problem using timed colored Petri nets.Journal of Shanghai Jiaotong University (Science), 14: 713–719

work page 2009

[22] [22]

Zamani, R.; and Shue, L.-Y . 1998. Solving project schedul- ing problems with a heuristic learning algorithm.Journal of the Operational Research Society, 49(7): 709–716

work page 1998