Fast minimum float computation in activity networks under interval uncertainty

International audienceThis paper considers the following basic problem in scheduling under uncertainty: given an activity-on-node network where each activity has an uncertain duration represented by an interval, compute the minimum float of each activity over all duration scenarios. For solving this NP-hard problem, Dubois et al. 2005 and Fortin et al. 2010 have recently proposed an algorithm based on path enumeration. In this paper, we establish structural properties of optimal solutions and a new lower bound allowing us to design an efficient branch-and-bound procedure. We also propose two mixed integer programming formulations. The methods are compared experimentally on a large variety of randomly generated problem instances. The results show that the proposed branch-and-bound procedure is very fast and consistently outperforms the MIP formulations and the path enumeration algorithm