Robust optimization for resource-constrained project scheduling with uncertain activity durations

The purpose of this paper is to propose models for
project scheduling when there is considerable uncertainty in the
activity durations, to the extent that the decision maker cannot
with confidence associate probabilities with the possible scenarios.
Our modeling techniques stem from robust optimization, which
is a theoretical framework that enables the decision maker to
produce solutions that will have a reasonably good objective value
under any likely input data scenario. We develop and implement
a scenario-relaxation algorithm and a scenario-relaxationbased
heuristic. The first algorithm produces optimal solutions
but requires excessive running times even for medium-sized
instances; the second algorithm produces high-quality solutions
for medium-sized instances and outperforms two benchmark
heuristics.