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

Christian Artigues (1) , Roel Leus (2) , Fabrice Talla Nobibon (2)

1 LAAS-MOGISA
2 KU Leuven - Catholic University of Leuven = Katholieke Universiteit Leuven

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 outcomes of a decision. 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-relaxation-based 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.

Mots clés: project scheduling; RCPSP; uncertainty; robust optimization

Domaines: Recherche opérationnelle [math.OC]

Christian Artigues, Roel Leus, Fabrice Talla Nobibon. Robust optimization for resource-constrained project scheduling with uncertain activity durations. Flexible Services and Manufacturing Journal, 2013, 25 (1-2), pp.175-205. ⟨10.1007/s10696-012-9147-2⟩. ⟨hal-00564435⟩