Summary: This paper concerns project scheduling under uncertainty. The project is modeled as an activity-on-node network, each activity having an uncertain duration represented by an interval. The problem of computing the minimum float of each activity over all duration scenarios is addressed. For solving this NP-hard problem, D. Dubois et al. [“Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks”, J. Intell. Manuf. 16, 407–422 (2005)] and J. Fortin et al. [J. Sched. 13, No. 6, 609–627 (2010; Zbl 1208.90061)] have proposed an algorithm based on path enumeration. In this paper, new structural properties of optimal solutions are established and used for deriving a lower bound and designing an efficient branch-and-bound procedure. Two mixed-integer programming formulations are also proposed. Computational experimentations have been conducted 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.