Research Article
A Ford-Based Branch-and-Bound with Minimum Cut Lower Bounds for the Resource-constrained Project Scheduling Problem
Hawa Kaba Bah,
Amadou Oury Balde,
Ibrahima Bah,
Aboubakary Diakhaby*
Issue:
Volume 11, Issue 4, August 2026
Pages:
64-70
Received:
4 June 2026
Accepted:
13 June 2026
Published:
30 July 2026
DOI:
10.11648/j.mcs.20261104.11
Downloads:
Views:
Abstract: The Resource-Constrained Project Scheduling Problem (RCPSP) is a classical NP-hard optimization problem with numerous real-world applications in construction, manufacturing, software development, and logistics. The Ford algorithm efficiently computes earliest and latest start times under precedence constraints in linear time. However, its direct extension to the resource-constrained case is not trivial because resource constraints break the topological order independence. This paper presents a new exact branch-and-bound algorithm that integrates the Ford algorithm for precedence propagation with a minimum cut lower bound for resource constraints. The minimum cut bound is computed via a max-flow algorithm on a time-expanded network constructed from the earliest start and latest finish times of unscheduled activities. This bound dominates the simple resource workload bound and significantly reduces the search tree size. We combine the remaining critical path length with the min-cut bound to obtain a tight admissible lower bound. A depth-first search with time-indexed branching and a dominance rule is developed. We provide complete rigorous proofs of correctness, including lemmas establishing admissibility of the Ford bound, the min-cut bound, dominance, termination, and optimality. Computational experiments are conducted on the standard PSPLIB benchmark sets. Our algorithm solves all 480 j30 instances (30 activities, 4 resources) optimally within 2 seconds on average, and solves 89% of the 480 j60 instances (60 activities) optimally within a 600-second time limit, outperforming the classical workload bound by 11% in solved instances and 31% in CPU time. The min-cut bound reduces the search tree size by 47% on j60 instances. The algorithm is transparent, easy to implement, requires no commercial software, and is fully reproducible.
Abstract: The Resource-Constrained Project Scheduling Problem (RCPSP) is a classical NP-hard optimization problem with numerous real-world applications in construction, manufacturing, software development, and logistics. The Ford algorithm efficiently computes earliest and latest start times under precedence constraints in linear time. However, its direct ex...
Show More
