NZ Level 8 (NZC) Level 3 (NCEA) [In development]
topic badge
Tasks with dependencies
Lesson

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, we’re going to think about an easy, but very important, task - making tea! Hot tea, out of a kettle, that is. What do we need to do?

We need to fill the kettle, boil it, put the tea in the pot, put the boiled water in the pot, wait for the tea to infuse, pour it into a cup, add milk and sugar, then drink it.

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. 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 table, like this:

Activity Description Dependencies
$A$A Water in kettle -
$B$B Tea in pot -
$C$C Boil kettle $A$A
$D$D Water in pot $B$B,$C$C
$E$E Infuse $D$D
$F$F Tea in cup $E$E
$G$G Milk $F$F
$H$H Sugar $F$F
$J$J Stir $H$H,$G$G

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$E, “Infuse”, requires task $D$D, “Water in pot”, so $D$D is a dependency for $E$E. Task $A$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:

Activity Description Dependencies Time (seconds)
$A$A Water in kettle - $20$20
$B$B Tea in pot - $15$15
$C$C Boil kettle $A$A $30$30
$D$D Water in pot $B$B,$C$C $10$10
$E$E Infuse $D$D $120$120
$F$F Tea in cup $E$E $8$8
$G$G Milk $F$F $5$5
$H$H Sugar $F$F $4$4
$J$J Stir $H$H,$G$G $5$5

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 this next example will illustrate.

You’re in charge of organising a book release and press tour for a very famous author. In the planning meeting you and your team put together a list of all the things you need to organise, and how each task links up with the next, and write an activity table for the project:

Activity Description Dependencies Time (days)
$A$A Get manuscript from author - $1$1
$B$B Figure out tour dates - $4$4
$C$C Format manuscript for printing $A$A $7$7
$D$D Print books $C$C $15$15
$E$E Design cover $C$C $7$7
$F$F Book venues for tour $B$B $12$12
$G$G Print covers $E$E $10$10
$H$H Collect books from printers $D$D,$G$G $1$1
$J$J Run social media competition $F$F $16$16
$K$K Plan travel and accommodation $F$F $13$13
$L$L Deliver books to venues and competition winners $H$H,$J$J $9$9
$M$M Create itinerary for author and entourage $K$K $5$5

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$A and $B$B) with no dependencies, so we draw two arrows coming out of the start vertex. Don’t put arrowheads on the ends yet! You’ll see why in just a moment.

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

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

$G$G depends on $E$E, and $M$M depends on $K$K:

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

$L$L depends on both $H$H and $J$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.

 

Dealing with multiple dependencies

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. Here's an example of such an activity table:

Activity Dependencies Duration
$A$A - $3$3
$B$B - $4$4
$C$C - $5$5
$D$D $A,B$A,B $3$3
$E$E $B,C$B,C $2$2

Notice that $B$B is a dependency for both $D$D and $E$E, but $A$A is not a dependency for $E$E, and $C$C is not a dependency for $D$D. To draw this as a network, we need to introduce some new edges:

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

Outcomes

M8-5

Develop network diagrams to find optimal solutions, including critical paths.

91576

Use critical path analysis in solving problems

What is Mathspace

About Mathspace