9.05 Schedule problems and critical paths

Many things in life take work, and even simple tasks can be broken down into many smaller ones that all need to be completed in sequence. To start with consider the task, "making tea". What do we need to do? If we forget something or get the order wrong, we won’t have tea, if we try to boil the kettle before we put water in it, for example, we’ll never get anywhere.

We can create a directed network to illustrate the procedure of "making tea". An initial vertex with edges coming out of it represents tasks we can do straight away, and then we add in more vertices to indicate changing from one task to another:

We can also represent the same information in an activity or precedence table like this:

Each of the tasks has been given a capital letter for ease of reference. The final column (dependencies, sometimes immediate predecessors) tells us what tasks have to be completed immediately before the new task begins. The tasks that have no letters in the dependency column have no dependencies (sometimes no predecessors). For example, we can tell that task E, “Infuse”, requires task D, “Water in pot”, so D is a dependency for E. Task A, "Water in kettle", has no dependencies.

If you make tea all the time, you might like to know how long it all takes. If we add times to the edges as weights, our network looks like this:

And our activity table would then look like this:

An extra column has been added to represent the time it will take to perform each step.

We can go back the other way, from an activity table to a network as well.

Examples

Example 1

Given the following network, fill in the activity chart.

List the duration and direct dependencies for each activity in the table below.

Activity	Duration	Dependencies
A
B
C
D
E
F
G
H

If an activity has no dependencies, write X. If there are multiple dependencies, write them in the same box separated by commas.

Worked Solution

Create a strategy

Use the weights of the edges for the durations, and the previous connected edge for the dependencies.

Apply the idea

We will move from left to right along the network.

Activities A, B, and C have no edges to the left of them that they are connected to. So these activities do not have dependencies. Their durations are their weights next to the letters.

Activity	Duration	Dependencies
A	5	X
B	8	X
C	6	X
D	5	A
E	6	B
F	3	D, E
G	6	C
H	1	F, G

Activity D is connected to activity A on its left, so it's dependency is A.

Activity E is connected to activity B on its left, so it's dependency is B.

Activity F is connected to activities D and E on its left, so it's dependencies are D and E.

Activity G is connected to activity C on its left, so it's dependency is C.

Activity H is connected to activities F and G on its left, so it's dependencies are F and G.

Watch question walkthrough

By moving forwards through a network we can find the earliest start time for each activity. After we have finished forward scanning, we can then backward scan to find the latest possible start times.

We have a directed, weighted network that looks like this:

Imagine that you and a friend are on a team, racing to make a cup of 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 job should you take?

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

But if they put water in the kettle (2 \times 20 = 40 \text{ )}, and wait for it to boil (30\text{ s}), it doesn’t matter that it only took you 15 \text{ s} 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 is called the critical path. For our example above, this looks like:

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.

Let's go from an activity table to a network.

Imagine that we are in charge of organising a book release and press tour for a very famous author. In the planning meeting, our team puts together a list of all the things we need to organise and how each task links up with the next. We can put this information into an activity table for the project:

Let’s draw this as a network to do some analysis, by the end we will know which are the most important tasks with strict deadlines, and which ones have a bit of leeway.

There are two tasks (A and B) with no dependencies, so we draw two arrows coming out of the start vertex. Don’t put arrowheads on the ends yet.

Since C depends on A, we draw a vertex at the end of A, add in the arrowhead for A, and draw task C coming out of it (no arrowhead yet). We do the same for F, which depends on B.

Both D and E depend on C, while both J and K depend on F.

G depends on E, and M depends on K.

Now H depends on both D and G. We are going to create just one vertex that links D and G G together, so we continue the lines for each to that single vertex, add the arrowheads, then draw H coming out of that.

L depends on both H and J, so we do the same thing as we did above.

Now we’re out of tasks. We complete the remaining edges together at the Finish vertex with arrowheads.

All done. Well, some of those arrows do look a little wonky. It’s hard to know how it’s going to turn out while you’re doing it. But now we know the shape of it, we can redraw it a bit neater if we want.

Now we can clearly tell how each of the tasks in the project depend on each other quickly and easily.

Twelve tasks in all in which tasks are the most critical, where delays are costly and should have your best people on it? Which tasks allow for a little leeway?

To figure that out, we are going to do a forward and backward scan. Start by putting a little box both above and below each vertex (you can put just one for the Start and Finish):

Some places will get you to draw a line inside the vertex, or not use boxes at all, or something else entirely - how you do it isn’t important, what we need are two places to put numbers at each vertex.

We put a 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:

• we can start C after 1 day (we have to wait for A),

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

• and start G after 8+7=15 days (wait for A and then C and then E).

Reading along the bottom:

• we can start F after 4 days (wait for B),

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

