7.03 Analysing tasks on a project network

 

Critical path analysis

Let’s consider the “making tea” example from our lesson on project networks. 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. What is the minimum time required to make a cup of tea? Let's focus on the first set of tasks:

If you put the water in the kettle ($20$20 s) and wait for it to boil ($30$30 s), your friend has $20+30=50$20+30=50 s to put the tea in the pot. It will take them $15$15 s, so by the time the water is ready they’ve had plenty of time. As all three tasks must be completed before our next step, the minimum time before we can pour the water in the pot is $50$50 s.

At each stage all dependent activities must be completed before the next step can begin. So while it was seem counter-intuitive, the longest path through a project network will give the minimum possible completion time for the project.

This 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 critical tasks. Any delay in any task along this path means a delay overall project. The minimum completion time for a project is the length of the critical path. For our example the minimum time to complete making a cup of tea is: $20+30+10+120+8+5+5=198$20+30+10+120+8+5+5=198 s.

 

Exploration

In the “making tea” example the critical path was easy to spot. Finding the critical path in the “book tour”, from the previous lesson, is a little more complicated.

There are twelve tasks in all. Which tasks are the most critical, where delays are costly? Which tasks can be delayed without impacting the overall finish time?

To figure this 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):

The top boxes will be used for the forward scan and the bottom boxes for the backward scan.

Forward scanning

In the forward scan we calculate the earliest possible time for each task to begin, once all its predecessors are complete.

We put 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,

• we can 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),
• and 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:

• we can 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),
• and 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. Since they 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.

 

Backward scanning

Now, we start our backwards scan. The backward scan will tell us the latest start times for each task. If each task begins no later than this time, then all remaining tasks can be completed without delaying the overall finish time.

The process is similar to forward scanning, 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.

Starting from the Finish vertex, 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. The smallest difference is $16$16, so we write that in the box and continue working backwards.

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. Where there are multiple tasks starting at a vertex the latest start time relates to the latest start time of the most critical task leading from the vertex. 

 

Identifying the critical path

Taking 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 identified the critical path.

We can name the critical path by listing the task names: $B\rightarrow F\rightarrow J\rightarrow L$B→F→J→L or just $BFJL$BFJL.

Note: In some cases there may be more than one critical path. We may also encounter networks that include dummy tasks. These tasks have a completion time of $0$0 and the forward and backward scan is performed as if these are regular tasks.

 

When we are forward scanning and backward scanning, we need to take care with vertices that have multiple arrows going in or out.

 

 

Practice questions

Question 1

Question 2

 

Float time (or slack time)

 

Non-critical tasks have some flexibility in the time they take to complete before a delay to the entire project would result. The amount of leeway a task has before it would become critical is called the float time (sometimes called slack time).

Critical tasks have a float time of $0$0. Their earliest and latest start times are equal, so the tasks have no ability to allow for a delay without an overall delay for the entire project.

We can see how much delay a task can tolerate by calculating the difference between a task's earliest start time (EST) and latest start time(LST). For activities that are the only task leading from a vertex this is simply the difference between the two boxes on the vertex the activity is coming from.

For a general activity the float time can be calculated as follows:

$\text{Float time}$Float time

$=$=

$LST_2-EST_1-\text{Activity time}$LST2​−EST1​−Activity time

That is, take the LST of the vertex that the activity points to, subtract the EST of the vertex that it comes from, and then subtract the duration of the activity.

Let's look again at our completed network and calculate the float times for non-critical tasks.

 

The non-critical tasks in this case are $A$A, $C$C, $D$D, $E$E, $G$G, $H$H, $K$K and $M$M and their float times are shown below:

