PERT and CPM

Network-based project planning and control using PERT (probabilistic) and CPM (deterministic), including critical path, floats, time–cost trade-offs, and completion-time probability.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Projects in manufacturing, construction, maintenance shutdowns, and new product introduction must meet deadlines at minimum cost. PERT and CPM let you model task dependencies, find the true project duration (critical path), allocate buffers (floats), estimate on-time probabilities under uncertainty, and decide where to spend to accelerate (crash) the project economically.

Key ideas

  • A project is a set of interdependent tasks with precedence constraints. A network graph encodes this logic so that time analysis respects dependencies.
  • Activity: a task that consumes time and (usually) resources. In CPM, durations are treated as deterministic; in PERT, they are random.
  • Event (node): an instant marking the start or completion of activities. In Activity-on-Arrow (AOA) networks, arrows are activities and nodes are events. In Activity-on-Node (AON) networks, nodes are activities and arrows show precedence.
  • Dummy activity: a zero-duration, zero-resource arrow used in AOA to show logical precedence or to avoid two activities having the same head and tail events; dummies never affect project time directly.
  • Precedence constraints: an activity can start only when all its immediate predecessors finish. Networks must be acyclic (no loops), connected from a unique start to a unique finish.

Network construction and numbering

  • AON is common in software tools; AOA appears in exam questions due to float formulas and dummies. Both represent the same logic.
  • Fulkerson-style topological numbering: assign increasing event numbers ensuring all arrows go from a lower-numbered event to a higher-numbered event; number an event only after all its predecessors are numbered. This avoids backward arrows and clarifies precedence.

Time analysis — CPM (deterministic durations)

  • Earliest event time (E): the earliest time an event can occur, obtained by a forward pass taking maxima over predecessor finishes.
  • Latest event time (L): the latest time an event can occur without delaying project completion, obtained by a backward pass taking minima over successor starts.
  • For an activity i→j with duration dᵢⱼ:
    • Earliest start (ES) = Eᵢ; Earliest finish (EF) = ES + dᵢⱼ.
    • Latest finish (LF) = Lⱼ; Latest start (LS) = LF − dᵢⱼ.
  • Critical path: any path from start to finish with maximum total duration. Activities on every critical path have zero total float; delaying any one delays the project.
  • Theorem (critical path property): Project duration equals the maximum of all path lengths; total float of activities on any longest path is zero.

Floats (for activity i→j, duration dᵢⱼ)

  • Total float (TF): time an activity can be delayed without delaying the project. TFᵢⱼ = Lⱼ − Eᵢ − dᵢⱼ = LS − ES = LF − EF.
  • Free float (FF): delay possible without affecting the earliest start of any successor. FFᵢⱼ = Eⱼ − Eᵢ − dᵢⱼ.
  • Independent float (IF): delay possible without affecting earliest successor or using slack from predecessors. IFᵢⱼ = Eⱼ − Lᵢ − dᵢⱼ; take IF = max(0, IFᵢⱼ).
  • Interfering float: portion of total float that, if used, will delay successors’ earliest starts but not the overall project. Interfering float = TF − FF = Lⱼ − Eⱼ.
  • Standard results: On any critical activity, TF = FF = IF = 0. Free float ≤ total float, independent float ≤ free float (by definition and nonnegativity truncation).

Time–cost trade-off (CPM crashing)

  • Normal time/cost: planned duration and cost without expediting; Crash time/cost: shortest feasible duration and its (usually higher) direct cost.
  • Cost slope (linear crashing assumption): cost increase per unit time saved on an activity. Cost slope = (Crash cost − Normal cost) / (Normal time − Crash time).
  • Crashing procedure: iteratively reduce durations of activities on the current critical path(s), choosing the smallest cost slope that reduces project duration without violating precedence or exceeding crash limits; when multiple critical paths exist, crash common critical activities or crash across all critical paths concurrently. Stop when further crashing raises total cost (direct + indirect) or is infeasible.
  • Indirect cost: time-dependent overhead per unit time; total project cost = direct cost + indirect cost × project duration (assuming linear indirect cost).
  • Economic rule of thumb: crash while the least crash cost per time unit on the critical path is less than the indirect cost saving per time unit; recompute critical paths after each crash.

