Coaching Centre
Forward and backward scanning
Earliest starting times (EST) by forward scanning, the minimum completion time, and latest starting times (LST) by backward scanning, with the largest-in, smallest-out rules.
Once a project is drawn as a network, two quick sweeps across it tell you almost everything: how soon each job can start, how long the whole project must take, and how late each job could start without holding anything up. The sweeps are called forward and backward scanning.
Forward scanning: earliest starting times
The earliest starting time (EST) at a node is the soonest that the activities leaving it can begin. Start at node 1 with EST $= 0$ and work forwards.
- For each arrow coming into a node: EST at its tail $+$ its duration.
- If more than one arrow comes in, take the largest. The next activities can't start until every incoming activity is finished, and the slowest one decides that.
The EST at the finish node is the minimum completion time: the shortest time the whole project can take.
A garden shed is built in these steps (times in days). Arcs: A Clear the site ($1$) from node 1 to 2, B Buy materials ($4$) from 1 to 3, C Pour the slab ($2$) from 2 to 3, D Build the frame ($3$) from 3 to 4, E Fit the roof ($2$) from 4 to 5, F Paint ($2$) from 4 to 6, G Gutters ($1$) from 5 to 6. Find the EST at each node and the minimum completion time.
Backward scanning: latest starting times
The latest starting time (LST) at a node is the latest that the activities leaving it can begin without making the project finish late. Start at the finish node, where LST $=$ EST $=$ the minimum completion time, and work backwards.
- For each arrow going out of a node: LST at its head $-$ its duration.
- If more than one arrow goes out, take the smallest. Leave it any later than that and at least one of those paths will run late.
Find the LST at each node of the shed network.
| Node | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|
| EST | $0$ | $1$ | $4$ | $7$ | $9$ | $10$ |
| LST | $0$ | $2$ | $4$ | $7$ | $9$ | $10$ |
Node 2 is the only node where the two times differ. That gap is spare time, which is the subject of 9C.
This kitchen renovation has a dummy from node 3 to node 4. Do the forward scan one node at a time: type the EST and press Check. At node 4, remember the dummy counts as an arrow with duration $0$.
Then switch to the backward scan. At node 3, two arrows leave (G and the dummy). Which one decides the LST, and why?
Your turn
For the school video in 9A (A $3$, B $2$, C $1$, D $2$, E $4$; arcs A 1→2, B 2→3, C 2→4, D 3→4, E 4→5), find the EST at every node and the minimum completion time.
Show the working
Node 1: $0$. Node 2: $0 + 3 = 3$. Node 3: $3 + 2 = 5$. Node 4: C gives $3 + 1 = 4$, D gives $5 + 2 = 7$, take $7$. Node 5: $7 + 4 = 11$. Minimum completion time: $11$ days.
In a forward scan, two arrows enter a node, giving $9$ and $12$. The EST at the node is:
Take the largest: the next activities can't start until both incoming activities are finished, and that happens at $12$.
In a backward scan, two arrows leave a node, giving $6$ and $4$. The LST at the node is:
Take the smallest. Starting any later than $4$ would delay the path that gave $4$.
School video network: A ($3$) from node 1 to 2, B ($2$) from 2 to 3, C ($1$) from 2 to 4, D ($2$) from 3 to 4, E ($4$) from 4 to 5. Find the EST at node 4.
Node 2: $3$. Node 3: $3 + 2 = 5$. Into node 4: C gives $3 + 1 = 4$ and D gives $5 + 2 = 7$. Largest: $7$.
For the same network, find the minimum completion time in days.
Node 5: $7 + 4 = 11$. The EST at the finish node is the minimum completion time, $11$ days.
For the same network, find the LST at node 2.
Node 5: $11$, node 4: $11 - 4 = 7$, node 3: $7 - 2 = 5$. Out of node 2: B gives $5 - 2 = 3$ and C gives $7 - 1 = 6$. Smallest: $3$.
Café network: K ($2$) from node 1 to 2, L ($5$) from 1 to 3, a dummy from 2 to 3, M ($6$) from 2 to 4, N ($3$) from 3 to 4. Find the EST at node 3.
Into node 3: L gives $0 + 5 = 5$, the dummy gives $2 + 0 = 2$. Largest: $5$.
For the café network, find the minimum completion time in days.
Into node 4: M gives $2 + 6 = 8$, N gives $5 + 3 = 8$. Both give $8$, so the minimum completion time is $8$ days.
Exam style: In the shed network from Example 1, buying materials (B) now takes only $2$ days. Find the new minimum completion time.
Node 2: $1$. Node 3: B gives $0 + 2 = 2$, C gives $1 + 2 = 3$, so $3$. Node 4: $3 + 3 = 6$. Node 5: $6 + 2 = 8$. Node 6: F gives $6 + 2 = 8$, G gives $8 + 1 = 9$, so $9$ days.
Exam style: In the original shed network, painting (F) now takes $4$ days. Find the new minimum completion time.
ESTs up to node 5 are unchanged: node 4 is $7$ and node 5 is $9$. Node 6: F gives $7 + 4 = 11$, G gives $9 + 1 = 10$, so $11$ days. The project is now $1$ day longer.