9.08 Planning activities with dependencies

Many tasks in life involve a sequence of steps, and even simple tasks can be broken down into many smaller steps 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. For example, if we try to boil the kettle before we put water in it 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,C$B,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

Each of the tasks has been given a capital letter for ease of reference. The final column, Dependencies, 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, and are initial activities that can be started straight away. 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 and so it is an initial activity.

If you make tea all the time, you might like to know how long it all takes. If we write the times in minutes on 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,C$B,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	$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 shows.

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,G$D,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,J$H,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 tasks 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.

$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, and 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, and add the arrowheads that point to $H$H:

$L$L depends on both $H$H and $J$J, so we follow the same procedure as in the previous step.

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 and quickly tell how each of the tasks in the project depend on each other.

 

Practice questions

Question 1

Question 2