We study branch-and-bound algorithms for resource-constrained
project scheduling where processing times of jobs are random. The
objective is to find a so-called scheduling policy which
minimizes the project makespan in expectation. The proposed
procedures are based upon four classes of scheduling policies
which differ considerably with respect to their computational
tractability as well as with respect to the optimum costs that can
be achieved within the respective class.
The purpose of the paper is twofold. First, we establish results on
the trade-off between computational efficiency and solution quality
for each of the considered classes of policies and evaluate their
practical applicability for scheduling stochastic
resource-constrained projects. Second, we develop and apply various
ingredients such as dominance rules and lower bounds that turn out
to be useful within the computation. In order to comprehensively
study these issues we have implemented five different
branch-and-bound algorithms and explore their computational behavior
on 1440 test instances.
