Graph Search Beats Tree Search for Scheduling — and Two Fields Spent Decades Not Noticing

A controlled experiment pits OR's Branch-and-Bound against AI's A* on 480 scheduling instances. A*'s duplicate-state detection is the decisive mechanism.

Imagine you're solving a maze, but this maze has multiple paths that lead to the same intersection. A tree-search explorer treats every arrival at that intersection as a brand-new discovery — redoing all the work downstream each time. A graph-search explorer marks intersections as visited. Over a large maze, the graph searcher finishes while the tree searcher is still wandering through corridors it has already mapped. This paper takes that insight and applies it to the Resource-Constrained Project Scheduling Problem (RCPSP), a well-studied NP-hard problem where you assign tasks to limited resources over time. The committed claim: graph-based A* with duplicate-state detection substantially outperforms Branch-and-Bound (B&B) tree search on RCPSP, not because of heuristic cleverness, but because of the fundamental difference in how they handle states reachable by multiple paths. The authors deliberately use basic implementations of both methods — same lower bound, same best-first node selection — to isolate the search mechanism itself from solver engineering. This is a clean experiment, not a product comparison. The results are unambiguous. On 480 standard PSPLIB benchmark instances (the J30, J60, J90, J120 sets), A* with pruning rules proves optimality for all 480 instances within the time and memory limits. Best-first B&B manages 445 under identical constraints. The gap widens on harder instances. The paper also tests depth-first B&B, which trades optimality guarantees for lower memory consumption — useful when you need any feasible solution fast but don't need proof of optimality. Architecturally, the paper bridges three representations that these communities rarely connect: mixed-integer linear programming (MILP) formulations from OR, state-action models from AI planning, and timed Petri-net models from systems theory. The authors show formal equivalences between these representations, which is genuinely useful for cross-pollination. The MILP relaxation provides lower bounds; A* uses these bounds within its graph search; B&B uses them within its tree search. Stronger LP relaxations tighten the bound but introduce enough computational overhead that the net effect is ambiguous — a finding that matters for practitioners choosing solver configurations. The integrity setup is solid for this type of work. PSPLIB is the community standard benchmark for RCPSP, publicly available and used for decades. The comparison is controlled: same bounds, same node selection strategy, same hardware, same time limits. The authors are honest about what they are NOT doing — they explicitly avoid comparing against state-of-the-art solvers with decades of engineering, because the point is to understand the mechanism, not to crown a winner. This is a methodological contribution, not a performance claim. The limitation is scope. RCPSP is one problem class. The authors acknowledge but do not test whether the A* advantage from duplicate-state detection transfers to other combinatorial optimization problems with similar structure. They also don't test on instances larger than 120 activities, which is modest by industrial standards. The obvious next experiment — scaling to 500+ activity instances and testing on multi-mode or multi-project variants — wasn't run, likely because the point of this paper is the controlled comparison, not industrial scaling. The real value here is the bridge itself. OR researchers building B&B solvers should seriously consider incorporating duplicate-state detection. AI researchers building A* planners for scheduling should look at LP relaxation bounds from the OR toolkit. Two communities, one search space, decades of parallel development with surprisingly little cross-talk. This paper maps the gap concretely enough to start closing it.