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
- Branch-and-Bound (B&B) and $A^*$ are popular exact search methods originating from Operations Research and Artificial Intelligence, respectively.
- Experiments on 480 benchmark RCPSP instances show that graph-based $A^*$ substantially outperforms the B&B variants considered.
- With additional pruning rules, $A^*$ proves optimality for all 480 instances, compared with 445 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.
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
- Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling
arXiv cs.AI · 11 Nov 2026, 04:03 AEST