Temporal Analysis of Projects Under Interval Uncertainty

Christian Artigues (1) , Cyril Briand (1) , Thierry Garaix (2)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes

Given an activity-on-node network where every activity has an uncertain duration represented by an interval, this chapter takes an interest in computing the minimum and maximum earliest start times, latest start times and floats of all activities over all duration scenarios. The basic results from the literature are recalled and efficient solving algorithms are detailed. A particular focus is put on the computation of minimum float, which remains a N P-hard optimization problem. For this last case, a recent and efficient branch and bound algorithm is described that outperforms previously proposed methods. In standard deterministic project scheduling, temporal analysis aims at determining the temporal degree of freedom of activities under simple finish-start precedence constraints. More precisely, it aims at computing for every activity i its earliest start and completion times ES i and EC i , its latest start and completion times LS i and LC i and its total float T F i. It is well known that these values can be computed via longest path computation in the project network where each arc (i, j) is evaluated by the duration of i. More precisely, if d i j denotes the length of the longest path from i to j in this graph, ES i is the longest path from dummy node 0 to node i: ES i = d 0i. LS i is the length of the longest path from dummy node 0 do dummy node n + 1 (schedule

Mots clés: Project scheduling; Temporal analysis; Interval uncertainty; Algorithms; Complexity; Branch-and-bound

Domaines: Recherche opérationnelle [math.OC]

Christian Artigues, Cyril Briand, Thierry Garaix. Temporal Analysis of Projects Under Interval Uncertainty. Christoph Schwindt; Jürgen Zimmermann. Handbook on Project Management and Scheduling, Volume 2, 2, Springer, 2015, 9783319059143. ⟨10.1007/978-3-319-05915-0_11⟩. ⟨hal-01231039⟩