7.03 Analysing tasks on a project network

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 \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 15\text{ 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\text{ 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 \text{ s}.

In the “making tea” example the critical path was easy to spot. Finding the critical path in the network below 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.

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 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 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.

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 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. The smallest difference is 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.

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\to F\to J\to L or just 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 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.

In some examples, instead of using a box above and below the vertex, project networks are drawn with a line inside the vertex circle or something else entirely. How we do it isn’t important, what we need are two places to put numbers at each vertex.

The three examples shown above are all equivalent indicate that the task coming out of this vertex has an earliest start time of 12 and latest start time of 17 (in the relevant time units).

In some cases, the vertex is numbered, as shown in the second and third examples where the vertex is number 3. The vertex numbering does not affect any time calculations.

Examples

Example 1

Given the following network:

a

Find the earliest starting time (EST) for each vertex.

\text{Vertex}	\text{Start}	1	2	3	4	5	6	\text{Finish}
\text{EST}

Worked Solution

Create a strategy

Do a forward scan of the network.

Apply the idea

The first node, Start, has an EST of 0.

\displaystyle \text{EST of 1}	\displaystyle =	\displaystyle 0+7	Add Start's EST and A's duration
	\displaystyle =	\displaystyle 7	Evaluate
\displaystyle \text{EST of 2}	\displaystyle =	\displaystyle 0+1	Add Start's EST and B's duration
	\displaystyle =	\displaystyle 1	Evaluate

For node 3, 7+6 \gt 1+2 so we add the durations for A and C.

\displaystyle \text{EST of 3}	\displaystyle =	\displaystyle 7+6	Add node 1's EST and C's duration
	\displaystyle =	\displaystyle 13	Evaluate
\displaystyle \text{EST of 4}	\displaystyle =	\displaystyle 13+4	Add node 3's EST and E's duration
	\displaystyle =	\displaystyle 17	Evaluate
\displaystyle \text{EST of 5}	\displaystyle =	\displaystyle 13+4	Add node 3's EST and F's duration
	\displaystyle =	\displaystyle 17	Evaluate

For node 6, 4+6 \gt 4+3 so we add the durations for F and H.

\displaystyle \text{EST of 6}	\displaystyle =	\displaystyle 17+6	Add node 5's EST and H's duration
	\displaystyle =	\displaystyle 23	Evaluate
\displaystyle \text{EST of FINISH}	\displaystyle =	\displaystyle 23+9	Add node 6's EST and I's duration
	\displaystyle =	\displaystyle 32	Evaluate

\text{Vertex}	\text{Start}	1	2	3	4	5	6	\text{Finish}
\text{EST}	0	7	1	13	17	17	23	32

b

Now find the latest starting time (LST) for each vertex.

\text{Vertex}	\text{Start}	1	2	3	4	5	6	\text{Finish}
\text{EST}	0	7	1	13	17	17	23	32
\text{LST}

Worked Solution

Create a strategy

Do a backward scan of the network.

Apply the idea

The last node, Finish, has an LST of 32.

\displaystyle \text{LST of 6}	\displaystyle =	\displaystyle 32-9	Subtract I 's duration from the Finish LST
	\displaystyle =	\displaystyle 23	Evaluate
\displaystyle \text{LST of 5}	\displaystyle =	\displaystyle 23-6	Subtract H 's duration from 6's LST
	\displaystyle =	\displaystyle 17	Evaluate
\displaystyle \text{LST of 4}	\displaystyle =	\displaystyle 23-20	Subtract G 's duration from 6's LST
	\displaystyle =	\displaystyle 20	Evaluate

For node 3, 17-4 \lt 20-4 so we are going to use node 5's LST.

\displaystyle \text{LST of 3}	\displaystyle =	\displaystyle 17-4	Subtract F 's duration from 5's LST
	\displaystyle =	\displaystyle 13	Evaluate
\displaystyle \text{LST of 2}	\displaystyle =	\displaystyle 13-2	Subtract D 's duration from 3's LST
	\displaystyle =	\displaystyle 11	Evaluate
\displaystyle \text{LST of 1}	\displaystyle =	\displaystyle 13-6	Subtract C 's duration from 3's LST
	\displaystyle =	\displaystyle 7	Evaluate

For the Start node, 7-7\lt 11-1 so we are going to use node 1's LST.

\displaystyle \text{LST of Start}	\displaystyle =	\displaystyle 7-7	Subtract A 's duration from 1's LST
	\displaystyle =	\displaystyle 0	Evaluate

So the completed table is:

\text{Vertex}	\text{Start}	1	2	3	4	5	6	\text{Finish}
\text{EST}	0	7	1	13	17	17	23	32
\text{LST}	0	7	11	13	20	17	23	32

c

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

Worked Solution

Create a strategy

Use the table from part (b) to 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,5,6, and the Finish node.

By following these nodes we pass through activities A,C,F,H, and I.

The critical path is A,C,F,H,I.

d

What is the duration of the critical path?

Worked Solution

Create a strategy

The duration of the critical path is the EST of the last node.

Apply the idea

The EST of the last node, Finish, is 32.

So the duration of the critical path is 32.

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. 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 $=$ LST$_2$ $-$ EST$_1$ $-$ 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,C,D,E,G,H,K, and M and their float times are shown below:

Some observations:

• The critical tasks B,F,J, and L have a float time of 0 and cannot have any delay without causing delay to the entire project.

• Tasks on the path A,C,E,G,H all have a float time of 6. In fact, these float times are shared along this path. For example, 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.

• Tasks on the path K,M both have a float time of 8 days. Again this float time is shared across both tasks. For example, if task K was delayed by 5 days then task M would then have a reduced float time of 3 days.

• Task D has a float time of 8 days, this means the task can take up to 23 days to complete before becoming critical and any further delay would delay the entire project.

Examples

Example 2

In the following network the critical path has been highlighted in red:

a

List all non-critical activities.

Worked Solution

Create a strategy

List all activities that are not on the highlighted critical path.

Apply the idea

The non-critical activities are B,C,E,F,G,I.

b

Find the float time for each non-critical 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	6-0-1	5
C	6-0-2	4
E	9-1-3	5
F	10-1-3	6
G	10-2-4	4
I	11-6-1	4

Example 3

A small swimming club is planning a competition. The various tasks that need to be completed in preparation for the competition, A-M, are described in the precedence table below:

Job	Time (days)	Prerequisites	Earliest Start Time	Latest Start Time
A	2	\text{NONE}	0	7
B	3	A	2	9
C	8	\text{NONE}	0	0
D	7	\text{NONE}	0	1
E	7	A	2	9
F	5	E	9	16
G	9	B,H,J	12	12
H	4	C	8	8
I	6	F,G	21	21
J	4	D	7	8
K	5	H,J	12	16
L	2	I	27	27
M	8	K	17	21

a

Select all jobs from the following options that are on the critical path.

A

L

B

G

C

M

D

B

Worked Solution

Create a strategy

Find the jobs where the EST and LST are equal in the table.

Apply the idea

EST and LST are equal for jobs C, G, H, I, and L, so they are all on the critical path. Options A and B are in this list.

The answers are options A and B.

b

Calculate the minimum completion time for the competition preparation.

Worked Solution

Create a strategy

Add the activity time and the EST of the last job.

Apply the idea

We can find the last job by finding the job with the highest EST since it indicates the duration of the whole project.

The highest EST is 27 which is at L with activity time of 2 days.

So the minimum completion time is 27+2=29 days.

c

Task J is delayed by 3 days, what effect will this have on the minimum completion time?

A

An overall delay of 1 day as the delay exceeds the task's float time by 1 day.

B

An overall delay of 3 days as the task is critical.

C

None, as the task is not critical and the delay is under the float time.

D

An overall delay of 2 days as the delay exceeds the task's float time by 2 days.

Worked Solution

Create a strategy

Find the job's float time to check if the delay exceedes the float time.

Apply the idea

The float time of J is the difference of its EST from its LST.

\displaystyle \text{Float time of }J	\displaystyle =	\displaystyle 8-7	Subtract EST from LST
	\displaystyle =	\displaystyle 1 \text{ day}	Evaluate

Since the float time of J is 1 and it is delayed by 3 days, the overall delay is 3-1=2 days as the delay exceeds the task's float time by 2 days.

The answer is option D.

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.

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?

Examples

Example 4

The network displays the times (in hours) in the production process for a toy manufacturer's new toy. The forwards and backwards scan with critical path highlighted is shown.

a

If task M is delayed by 4 hours, what will be the new completion time for a toy?

Worked Solution

Create a strategy

If the task is critical, add the delayed time to the EST of the activity.

Apply the idea

Task M is critical, so the new completion time is 25+4=29 hours.

b

If task H is delayed by 4 hours, what impact on the completion time will this have?

A

An overall delay of 2 hours as the delay exceeds the task's float time by 2 hours.

B

None, as the task is not critical and the delay is under the float time.

C

An overall delay of 1 hour as the delay exceeds the task's float time by 1 hour.

D

An overall delay of 4 hours as the task is critical.

Worked Solution

Create a strategy

Find the task's float time using the formula: \text{Float time}=\text{LST}_2-\text{EST}_1- \text{duration}

Apply the idea

\displaystyle \text{Float time of }H	\displaystyle =	\displaystyle 15-10-2	Subtract EST from LST
	\displaystyle =	\displaystyle 3 \text{ hours}	Evaluate

Since the float time of H is 3 and delayed by 4 days, the overall delay is 4-3=1 hour as the delay exceeds the task's float time by 1 hour.

The answer is option C.

c

What is the most that task E can be reduced by and still have an effect on the overall completion time?

Worked Solution

Create a strategy

Find the duration of the next longest path that does not include the given activity.

Apply the idea

The next longest path without E is CFGKMN.

\displaystyle \text{Duration of } CFGKMN	\displaystyle =	\displaystyle 13+5+3+2+4+6	Add the durations of each activity
	\displaystyle =	\displaystyle 23 \text{ hours}	Evaluate

Since the critical path has a duraction of 25 hours, task E can be reduced by 25-23=2 hours.

d

If task L is delayed by 2 hours it becomes critical and the network will contain 2 critical paths. What is the second critical path formed?

Worked Solution

Create a strategy

Add the delayed hours to the task.

Apply the idea

Now task L has new duration of 2+2=4 hours.

Using the critical path but turning to L from K the new critical path is BEGKLN.

The duration of BEGKLN is 15+4+6=25 hours which is the same as the original critical path, so this confirms that it is a critical path.