Network Analysis: CPM & PERT

Project network analysis (CPM/PERT) is a high-yield GATE ME topic (~2 marks). The critical-path/float logic and the PERT expected-time/variance formulas are heavily tested.

CPM (deterministic)

Represent a project as a network of activities. The critical path is the longest path through the network — it sets the minimum project duration and has zero float.

• Forward pass: earliest start ES and earliest finish EF (EF = ES + duration).
• Backward pass: latest finish LF and latest start LS.
• Total float = LS − ES = LF − EF (slack an activity can absorb without delaying the project). Critical activities have total float = 0. Free float ≤ total float (delay without affecting the next activity's ES).
• Crashing: shorten critical activities (at extra cost) to reduce duration — crash the lowest cost-slope activity first.

PERT (probabilistic)

Uses three time estimates per activity: optimistic (to), most likely (tm), pessimistic (tp).

• Expected time te = (to + 4·tm + tp)/6.
• Variance σ² = ((tp − to)/6)².
  Project duration follows a normal distribution; project variance = sum of variances of critical-path activities. Probability of finishing by a date via z = (T − Σte)/σ_project.

Exam Tricks & Tips

• 🎯 Critical path = longest path = zero float; it fixes project duration — the single most-tested idea.
• 🎯 PERT te = (to + 4tm + tp)/6, variance = ((tp − to)/6)² — direct plug-in formulas.
• 🎯 Total float = LS − ES = LF − EF; critical activities have zero total float.
• 🎯 Project variance = sum of variances along the CRITICAL path only — not all activities.
• 🎯 Crash the activity with the lowest cost-slope first to reduce duration most cheaply.
• ❌ Common mistake: treating float per activity as additive along a path — total float belongs to the path, and using up one activity's float reduces the float available to others on the same path.

Expected exam pattern

A 1-mark PERT te/variance or float NAT, and a 2-mark critical-path, project-completion-probability, or crashing problem. The longest-path/zero-float rule and PERT formulas are among the most repeated GATE points.

Quick recap

CPM: critical path = longest path, zero float, sets duration. Forward pass ES/EF, backward LS/LF; total float = LS−ES = LF−EF. PERT: te = (to+4tm+tp)/6, σ² = ((tp−to)/6)²; project variance = Σ(critical-path variances); z for completion probability. Crash lowest cost-slope first.

Cover the answer, recall, then check. 11 cards on CPM/PERT for GATE ME.

Q1. What is the critical path?
A1. The longest path through the project network; it determines the minimum project duration and has zero float.

Q2. How do you find earliest times?
A2. Forward pass: ES of an activity = max EF of predecessors; EF = ES + duration.

Q3. How do you find latest times?
A3. Backward pass: LF = min LS of successors; LS = LF − duration.

Q4. Define total float.
A4. Total float = LS − ES = LF − EF — the delay an activity can absorb without extending the project. Critical activities have zero.

Q5. Difference between total float and free float?
A5. Free float is delay possible without affecting the next activity's earliest start; it is ≤ total float.

Q6. PERT expected activity time?
A6. te = (to + 4·tm + tp)/6, from optimistic, most-likely, and pessimistic estimates.

Q7. PERT activity variance?
A7. σ² = ((tp − to)/6)².

Q8. How is project variance computed?
A8. As the sum of the variances of the activities on the critical path only.

Q9. How do you find the probability of finishing by a date T?
A9. z = (T − Σte)/σ_project, then read the standard-normal probability.

Q10. What is crashing?
A10. Deliberately shortening critical activities at extra cost to reduce project duration; crash the lowest cost-slope activity first.

Q11. Key difference between CPM and PERT?
A11. CPM uses single deterministic durations (cost-oriented); PERT uses three probabilistic estimates (time/uncertainty-oriented).

Project scheduling — building a plant, launching a product — is managed with network techniques CPM and PERT. GATE tests critical-path identification, float calculation, and PERT's probabilistic time estimates. It is systematic arithmetic on an activity network.

Core concept: a project is a network of activities with precedence; the longest path (critical path) sets the minimum project duration, and activities off that path have slack.

Deep explanation

Beginner — network and critical path

Draw activities as arrows (activity-on-arrow) or nodes with precedence. Compute:

• Forward pass: earliest start (ES) and earliest finish (EF = ES + duration) for each activity.
• Backward pass: latest finish (LF) and latest start (LS = LF − duration).
• The critical path is the longest-duration path (project duration); its activities have zero float.

Intermediate — float (slack)

• Total float = LS − ES = LF − EF: how much an activity can slip without delaying the project.
• Free float = slack without delaying the following activity's earliest start.
  Critical activities have zero total float — delaying any of them delays the whole project. Identifying them focuses management attention.

Advanced — PERT (probabilistic) and crashing

PERT handles uncertain durations with three estimates: optimistic (a), most likely (m), pessimistic (b):

• Expected time t_e = (a + 4m + b)/6,
• Variance σ² = ((b − a)/6)².
  Project duration variance = sum of variances of critical activities; use the normal distribution to find the probability of finishing by a target date (z = (target − expected)/σ_project).
  Crashing (CPM cost model): shorten the project by spending more on critical activities; the cost slope = (crash cost − normal cost)/(normal time − crash time) picks the cheapest activity to crash first.

Worked example

An activity has optimistic 4, most likely 6, pessimistic 14 days. Find its PERT expected time and variance.
t_e = (a + 4m + b)/6 = (4 + 4×6 + 14)/6 = (4 + 24 + 14)/6 = 42/6 = 7 days.
Variance σ² = ((b − a)/6)² = ((14 − 4)/6)² = (10/6)² = (1.667)² = 2.78 days². (Standard deviation ≈ 1.67 days; large spread signals schedule risk.)

GATE relevance

Critical-path and float calculation, PERT expected-time and variance formulas, probability of completion, and crashing/cost-slope are recurring Industrial Engineering questions. The t_e = (a+4m+b)/6 and variance = ((b−a)/6)² formulas are must-memorise.

Exam tricks & shortcuts

• Critical path = longest path = zero float; find it by forward/backward pass.
• PERT: t_e = (a + 4m + b)/6, variance = ((b − a)/6)² — memorise both.
• Project variance = sum of critical-path variances only.
• Crash the activity with the lowest cost slope first.
• Mnemonic: "a plus four-m plus b, all over six."

Key formulas

• CPM: critical path = longest duration path; slack = LS − ES = LF − EF = 0 on it.
• Forward pass: EF = ES + t; backward pass: LS = LF − t.
• PERT expected time: t_e = (t_o + 4t_m + t_p)/6; variance σ² = ((t_p − t_o)/6)².
• Project variance = Σ(variances on critical path); Z = (T_target − T_expected)/σ.

CPM finds the longest (critical) path; PERT adds probabilistic time estimates using a beta distribution.

Worked Example

Problem: A project has five activities: A (3 days) and B (4 days) can start immediately; C (2 days) follows A; D (5 days) follows B; E (3 days) follows both C and D. (a) Find the critical path and project duration. (b) For activity D, if its optimistic, most-likely, and pessimistic times are 2, 5, 8 days, find its PERT expected time and variance.

Solution:
(a) Enumerate the paths from start to finish and sum durations:
Path A→C→E: 3 + 2 + 3 = 8 days.
Path B→D→E: 4 + 5 + 3 = 12 days.
The longest path is the critical path: B → D → E, with project duration = 12 days.

(b) PERT expected time (beta-distribution weighting):
t_e = (t_o + 4t_m + t_p)/6 = (2 + 4×5 + 8)/6 = 30/6 = 5 days.
Variance:
σ² = ((t_p − t_o)/6)² = ((8 − 2)/6)² = (1)² = 1 day².

Answer: (a) Critical path B–D–E, duration 12 days; (b) t_e = 5 days, variance = 1 day².