When it is worthwhile to work with the stochastic RCPSP?

The Resource-Constrained Project Scheduling Project (RCPSP), together with some of its extensions, has been widely studied. A fundamental assumption in this basic problem is that the duration of activities is known before their execution. Very little effort has been made in developing heuristics for the RCPSP with stochastic durations, that is, when the duration of activities is given by a distribution of probability. In fact, the deterministic approach is often used even in the presence of non-trivial distributions. In this paper we discuss when it is worth the effort, in heuristic algorithms, to work with stochastic durations instead of deterministic ones. We also describe techniques that seem to be useful for a wide variety of heuristic algorithms for the stochastic problem. We develop two algorithms that include these procedures and that are capable of outperforming other existing heuristics in the literature. Computational experiments are provided on instances based on the standard set j120, generated using ProGen, and on the well-known Patterson set.