PERT (probabilistic durations)

  • Assumes each activity duration is a random variable approximated by a Beta distribution on [optimistic, pessimistic], summarized by three estimates:
    • Optimistic time (tₒ): shortest plausible time (everything goes very well).
    • Most likely time (tₘ): mode of the distribution; the most probable duration.
    • Pessimistic time (tₚ): longest plausible time (adverse conditions).
  • Expected activity time (tₑ): weighted mean, tₑ = (tₒ + 4tₘ + tₚ)/6.
  • Activity variance (σ²): approximated by ((tₚ − tₒ)²)/36; standard deviation σ = (tₚ − tₒ)/6.
  • Compute a PERT network using expected times like CPM to identify the likely critical path and its mean project duration μ (sum of tₑ along the critical path).
  • Under the standard independence assumption, the project duration variance along a single dominating critical path equals the sum of variances of activities on that path: σ²_proj = Σσ² (critical path). The project completion time is then approximated as Normal(μ, σ²_proj), giving on-time probability via Z = (T − μ)/σ_proj and standard normal tables.
  • Assumptions and caveats:
    • Activity durations are independent; the critical path identified using expected times dominates the completion-time variance. In reality, path switching and correlation can occur (merge bias), so the normal approximation can be optimistic. GATE/PSU questions typically accept the single-path normal approximation unless stated otherwise.
    • If tₒ = tₘ = tₚ (zero variance), PERT reduces to CPM.

Sign conventions and units

  • Time origin at project start t = 0; durations and event times are nonnegative.
  • Use consistent time units across the network (days are common in practice; SI base unit of time is second; conversions are not usually needed for exam numericals — state your chosen unit).

Why real projects differ from the ideal

  • Durations can be correlated (shared crews, learning, weather), violating independence.
  • Resource constraints (limited machines/labour) can create infeasible schedules even if precedence allows — this needs resource leveling/smoothing (covered under Scheduling and sequencing).
  • Crashing is often discrete or nonlinear, not perfectly linear cost slopes.
  • Networks evolve; re-baselining can change critical paths.

Formulas

Project duration (deterministic) = max over all paths of (sum of activity durations on the path) Meaning: The time from project start to finish equals the length of the longest precedence-respecting path. Unit: time (e.g., day). Applies to CPM.

ESᵢⱼ = Eᵢ; EFᵢⱼ = ESᵢⱼ + dᵢⱼ ESᵢⱼ earliest start of activity i→j; Eᵢ earliest time of tail event i; EFᵢⱼ earliest finish; dᵢⱼ duration (time). Forward pass in CPM/PERT.

Eⱼ = max over all predecessors k of (EFₖⱼ) Earliest time of head event j; unit: time. Forward pass rule.

LFᵢⱼ = Lⱼ; LSᵢⱼ = LFᵢⱼ − dᵢⱼ LFᵢⱼ latest finish of activity i→j; Lⱼ latest time of head event j; LSᵢⱼ latest start. Backward pass in CPM/PERT.

Lᵢ = min over all successors m of (LSᵢₘ) Latest time of tail event i; unit: time. Backward pass rule.

Total float TFᵢⱼ = Lⱼ − Eᵢ − dᵢⱼ = LSᵢⱼ − ESᵢⱼ = LFᵢⱼ − EFᵢⱼ Measures allowable delay without extending project completion; unit: time. CPM/PERT on deterministic or expected times.

Free float FFᵢⱼ = Eⱼ − Eᵢ − dᵢⱼ Allowable delay without delaying earliest start of any successor; unit: time.

Independent float IFᵢⱼ = Eⱼ − Lᵢ − dᵢⱼ (use IF = max(0, IFᵢⱼ)) Delay possible without affecting earliest successor or using predecessor slack; unit: time.

Interfering float = TF − FF = Lⱼ − Eⱼ Portion of total float that, if used, delays successors’ earliest starts. Unit: time.

Event slack Sⱼ = Lⱼ − Eⱼ Slack at event j; equals the interfering float for any activity ending at j. Unit: time.

PERT expected time tₑ = (tₒ + 4tₘ + tₚ) / 6 Activity mean duration; tₒ optimistic, tₘ most likely, tₚ pessimistic (time). Applies to PERT.

PERT variance σ² = ((tₚ − tₒ)²) / 36; standard deviation σ = (tₚ − tₒ) / 6 Uncertainty measures for an activity; units: time² for variance, time for σ. PERT approximation.

Project mean μ = sum of tₑ on the (assumed) critical path; Project variance σ²_proj = sum of σ² on that path Mean and variance of project duration under independence and single-path dominance. Units: time, time².

Z = (T − μ) / σ_proj Standardized normal variate for project completion by time T; unitless. Use standard normal CDF for probability.

Cost slope = (Crash cost − Normal cost) / (Normal time − Crash time) Rate of direct cost increase per unit time saved; units: currency per time. Linear crashing assumption.

Total project cost = (sum of direct activity costs) + (Indirect cost rate × project duration) Total cost model used in crashing trade-offs; indirect cost rate: currency per time; duration: time.