• and start M after 16+12=28 days (wait for B and then F and then 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 days to get ready for D, then 15 days to do it, so the first dependency is going to be ready after 23 days. At the same time, it takes 15 days to get ready for G, and then 10 days to do it, so the second dependency is going to be ready after 25 days.

Since they both need to be ready before moving on, we write the largest number, 25, in the box to indicate how long it takes before we can get started on 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 (EST) 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 days for everything to be ready - again, if all goes to plan. Our forward scan is complete.

Now, we start our backwards scan. The backward scan will tell us the latest start times (LST) 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 by day 32, and it takes 16 days to do it, so the latest we can start task J is day 16. Similarly, we need to finish K by day 36, and it takes 12 days to do it, so the latest we can start task K is day 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 of a vertex are the latest start times for the activity starting at this vertex - if this amount of time has passed and the task hasn’t begun, the whole project will be delayed.

To summarize the tricky cases when we are forward scanning, look for vertices with groups of arrows going into them.

And when we are backward scanning look out for vertices that have groups of arrows coming out of them.

Sometimes a task may be a dependency for more than one other task. In these cases we might have to introduce additional vertices and edges to show this information. This is referred to as a 'dummy activity' Here's an example of such an activity table:

Notice that B is a dependency for both D and E, but A is not a dependency for E, and C is not a dependency for D. To draw this as a network, we need to introduce a dummy activity using dotted lines.

We represent these dependencies using dummy activities with a completion time of 0. The forward and backward scan works the same way.

Let’s take a closer look at the network after completing the forward and backward scan.

Notice that there is a single path from start to finish through vertices where the earliest start time and the latest start time are the same - if we highlight this path, we have what is called the critical path.

The difference between the top and bottom numbers is called the float time (sometimes called slack time), and it tells you how much leeway there is on the task. Tasks that have a float time of 0 lie on the critical path - these tasks need your best people. Delays in these tasks will either result in an overall delay for the whole project, or additional expenditure to get things back on track (called crashing).

For the other tasks, you can see how much “extra time” the person doing it can take. We have put the float times for tasks not on the critical path within the vertex to illustrate:

It’s important for us to return back to the original motivation for the problem to interpret our results. We now have the earliest and latest start times for each task, but also the amount of time we have to waste for each task. Some observations:

• The tasks B,F,J, and L cannot have any delay.

• Task M can take up to 13 days days even though it only needs 5.

• Task G can take 16 days days even though it only needs 10.

• The tasks lying above the critical path (A, C, D, E, G) have only 6 days of leeway between all of them. If task A takes 7 days instead of 1, all subsequent tasks must be started on their latest start date in order to avoid delays.

Having just looked at forward and backward scanning as a process to identify the critical path, we are now able to examine direct applications regarding this project.

The critical path is the sequence of activities that cannot be delayed without affecting the overall completion time of the project.

In particular, we can examine what may happen if activities are delayed.

(a) If the first run of books takes a few more days to be completed, how might this affect the project?

First run of books is activity D. D is on the critical path, so any delays result in the project being delayed.

We can examine how long this will delay the overall project by following this addition of 3 days through the network. Our forward scanning now changes to the following: Along D we have 13+18=31. Along H we have 31+8=39. And finally along L we have 39+9=48. So the overall project will now take 48 days.

(b) If the media release announcing the tour is delayed by 3 days, how might this affect the project?

Media release is activity M. M is not on the critical path, but this doesn't mean automatically that it doesn't affect the project. If M takes 8 days instead, then we need to check the forward scan. 29+8=37. Still less than 45 so this delay will not affect the project.

(c) If the books are delivered to venues and competition winners 2 days early, how might this affect the project?

Ensuring that books are delivered to venues and competition winners is Activity L. Activity L is on the critical path. If L is completed earlier than timetabled then the entire project can be ready earlier.

We looked at an example where changing an activity that was not on the critical path may or may not have affected the final outcome. To make this determination we had to check our forward scanning calculations.

Based on the original forward scanning for activity M, \, 29 + 5 = 34. The forward scanning value we took for the finish time was 45.

This difference is our float time. That is, the time this activity can be delayed before it actually does affect the final project.

So for activity M, the float time is 45-34=11 M, \, 29 + 5 = 34. hrs. As long as this activity is not delayed by more than 11 hours then we are fine.

This float time can also be seen on the vertices, it is the difference between the forward scan and the backward scan.

So above, E has a float time of 1 day. If E is delayed by more than that, then the entire project is delayed and a new critical path would follow.

Examples

Example 2

Given the following network:

a

Determine a critical path through the network by listing the activities in order.

Worked Solution

Create a strategy

Find the nodes where the EST and LST are equal. Find the activities those nodes pass through.

Apply the idea

EST and LST are equal at nodes Start, 1,3,4,7, and the Finish node.

By following these nodes we pass through activities A,C,E,H, and K.

The critical path is A,C,E,H,K.

Watch question walkthrough

b

List all non-critical activities.

Worked Solution

Create a strategy

List all activities that are not on the critical path.

Apply the idea

The non-critical activities are B,D,F,G,I,J.

Watch question walkthrough

c

Complete the table by determining the float time of each activity.

Worked Solution

Create a strategy

Use the formula: \text{Float time $=$ LST$_2$ $-$ EST$_1$ $-$ Activity time}

Apply the idea

The calculation for each float time is shown in the table below:

Activity	Calculation	Float time
B	13-0-9	4
D	16-9-3	4
F	33-16-6	11
G	25-16-7	2
I	34-22-1	11
J	34-23-9	2

Watch question walkthrough