A novel branch-and-bound algorithm for the chance-constrained RCPSP

The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a MILP formulation that solve the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. Since solving CC-RCPSP is computationally intractable, its sample average approximation counterpart is considered to be solved. The computational results suggest that the proposed branch-and-bound procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.