Worked examples

Example 1 — Direct CPM computation (critical path and floats) Given:

  • Activities with durations (days) and predecessors (AON):
    • A: 4, —
    • B: 3, —
    • C: 5, pred A
    • D: 2, pred A
    • E: 4, pred B and C
    • F: 6, pred D
    • G: 3, pred E and F Assume deterministic durations and no resource limits.

Steps:

  1. Forward pass (ES/EF):
    • A: ES = 0 d, EF = 0 + 4 = 4 d.
    • B: ES = 0 d, EF = 0 + 3 = 3 d.
    • C: ES = EF(A) = 4 d, EF = 4 + 5 = 9 d.
    • D: ES = EF(A) = 4 d, EF = 4 + 2 = 6 d.
    • E: ES = max(EF(B), EF(C)) = max(3, 9) = 9 d, EF = 9 + 4 = 13 d.
    • F: ES = EF(D) = 6 d, EF = 6 + 6 = 12 d.
    • G: ES = max(EF(E), EF(F)) = max(13, 12) = 13 d, EF = 13 + 3 = 16 d. Project duration = 16 d.
  2. Backward pass (LS/LF), start from finish at 16 d:
    • G: LF = 16 d, LS = 16 − 3 = 13 d.
    • E: LF = LS(G) = 13 d, LS = 13 − 4 = 9 d.
    • F: LF = LS(G) = 13 d, LS = 13 − 6 = 7 d.
    • C: successor is E with LS(E) = 9 d ⇒ LF(C) = 9 d, LS = 9 − 5 = 4 d.
    • D: successor is F with LS(F) = 7 d ⇒ LF(D) = 7 d, LS = 7 − 2 = 5 d.
    • B: successor is E with LS(E) = 9 d ⇒ LF(B) = 9 d, LS = 9 − 3 = 6 d.
    • A: successors C (LS = 4 d) and D (LS = 5 d) ⇒ LF(A) = min(4, 5) = 4 d, LS = 4 − 4 = 0 d.
  3. Floats TF = LS − ES; FF = min(ES of successors) − EF:
    • A: TF = 0 − 0 = 0 d (critical).
    • B: TF = 6 − 0 = 6 d; FF = ES(E) − EF(B) = 9 − 3 = 6 d.
    • C: TF = 4 − 4 = 0 d (critical).
    • D: TF = 5 − 4 = 1 d; FF = ES(F) − EF(D) = 6 − 6 = 0 d.
    • E: TF = 9 − 9 = 0 d (critical).
    • F: TF = 7 − 6 = 1 d; FF = ES(G) − EF(F) = 13 − 12 = 1 d.
    • G: TF = 13 − 13 = 0 d (critical).
  4. Critical path: A–C–E–G with total duration 4 + 5 + 4 + 3 = 16 d.

Answer: Project duration = 16 days; critical path = A–C–E–G; non-critical floats as computed above.

Example 2 — PERT with probability and slack on expected times Given network (same logic as Example 1), three-time estimates (days):

  • A: tₒ = 2, tₘ = 4, tₚ = 10
  • B: tₒ = 1, tₘ = 2, tₚ = 3
  • C: tₒ = 2, tₘ = 3, tₚ = 4 (pred A)
  • D: tₒ = 3, tₘ = 5, tₚ = 11 (pred A)
  • E: tₒ = 1, tₘ = 2, tₚ = 7 (pred B and C)
  • F: tₒ = 4, tₘ = 6, tₚ = 8 (pred D)
  • G: tₒ = 3, tₘ = 4, tₚ = 5 (pred E and F) Assume independence of activity durations.

