@article{10.11648/j.mcs.20261104.11,
  author = {Hawa Kaba Bah and Amadou Oury Balde and Ibrahima Bah and Aboubakary Diakhaby},
  title = {A Ford-Based Branch-and-Bound with Minimum Cut Lower Bounds for the Resource-constrained Project Scheduling Problem},
  journal = {Mathematics and Computer Science},
  volume = {11},
  number = {4},
  pages = {64-70},
  doi = {10.11648/j.mcs.20261104.11},
  url = {https://doi.org/10.11648/j.mcs.20261104.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20261104.11},
  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.},
 year = {2026}
}

Copy | Download

TY  - JOUR
T1  - A Ford-Based Branch-and-Bound with Minimum Cut Lower Bounds for the Resource-constrained Project Scheduling Problem
AU  - Hawa Kaba Bah
AU  - Amadou Oury Balde
AU  - Ibrahima Bah
AU  - Aboubakary Diakhaby
Y1  - 2026/07/30
PY  - 2026
N1  - https://doi.org/10.11648/j.mcs.20261104.11
DO  - 10.11648/j.mcs.20261104.11
T2  - Mathematics and Computer Science
JF  - Mathematics and Computer Science
JO  - Mathematics and Computer Science
SP  - 64
EP  - 70
PB  - Science Publishing Group
SN  - 2575-6028
UR  - https://doi.org/10.11648/j.mcs.20261104.11
AB  - 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.
VL  - 11
IS  - 4
ER  - 

Copy | Download