📖 Loading…

0 sections · 0 topics · 0 min reading · 0 sessions

CPM & PERT – Complete Study Notes

GATE ESE / IES SSC JE State PSC

Comprehensive chapter-wise notes covering all 7 topics of CPM & PERT — network construction (AOA and AON), forward and backward pass calculations, float types, critical path identification, time-cost trade-off (crashing), PERT probabilistic scheduling, and Gantt charts with resource scheduling. All formulae, worked step-by-step examples, and exam-focused tables included.

Ch 1 · Project Networks Ch 2 · Forward & Backward Pass Ch 3 · Float & Critical Path Ch 4 · CPM Time–Cost Trade-off Ch 5 · PERT Probabilistic Analysis Ch 6 · Gantt Charts Ch 7 · Resource Scheduling ★ Quick Revision

1Project Networks►

1.1 Network Terminology

Term	Definition
Activity	A task or work package that consumes time and/or resources
Event (node)	A point in time representing the start or end of one or more activities; consumes no time
Predecessor	An activity that must be completed before the current activity can start
Successor	An activity that cannot start until the current activity is finished
Dummy activity	A fictitious activity with zero duration used in AOA networks to show logical dependency without actual work
Network	A directed graph of all activities and their precedence relationships

1.2 AOA vs AON Networks

Feature	AOA (Activity on Arrow)	AON (Activity on Node / Precedence Diagram)
Representation	Activities on arrows; nodes are events	Activities on nodes; arrows show dependencies
Dummy activities	Required to avoid ambiguity	Not needed
Start and end	Single start node, single end node	Single start node, single end node
Lags	Not easily handled	Supports SS, FF, SF, FS with lags
Software use	Older; PERT originated here	Modern PM software (MS Project, Primavera)

1.3 Rules for AOA Network Construction

1. Each activity is represented by exactly one arrow
2. No two activities can share both the same start node and end node → use dummy activity
3. Dummy activities (dashed arrows) have zero duration and zero resource consumption
4. Network must have a single start event and single end event (merge/burst if needed)
5. No loops (circular dependencies) permitted
6. All events are numbered; no two events have the same number

📝 GATE Tip: Most GATE questions use AOA (arrow diagram). Recognise when a dummy activity is required — two activities with the same start and end nodes always need a dummy. Dummy = dashed arrow, zero duration.

2Forward & Backward Pass►

2.1 Event Times

Symbol	Name	Definition
E_i / TE_i / EST	Earliest Event Time	Earliest time an event can occur (finish of all preceding activities)
L_i / TL_i / LST	Latest Event Time	Latest time an event can occur without delaying the project

2.2 Activity Times

Symbol	Name	Formula
EST	Earliest Start Time	EST(i–j) = E_i
EFT	Earliest Finish Time	EFT(i–j) = EST + D = E_i + D
LST	Latest Start Time	LST(i–j) = LFT − D = L_j − D
LFT	Latest Finish Time	LFT(i–j) = L_j

2.3 Forward Pass (Earliest Times)

Start from the first node: E_1 = 0
For each subsequent node j:
E_j = max over all activities (i→j) of: E_i + D(i–j)
(take the MAXIMUM because all predecessors must finish before j can start)

Project duration = E_n (earliest time of final node n)

2.4 Backward Pass (Latest Times)

