PM Methodologies

Critical Path Method: History, Worked Example, Crashing

By Vact Published · Updated

The critical path method (CPM) finds the longest chain of dependent activities in a project. That chain sets the earliest possible finish date, and each day it slips moves the finish by a day unless the plan changes. The US Government Accountability Office (GAO) puts it this way: when a network has no date constraints, critical activities have zero float, “and therefore any delay in the critical activity causes the same day-for-day delay in the program forecast finish date” (GAO-16-89G, Best Practice 6). Everything else in CPM, from the forward pass to crashing, is a way of finding that chain and deciding what to do about it.

Where CPM came from

CPM was built between a chemical company and a computer maker. James E. Kelley Jr. and Morgan R. Walker presented “Critical-Path Planning and Scheduling” at the Eastern Joint Computer Conference in Boston on 1-3 December 1959 (DOI 10.1145/1460299.1460318, pages 160-173). The paper lists both authors at Mauchly Associates of Ambler, Pennsylvania; the work it describes was done earlier, for DuPont. Their account of the origin, in the paper’s own text (scan hosted by Mosaic Projects):

  • In late 1956 DuPont’s Integrated Engineering Control group began surveying how computers could help manage engineering projects. It wanted the planning and scheduling of all project functions combined into “a single master plan”. Remington Rand UNIVAC assigned Kelley to help as part of its customer service, while Walker represented DuPont.
  • The fundamentals were developed in early 1957. By May 1957 a cooperative effort began, with Remington Rand supplying programs for DuPont’s UNIVAC I in Newark, Delaware, and the results were officially demonstrated in September 1957.
  • The first full test, called Project A in the paper, used a team given a 40-hour workshop. The plan was so detailed that the UNIVAC I programs became impractical, and Remington Rand reprogrammed the system for the larger 1103A.
  • A second test applied the method to a plant shutdown and overhaul at DuPont’s Louisville Works.

The paper’s results explain why the method spread. On Project A the authors report that the computer indicated two months could be gained at no additional cost, and a further two months for a 1% increase in the variable direct cost of the project. The reason, they say, was that “only a very few jobs were critical - about 10%”, so only those needed expediting. Of 156 delivery items, the computation found seven critical ones, three of which the conventional scheduling group had missed. These figures come from DuPont’s test projects; the share of critical work on any other project depends on its own network.

The parallel PERT story

The US Navy developed PERT in 1958 for the Polaris Fleet Ballistic Missile (FBM) program, while DuPont’s CPM tests were still running. Polaris was run by the Navy’s Special Projects Office, set up on 17 November 1955 at President Eisenhower’s direction (US Navy Strategic Systems Programs). PERT’s developers, three operations analysts from Booz, Allen and Hamilton and W. Fazar of the Special Projects Office, described the work in Operations Research in 1959 (Malcolm, Roseboom, Clark and Fazar, DOI 10.1287/opre.7.5.646):

  • The project was named PERT for “Program Evaluation Research Task” and later renamed the Program Evaluation and Review Technique.
  • The Special Projects Office implemented it in 1958, running the calculations on the Naval Ordnance Research Computer (NORC) at Dahlgren, Virginia.
  • By mid-1959, “only 17 months after the research task began”, PERT covered most of the FBM weapon system, with 23 networks of more than 2,000 events and some 3,000 activities.

Later accounts are more sceptical about its day-to-day role. A Mosaic Projects white paper says PERT was not widely used within the Polaris program itself, although it was widely publicised and credited with “saving 2 years”.

PERT differs from CPM in how it treats uncertainty. Each activity gets an optimistic (a), most likely (m) and pessimistic (b) time. The 1959 paper combines them as [2m + (a + b) / 2] / 3, which is the familiar (a + 4m + b) / 6. To keep the computation practical, the developers gave each event the expected time and variance of its longest incoming path, and wrote that “this simplification gives biased estimates such that the estimated expected time of events are always too small”. A 2020 paper in The Professional Constructor, “PERT, CPM and the Tangled History of Network Scheduling”, argues that CPM was derived from PERT and that the two have a closer shared origin than the usual story of independent inventions. The published accounts differ on this, so treat the two methods as contemporaries that share the same network logic.

Timeline