Steps:

  1. Compute expected time tₑ and variance σ² for each activity:
    • A: tₑ = (2 + 4·4 + 10)/6 = 28/6 = 4.667 d; σ² = (10 − 2)²/36 = 64/36 = 1.778 d².
    • B: tₑ = (1 + 4·2 + 3)/6 = 12/6 = 2.000 d; σ² = (3 − 1)²/36 = 4/36 = 0.111 d².
    • C: tₑ = (2 + 4·3 + 4)/6 = 18/6 = 3.000 d; σ² = (4 − 2)²/36 = 4/36 = 0.111 d².
    • D: tₑ = (3 + 4·5 + 11)/6 = 34/6 = 5.667 d; σ² = (11 − 3)²/36 = 64/36 = 1.778 d².
    • E: tₑ = (1 + 4·2 + 7)/6 = 16/6 = 2.667 d; σ² = (7 − 1)²/36 = 36/36 = 1.000 d².
    • F: tₑ = (4 + 4·6 + 8)/6 = 36/6 = 6.000 d; σ² = (8 − 4)²/36 = 16/36 = 0.444 d².
    • G: tₑ = (3 + 4·4 + 5)/6 = 24/6 = 4.000 d; σ² = (5 − 3)²/36 = 4/36 = 0.111 d².
  2. Use expected times as CPM durations to find critical path and expected project duration μ (forward pass):
    • A: EF = 4.667 d; B: EF = 2.000 d.
    • C: ES = EF(A) = 4.667 d ⇒ EF = 4.667 + 3.000 = 7.667 d.
    • D: ES = EF(A) = 4.667 d ⇒ EF = 4.667 + 5.667 = 10.334 d.
    • E: ES = max(EF(B), EF(C)) = max(2.000, 7.667) = 7.667 d ⇒ EF = 7.667 + 2.667 = 10.334 d.
    • F: ES = EF(D) = 10.334 d ⇒ EF = 10.334 + 6.000 = 16.334 d.
    • G: ES = max(EF(E), EF(F)) = max(10.334, 16.334) = 16.334 d ⇒ EF = 16.334 + 4.000 = 20.334 d. Critical path: A–D–F–G. Expected project duration μ ≈ 20.334 d.
  3. Project variance σ²_proj = sum of variances on critical path (A, D, F, G): σ²_proj = 1.778 + 1.778 + 0.444 + 0.111 = 4.111 d² ⇒ σ_proj = √4.111 ≈ 2.028 d.
  4. Probability the project finishes within T = 20.0 d: Z = (T − μ)/σ_proj = (20.0 − 20.334)/2.028 = −0.334/2.028 ≈ −0.165. From standard normal tables, Φ(−0.165) ≈ 0.434. So probability ≈ 43.4%.
  5. Deadline for 90% on-time probability (Φ(Z) = 0.90 ⇒ Z ≈ +1.282): T₀.₉ = μ + Z·σ_proj = 20.334 + 1.282·2.028 ≈ 20.334 + 2.600 = 22.934 d. So a ≈22.93-day deadline gives ~90% chance of on-time completion (under assumptions).
  6. Slack example on expected times (optional): By backward pass, LF(E) = LS(G) = 16.334 d; thus LS(E) = 16.334 − 2.667 = 13.667 d. Total float TF(E) = LS − ES = 13.667 − 7.667 ≈ 6.000 d.

Answers: μ ≈ 20.334 d; σ_proj ≈ 2.028 d; P(T ≤ 20 d) ≈ 0.434; T for 90% ≈ 22.93 d.

Common mistakes

  • Forgetting that every activity on any critical path must have zero total float (not just the single longest path when ties exist).
  • Miscomputing floats: using EF instead of ES in FF, or not truncating independent float below at zero.
  • Ignoring new critical paths after crashing; crashing a non-critical activity will not reduce project duration.
  • PERT errors: using arithmetic mean of tₒ, tₘ, tₚ instead of (1,4,1) weighted mean; computing project variance by averaging instead of summing along the critical path; forgetting that Z uses μ and σ of the project, not per-activity values.
  • Probability sign mistakes: computing Z with (μ − T)/σ or reading the wrong tail from the normal table.
  • AOA specifics: omitting necessary dummies when two activities share both start and end events, or creating multiple parallel activities with identical i and j without a dummy.

For GATE ME

  • Draw a valid AOA/AON network from a precedence table; count dummy activities (AOA).
  • Do full CPM: ES/EF, LS/LF, floats (TF, FF, IF), critical path, project duration.
  • PERT: compute tₑ, σ², identify likely critical path on expected times, on-time probability by a given deadline, or required deadline for a target probability.
  • Time–cost trade-off: compute cost slopes, select crashing sequence, handle multiple critical paths, compute optimum project duration given an indirect cost rate.
  • What to practise:
    • Forward/backward passes quickly and accurately; memorize float formulas and when to use max/min.
    • For PERT, be fluent with tₑ and σ², summing variances on the critical path, and Z-to-probability conversions.
    • For crashing, recompute the critical path(s) after each reduction and watch for the emergence of parallel critical paths.

Quick check

  1. Define total float and free float for an activity and state which is always greater or equal.
  2. In PERT, write the formulas for expected time and variance using tₒ, tₘ, tₚ.
  3. A project’s two longest paths are both 24 days. What is the project duration and what is the total float of activities common to both paths?

Answers: 1) TF = LS − ES = LF − EF; FF = Eⱼ − Eᵢ − d; TF ≥ FF. 2) tₑ = (tₒ + 4tₘ + tₚ)/6; σ² = (tₚ − tₒ)²/36. 3) Duration = 24 days; total float of common activities = 0 days.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?