Start from the last node: L_n = E_n (project deadline)
For each preceding node i:
L_i = min over all activities (i→j) of: L_j − D(i–j)
(take the MINIMUM to find the latest time that still meets all successors' deadlines)

Check: L_1 should = E_1 = 0 (consistency check)

📝 GATE Tip: Forward pass uses MAX; backward pass uses MIN — this distinction causes many errors. Always verify L_1 = 0 as a check. Tabulate all activity EST, EFT, LST, LFT in a table for clarity.

3Float & Critical Path►

3.1 Types of Float

Float Type	Formula	Meaning
Total Float (TF)	TF = L_j − E_i − D(i–j) = LST − EST = LFT − EFT	Maximum delay without delaying project completion
Free Float (FF)	FF = E_j − E_i − D(i–j) = E_j − EFT	Delay without delaying successor's earliest start
Independent Float (IF)	IF = E_j − L_i − D(i–j) ≥ 0 (negative = zero)	Float available regardless of when predecessors finish or successors start
Interfering Float	Interfering Float = TF − FF	Portion of TF that, if used, delays a successor

3.2 Relationships Between Float Types

Always: IF ≤ FF ≤ TF
If TF = 0: activity is on critical path
Free Float can be used without affecting anyone else's schedule
Total Float is shared among activities on a path — using it on one activity reduces others' TF

3.3 Critical Path

Critical path = longest path through the network from start to finish
All activities on critical path have TF = 0 (and FF = 0, IF = 0)
Project duration = length of critical path

Identifying critical path:
Method 1: Mark all activities with TF = 0; trace connected path from start to end
Method 2: List all paths; sum durations; longest = critical path

A network can have MULTIPLE critical paths (all with the same duration = project duration)

📝 GATE Tip: TF = L_j − E_i − D is the most frequently tested calculation. Critical path has TF = 0. Free Float = E_j − E_i − D — used when you want to know if an activity can be delayed without impacting any successor. IF ≤ FF ≤ TF always.

4CPM Time–Cost Trade-off (Crashing)►

4.1 Normal vs Crash

Parameter	Normal	Crash
Duration	Normal time t_n (maximum economical)	Crash time t_c (minimum possible)
Cost	Normal cost C_n (minimum for normal time)	Crash cost C_c (maximum for crash time)
Relationship	t_n > t_c; C_n < C_c	Crashing reduces duration but increases direct cost

4.2 Cost Slope

Cost slope = rate of increase of direct cost per unit reduction in time
Cost slope = (C_c − C_n) / (t_n − t_c)

Units: cost per day (₹/day or $/day)
Lower cost slope = cheaper to crash → crash these activities first

4.3 Crashing Procedure

1. Identify all critical activities (TF = 0)
2. Select critical activity with lowest cost slope
3. Crash it by 1 unit time; update costs and network
4. Recheck critical path — crashing may create new critical paths
5. If multiple critical paths exist, must crash activities on ALL of them simultaneously
6. Stop when: (a) crash limit reached, (b) crashing cost = indirect cost saving, or (c) target duration reached

Total project cost = Direct cost + Indirect cost
Optimal duration = duration at minimum total project cost

4.4 Indirect Costs

Indirect costs (overheads, site establishment, supervision) typically DECREASE as project duration decreases
Indirect cost rate = ₹ per day of project duration

Minimum total cost point: where (marginal crash cost) = (marginal indirect cost saving)
Graphically: intersection of total direct cost curve and total indirect cost savings curve

📝 GATE Tip: Cost slope = (C_c − C_n)/(t_n − t_c) — always crash critical activity with minimum cost slope first. When multiple critical paths develop, the crashing cost equals the sum of cost slopes on all critical paths for that step.

5PERT Probabilistic Analysis►

5.1 PERT vs CPM

Feature	CPM	PERT
Activity durations	Deterministic (single estimate)	Probabilistic (three time estimates)
Application	Construction, manufacturing (well-defined tasks)	R&D, new product development (uncertain tasks)
Focus	Time–cost trade-off	Probability of completing by a deadline
Origin	DuPont Corporation, 1956	US Navy Polaris missile project, 1958

5.2 Three Time Estimates

Estimate	Symbol	Definition
Optimistic time	t_o (or a)	Minimum time if everything goes perfectly; probability ≈ 1%
Most likely time	t_m (or m)	Time that would occur most often if activity repeated many times; mode of distribution
Pessimistic time	t_p (or b)	Maximum time if everything goes wrong; probability ≈ 1%

5.3 Expected Time and Variance

Expected (mean) activity duration:
t_e = (t_o + 4t_m + t_p) / 6

Variance of activity duration:
σ² = [(t_p − t_o) / 6]²
Standard deviation: σ = (t_p − t_o) / 6

Note: the distribution assumed is Beta distribution (bounded, unimodal)

5.4 Project Completion Probability

Expected project duration: T_E = Σ t_e (sum along critical path)
Project variance: σ_p² = Σ σ² (sum of variances along critical path)
Project standard deviation: σ_p = √(σ_p²)

Probability of completing project by target date T_S:
Z = (T_S − T_E) / σ_p
P(T ≤ T_S) = Φ(Z) [standard normal CDF; look up in Z-table]

Z > 0: target is after expected; probability > 50%
Z = 0: target = expected; probability = 50%
Z < 0: target is before expected; probability < 50%

📝 GATE Tip: t_e = (a + 4m + b)/6 and σ² = [(b−a)/6]² are essential formulae — asked almost every year. Z = (T_S − T_E)/σ_p and using the Z-table to find probability is the standard numerical type. Always sum variances (not σ) along the critical path.

6Gantt Charts►

6.1 Description

A Gantt chart (bar chart) is a horizontal bar graph that represents the project schedule. Each activity is shown as a bar spanning its start to finish times. Developed by Henry Gantt (1910–1915).

6.2 Features

Feature	Description
Horizontal axis	Time scale (days, weeks, months)
Vertical axis	List of activities / work packages
Bars	Span from EST to EFT (or LST to LFT); length = duration
Float	Often shown as thin lines or hatching extending beyond the solid bar to LFT
Milestone	Diamond symbol ◆ marking a key event with zero duration
Progress tracking	Bars partially filled to show % complete

6.3 Advantages and Limitations

Advantages:
Simple and easy to read; good for communication with clients and field staff
Shows schedule at a glance; allows progress tracking

Limitations:
Does not clearly show interdependencies between activities
Does not identify critical path explicitly
Becomes unwieldy for large complex projects (> ~50 activities)
Cannot easily model changes in logic

Best used alongside CPM/PERT network, not as a replacement

📝 GATE Tip: Gantt chart limitations vs CPM advantages is a common theoretical question. Key point: Gantt charts do NOT show logical dependencies between activities, while CPM/PERT networks do.

7Resource Scheduling►

7.1 Resource Levelling vs Resource Allocation

Technique	Objective	Constraint
Resource levelling	Minimise fluctuations in resource usage; smooth the demand profile	Project duration fixed; resources unlimited but peak usage minimised
Resource allocation (limited)	Complete project with available resources; may extend duration	Resource limit fixed; project duration may extend

7.2 Resource Levelling Procedure

1. Prepare time-scaled network with earliest start schedule
2. Plot resource histogram (resource units vs time)
3. Identify peaks: shift non-critical activities within their float to smooth the profile
4. Key rule: only shift non-critical activities (shift critical activities = extends project)
5. Use float available: shifting an activity by ≤ TF will not delay the project

Resource usage rate (RUR) formula:
Σ(r_i² × d_i) should be minimised (r_i = resource units in period i; d_i = duration of period i)
Equivalently: minimise variance of resource usage

7.3 Heuristic Rules for Scheduling

When resources are limited and activities compete:
Priority rules (examples):
1. Minimum Total Float first (most critical first)
2. Minimum duration first (shortest job first)
3. Minimum Latest Finish Time first

No single optimal algorithm for resource-constrained scheduling (NP-hard problem in general);
heuristic rules give practical near-optimal solutions.

📝 GATE Tip: Resource levelling vs resource allocation distinction is commonly asked as a definition question. The key principle for levelling: shift non-critical activities within available float — never shift critical activities or the project is delayed.

★Quick Revision — Key Formulae►

Topic	Key Formula / Rule
Forward pass	E_j = max(E_i + D) over all predecessors i
Backward pass	L_i = min(L_j − D) over all successors j
Total Float	TF = L_j − E_i − D = LST − EST
Free Float	FF = E_j − E_i − D
Independent Float	IF = E_j − L_i − D (≥ 0)
Relationship	IF ≤ FF ≤ TF
Critical path	TF = 0 for all activities on critical path
Cost slope (crashing)	(C_c − C_n) / (t_n − t_c)
PERT expected time	t_e = (t_o + 4t_m + t_p) / 6
PERT variance	σ² = [(t_p − t_o) / 6]²
Z-score for probability	Z = (T_S − T_E) / σ_p; P = Φ(Z)
Crash priority	Crash critical activity with minimum cost slope first

Login Required

CPM & PERT – Complete Study Notes

1.1 Network Terminology

1.2 AOA vs AON Networks

1.3 Rules for AOA Network Construction

2.1 Event Times

2.2 Activity Times

2.3 Forward Pass (Earliest Times)

2.4 Backward Pass (Latest Times)

3.1 Types of Float

3.2 Relationships Between Float Types

3.3 Critical Path

4.1 Normal vs Crash

4.2 Cost Slope

4.3 Crashing Procedure

4.4 Indirect Costs

5.1 PERT vs CPM

5.2 Three Time Estimates

5.3 Expected Time and Variance

5.4 Project Completion Probability

6.1 Description

6.2 Features

6.3 Advantages and Limitations

7.1 Resource Levelling vs Resource Allocation

7.2 Resource Levelling Procedure

7.3 Heuristic Rules for Scheduling