9.09 Forward and backward scanning

Let’s take another look at the network example from 9.08 that represents the tasks involved in making tea. We have a directed, weighted network that looks like this:

Suppose you and a friend are on a team, racing to make tea as fast as you can. One of you is going to boil the water while the other is going to add the tea to the pot. Unfortunately, your friend takes twice as long as you to do any task. Which task should each of you take?

If you pour the water in the kettle ($20$20s) and wait for it to boil ($30$30s), your friend has $20+30=50$20+30=50s to put the tea in the pot. It will take them $2\times15=30$2×15=30s, so by the time the water is ready they’ve had plenty of time.

But if they put water in the kettle ($2\times20=40$2×20=40s) and wait for it to boil ($30$30s), it doesn’t matter that it only took you $15$15s to put the tea in the pot - overall it takes more than a minute to get to the same place.

There is a path through the whole network called the critical path, which looks like this:

It goes from start to finish, highlighting the tasks where delays are costly. Any delay in any task along this path means a delay overall, so the best and fastest people should do these jobs.

Now in this “making tea” example the critical path was easy to spot. The “book tour” example from 9.08 is a little more complicated:

Twelve tasks in all - but which tasks are the most critical? Where are delays costly and should have the best people on it? Which tasks allow for a little flexibility? To figure this out, we are going to do a forward and backward scan. We start by putting a little box both above and below each vertex (only one is needed for the Start and Finish):

We write a $0$0 in the Start box and move along each task, adding up how long it would take to start the next task as we go, and writing it in the top box for each vertex. If there is only one arrowhead pointing at a vertex, just take the number at the previous vertex and add the task time to get the new number. Here are the first seven boxes filled in:

Reading along the top,

• start $C$C after $1$1 day (we have to wait for $A$A),
• start both $D$D and $E$E after $1+7=8$1+7=8 days (we have to wait for $A$A and then wait for $C$C),
• start $G$G after $8+7=15$8+7=15 days (wait for $A$A and then $C$C and then $E$E).

Reading along the bottom:

• start $F$F after $4$4 days (wait for $B$B),
• start both $J$J and $K$K after $4+12=16$4+12=16 days (wait for $B$B and then $F$F),
• start $M$M after $16+12=28$16+12=28 days (wait for $B$B and then $F$F and then $K$K).

Now the remaining vertices have more than one arrowhead pointing at them. This means that more than one task is a dependency, so they all need to be completed before we continue. Let’s zoom in on the top part of the diagram.

It takes $8$8 days to get ready for $D$D, then $15$15 days to do it, so the first dependency is going to be ready after $23$23 days. At the same time, it takes $15$15 days to get ready for $G$G, and then $10$10 days to do it, so the second dependency is going to be ready after $25$25 days. Both need to be ready before moving on, we write the largest number, $25$25, in the box to indicate how long it takes before we can get started on $H$H.

We do this for the rest of the mergers all the way to the finish - picking the largest sum along all the tasks before it.

The numbers in these boxes are the earliest start times for each activity. As long as everything goes to plan, each task can start on the day sitting above the vertex that it is drawn from. We can also tell that it will take $41$41 days for everything to be ready, if all goes to plan. Our forward scan is complete!

Now, we start our backward scan. This will tell us the latest start times for each task. The idea is very similar, but this time we start with the number on the right and subtract the task duration instead of adding. If there is only one edge coming out of the vertex we are heading towards, we simply subtract the task time. Here are the first four boxes from the backwards scan filled in:

When two or more edges emerge from the same vertex, we want to pick the smallest number. Let’s zoom in on the bottom branch:

We need to finish $J$J by day $32$32, and it takes $16$16 days to do it, so the latest we can start task $J$J is day $16$16. Similarly, we need to finish $K$K by day $36$36, and it takes $12$12 days to do it, so the latest we can start task $K$K is day $24$24. We write the smallest of the differences we found in the box and continue along.

By the end of this process the numbers on the bottom are the latest start times for each activity. If this amount of time has passed and the task hasn’t begun, the whole project will be delayed.

To summarise the tricky cases with forward scanning, look for vertices with groups of arrows going into them:

And while backward scanning, look out for vertices that have groups of arrows coming out of them:

 

 

Practice question

Question 1