Journal
JOURNAL OF INTELLIGENT MANUFACTURING
Volume 16, Issue 4-5, Pages 407-421Publisher
SPRINGER
DOI: 10.1007/s10845-005-1654-5
Keywords
PERT; CPM; earliest starting date; latest starting date; float; series-parallel graph
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available