Project Schedule: Method

Critical Path Method, PERT and Schedule Risk

The activity network

A project is a set of activities, each with a duration and a list of immediate predecessors: the activities that must be finished (or, with the other relation types, started) before it can begin. Drawn as an activity-on-node network the project reads from a start to a finish, and every path through it is a chain of activities that must be done one after the other. The longest path sets the shortest possible project duration; that path is the critical path (Kelley and Walker 1959, who built the method for Du Pont plant maintenance; the Navy's PERT of Malcolm, Roseboom, Clark and Fazar 1959 added the three-point estimates). The tool takes the list as text, one activity per line, with the id, a name, the duration or the three estimates and the predecessors, and checks it for unknown ids, duplicated ids and cycles.

Forward and backward passes

The forward pass walks the activities in an order where every predecessor comes first (a topological order) and gives each its earliest start ES, the latest moment at which its predecessor constraints are all satisfied, and earliest finish EF = ES + d. With plain finish-to-start relations ES is the largest EF of the predecessors and zero for a first activity. The project duration T is the largest EF. The backward pass walks the same order in reverse from T: the latest finish LF is the earliest moment at which a successor's constraint would be violated (the smallest LS of the successors, or T for a last activity) and LS = LF − d. The two passes are exact for any network without cycles, however many paths it holds, which is why they replace the enumeration of paths for large projects; the tool still lists the paths and their lengths when there are no more than thirty, because the path table is the quickest way to see which chains are close to critical.

Float

Total float TF = LS − ES = LF − EF is the delay an activity can absorb without delaying the project, provided nothing else slips. Activities with zero total float are critical and form the critical path; a delay on any of them delays the project by the same amount, and shortening the project means shortening them. Free float FF is the smaller quantity: the delay that leaves every successor's earliest start unchanged, min over successors of ES_s − EF (for a finish-to-start relation) and T − EF for a last activity. An activity with total float but no free float shares its float with the chain behind it; using it there takes it from the activities downstream. The Gantt chart shows every activity at its early schedule with the total float as a light band out to its late finish.

Relations and lags

The precedence diagramming method (PMI Practice Standard for Scheduling, 2nd ed., Chapter 4; PMBOK Guide 6th ed. §6.3.2.3) allows four relation types, each with a lag (a delay, positive) or a lead (negative lag):

• finish-to-start, FS + lag: ES_s ≥ EF_p + lag (the default; "A FS+2" means the successor starts at least two time units after A finishes);
• start-to-start, SS + lag: ES_s ≥ ES_p + lag (the successor may start once the predecessor has been under way for the lag);
• finish-to-finish, FF + lag: EF_s ≥ EF_p + lag (the successor cannot finish until the lag after the predecessor finishes);
• start-to-finish, SF + lag: EF_s ≥ ES_p + lag (rare; the successor cannot finish until the lag after the predecessor starts).

The tool writes them as "A SS+3", "A FF-1" or "A(SF+6)" after the predecessor id. The forward pass takes each constraint as a lower bound on ES (for FF and SF the bound on EF is turned into a bound on ES by subtracting the duration); the backward pass takes the mirror image as an upper bound on LF. An early start that a lead would push before the project start is held at zero. Total and free float are then defined as above, with the free float measured on each successor's constraint. Durations are plain numbers in one time unit (days, weeks, months); the tool does not use calendars, resources or constraints on dates.

PERT three-point estimates

When the durations are uncertain, PERT asks for three estimates per activity: the optimistic a (everything goes well), the most likely m and the pessimistic b (everything that can go wrong does, short of disasters). Taking the duration as a beta random variable on [a, b] with its mode at m, the original authors approximated its mean and variance by

μ = (a + 4m + b)/6, σ² = ((b − a)/6)².

The first is the beta mean for the shape parameters 1 + 4(m − a)/(b − a) and 1 + 4(b − m)/(b − a); the second says the whole range a to b spans six standard deviations. Hillier and Lieberman (Chapter 22) then make three simplifying approximations: the mean critical path (the critical path found with every duration at its mean) stays the longest path whatever the durations turn out to be; the durations are independent, so the project mean μ_p and variance σ_p² are the sums over that path; and by the central limit theorem the project duration T is normal. The probability of meeting a deadline d is then Φ((d − μ_p)/σ_p) and the completion time met with confidence C is μ_p + Φ⁻¹(C) σ_p. When several paths tie as the mean critical path the tool uses the one with the largest variance, which gives the lower (safer) probability.

Why PERT is optimistic, and the Monte Carlo

The first approximation fails whenever another path is nearly as long as the critical one: in the outcomes where that path runs long it becomes the critical path, and the project finishes later than the mean critical path alone would say. The project duration is the maximum over the paths, and the mean of a maximum exceeds the maximum of the means; this is the merge bias, and PERT's deadline probability is therefore an upper bound. The same approximation also understates how often the "non-critical" activities matter. Van Slyke (1963) proposed the remedy that every scheduling package now uses: simulate. The tool draws each activity's duration from its own distribution, runs the forward and backward passes, and records the project duration and the critical path, 5,000 times with a fixed seed so that the result reproduces. From the sample it reports the mean, the standard deviation, the percentiles (the 80th or 90th percentile is the figure a cautious plan commits to), the empirical probability of meeting the deadline and the completion time at the chosen confidence, all without a normality assumption. Each activity's criticality index is the fraction of runs in which it had zero total float: the deterministic CPM calls an activity critical or not, the simulation grades it, and an activity with 30 % criticality that CPM marked non-critical deserves watching.

Two sampling distributions are offered. The PERT beta is the distribution the three-point formula describes, with mean (a + 4m + b)/6, so the simulated mean duration of each activity matches PERT and the difference between the simulation and PERT at the project level is the merge bias alone. The triangular distribution on a, m, b is the common choice of schedule-risk practice; its mean (a + m + b)/3 gives more weight to the pessimistic tail, so it produces longer durations than PERT's formula and a lower probability of meeting the deadline. The two should be read as two statements of the same estimates, not as two answers: the beta trusts the most likely value more, the triangular trusts the extremes more.

Worked example on the page

The default data are the Reliable Construction Co. project of Hillier and Lieberman (Introduction to Operations Research, 11th ed., Chapter 22): fourteen activities from excavation to the interior fixtures, three-point estimates in weeks (Table 22.4), a deadline of 47 weeks. The book finds the critical path A → B → C → E → F → J → L → N of 44 weeks (Fig. 22.5, Table 22.3 for the slacks), the six paths of Table 22.2 (40, 31, 43, 44, 41 and 42 weeks), μ_p = 44 and σ_p² = 9 (Table 22.6) and the probability 0.8413 of finishing within 47 weeks; the page reproduces each of them. The simulation shows the merge bias: with PERT-beta durations the chance of meeting 47 weeks is about 0.82 instead of 0.84, and with triangular durations about 0.59, because the path through the roof and the exterior painting (40 weeks at the means but 70 at the pessimistic estimates) overtakes the mean critical path in a third of the runs.

Limits of the tool

• Time only: no resources, resource levelling, calendars, imposed dates or milestones; durations are numbers in one unit.
• No time-cost trade-off (crashing) and no earned value; the Earned Value tool covers the latter.
• The PERT probability relies on the three approximations above; use the Monte Carlo figures when a near-critical path exists, and remember that correlated durations (one cause delaying several activities) widen the distribution beyond what independent sampling shows.
• The three-point estimates are as good as the people who give them; a and b are usually too close to m. Where the pessimistic estimate is meant as a rare extreme the beta is the better model, where it is a plausible bad outcome the triangular.
• The critical-path listing is capped at 25 paths and the path table at 30; large networks are still solved exactly by the passes.