Network Analysis — CPM

Critical Path Method (CPM)

CPM was developed in the late 1950s (by DuPont with Remington Rand) for planning and scheduling projects with deterministic (known) activity durations. It is activity-oriented and widely used in construction, where durations can be estimated from experience; it also forms the basis of time–cost trade-off (crashing).

Network terminology

Types of network diagrams

Activity on arrow (AOA)

• Activities on arrows, events as nodes (circles); activity identified by $(i,j)$ — tail and head events.
• Needs dummies for correct logic.

Activity on node (AON) / precedence diagram

• Activities in nodes (boxes); arrows show dependencies only.
• No dummies needed; easier to draw and modify; used by most software.
• Allows relationships FS, SS, FF, SF with lags/leads.

Rules for drawing AOA networks

1. Each activity is represented by one arrow only.
2. No two activities may have the same tail and head events — use a dummy.
3. There should be one initial and one final event (in a basic network).
4. Arrows flow from left to right; no looping (circular logic).
5. No dangling — every activity except the last must have a successor, and every event except the first must have a predecessor.
6. Avoid redundant dependencies.
7. The length of the arrow has no significance (not to scale).

Fulkerson's rule for numbering events

1. Number the initial event 1.
2. Delete all arrows emerging from numbered events; this creates new initial events — number them 2, 3, …
3. Repeat until the final event is numbered.

Result: for every activity $(i,j)$, $i<j$ (head number greater than tail number).

Common errors

• Looping (cycling) — endless loop of activities.
• Dangling — an activity disconnected from the end event.
• Redundancy — unnecessary dummy or link where dependency is already implied.

Time computations

Floats

• Relationship: $IF\le FF\le TF$.
• Critical activities have zero total float (when the project's scheduled completion equals its earliest completion). Negative float indicates the schedule cannot meet a target date.
• The critical path joins critical activities from start to end; there may be more than one critical path.

Worked example 1 — AOA network

Worked example 2 — using a dummy

Precedence diagram relationships (AON)

AON node boxes typically show ES, EF, LS, LF, duration and total float.

Advantages of CPM

• Shows interdependencies; identifies critical activities needing close control.
• Computes floats — flexibility for resource allocation.
• Basis for crashing, resource levelling, cost control and updating.
• Effect of delays on the project can be analysed.

Frequently tested points

• CPM: deterministic durations, activity-oriented, used for time–cost trade-off; PERT: probabilistic, event-oriented.
• Dummy: zero time, zero resources, dashed arrow — logic or unique identification.
• Fulkerson's rule numbers events so that $i<j$ for every activity.
• Errors: looping, dangling, redundancy.
• $E_j=\max (E_i+t)$; $L_i=\min (L_j-t)$.
• TF = L_j − E_i − t; FF = E_j − E_i − t; IF = E_j − L_i − t; interfering float = TF − FF = head slack.
• IF ≤ FF ≤ TF; critical activities TF = 0; critical path = longest path; may be several.
• AON needs no dummies; FS, SS, FF, SF relationships with lags.