DateEventSource
17 Nov 1955US Navy Special Projects Office set up to develop the first submarine-launched ballistic missile, which became PolarisUS Navy SSP
Late 1956DuPont’s Integrated Engineering Control group starts surveying computer aids for project planningKelley and Walker 1959
Early 1957Kelley and Walker develop the CPM fundamentalsKelley and Walker 1959
May 1957Remington Rand and DuPont begin cooperative implementation on a UNIVAC IKelley and Walker 1959
Sep 1957CPM officially demonstratedKelley and Walker 1959
Early 1958PERT research task begins at the Special Projects Office, with Booz, Allen and HamiltonMalcolm et al. 1959
March 1958First part of Project A test complete; about 40% plan change led to a recomputeKelley and Walker 1959
Mid-1959PERT covers most of the Polaris weapon system: 23 networks, more than 2,000 eventsMalcolm et al. 1959
Dec 1959Kelley and Walker present the CPM paper in BostonKelley and Walker 1959

The vocabulary: ES, EF, LS, LF and float

Every activity in a CPM network carries four dates and two float values. The definitions below follow the GAO’s Schedule Assessment Guide.

TermMeaningHow it is calculated
Early start (ES)Earliest the activity can beginLatest early finish among its predecessors (0 if none)
Early finish (EF)Earliest the activity can endES + duration
Late finish (LF)Latest the activity can end without delaying the projectEarliest late start among its successors (project finish if none)
Late start (LS)Latest the activity can begin without delaying the projectLF - duration
Total floatHow far the activity can slip before the project finish movesLS - ES (or LF - EF)
Free floatHow far it can slip before it delays its immediate successorEarliest successor ES - EF

The GAO describes the forward pass as adding durations successively through the network, and the backward pass as subtracting durations from late finishes. Kelley and Walker’s original paper already defined four kinds of float: total, free, independent and interfering. Total float can be negative when a date constraint is tighter than the logic allows, and the GAO treats an activity with zero or negative total float as critical.

A complete worked example

Eight activities for fitting out a small office. Durations are working days, and day 0 is the start of day 1.

ActivityDescriptionDurationPredecessors
ASurvey and measure3none
BLayout drawings4A
CLandlord approvals6A
DOrder furniture5B
EElectrical and data work4B, C
FInstall and inspect3D, E
GSignage permit2C
HHandover2F, G

Forward pass

Start at 0 and add durations. Where an activity has several predecessors, take the latest early finish. E waits for both B (day 7) and C (day 9), so E starts on day 9. F waits for D (day 12) and E (day 13), so F starts on day 13. H waits for F (day 16) and G (day 11), so H starts on day 16 and finishes on day 18.

Backward pass

Start from the finish, day 18, and subtract. Where an activity has several successors, take the earliest late start. C feeds E (late start 9) and G (late start 14), so C’s late finish is 9. B feeds D (late start 8) and E (late start 9), so B’s late finish is 8.

Result

ActivityDurationESEFLSLFTotal floatFree float
A3030300
B4374810
C6393900
D571281311
E491391300
F31316131600
G2911141655
H21618161800

The critical path is A, C, E, F, H: 3 + 6 + 4 + 3 + 2 = 18 working days. Three observations that the table makes visible:

  • B and D share one day of float. A-B-D-F-H adds up to 17 days, one day under the critical path. Their one day of total float is shared between them: B has total float 1 but free float 0, because using that day pushes D’s early start from 7 to 8. D then has 1 day of free float because F is waiting on E until day 13 anyway. This is the distinction the GAO draws when it says float “is shared along a sequence of activities” and “should not be treated as schedule contingency”.
  • G has 5 days of float and can move without touching anything critical. That is the activity a manager shifts when a signage contractor is unavailable.
  • B and D are near-critical. The GAO calls activities with total float close to the critical path’s “near-critical” because they “can quickly become critical if their small amount of total float is used up in a delay”, and says management must monitor them closely.

Crashing and fast-tracking

When the calculated finish is later than the deadline, only changes to the critical path help. The GAO’s table of recovery and acceleration strategies lists the two classic techniques and their side effects:

TechniqueWhat it doesSide effect named by the GAO
CrashingAdds resources to time-dependent activitiesRequires additional resources and increases costs; may reduce quality if less-experienced labor is used
Fast trackingReduces sequential dependencies to partial ones, for example finish-to-start becomes start-to-startResources may become overallocated; quality may suffer and risk rises when work that is best done in sequence runs in parallel

