About Critical Path Method — CPM & PERT
This simulator demonstrates the Critical Path Method (CPM) and the Program Evaluation and Review Technique (PERT), two foundational algorithms in project scheduling. CPM computes the forward pass (Early Start and Early Finish for each task) and the backward pass (Late Start, Late Finish, and float/slack), then highlights the critical path — the longest chain of dependent tasks that determines the minimum project duration. PERT extends CPM by treating each task duration as a random variable with optimistic (o), most likely (m), and pessimistic (p) estimates, yielding an expected duration t_e = (o + 4m + p) / 6 and a variance used to compute the probability of meeting a deadline.
CPM was developed jointly by DuPont and Remington Rand in the late 1950s for industrial plant maintenance, while PERT was created simultaneously by the U.S. Navy for the Polaris missile program. Both methods are still integral to modern project management frameworks such as PMI's PMBOK and the ISO 21500 standard.
Frequently Asked Questions
What is the critical path in CPM?
The critical path is the longest sequence of dependent tasks from project start to finish, and its total duration equals the minimum possible project completion time. Tasks on the critical path have zero float (slack), meaning any delay to them directly delays the entire project. The simulator highlights these tasks and their connecting edges in red so you can see them instantly.
How do I use the CPM/PERT simulator?
Select a preset project from the dropdown (Textbook DAG, Parallel Tracks, or Near-Tie) to load a directed acyclic graph of tasks. Click any node to select it, then drag the duration slider to change its length and watch the critical path recompute in real time. Use the Step button to animate the forward pass then the backward pass one task at a time, or Auto to play through the full animation. Switch to PERT mode to see expected durations and set a deadline to get the probability of finishing on time.
What is float (slack), and why does it matter?
Float, also called slack, is the amount of time a task can be delayed without delaying the project completion. It is calculated as Late Start minus Early Start (or equivalently Late Finish minus Early Finish). Tasks with zero float are critical; tasks with positive float can be delayed or have resources shifted to critical tasks — a technique called resource leveling that is central to practical project management.
What are the PERT three-point estimates and how is variance computed?
PERT models each task duration as a beta distribution parameterized by three time estimates: optimistic (o, best case), most likely (m, mode), and pessimistic (p, worst case). The expected duration is t_e = (o + 4m + p) / 6, a weighted average that gives four times more weight to the most likely estimate. The variance for each task is σ² = ((p − o) / 6)². For the entire critical path, variances are summed (tasks are assumed independent), giving the path variance used to compute the Z-score for deadline probability.
How is the probability of meeting a deadline calculated in PERT?
Once the expected project duration μ and the summed critical-path variance σ² are known, the deadline probability uses the normal approximation: Z = (deadline − μ) / σ, where σ = √σ². The cumulative normal distribution at Z gives P(T ≤ deadline). The simulator uses the Abramowitz & Stegun polynomial approximation of the error function (erf) to compute this without external libraries. A deadline equal to the expected duration yields roughly 50% probability; adding one σ raises it to about 84%.
Can a project have more than one critical path?
Yes. Multiple paths through the network can share the same maximum duration, making all of them critical simultaneously. This is illustrated by the Near-Tie preset in the simulator, where two parallel routes have nearly equal lengths — a small change to any task on either route can shift which path is critical. Having multiple critical paths is considered higher risk because any delay on any of those paths immediately impacts the project end date.
Who invented CPM and PERT, and when?
CPM was developed in 1957 by Morgan Walker (DuPont) and James Kelley (Remington Rand) for scheduling chemical plant overhauls. PERT was developed independently and almost simultaneously (1957–1958) by the U.S. Navy Special Projects Office with Booz Allen Hamilton for the Polaris Fleet Ballistic Missile program, which required coordinating thousands of contractors and sub-contractors. Both methods were first published in 1959 and are widely credited with reducing the Polaris program schedule by two years.
What is the difference between a DAG and a general graph in scheduling?
CPM and PERT require a Directed Acyclic Graph (DAG) — a directed graph with no cycles — because a cyclic dependency (A depends on B, B depends on A) would make scheduling logically impossible. The topological sort used in the forward and backward passes is only valid for DAGs. Real project networks are always DAGs by definition: a task cannot start before itself is finished. The simulator enforces this by using only the preset acyclic structures.
How is CPM/PERT used in modern software and construction projects?
CPM is embedded in tools such as Microsoft Project, Primavera P6, and open-source alternatives like ProjectLibre. In construction, the Association for the Advancement of Cost Engineering (AACE) mandates CPM scheduling for large projects; on software projects, CPM underlies Gantt chart generation in Jira and similar platforms. PERT three-point estimation is also the basis for Planning Poker refinements and reference-class forecasting used in agile story-pointing.
What are the limitations of classical CPM/PERT analysis?
CPM assumes deterministic durations, which is rarely true in practice. PERT addresses this partially but still assumes independence between task durations (correlated risks are ignored) and approximates the path duration distribution as normal, which underestimates the probability of delay — the so-called “merge bias” or “PERT bias.” Monte Carlo simulation (sampling thousands of random scenarios) is the modern remedy, used in risk-adjusted scheduling tools. Additionally, neither method accounts for resource constraints; that requires resource-constrained project scheduling (RCPS), which is NP-hard in general.
What related scheduling problems extend CPM?
Resource-Constrained Project Scheduling (RCPS) adds resource limits to CPM, making it NP-hard. Critical Chain Project Management (CCPM), proposed by Eliyahu Goldratt, relocates buffers from individual tasks to the end of the chain and to feeding chains. Time-cost tradeoff (crashing) extends CPM by letting you spend extra money to shorten task durations and asks: what is the cheapest way to shorten the project by a given amount? These extensions are active research areas in operations research and management science.