A Branch-and-Bound Algorithm for the Proactive Resource-Constrained Project Scheduling Problem with Robustness Maximization Objective

This paper proposes a branch-and-bound algorithm (B&B) for the proactive scheduling problem, which incorporates a degree of anticipation for variability in practical projects. First, the resource-constrained proactive scheduling model is formulated. Second, solving its resource-unconstrained problem with an adapted Fulkerson algorithm provides an upper-bound solution. Then, the subproblems of the model are derived by introducing additional precedence relationships for resolving the resource conflict in the upper-bound solution. Third, we solve the resource-constrained proactive scheduling problem with the proposed B&B algorithm. The resource conflicts detected in an upper-bound solution are resolved by adding extra precedence relationships. According to the problem analysis, two dominance rules proposed for additional node fathoming aim to improve the algorithm. Finally, we conduct an extensive computational experiment on 3,000 randomly generated instances. The obtained results show that the B&B algorithm reduces the computational time on average by 94% compared with CPLEX. In addition, the sensitivity analysis of the three key parameters indicates their different impacts on the trend in terms of the computational time and identifies the project deadline among these three parameters as the bottleneck for improving project robustness