Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks

In project management, three quantities are often used by project managers: the earliest starting date, the latest starting date and the float of tasks. These quantities are computed by the Program Evaluation and Review Techniques/Critical Path Method (PERT/CPM) algorithm. When task durations are ill known, as is often the case at the beginning of a project, they can be modeled by means of intervals, representing the possible values of these task durations. With such a representation, the earliest starting dates, the latest starting dates and the floats are also intervals. The purpose of this paper is to give efficient algorithms for their computation. After recalling the classical PERT/CPM problem, we present several properties of the concerned quantities in the interval-valued case, showing that the standard criticality analysis collapses. We propose an efficient algorithm based on path enumeration to compute optimal intervals for latest starting times and floats in the general case, and a simpler polynomial algorithm in the case of series-parallel activity networks.