An exact algorithm for the chance-constrained resource-constrained project scheduling problem

The chance-constrained resource-constrained project scheduling problem (CC RCPSP) is the problem of finding a non-preemptive schedule of minimum makespan, such that it is feasible with respect to the precedence and the resource constrains, for a given probability (or confidence). One of the main attributes of this problem is that it generates a robust proactive schedule which is independent of any reactive policy that is planned to be applied. The drawback is its computational tractability: the well-known (theoretical and practical) computational intractability of the (deterministic) RCPSP is amplified in this case. Here, we present an exact branch and bound (b&b) algorithm for solving the CC RCPSP. It is based on upper and lower bounds obtained by solving the RCPSP. Thus, our method does not depend on integer programming (IP) formulations of the RCPSP that in general perform worse than ad-hoc methods, i.e. methods that are not based on linear programming relaxations. We provide results of computational experiments that clearly show the practical benefits of our algorithm over an alternative IP approach: our algorithm was able to solve more instances to optimality for small confidence levels; its optimality gaps were smaller for all confidence levels; it requires less memory; and it does not have precision problems. Finally, we believe that this research is a contribution to the general chance-constrained programming (CCP) literature since all theoretical and algorithmic results can be extended to general CCP problems.status: publishe