Petri Net Induced Heuristic Search for Resource Constrained Scheduling

# Petri Net Induced Heuristic Search for Resource Constrained Scheduling
Source: [https://arxiv.org/html/2605.15983](https://arxiv.org/html/2605.15983)
###### 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 withA∗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 forA∗A^\{\*\}and formulation size for MIP, with resource strength mediating which solver benefits from scale\.

## Introduction

The*Resource\-Constrained Project Scheduling Problem*\(RCPSP\) asks how to schedule precedence\-constrained activities under limited shared resources so as to minimize completion time\(Herroelenet al\.[1998](https://arxiv.org/html/2605.15983#bib.bib37); Bruckeret al\.[1999](https://arxiv.org/html/2605.15983#bib.bib21); Hartmann and Briskorn[2022](https://arxiv.org/html/2605.15983#bib.bib44)\)\. As a strongly NP\-hard generalization of classical scheduling problems\(Blazewiczet al\.[1983](https://arxiv.org/html/2605.15983#bib.bib73)\), RCPSP is a fundamental problem at the intersection of scheduling, combinatorial search, and resource\-bounded reasoning\. It also arises in temporal planning, robotic task coordination, spacecraft mission scheduling, multiprocessor scheduling, and project management\. RCPSP has long served as a benchmark for exact and approximate methods, yet no single method dominates across all instance classes\.

The leading exact solution approach is*Mixed\-Integer Linear Programming*\(MIP\), typically solved by branch\-and\-cut\(Dorndorfet al\.[2000](https://arxiv.org/html/2605.15983#bib.bib31); Konéet al\.[2011](https://arxiv.org/html/2605.15983#bib.bib40); Artigueset al\.[2015](https://arxiv.org/html/2605.15983#bib.bib18)\)\. While MIP provides optimality guarantees, it scales poorly, and strong solvers such as SCIP\(Achterberg[2009](https://arxiv.org/html/2605.15983#bib.bib15)\)often fail to solve benchmark instances within practical time limits\. Metaheuristics\(Pellerinet al\.[2020](https://arxiv.org/html/2605.15983#bib.bib57)\)improve scalability at the cost of optimality, and hybrid methods seek a middle ground, yet no existing approach reliably achieves both\. A natural exact alternative is*heuristic search*\(Hartet al\.[1968](https://arxiv.org/html/2605.15983#bib.bib33)\)\.Bell and Park \([1990](https://arxiv.org/html/2605.15983#bib.bib70)\)appliedA∗A^\{\*\}to RCPSP through conflict sequencing, but the method becomes intractable on highly resource\-constrained instances\.Zamani and Shue \([1998](https://arxiv.org/html/2605.15983#bib.bib69)\)introduced the activity\-dispatch state space and appliedA∗A^\{\*\}via*SLA\**, improving performance but requiring multiple search trials to reach optimality\. In both cases, the lack of a consistent heuristic prevents safe duplicate pruning and causes redundant re\-expansion of equivalent scheduling states–we tackle this issue in the current work\. More broadly, a recent survey\(Huanget al\.[2023](https://arxiv.org/html/2605.15983#bib.bib38)\)highlights the promise of heuristic search over reachability graphs for balancing solution quality and computational effort\. Related Petri\-net\-based ideas have been explored in project and manufacturing scheduling\(Mejiaet al\.[2016](https://arxiv.org/html/2605.15983#bib.bib53); Mejia and Odrey[2005](https://arxiv.org/html/2605.15983#bib.bib51)\), directed heuristic search over Petri net reachability graphs has been studied in the model checking context\(Edelkamp and Jabbar[2006](https://arxiv.org/html/2605.15983#bib.bib79)\), and simulation has been used to estimate RCPSP project duration\(Wuet al\.[2009](https://arxiv.org/html/2605.15983#bib.bib66)\)\. Yet, to the best of our knowledge, no prior work has applied optimal heuristic search to the induced reachability graph of an RCPSP formulation\.

This paper develops a new RCPSP formulation as an optimal search over the reachability graph induced by a*Timed Transition Petri Net with Resources*\(TTPNR\), making local scheduling decisions explicit and representing time uniformly through token delays\. This yields an exact search formulation with admissible heuristics, safe duplicate pruning, and efficient treatment of zero\-cost transitions\. We prove that the combined Critical Path and resource\-based heuristic is consistent, and show on standard PSPLIB benchmarks that the resulting approach is competitive with strong exact MIP baselines, including SCIP and CBC\.

## RCPSP Problem Definition

RCPSP is characterized by the tuple\(𝔸,E,R,C,U,τ\)\(\\mathbb\{A\},E,R,C,U,\\tau\):

- •𝔸=\{0,1,…,n,n\+1\}\\mathbb\{A\}=\\\{0,1,\\dots,n,n\+1\\\}: set of activities, where0andn\+1n\+1are dummy start and finish\.
- •E⊂𝔸×𝔸E\\subset\\mathbb\{A\}\\times\\mathbb\{A\}: precedence constraints, where\(i,j\)∈E\(i,j\)\\in Emeansjjcannot start beforeiicompletes\. Let∙j=\{i∣\(i,j\)∈E\}\\bullet j=\\\{i\\mid\(i,j\)\\in E\\\}be the set of immediate predecessors ofjj\.
- •R=\{r1,…,rk\}R=\\\{r\_\{1\},\\dots,r\_\{k\}\\\}: renewable resource types with capacitiesC=\{c1,…,ck\}C=\\\{c\_\{1\},\\dots,c\_\{k\}\\\}\.
- •uj,iu\_\{j,i\}: demand of activityjjfor resourcerir\_\{i\}\.
- •τj\\tau\_\{j\}: duration of activityjj\.

As in standard RCPSP formulations, the dummy activities have zero duration \(τ0=τn\+1=0\\tau\_\{0\}=\\tau\_\{n\+1\}=0\) and zero resource demand \(u0,i=un\+1,i=0u\_\{0,i\}=u\_\{n\+1,i\}=0for allri∈Rr\_\{i\}\\in R\)\.

A project*schedule*assigns a start timeSj≥0S\_\{j\}\\geq 0to each activityj∈𝔸j\\in\\mathbb\{A\}\. A feasible schedule satisfies two constraints:

1. 1\.*Precedence:*An activity cannot start until all of its predecessors complete \(for every\(i,j\)∈E\(i,j\)\\in E,Sj≥Si\+τiS\_\{j\}\\geq S\_\{i\}\+\\tau\_\{i\}\)\.
2. 2\.*Resource:*At any timett, the total amount of each resource typeri∈Rr\_\{i\}\\in Rallocated to ongoing activities cannot exceed its available capacityci∈Cc\_\{i\}\\in C\.

The objective is to find a schedule with minimal makespan, that is, the start time of the dummy finish activity:min⁡Sn\+1\.\\min S\_\{n\+1\}\.The interaction between precedence and resource constraints creates a highly constrained combinatorial problem, which we later formulate both as a reachability graph and as a MIP\. We use the next example throughout the paper\.

###### Example 1\.

Consider an RCPSP instance with activities𝔸=\{0,1,2,3,4,5\}\\mathbb\{A\}=\\\{0,1,2,3,4,5\\\}\(denote by0≡a,1≡b,2≡c,0\\equiv a,\\;1\\equiv b,\\;2\\equiv c,\\;etc\.\)\.aaandffare the dummy start and finish activities\. The precedence set isE=\{\(a,b\),\(a,d\),\(b,c\),\(d,e\),\(c,f\),\(e,f\)\},E=\\\{\(a,b\),\(a,d\),\(b,c\),\(d,e\),\(c,f\),\(e,f\)\\\},forming two parallel chainsa→b→c→fa\\rightarrow b\\rightarrow c\\rightarrow fanda→d→e→f\.a\\rightarrow d\\rightarrow e\\rightarrow f\.There is one renewable resourcerrwith capacityc1=2c\_\{1\}=2\. Each non\-dummy activity requires one unit, i\.e\.,ub,1=uc,1=ud,1=ue,1=1,u\_\{b,1\}=u\_\{c,1\}=u\_\{d,1\}=u\_\{e,1\}=1,andua,1=uf,1=0\.u\_\{a,1\}=u\_\{f,1\}=0\.The durations areτa=τf=0,τb=3,τc=1,τd=3,τe=2\.\\tau\_\{a\}=\\tau\_\{f\}=0,\\quad\\tau\_\{b\}=3,\\quad\\tau\_\{c\}=1,\\quad\\tau\_\{d\}=3,\\quad\\tau\_\{e\}=2\.An optimal schedule has makespan55withSa=Sb=Sd=0,Sc=Se=3,Sf=5\.S\_\{a\}=S\_\{b\}=S\_\{d\}=0,\\quad S\_\{c\}=S\_\{e\}=3,\\quad S\_\{f\}=5\.Figure[1](https://arxiv.org/html/2605.15983#Sx3.F1)\(a\) summarizes the problem instance parameters\.

## Timed Transition Petri Net with Resources

A*Petri net*\(Petri[1966](https://arxiv.org/html/2605.15983#bib.bib54)\)is a bipartite graph consisting of*places*\(denoted by circles\) and*transitions*\(rectangles\) connected by directed arcs\. Places hold*tokens*, whose distribution defines the*marking*MM\. Formally, a Petri net is the tuple\(P,T,F,W,M0\)\(P,T,F,W,M\_\{0\}\), wherePPandTTare finite sets of places and transitions,F⊆\(P×T\)∪\(T×P\)F\\subseteq\(P\\times T\)\\cup\(T\\times P\)is the arc set,W:F→ℤ\+W:F\\rightarrow\\mathbb\{Z\}^\{\+\}is a weight function, andM0M\_\{0\}is the initial marking\. We write∙t=\{p∈P∣\(p,t\)∈F\}\\bullet t=\\\{p\\in P\\mid\(p,t\)\\in F\\\}for the input places of transitiontt\. A transitionttisenabledif every placep∈∙tp\\in\\bullet tholds at leastW​\(p,t\)W\(p,t\)tokens; firing consumes and deposits tokens accordingly, thereby modeling concurrency and synchronization\. In our formulation, each reachable marking corresponds to a search state, and the reachable markings define thereachability graphthat our approach generates and searches incrementally\.

To distinguish the original RCPSP formulation from its Petri\-net encoding, we usej∈𝔸j\\in\\mathbb\{A\}for RCPSP activities andt∈Tt\\in Tfor Petri\-net transitions\. Below, each transition corresponds to a single activity\. We extend the classical Petri net to a TTPNR with time and resource perspectives,

𝒩=\(P,T,F,W,M0,λ,τT,R,C\),\\mathcal\{N\}=\(P,T,F,W,M\_\{0\},\\lambda,\\tau\_\{T\},R,C\),whereλ:T→𝔸\\lambda:T\\to\\mathbb\{A\}maps each Petri\-net transition to its corresponding RCPSP activity,τT:T→ℕ0\\tau\_\{T\}:T\\to\\mathbb\{N\}\_\{0\}assigns a duration to each transition, andR,CR,Cdefine the resource types and their capacities\. Each transition inherits the duration of its associated activity \(τT​\(t\):=τλ​\(t\)\\tau\_\{T\}\(t\):=\\tau\_\{\\lambda\(t\)\}\)\. A dedicated subsetPR⊂PP\_\{R\}\\subset Pof resource places enforces capacity constraints:M0M\_\{0\}allocates exactlycic\_\{i\}tokens to each resource place\. The single enabling ruleM​\(p\)≥W​\(p,t\)M\(p\)\\geq W\(p,t\)then guarantees that an activity can start only if both its precedence conditions and resource requirements are satisfied\. This unified enabling rule is a key advantage over prior RCPSP search formulations, where precedence and resource constraints require separate conflict\-resolution mechanisms outside the search space\.

Figure[1](https://arxiv.org/html/2605.15983#Sx3.F1)\(b\) illustrates the TTPNR formulation of the RCPSP instance from Example[1](https://arxiv.org/html/2605.15983#Thmexample1)\(Figure[1](https://arxiv.org/html/2605.15983#Sx3.F1)\(a\)\)\. Here,aaandffdenote the dummy start and dummy finish activities, respectively\. The figure shows the initial markingM0M\_\{0\}, in which a single token is placed inp1p\_\{1\}and two in the resource placeprp\_\{r\}\(resource type index is omitted for readability\)\. The only enabled transition atM0M\_\{0\}isaa; firing it consumes the token fromp1p\_\{1\}and produces tokens inp2p\_\{2\}andp3p\_\{3\}, making activitiesbbandddavailable to compete for the shared resource\.

Problem instanceact\.succ\.dur\.rraabb,dd00bbcc31ccff11ddee31eeff21ff—00

\(a\)
![Refer to caption](https://arxiv.org/html/2605.15983v1/Petri.png)\(b\)
![Refer to caption](https://arxiv.org/html/2605.15983v1/search-graph_v2.png)\(c\)

Figure 1:\(a\) RCPSP instance; \(b\) TTPNR initial marking; \(c\)A∗A^\{\*\}search over the induced reachability graph\. Nodes show\(g,h,f\)\(g,h,f\)and token delaysθ\\theta, green nodes are expanded\.
## Modeling RCPSP as a Search Problem

To solve the RCPSP via heuristic search, we induce a reachability graph directly from the TTPNR\. In this search graph, each node represents a system state, and each edge corresponds to the commitment to execute a specific project activity by firing a Petri\-net transition\.

A*state*s∈𝕊s\\in\\mathbb\{S\}is a marking augmented with relative delays on tokens\. By encoding time as token delaysθ\\theta, we avoid a global clock, allowing more states to be recognized as identical and safely pruned; heuristic consistency then guarantees that the first expansion of any state is optimal\. Formally,

s=\[p1:l1θl1,…,pn:lnθln,pr1:r1θr1,…,prk:rkθrk\]\\displaystyle s=\\left\[p\_\{1\}:l\_\{1\}^\{\\theta\_\{l\_\{1\}\}\},\\dots,p\_\{n\}:l\_\{n\}^\{\\theta\_\{l\_\{n\}\}\},\\,\\,p\_\{r\_\{1\}\}:r\_\{1\}^\{\\theta\_\{r\_\{1\}\}\},\\dots,p\_\{r\_\{k\}\}:r\_\{k\}^\{\\theta\_\{r\_\{k\}\}\}\\right\]where a token with delayθ\>0\\theta\>0is not yet available, whileθ=0\\theta=0\(omitted by convention\) means immediate availability\. Here,liθlil\_\{i\}^\{\\theta\_\{l\_\{i\}\}\}denoteslil\_\{i\}tokens in placepip\_\{i\}with delayθli\\theta\_\{l\_\{i\}\}, andrjθrjr\_\{j\}^\{\\theta\_\{r\_\{j\}\}\}denotesrjr\_\{j\}resource tokens with delayθrj\\theta\_\{r\_\{j\}\}\(only positive token counts are shown\)\.

The*start state*s0s\_\{0\}has one token in the input place of the dummy start transition and all resource places at their initial marking; the*goal state*has one token in the output place of the dummy finish transition with resource places restored\.

We consider a transitiont∈Tt\\in T*enabled*if its input places contain sufficient tokens, irrespective of their current relative delays\. Firingttcommits the corresponding activityλ​\(t\)\\lambda\(t\)and proceeds as follows\. \(1\)*Time jump:*Consume the required input tokens, prioritizing tokens with smallest relative delay\. The induced time jump isΔ​t=max⁡\(θconsumed\)\.\\Delta t=\\max\(\\theta\_\{\\mathrm\{consumed\}\}\)\.\(2\)*Delay and token generation:*All remaining token delays are reduced byΔ​t\\Delta t:θnew=max⁡\(0,θ−Δ​t\)\.\\theta^\{\\mathrm\{new\}\}=\\max\(0,\\theta\-\\Delta t\)\.Newly produced tokens are assigned the delayτT​\(t\)=τλ​\(t\)\.\\tau\_\{T\}\(t\)=\\tau\_\{\\lambda\(t\)\}\.Also, each node maintains the path costg​\(s′\)=g​\(s\)\+Δ​tg\(s^\{\\prime\}\)=g\(s\)\+\\Delta tfor use byA∗A^\{\*\}\.

### Heuristics

We use two lower bounds on the remaining makespan from a statess: the critical\-path boundhC​P​\(s\)h\_\{CP\}\(s\), obtained by relaxing resource capacities, and the resource\-load boundhr​e​s​\(s\)h\_\{res\}\(s\), obtained by relaxing precedence constraints\. Their combination ishmax​\(s\)=max⁡\(hC​P​\(s\),hr​e​s​\(s\)\)h\_\{\\max\}\(s\)=\\max\(h\_\{CP\}\(s\),\\,h\_\{res\}\(s\)\)\.

#### Critical\-Path Heuristic

hC​P​\(s\)h\_\{CP\}\(s\)is the length of the longest*residual*precedence path to the dummy finish activityn\+1n\{\+\}1, computed by propagating*residual*earliest finish times,R​E​FREF, in topological order:

R​E​Fj=\{0ifjis completed,θjifjis currently executing,maxi⁣∈⁣∙j⁡R​E​Fi\+τjifjhas not yet started,REF\_\{j\}=\\begin\{cases\}0&\\text\{if $j$ is completed,\}\\\\ \\theta\_\{j\}&\\text\{if $j$ is currently executing,\}\\\\ \\displaystyle\\max\_\{i\\in\\bullet j\}REF\_\{i\}\+\\tau\_\{j\}&\\text\{if $j$ has not yet started,\}\\end\{cases\}initialized withR​E​F0=0REF\_\{0\}=0, andhC​P​\(s\)=R​E​Fn\+1h\_\{CP\}\(s\)=REF\_\{n\+1\}\.

Proposition 1\.hC​Ph\_\{CP\}is admissible and consistent\.

###### Proof\.

Admissibility\.Removing resource constraints cannot extend the remaining completion time, sohC​P​\(s\)≤h∗​\(s\)h\_\{CP\}\(s\)\\leq h^\{\*\}\(s\)\.

Consistency\.Consider a successors′s^\{\\prime\}ofsswith time incrementδ​\(s,s′\):=g​\(s′\)−g​\(s\)\\delta\(s,s^\{\\prime\}\):=g\(s^\{\\prime\}\)\-g\(s\)\. For every activityjj, its residual duration decreases by at mostδ​\(s,s′\)\\delta\(s,s^\{\\prime\}\): executing activities lose at mostδ​\(s,s′\)\\delta\(s,s^\{\\prime\}\), unstarted activities are unchanged, and a newly started activityλ​\(t\)\\lambda\(t\)receives residual delayτλ​\(t\)\\tau\_\{\\lambda\(t\)\}ins′s^\{\\prime\}, identical to its value before firing\. Since precedence enforces sequential execution along any single path, at most one activity on the longest pathP∗P^\{\*\}is executing inss, so the total residual length ofP∗P^\{\*\}decreases by at mostδ​\(s,s′\)\\delta\(s,s^\{\\prime\}\)\. SincehC​P​\(s′\)h\_\{CP\}\(s^\{\\prime\}\)is the maximum over all paths,

hC​P​\(s′\)≥hC​P​\(s\)−δ​\(s,s′\),h\_\{CP\}\(s^\{\\prime\}\)\\geq h\_\{CP\}\(s\)\-\\delta\(s,s^\{\\prime\}\),which rearranges tohC​P​\(s\)≤c​\(s,s′\)\+hC​P​\(s′\)h\_\{CP\}\(s\)\\leq c\(s,s^\{\\prime\}\)\+h\_\{CP\}\(s^\{\\prime\}\)\. ∎

#### Resource\-Based Heuristic

hr​e​s​\(s\)h\_\{res\}\(s\)is the minimum time to clear the remaining workload on the most heavily loaded resource, ignoring precedence constraints\. Letactive​\(s\)\\mathrm\{active\}\(s\)andunstarted​\(s\)\\mathrm\{unstarted\}\(s\)denote the currently executing and not\-yet\-started activities, respectively\.

hr​e​s​\(s\)=maxr∈R⁡∑a∈active​\(s\)θa​ua,r\+∑a∈unstarted​\(s\)τa​ua,rcr\.h\_\{res\}\(s\)=\\max\_\{r\\in R\}\\frac\{\\displaystyle\\sum\_\{a\\in\\mathrm\{active\}\(s\)\}\\theta\_\{a\}\\,u\_\{a,r\}\+\\sum\_\{a\\in\\mathrm\{unstarted\}\(s\)\}\\tau\_\{a\}\\,u\_\{a,r\}\}\{c\_\{r\}\}\.
Proposition 2\.hr​e​sh\_\{res\}is admissible and consistent\.

###### Proof\.

Admissibility\.Dropping precedence constraints can only reduce the remaining makespan, sohr​e​s​\(s\)≤h∗​\(s\)h\_\{res\}\(s\)\\leq h^\{\*\}\(s\)\.

Consistency\.The argument mirrors that ofhC​Ph\_\{CP\}: firingttadvances the clock byδ​\(s,s′\)\\delta\(s,s^\{\\prime\}\), reducing the residual workload numerator by at mostδ​\(s,s′\)⋅cr\\delta\(s,s^\{\\prime\}\)\\cdot c\_\{r\}per resource \(executing activities lose at mostδ​\(s,s′\)⋅ua,r≤δ​\(s,s′\)⋅cr\\delta\(s,s^\{\\prime\}\)\\cdot u\_\{a,r\}\\leq\\delta\(s,s^\{\\prime\}\)\\cdot c\_\{r\}, unstarted activities are unchanged, andλ​\(t\)\\lambda\(t\)satisfiesθλ​\(t\)=τλ​\(t\)\\theta\_\{\\lambda\(t\)\}=\\tau\_\{\\lambda\(t\)\}immediately after firing\)\. Dividing bycrc\_\{r\}and taking the maximum over resources yieldshr​e​s​\(s\)≤c​\(s,s′\)\+hr​e​s​\(s′\)h\_\{res\}\(s\)\\leq c\(s,s^\{\\prime\}\)\+h\_\{res\}\(s^\{\\prime\}\)\. ∎

Proposition 3\.A combined heuristic

hmax​\(s\)=max⁡\(hC​P​\(s\),hr​e​s​\(s\)\)h\_\{\\max\}\(s\)=\\max\(h\_\{CP\}\(s\),h\_\{res\}\(s\)\)is admissible and consistent\.

###### Proof\.

The max over admissible and consistent heuristics is admissible and consistent\(Russell and Norvig[2020](https://arxiv.org/html/2605.15983#bib.bib77)\)\. ∎

Consistency guarantees thatA∗A^\{\*\}remains optimal while eliminating the need to reopen expanded states\(Hartet al\.[1968](https://arxiv.org/html/2605.15983#bib.bib33); Dechter and Pearl[1985](https://arxiv.org/html/2605.15983#bib.bib75)\)\. Our formulation also enables an effective caching optimization: wheneverδ​\(s,s′\)=0\\delta\(s,s^\{\\prime\}\)=0, both lower bounds are preserved, sohmax​\(s′\)=hmax​\(s\)h\_\{\\max\}\(s^\{\\prime\}\)=h\_\{\\max\}\(s\)\. Thus, zero\-cost successors can reuse the parent’s cached heuristic value, without recomputation\.

In the resultingA∗A^\{\*\}search, we prioritize nodes with minimalf​\(s\)=g​\(s\)\+hmax​\(s\)f\(s\)=g\(s\)\+h\_\{\\max\}\(s\)\.ff\-ties are broken by preferring highergg\-cost, then more finished activities, then more active activities, then FIFO, driving the search depth\-first through equalff\-cost plateaus\.

Table 1:Overall Success Rate and Average Time, alongside breakdowns by Resource Strength \(RS\) and Resource Factor \(RF\)\.Figure[1](https://arxiv.org/html/2605.15983#Sx3.F1)\(c\) illustrates theA∗A^\{\*\}guided search over the induced reachability graph of Example[1](https://arxiv.org/html/2605.15983#Thmexample1)\. Each node shows\(g,h,f\)\(g,h,f\)values and active token delaysθ\\theta\. At each expansion, a successor is generated for enabled transitions, and the prioritized node is selected for expansion\.

## MIP Formulation

Since MIP\-based branch\-and\-cut is the dominant exact approach for RCPSP\(Dorndorfet al\.[2000](https://arxiv.org/html/2605.15983#bib.bib31)\), we compare against two strong off\-the\-shelf branch\-and\-cut solvers, SCIP\(Achterberg[2009](https://arxiv.org/html/2605.15983#bib.bib15)\)and CBC\(Forrest and Lougee\-Heimer[2005](https://arxiv.org/html/2605.15983#bib.bib76)\), using the standard time\-indexed formulation\(Artigueset al\.[2015](https://arxiv.org/html/2605.15983#bib.bib18)\): a binary variablexj​t∈\{0,1\}x\_\{jt\}\\in\\\{0,1\\\}indicates whether activityjjstarts at timett\. The full encoding is:

min\\displaystyle\\min∑t∈H\\displaystyle\\sum\_\{t\\in H\}\\t⋅xn\+1,t\\displaystyle t\\cdot x\_\{n\+1,t\}\(1\)s\.t\.∑t∈Hxj​t\\displaystyle\\sum\_\{t\\in H\}x\_\{jt\}=1∀j∈𝔸\\displaystyle=1\\quad\\forall j\\in\\mathbb\{A\}\(2\)Sj\+τj\\displaystyle S\_\{j\}\+\\tau\_\{j\}≤Si∀\(j,i\)∈E\\displaystyle\\leq S\_\{i\}\\quad\\forall\(j,i\)\\in E\(3\)∑j∈𝔸uj,r​∑q=t−τj\+1txj​q\\displaystyle\\sum\_\{j\\in\\mathbb\{A\}\}u\_\{j,r\}\\sum\_\{q=t\-\\tau\_\{j\}\+1\}^\{t\}x\_\{jq\}≤cr∀r∈R,∀t∈H\\displaystyle\\leq c\_\{r\}\\quad\\forall r\\in R,\\ \\forall t\\in H\(4\)Constraints \([2](https://arxiv.org/html/2605.15983#Sx5.E2)\)–\([4](https://arxiv.org/html/2605.15983#Sx5.E4)\) ensure activities start exactly once, enforce precedence and resource capacity, withSj=∑t∈Ht​xj​tS\_\{j\}=\\sum\_\{t\\in H\}t\\,x\_\{jt\}andH=\{0,…,T\}H=\\\{0,\\dots,T\\\}, whereT=∑j∈𝔸τjT=\\sum\_\{j\\in\\mathbb\{A\}\}\\tau\_\{j\}\.

## Experiments and Discussion

We evaluatedA∗A^\{\*\}\(denoted TTPNR\) against SCIP and CBC on the standard public RCPSP benchmark suite PSPLIB\(Kolisch and Sprecher[1997](https://arxiv.org/html/2605.15983#bib.bib39)\), using the J30, J60, and J90 sets \(30, 60, and 90 activities; 480 instances per set\)\. Each instance has four renewable resource types, and the instances in each set are organized into 48 groups of 10 with shared generation parameters\. These parameters \(discussed later\) vary structural properties and resource tightness, yielding a diverse collection of challenging RCPSP instances\. Evaluations were run sequentially on a single\-core Intel Xeon Gold 6248R CPU @ 3\.00GHz with a 5\-minute timeout\. To ensure a rigorous comparison of the underlying search engines and branching mechanics, the MIP solvers and TTPNR were executed without preprocessing\. TTPNR was implemented in C\+\+ and will be publicly available\.

Table[1](https://arxiv.org/html/2605.15983#Sx4.T1)summarizes success rate, average time, and performance breakdowns by problem features\. TTPNR outperforms both MIP solvers in success rate and is substantially faster across all datasets\.

### Impact of Problem Features on TTPNR

*Network Complexity \(NC\)*measures how strongly precedence constraints restrict activity order, counting only non\-redundant arcs \(redundant arcs are implied by transitivity\)\. Higher NC makes the schedule more sequential, reducing the number of simultaneously enabled activities, reducing the branching factor\. From our experiments, NC proved to be the least impactful parameter for both MIP solvers and TTPNR, and is thus omitted from Table[1](https://arxiv.org/html/2605.15983#Sx4.T1)\.

*Resource Strength \(RS\)*measures how restrictive the resource capacities are\. At RS = 1, resources are abundant enough that competition for resources is minimal, while RS=0~=0implies that capacities are near their minimum feasible levels and competition for resources is maximal\. When RS is low, many delays are caused by resource conflicts rather than precedence, so the true remaining makespan can be much larger than the precedence\-only lower bound\. This makeshC​Ph\_\{CP\}, and thereforehmaxh\_\{\\max\}, less informative for search, weakeningA∗A^\{\*\}guidance and reducing success rates \(RS section of Table[1](https://arxiv.org/html/2605.15983#Sx4.T1)\)\.

*Resource Factor \(RF\)*measures the average proportion of resource types required per activity\. While SCIP strictly degrades as RF increases, CBC exhibits mixed sensitivity\. TTPNR demonstrates robustness to RF variations\. In TTPNR multi\-resource requirements involve transitions concurrently consuming tokens from multiple places, preventing branching factor inflation and ensuring stable success rates for any RF \(RF section of Table[1](https://arxiv.org/html/2605.15983#Sx4.T1)\)\.

## Conclusion

We formulated RCPSP as optimal search on the reachability graph of a TTPNR with relative\-delay tokens, and solved it withA∗A^\{\*\}guided by a consistent heuristic combining Critical Path and resource\-based lower bounds\. More broadly, any scheduling problem expressible as a timed Petri net with resources inherits the same search machinery, including consistent heuristics, safe duplicate pruning, and zero\-cost caching\. Empirically, heuristic search and MIP degrade along independent axes—resource tightness forA∗A^\{\*\}, formulation size for MIP—with resource strength mediating which solver benefits from scale\. Future work includes stronger resource\-aware heuristics for low\-resource\-strength instances, algorithm selection across the two paradigms, and bidirectional search methods such as BAE\*\(Sadhukhan[2013](https://arxiv.org/html/2605.15983#bib.bib78)\), which fit our state representation\.

## References

- T\. Achterberg \(2009\)SCIP: solving constraint integer programs\.Mathematical Programming Computation1,pp\. 1–41\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2),[MIP Formulation](https://arxiv.org/html/2605.15983#Sx5.p1.3)\.
- C\. Artigues, O\. Koné, P\. Lopez, and M\. Mongeau \(2015\)Mixed\-integer linear programming formulations\.Handbook on project management and scheduling vol\. 1,pp\. 17–41\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2),[MIP Formulation](https://arxiv.org/html/2605.15983#Sx5.p1.3)\.
- C\. E\. Bell and K\. Park \(1990\)Solving resource constrained project scheduling problems by a\* search\.Naval Research Logistics \(NRL\)37\(1\),pp\. 61–84\.External Links:[Document](https://dx.doi.org/10.1002/1520-6750%28199002%2937%3A13.0.CO),[Link](https://ideas.repec.org/a/wly/navres/v37y1990i1p61-84.html)Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- J\. Blazewicz, J\.K\. Lenstra, and A\. Kan \(1983\)Scheduling subject to resource constraints: classification and complexity\.Discrete Applied Mathematics5\(1\),pp\. 11–24\.External Links:ISSN 0166\-218X,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/0166-218X%2883%2990012-4),[Link](https://www.sciencedirect.com/science/article/pii/0166218X83900124)Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p1.1)\.
- P\. Brucker, A\. Drexl, R\. Möhring, K\. Neumann, and E\. Pesch \(1999\)Resource\-constrained project scheduling: notation, classification, models, and methods\.European journal of operational research112\(1\),pp\. 3–41\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p1.1)\.
- R\. Dechter and J\. Pearl \(1985\)Generalized best\-first search strategies and the optimality of a\*\.J\. ACM32\(3\),pp\. 505–536\.External Links:ISSN 0004\-5411,[Link](https://doi.org/10.1145/3828.3830),[Document](https://dx.doi.org/10.1145/3828.3830)Cited by:[Resource\-Based Heuristic](https://arxiv.org/html/2605.15983#Sx4.SSx1.SSSx2.p4.3)\.
- U\. Dorndorf, E\. Pesch, and T\. Phan\-Huy \(2000\)A branch\-and\-bound algorithm for the resource\-constrained project scheduling problem\.Mathematical Methods of Operations Research52,pp\. 413–439\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2),[MIP Formulation](https://arxiv.org/html/2605.15983#Sx5.p1.3)\.
- S\. Edelkamp and S\. Jabbar \(2006\)Action planning for directed model checking of Petri nets\.Electronic Notes in Theoretical Computer Science149\(2\),pp\. 3–18\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- J\. Forrest and R\. Lougee\-Heimer \(2005\)CBC user guide\.Technical reportCOIN\-OR Foundation\.Cited by:[MIP Formulation](https://arxiv.org/html/2605.15983#Sx5.p1.3)\.
- P\. E\. Hart, N\. J\. Nilsson, and B\. Raphael \(1968\)A formal basis for the heuristic determination of minimum cost paths\.IEEE transactions on Systems Science and Cybernetics4\(2\),pp\. 100–107\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2),[Resource\-Based Heuristic](https://arxiv.org/html/2605.15983#Sx4.SSx1.SSSx2.p4.3)\.
- S\. Hartmann and D\. Briskorn \(2022\)An updated survey of variants and extensions of the resource\-constrained project scheduling problem\.European Journal of operational research297\(1\),pp\. 1–14\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p1.1)\.
- W\. Herroelen, B\. De Reyck, and E\. Demeulemeester \(1998\)Resource\-constrained project scheduling: a survey of recent developments\.Computers & Operations Research25\(4\),pp\. 279–302\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p1.1)\.
- B\. Huang, M\. Zhou, X\. S\. Lu, and A\. Abusorrah \(2023\)Scheduling of resource allocation systems with timed petri nets: a survey\.ACM Computing Surveys55\(11\),pp\. 1–27\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- R\. Kolisch and A\. Sprecher \(1997\)PSPLIB\-a project scheduling problem library: OR software\-ORSEP operations research software exchange program\.European Journal of Operational Research96\(1\),pp\. 205–216\.Cited by:[Experiments and Discussion](https://arxiv.org/html/2605.15983#Sx6.p1.1)\.
- O\. Koné, C\. Artigues, P\. Lopez, and M\. Mongeau \(2011\)Event\-based milp models for resource\-constrained project scheduling problems\.Computers & Operations Research38\(1\),pp\. 3–13\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- G\. Mejia, K\. Nino, C\. Montoya, M\. A\. Sanchez, J\. Palacios, and L\. Amodeo \(2016\)A petri net\-based framework for realistic project management and scheduling: an application in animation and videogames\.Computers & Operations Research66,pp\. 190–198\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- G\. Mejia and N\. G\. Odrey \(2005\)An approach using petri nets and improved heuristic search for manufacturing system scheduling\.Journal of Manufacturing Systems24\(2\),pp\. 79–92\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- R\. Pellerin, N\. Perrier, and F\. Berthaut \(2020\)A survey of hybrid metaheuristics for the resource\-constrained project scheduling problem\.European Journal of Operational Research280\(2\),pp\. 395–416\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- C\. A\. Petri \(1966\)Communication with automata\.Technical Report No\. RADC\-TR\-65\-377\.Cited by:[Timed Transition Petri Net with Resources](https://arxiv.org/html/2605.15983#Sx3.p1.12)\.
- S\. Russell and P\. Norvig \(2020\)Artificial intelligence: a modern approach\.4th edition,Pearson\.Note:Cited by:[Proof\.](https://arxiv.org/html/2605.15983#Sx4.SSx1.SSSx2.3.p1.1)\.
- S\. K\. Sadhukhan \(2013\)Bidirectional heuristic search based on error estimate\.CSI Journal of Computing2\(1\-2\),pp\. S1:57–S1:64\.Cited by:[Conclusion](https://arxiv.org/html/2605.15983#Sx7.p1.2)\.
- Y\. Wu, X\. Zhuang, G\. Song, X\. Xu, and C\. Li \(2009\)Solving resource\-constrained multiple project scheduling problem using timed colored petri nets\.Journal of Shanghai Jiaotong University \(Science\)14,pp\. 713–719\.Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.
- R\. Zamani and L\. Shue \(1998\)Solving project scheduling problems with a heuristic learning algorithm\.Journal of the Operational Research Society49\(7\),pp\. 709–716\.External Links:[Document](https://dx.doi.org/10.1057/palgrave.jors.2600546),[Link](https://doi.org/10.1057/palgrave.jors.2600546),https://doi\.org/10\.1057/palgrave\.jors\.2600546Cited by:[Introduction](https://arxiv.org/html/2605.15983#Sx1.p2.2)\.