Kelley and Walker framed crashing as a cost trade-off. Each job has a normal duration and a shortest “crash duration”, and the extra cost of shortening it is fitted as a straight line between the two. Their procedure expedites only critical jobs, and among those only the ones that raise cost at the lowest rate. As the finish date moves in, more jobs become critical and the choice of jobs changes.

Crashing the office fit-out, step by step

The cost figures below are assumptions made for this example. Suppose each critical activity can be shortened by at most one day, at these prices per day: F, 500; E, 800; C, 1,200; A, 1,500; H, 2,000. B and D cannot be shortened. Crash the cheapest critical activity first and recalculate every path after each step.

StepActionAdded costA-C-E-F-HA-B-D-F-HFinish
Startnone0181718
1Crash F by 1 day500171617
2Crash E by 1 day800161616
3Crash A by 1 day (the cheapest shared activity left)1,500151515

Total cost for 3 days: 2,800. Step 2 shows why the work gets harder: the two paths now tie, so any further saving has to shorten both at once. With B and D fixed, that means an activity the paths share: F is already at its limit, and A at 1,500 is cheaper than H at 2,000. Crashing C alone would not help, because the path through B and D is already as long. Kelley and Walker describe the same mechanism: at each stage the jobs expedited form a “cut set” across the critical jobs, so every critical path gets shorter together.

Fast-tracking the same plan

Suppose the electrical work E can begin when approvals C are three days in, rather than after C finishes. Change C-to-E from finish-to-start to start-to-start with a 3-day lag. E now starts at day 7, when B finishes, instead of day 9. E ends on day 11, F runs from day 12 to 15 and H from 15 to 17. The project gains one day, not two, because the former near-critical path A-B-D-F-H (17 days) is now the longest. The risk is concentrated where the overlap happens: electrical work begins before approvals are complete.

Resource limits can change the answer

Standard CPM calculation assumes the people exist. Take activities A (2 days), then B (5 days) and C (3 days) in parallel, then D (2 days) after both. The A-B-D path takes 9 days and A-C-D takes 7, so C has 2 days of float. If B and C need the same person, they can no longer overlap: after A, their combined 8 days must run in sequence before D, and the finish becomes day 12 rather than 9. Resource availability belongs in the model before a date is promised. The GAO notes that leveling always consumes float along a path, and that it generally targets activities with free float first, because delaying them within that float leaves their successors untouched; see resource allocation planning for capacity methods.

How scheduling tools present it

Tools calculate the passes automatically, so the skill that matters is reading what they show and the settings that change it. Microsoft’s Project documentation says:

  • In the Detail Gantt view, critical tasks appear in red and total slack appears as a thin teal line (Manage your project’s critical path).
  • Project defines critical tasks as those that have no slack, and by default displays only one critical path, the one that affects the plan’s finish date. It can be configured to show a path for each independent series of tasks.
  • Total Slack and Free Slack fields appear in the Schedule table, and the threshold for “critical” can be raised in File > Options > Calculation Options, so that tasks with a little slack are flagged too (Show slack in your project).

Two cautions follow from the GAO guidance. A date constraint can produce negative float and make an activity appear critical even when it is not on the longest path, so Best Practice 6 asks that the critical path be validated as the longest path. And “unreasonably high total float on an activity or path indicates that schedule logic might be missing or invalid”, which is the quickest test for a dangling activity with no successor.

Where CPM sits today

CPM models work whose durations and dependencies can be stated: construction, shutdowns, hardware and infrastructure programs, and the release dependencies of larger software efforts. Teams that plan in fixed-length sprints rarely schedule every task this way, but the technique still maps release-level dependencies such as an API change that must land before a migration, and then an app store review. For how the approach compares with iterative planning, see agile vs waterfall.

Keeping the model true

  • Record actual starts and finishes, then re-estimate remaining work from today.
  • Look for activities with no successor, unexplained date constraints, and relationships added only to force a desired finish.
  • Compare the new controlling path with the last one and explain any change in the status report.
  • Build the activity list from a work breakdown structure, and test a first-pass date with the project timeline calculator.

Sources