Network scheduling is a set of techniques to plan, schedule and control complex projects consisting of many interdependent activities. It produces a network diagram showing the activities, their precedence relationships and their durations.
Two best-known techniques: CPM (Critical Path Method, deterministic) and PERT (Programme Evaluation and Review Technique, probabilistic).
A specific task that consumes time and resources. Represented as an arrow (arc) in the network. Activities are labelled by capital letters (A, B, C) or by the pair of nodes they connect (1, 2).
A point in time marking the start or completion of one or more activities. Represented as a circle (node).
An artificial activity with zero duration. Used to:
Drawn as a dotted arrow.
In the Activity-on-Arrow (AOA) convention used in this course:
The alternative Activity-on-Node (AON) convention uses nodes for activities — more common in modern software (MS Project, Primavera).
Case 1: Two parallel activities with the same start and end nodes.
Activities A and B both go from node 1 to node 2 — illegal. Add a dummy node and redirect one of them.
Case 2: Activity C depends on both A and B, but activity D depends only on A.
Cannot draw without a dummy. Solution: end A at node X, end B at node Y; dummy from X to Y so C starts at Y; D starts at X.
Once the network is drawn and activity durations are assigned, four key time values are computed for each event:
| Symbol | Meaning |
|---|---|
| \(E_i\) | Earliest occurrence time of event \(i\) (forward pass) |
| \(L_i\) | Latest allowable time of event \(i\) (backward pass) |
| \(\text{EST}_{ij}\) | Earliest start time of activity (i, j) |
| \(\text{EFT}_{ij}\) | Earliest finish time |
| \(\text{LST}_{ij}\) | Latest start time |
| \(\text{LFT}_{ij}\) | Latest finish time |
Start with \(E_1 = 0\). For each subsequent event \(j\):
where the maximum is taken over all activities (i, j) ending at j, and \(t_{ij}\) is the activity duration.
Activity times:
Start with \(L_n = E_n\) (project duration). For each preceding event \(i\):
Float (or slack) is the spare time available for an activity without delaying the project. There are several types.
Maximum time by which the activity can be delayed without delaying the project completion.
Float assuming all preceding activities are completed at their earliest. Equals total float minus the slack carried forward.
Float assuming all preceding activities take their longest time and following ones start at earliest.
Always: IF ≤ FF ≤ TF.
The critical path is the longest path in the project network — the path that determines the minimum project duration. Activities on the critical path have zero total float — any delay in them delays the entire project.
The length of the critical path = project completion time.
Activities and durations (days):
| Activity | Predecessors | Duration |
|---|---|---|
| A | — | 3 |
| B | — | 5 |
| C | A | 7 |
| D | B | 3 |
| E | B | 5 |
| F | C, D | 4 |
| G | E | 2 |
Forward pass: E₁ = 0; after A: E_A = 3; after B: E_B = 5; after C (3 + 7 = 10), so E_after-C = 10; after D = 5 + 3 = 8; E_after-D = 8. F starts when both C and D done ⇒ E_before-F = max(10, 8) = 10. After F: 14. After E: 5 + 5 = 10. After G: 10 + 2 = 12. End event: max(14, 12) = 14.
So project duration = 14 days.
Backward pass: L_end = 14. L_before-F = 14 − 4 = 10. L_before-G = 14 − 2 = 12. L_before-C = 10 − 7 = 3. L_before-D = 10 − 3 = 7. L_before-E = 12 − 5 = 7. L_after-A = 3. L_after-B = min(7, 7) = 7. L_start = min(3 − 3, 7 − 5) = 0.
Critical events: those with E = L. The path A → C → F has duration 3 + 7 + 4 = 14 = project duration. All on critical path.
Critical path: A → C → F; activities B, D, E, G have positive total float.
For activity B (Pred —, dur 5) above: E_start = 0, E_end = 5, L_end = 7, so TF = 7 − 5 = 2. B can be delayed up to 2 days without affecting the project.
For activity E (Pred B, dur 5): E_start = 5, E_end = 10, L_end = 12 ⇒ TF = 12 − 10 = 2.
PERT extends CPM to probabilistic activity durations. For each activity, three time estimates are made and combined to produce an expected duration and a measure of variability.
PERT assumes the activity duration follows a Beta distribution on \([a, b]\) with mode \(m\). The first two moments are approximated as:
Activities with three-time estimates:
| Activity | Preds | a | m | b | t_e | σ² |
|---|---|---|---|---|---|---|
| A | — | 2 | 3 | 4 | 3 | 0.111 |
| B | — | 4 | 5 | 12 | 6 | 1.778 |
| C | A | 5 | 6 | 13 | 7 | 1.778 |
| D | B | 2 | 3 | 4 | 3 | 0.111 |
| E | C, D | 3 | 4 | 5 | 4 | 0.111 |
Network paths: A→C→E = 3 + 7 + 4 = 14; B→D→E = 6 + 3 + 4 = 13. Critical path = A→C→E with \(T_e = 14\).
\(\sigma^2_{\text{project}} = 0.111 + 1.778 + 0.111 = 2.0;\;\; \sigma = 1.414\).
P(project completes by 15 days) = \(\Phi((15 - 14)/1.414) = \Phi(0.707) = 0.76\).
P(project completes by 16 days) = \(\Phi((16 - 14)/1.414) = \Phi(1.414) = 0.92\).
Using same data: time \(T\) for which P(completion ≤ T) = 0.95?
From standard normal, \(z_{0.95} = 1.645\). \(T = T_e + z\,\sigma = 14 + 1.645 \cdot 1.414 = 16.33\) days.
To be 95% sure the project completes on time, schedule its deadline at 16.33 days (round up to 17).
| Aspect | CPM | PERT |
|---|---|---|
| Origin | DuPont, 1957 | US Navy, 1958 |
| Activity time | Deterministic (single value) | Probabilistic (three values) |
| Project type | Repetitive (construction, maintenance) | Non-repetitive (R&D) |
| Focus | Cost-time trade-off (crashing) | Time uncertainty |
| Output | Critical path, exact duration | Critical path, expected duration with probability |
| Cost considerations | Built in | Not built in (PERT-Cost extension exists) |
Crashing an activity means reducing its duration by deploying extra resources (workers, machines, overtime). It increases the activity cost but may shorten the project duration if the activity is on the critical path.
This is the marginal cost of reducing the activity duration by one unit.
A small project has activities A, B, C, D, E with durations 4, 7, 6, 5, 3.
Precedence: B and C follow A; D follows B; E follows C; project ends after D and E.
Paths:
Critical path: A → B → D, duration 16 days.
Floats: Activity C has TF = 16 − 4 − 6 − 3 = 3; activity E similarly = 3.