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
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
Research Article
Comparing FDM, FVM, and FEM for Coupled Flow-Transport in a Guinean Bauxite Mining Aquifer
Michel Faya Kamano,
Mouhamadou Nassirou Diallo,
Mariama Ndiaye,
Aboubakary Dinakhaby*
Issue:
Volume 11, Issue 4, August 2026
Pages:
71-77
Received:
31 May 2026
Accepted:
10 June 2026
Published:
11 August 2026
DOI:
10.11648/j.mcs.20261104.12
Downloads:
Views:
Abstract: Bauxite mining in Guinea, particularly in the Boke region, generates significant risks of groundwater contamination by metals and acidification. This paper develops a deterministic coupled groundwater flow and reactive solute transport model applied to the N'Dangara and Boundou Wande bauxite plateaus (CBG concession, Sangaredi, Guinea). The steady-state flow equation and the transient advection-dispersion-reaction equation are discretised using three numerical methods: finite differences (FDM), finite volumes (FVM), and finite elements (FEM). Model parameters are taken from three field campaigns that provided piezometric measurements and physico-chemical analyses. The field data show dispersed flow directions controlled by topography and water table depths between 1.09 m and 17.39 m. Water quality analyses indicate acidic groundwater with pH values as low as 4.84--5.13. Numerical results show that FVM gives the best mass conservation (error < 0.1 \%) and sharpest fronts, FEM is most accurate on irregular geometries, and FDM is fastest but suffers from numerical dispersion. The calibrated model predictions agree well with field observations. This work offers a validated deterministic framework for groundwater risk assessment in Guinean bauxite mining and provides practical guidance for method selection in data-sparse regions.
Abstract: Bauxite mining in Guinea, particularly in the Boke region, generates significant risks of groundwater contamination by metals and acidification. This paper develops a deterministic coupled groundwater flow and reactive solute transport model applied to the N'Dangara and Boundou Wande bauxite plateaus (CBG concession, Sangaredi, Guinea). The steady-...
Show More
