How unit 3 is examined
This unit covers PERT and CPM networks, floats, PERT probability, updating, crashing, the LP form of CPM and resource levelling; no topic has been asked in the supplied papers, so learn the definitions and formulas below.
Project Scheduling: PERT and CPM with known activity times
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. PERT (Programme Evaluation and Review Technique) and CPM (Critical Path Method) are network techniques that plan, schedule and control a project made of activities with precedence relations.
Key points.
- An activity is a time-consuming task drawn as an arrow, and an event is a start or finish point drawn as a numbered node.
- Earliest event time is found by a forward pass, $E_j=\max(E_i+t_{ij})$, and latest event time by a backward pass, $L_i=\min(L_j-t_{ij})$.
- CPM uses one known (deterministic) time per activity, whereas PERT uses three time estimates and is probabilistic.
- A dummy activity of zero duration shows a dependence without using time or resources.
- The network rule is that an activity can start only when every activity entering its tail event is complete, and the network has one start event and one end event.
- The steps are: list activities and predecessors, draw the arrow diagram, number events so that $i<j$ on every arrow, then do the forward pass, the backward pass and mark the critical path.
- PERT is used for research and new projects with uncertain times and is event-oriented; CPM is used for repeat projects such as construction, is activity-oriented and can trade time against cost.
Example. One network is used for the whole unit. Activities (event $i$ to $j$, time in days): A(1-2)=4, B(1-3)=3, C(2-4)=3, D(3-4)=6, E(4-5)=2, F(3-5)=4.
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 510 338" width="510" height="338" role="img" aria-label="Network of the running example; bold path B-D-E is critical"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M53.4,155.6 L154.2,54.8" marker-end="url(#ah2)"/><path class="e" d="M184.2,51.4 L324.2,156.4" marker-end="url(#ah2)"/><path class="e hi" d="M53.4,182.4 L154.2,283.2" marker-end="url(#ahh2)"/><path class="e hi" d="M184.2,286.6 L324.2,181.6" marker-end="url(#ahh2)"/><path class="e hi" d="M360,169 L449,169" marker-end="url(#ahh2)"/><path class="e" d="M186.5,290.5 L450.7,177.3" marker-end="url(#ah2)"/><g class="wl"><rect x="91.3" y="95.5" width="26.4" height="18" rx="9"/><text class="t" x="104.5" y="104.5" dy=".35em" text-anchor="middle">A4</text></g><g class="wl"><rect x="241.8" y="95.5" width="26.4" height="18" rx="9"/><text class="t" x="255" y="104.5" dy=".35em" text-anchor="middle">C3</text></g><g class="wl hi"><rect x="91.3" y="224.5" width="26.4" height="18" rx="9"/><text class="t" x="104.5" y="233.5" dy=".35em" text-anchor="middle">B3</text></g><g class="wl hi"><rect x="241.8" y="224.5" width="26.4" height="18" rx="9"/><text class="t" x="255" y="233.5" dy=".35em" text-anchor="middle">D6</text></g><g class="wl hi"><rect x="392.3" y="160" width="26.4" height="18" rx="9"/><text class="t" x="405.5" y="169" dy=".35em" text-anchor="middle">E2</text></g><g class="wl"><rect x="306.3" y="224.5" width="26.4" height="18" rx="9"/><text class="t" x="319.5" y="233.5" dy=".35em" text-anchor="middle">F4</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">n1</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">n2</text><circle class="n" cx="169" cy="298" r="18"/><text class="t" x="169" y="298" dy=".35em" text-anchor="middle">n3</text><circle class="n" cx="341" cy="169" r="18"/><text class="t" x="341" y="169" dy=".35em" text-anchor="middle">n4</text><circle class="n" cx="470" cy="169" r="18"/><text class="t" x="470" y="169" dy=".35em" text-anchor="middle">n5</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Network of the running example; bold path B-D-E is critical</figcaption></figure>
| Event | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Earliest $E$ | 0 | 4 | 3 | 9 | 11 |
| Latest $L$ | 0 | 6 | 3 | 9 | 11 |
Paths: A-C-E $=9$, B-D-E $=11$, B-F $=7$. Project duration = 11 days, critical path 1-3-4-5 (B-D-E).
Answer frame. Open with the definition of PERT and CPM; draw the arrow network with numbered events; do the forward and backward pass in a table; close with the critical path and duration.
Critical Path Analysis, Various types of floats
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. The critical path is the longest path from start to end of the network; its activities have zero total float and it fixes the project duration.
Key points.
- An activity is critical when $E_i=L_i$, $E_j=L_j$ and $L_j-E_i=t_{ij}$.
- Total float $=L_j-E_i-t_{ij}$ is the delay an activity can take without delaying the project.
- Free float $=E_j-E_i-t_{ij}$ is the delay possible without affecting the earliest start of the next activity.
- Independent float $=E_j-L_i-t_{ij}$ is the delay possible when the predecessor finishes as late as possible and the successor starts as early as possible.
- Independent float can be negative, and a negative value is taken as zero; the order is total float $\ge$ free float $\ge$ independent float.
- Slack is the term used for events in PERT, $L_i-E_i$, while float is used for activities in CPM.
- More than one critical path can exist, and a delay in any critical activity delays the whole project day for day.
Example. From the running network:
| Activity | $t$ | Total float | Free float | Independent float |
|---|---|---|---|---|
| A (1-2) | 4 | 2 | 0 | 0 |
| C (2-4) | 3 | 2 | 2 | 0 |
| F (3-5) | 4 | 4 | 4 | 4 |
| B, D, E | 3, 6, 2 | 0 | 0 | 0 |
For C: total float $=L_4-E_2-3=9-4-3=2$; free float $=E_4-E_2-3=2$; independent float $=E_4-L_2-3=9-6-3=0$. Critical activities are B, D, E.
Answer frame. Open by defining critical path and float; write the three float formulas; show the table for the given network; close by naming the critical path.
Probability considerations in PERT
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. PERT takes three estimates per activity: optimistic $a$, most likely $m$ and pessimistic $b$, and treats the time as following a beta distribution.
Formula. $$t_e=\frac{a+4m+b}{6},\qquad \sigma^2=\left(\frac{b-a}{6}\right)^2$$
Key points.
- Project mean is the sum of $t_e$ on the critical path, and project variance is the sum of the variances of the critical activities.
- The probability of finishing by date $T_s$ is $P(Z\le Z_0)$ with $Z_0=\dfrac{T_s-T_e}{\sigma_{project}}$, read from normal tables.
- The most likely time $m$ is the mode, so it is given four times the weight of $a$ and $b$ in the mean.
- Activities are assumed independent, and by the central limit theorem the project time is approximately normal.
Example. Critical activities of the running network with $(a,m,b)$: B $(1,3,5)$: $t_e=3$, $\sigma^2=0.444$; D $(2,6,10)$: $t_e=6$, $\sigma^2=1.778$; E $(1,2,3)$: $t_e=2$, $\sigma^2=0.111$.
$T_e=3+6+2=11$, $\sigma^2=2.333$, $\sigma=1.528$. For $T_s=13$: $Z=(13-11)/1.528=1.31$, so $P\approx\Phi(1.31)=0.905$. Probability of finishing in 13 days is about 90.5 percent.
Answer frame. Open with the three time estimates; write $t_e$ and $\sigma^2$; tabulate the critical activities and sum them; find $Z$ and read the table; close with the probability.
Updating of PERT charts
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Updating means revising the network during the project, using actual progress and new estimates, to recompute the schedule and critical path.
Key points.
- Completed activities are removed or given zero time, and remaining durations are re-estimated from the current date.
- Event times are recomputed by fresh forward and backward passes, so the critical path may shift to a new path.
- Updating shows delays early, so management can shift resources to activities that have become critical.
- Updating is done at regular reporting dates, and the new completion date is compared with the target to decide whether crashing is needed.
Example. At day 3, B is complete and D is under way; if E is re-estimated at 4 days instead of 2, the remaining path is recomputed: $3+6+4=13$ days, so the new duration is 13 days and the critical path stays B-D-E.
Project crashing
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Crashing shortens the project duration by spending extra money to reduce the times of selected critical activities.
Formula. $$\text{Cost slope}=\frac{C_c-C_n}{T_n-T_c}$$ where $C_c$, $C_n$ are crash and normal costs and $T_n$, $T_c$ are normal and crash times.
Key points.
- Only critical activities are crashed, and the one with the lowest cost slope is crashed first.
- Crash one unit of time at a time, updating the critical path after each step, since a new path may become critical.
- Total cost is direct cost plus indirect cost; the best duration is where their sum is lowest.
- Direct cost rises as time is crashed, while indirect (overhead) cost falls, so total cost is a U-shaped curve.
- An activity cannot be crashed below its crash time, and when two parallel critical paths exist both must be shortened together, or a common activity crashed.
Example. Crash data: B: normal 3 days, Rs 300, crash 2 days, Rs 400, slope 100; D: 6 days, Rs 600, crash 4 days, Rs 800, slope 100; E: 2 days, Rs 200, crash 1 day, Rs 350, slope 150.
| Step | Crash | Extra cost | Duration | Critical paths |
|---|---|---|---|---|
| 0 | none | 0 | 11 | B-D-E |
| 1 | B by 1 | 100 | 10 | B-D-E |
| 2 | D by 1 | 100 | 9 | B-D-E and A-C-E |
| 3 | E by 1 | 150 | 8 | both |
Duration 8 days at an extra direct cost of Rs 350.
Answer frame. Open with the definition and the cost slope; draw the network; tabulate crashing steps cheapest slope first; close with total cost against duration.
Formulation of CPM as a linear programming problem
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. The critical path can be found as an LP by taking event times $x_j$ as variables and minimising the project length.
Formulation. $$\text{Minimise } Z=x_n-x_1$$ subject to $x_j-x_i\ge t_{ij}$ for every activity $(i,j)$, with $x_1=0$ and $x_j\ge 0$.
Key points.
- Each constraint says an event cannot occur until its predecessor event plus the activity time has passed.
- Constraints that hold as equalities at the optimum are the critical activities.
- For crashing, the reduction $y_{ij}$ is added with $x_j-x_i+y_{ij}\ge t_{ij}$, $y_{ij}\le t_{ij}-c_{ij}$, and cost $\sum k_{ij}y_{ij}$ is minimised.
- The dual of this LP is a maximum-flow style problem in which the longest path is the flow to be found.
Example. Running network: minimise $Z=x_5-x_1$ subject to $x_2-x_1\ge4$, $x_3-x_1\ge3$, $x_4-x_2\ge3$, $x_4-x_3\ge6$, $x_5-x_4\ge2$, $x_5-x_3\ge4$, $x_1=0$. The optimum is $Z=11$ with $x_3=3$, $x_4=9$, $x_5=11$.
Answer frame. Open with the variables (event times); write the objective; write one constraint per activity; close by naming the tight constraints as the critical path.
Resource levelling and resource scheduling
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Resource levelling smooths resource use over time within the project duration, whereas resource scheduling (allocation) fits activities to limited resources, possibly extending the duration.
Key points.
- Levelling uses the float of non-critical activities, so the project end date does not change.
- Scheduling under a resource limit gives priority to critical and least-float activities and delays the others.
- A resource histogram plots the demand per period and shows the peaks that levelling removes.
- Levelling moves an activity within its float, so it can be done only for non-critical activities.
- Resource-limited scheduling uses a priority rule such as minimum slack first: at each time step schedule the activity with the least slack that the available resource can support.
Example. In the running network, F (3 workers) and D (4 workers) both start at day 3, so demand is 7 for days 3-9. F has 4 days of float, so starting it at day 7 (finish at day 11) cuts the period of peak demand 7 from six days to two days, and the 11-day duration is unchanged.
Last-minute revision
- PERT is probabilistic with three estimates; CPM is deterministic with one time.
- Forward pass takes the maximum, backward pass takes the minimum.
- Total float $=L_j-E_i-t_{ij}$; free float $=E_j-E_i-t_{ij}$; independent float $=E_j-L_i-t_{ij}$.
- Critical activities have zero total float and form the longest path.
- $t_e=(a+4m+b)/6$ and $\sigma^2=((b-a)/6)^2$.
- $Z=(T_s-T_e)/\sigma$ gives the probability of meeting a date.
- Cost slope $=(C_c-C_n)/(T_n-T_c)$; crash the cheapest critical activity first.
- LP form: minimise $x_n-x_1$ with $x_j-x_i\ge t_{ij}$.
- Levelling keeps the project duration; limited-resource scheduling may extend it.
Memory hooks
- Forward Max, Backward Min: "FM and BM".
- Beta weights 1-4-1: optimistic once, most likely four times, pessimistic once.
- Crash the cheapest slope on the critical path, one day at a time.
- Total float is the biggest, free float is smaller, independent float is smallest.
Coverage checklist
- Project Scheduling: PERT and CPM with known activity times: covered, no past questions.
- Critical Path Analysis, Various types of floats: covered, no past questions.
- Probability considerations in PERT: covered, no past questions.
- Updating of PERT charts: covered, no past questions.
- Project crashing: covered, no past questions.
- Formulation of CPM as a linear programming problem: covered, no past questions.
- Resource levelling and resource scheduling: covered, no past questions.