Activity	Calculation	Float time (days)
$A$A	$7-0-1$7−0−1	$6$6
$C$C	$14-1-7$14−1−7	$6$6
$D$D	$31-8-15$31−8−15	$8$8
$E$E	$21-8-7$21−8−7	$6$6
$G$G	$31-15-10$31−15−10	$6$6
$H$H	$32-25-1$32−25−1	$6$6
$K$K	$36-16-12$36−16−12	$8$8
$M$M	$41-28-5$41−28−5	$8$8

Some observations:

• The critical tasks $B$B, $F$F, $J$J, and $L$L have a float time of $0$0 and cannot have any delay without causing delay to the entire project.
• Tasks on the path $A$A, $C$C, $E$E, $G$G, $H$H all have a float time of $6$6. In fact, these float times are shared along this path. For example, if task $A$A takes $7$7 days instead of $1$1, all subsequent tasks must be started on their latest start date in order to avoid delays.
  • Tasks on the path $K$K, $M$M both have a float time of $8$8 days. Again this float time is shared across both tasks. For example, if task $K$K was delayed by $5$5 days then task $M$M would then have a reduced float time of $3$3 days.
• Task $D$D has a float time of $8$8 days, this means the task can take up to $23$23 days to complete before becoming critical and any further delay would delay the entire project.

 

Practice question

Question 3

 

Analysing changes

Having just looked at forward and backward scanning, identifying the critical path and calculating float times, we can now asses the impact delays and changes may have on the project. Keep the following in mind when assessing changes:

• If a critical task is delayed by a given amount of time the entire project will also be delayed by the same amount.
• If a critical task is reduced, provided there is only one critical path, the completion time of the project will be reduced. However, the full reduction may not be realised as the critical path may change. In this case, we must carefully analyse the network to see if there are further changes. This may involve doing a partial or full re-scan of the network.
• If a non-critical task is delayed by less than its float time there will be no delay to the overall project completion time.
• Once a non-critical task is delayed by its float time it becomes critical and any further delay will delay the entire project.

 

Worked example

Here is the network graph for the book tour, after forward and backward scanning and with the critical path highlighted.

 

Let's recall the activity table for this project, with descriptions of each task.

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 an itinerary for author and entourage	$K$K	$5$5

(a) If it takes three days longer than expected to book venues for the tour, how might this affect the project?

Think:

• Booking venues is activity $F$F.
• $F$F is on the critical path, so any delay here will result in the project being delayed by the same amount.

Do: The overall project will now take $41+3=44$41+3=44 days.

(b) If creating the itinerary is delayed by $3$3 days, how might this affect the project?

Think:

• Creating the itinerary is activity $M$M.
• Task $M$M is not critical and has float time: $41-28-5=8$41−28−5=8 days.

Do: As the delay is less than the available float time for this task this will not affect the project.

(c) If the social media competition is completed $7$7 days early, how might this affect the project?

Think:

• The social media competition is Activity $J.$J.
• Activity $J$J is on the critical path and will now take $16-7=9$16−7=9 days.
• As $J$J is completed earlier than planned the entire project can be ready earlier.
• The full reduction may not be passed on as the critical path may change. Here we must look carefully at the network to see the impact of the change.

Do:

• The path through $B-F-J$B−F−J will now take $16+9=25$16+9=25.
• This is now earlier than the path through $A-C-E-G-H$A−C−E−G−H which is $26$26 days.

So the critical path has changed to $A-C-E-G-H-L$A−C−E−G−H−L, and the project can be completed in $35$35 days, which is an overall reduction of $6$6 days.

Limitations and assumptions

When analysing a project network it is good practice to think of what limitations the method has, as well as limitations and assumptions that may be particular to the given situation. Some questions to consider which may highlight some assumptions are:

• Is there enough staff, machinery and work space for tasks to run concurrently where possible? 
• Is it likely there will be no delays, such as weather delays on a building site?
• Can each activity start immediately after its dependent tasks are completed?
• Are there allowances for breaks, shift changes? 
• Are all staff at an experience level to complete the tasks in the time stated?

 

Multiple dependencies

 

Practice question

Question 4