AI TrackerFrontier desk · AEST
Back to news
normalaitech

Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling

arXiv cs.AI · 11 Nov 2026, 04:03 AEST

Branch-and-Bound and A* are two exact search methods with different computational performances in resource-constrained project scheduling. Experiments show that graph-based A* significantly outperforms B&B variants in solving benchmark instances.

Key facts

Read aloud

Branch-and-Bound and A are two exact search methods with different computational performances in resource-constrained project scheduling. Experiments show that graph-based A significantly outperforms B&B variants in solving benchmark instances. Branch-and-Bound B&B and $A^ $ are popular exact search methods originating from Operations Research and Artificial Intelligence, respectively. Experiments on four hundred eighty benchmark RCPSP instances show that graph-based $A^ $ substantially outperforms the B&B variants considered. With additional pruning rules, $A^ $ proves optimality for all four hundred eighty instances, compared with four hundred forty five for best-first B&B under the same time and memory limits. Our findings highlight the importance of duplicate-state detection and clarify the computational trade-offs between the search approaches.

Sources in this cluster