D1-4 Critical path analysis — 9FM0 revision notes

D1-4.1

Modelling of a project by an activity network, from a precedence table.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

An activity network is drawn activity on arc:
each activity is an arc labelled with its name and duration, and each numbered event is a node marking the moment when every activity into it has finished. A precedence table lists, for each activity, only its immediate predecessors, so an activity that depends on $A$ through $B$ is recorded as depending on $B$ alone.
A dummy is a zero-duration arc, always drawn dashed, and it is needed for two reasons. The first is logical: when one activity needs $A$ and $B$ while another needs only $A$ , the two cannot leave the same event, so $A$ ends at its own event and a dummy carries its dependency forward.
The second is uniqueness: two activities must never share both their start event and their end event, since each activity has to be identified by its pair of events, so a dummy separates them.
Every network has exactly one start event, with no arcs entering, and one finish event, with no arcs leaving.

Worked example

A project has activities $A$ and $B$ with no predecessors, $C$ with immediate predecessor $A$ , and $D$ with immediate predecessors $A$ and $B$ . Explain why a dummy is needed and describe the network.

1.Both $A$ and $B$ leave the start event, event $1$ .
2. $A$ must end at its own event, event $2$ , because $C$ depends on $A$ alone.
3. $B$ ends at event $3$ , and $D$ leaves event $3$ .
4.A dummy from event $2$ to event $3$ carries the dependency of $D$ on $A$ without making $C$ depend on $B$ .

Answer: One dummy is needed, from the end of $A$ to the start of $D$ , because $D$ depends on both $A$ and $B$ while $C$ depends on $A$ only.

Common mistakes

Don't fall into the trap of listing a predecessor that is implied by another one, so that the table is not reduced to immediate predecessors.
Don't fall into the trap of drawing two activities between the same pair of events without separating them with a dummy.
Don't fall into the trap of giving a dummy a non-zero duration or drawing it with a solid line.

Exam tip

Work down the precedence table one activity at a time and ask which activities must be complete before it starts; a dummy is needed exactly when two activities have overlapping but unequal predecessor sets.

Tier 1 · Easy

ORIGINAL

1.

Explain what is meant by a dummy in an activity network, and state the duration of a dummy.

(3)

(Total for Question 1 is 3 marks)

Tier 2 · Standard

ORIGINAL

1.

A project has the precedence table:

A

and

B

have no predecessors;

C

has immediate predecessor

A

;

D

has immediate predecessors

A

and

B

;

E

has immediate predecessor

C

;

F

has immediate predecessor

C

;

G

has immediate predecessors

D

and

E

;

H

has immediate predecessors

F

and

G

. Describe an activity network for this project, giving the event numbers of every arc.

(7)

(Total for Question 1 is 7 marks)

Tier 3 · Hard

ORIGINAL

1.

A project has activities

A

to

F

with the precedence table:

A

and

B

have no predecessors;

C

has immediate predecessor

A

;

D

has immediate predecessor

A

;

E

has immediate predecessors

B

and

C

;

F

has immediate predecessors

D

and

E

. Describe an activity network, state the number of dummies you have used, and justify each one.

(7)

(Total for Question 1 is 7 marks)

D1-4.2

Completion of the precedence table for a given activity network.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

Reading a precedence table off a network reverses the drawing process. For each activity, look at the event it leaves and list every activity that enters that event; those are its immediate predecessors.
A dummy is not an activity, so when a dummy enters the event, follow the dummy backwards and take the activities entering the dummy's own start event instead.
An activity leaving the start event has no predecessors.
Finally the table must be reduced: if an activity is listed and is also a predecessor of another listed activity, remove it, because a precedence table records only immediate predecessors.
A useful check is that every activity appears somewhere in the table, that the number of activities with no predecessors matches the number of arcs leaving the start event, and that no activity is listed as its own predecessor directly or through a chain.

Worked example

In a network, $A$ runs from event $1$ to event $2$ , $B$ runs from event $1$ to event $3$ , a dummy runs from event $2$ to event $3$ , $C$ leaves event $2$ and $D$ leaves event $3$ . Write down the precedence table.

1. $A$ and $B$ leave the start event $1$ , so neither has a predecessor.
2. $C$ leaves event $2$ ; only $A$ enters event $2$ , so $C$ depends on $A$ .
3. $D$ leaves event $3$ ; $B$ and the dummy enter event $3$ .
4.The dummy starts at event $2$ , which $A$ enters, so $D$ depends on $A$ and $B$ .

Answer: $A$ : none; $B$ : none; $C$ : $A$ ; $D$ : $A$ and $B$ .

Common mistakes

Don't fall into the trap of recording the dummy itself as a predecessor instead of tracing back through it.
Don't fall into the trap of leaving in a predecessor that is implied by another entry, so the table is not reduced.
Don't fall into the trap of reading the activities leaving the event rather than the activities entering it.

Exam tip

Take the activities in the order they appear on the network and write the event each one leaves beside it; the table then follows from a single scan of the arcs entering those events.

Tier 1 · Easy

ORIGINAL

1.

In an activity network, activity

E

leaves event

4

, and the only activities entering event

4

are

B

and

C

. Write down the immediate predecessors of

E

, and state what you would do differently if a dummy also entered event

4

.

(3)

(Total for Question 1 is 3 marks)

Tier 2 · Standard

ORIGINAL

1.

An activity network on events

1

to

6

has:

A

from

1

to

2

;

B

from

1

to

3

; a dummy from

2

to

3

;

C

from

2

to

4

;

D

from

3

to

4

;

E

from

3

to

5

;

F

from

4

to

5

;

G

from

5

to

6

. Write down the complete precedence table.

(7)

(Total for Question 1 is 7 marks)

Tier 3 · Hard

ORIGINAL

1.

An activity network on events

1

to

6

has:

A

from

1

to

2

;

B

from

1

to

3

;

C

from

1

to

4

; a dummy from

3

to

2

; a dummy from

3

to

4

;

D

from

2

to

5

;

E

from

4

to

6

;

F

from

5

to

6

. Write down the precedence table, explaining how you treated each dummy, and state which event is the finish event.

(8)

(Total for Question 1 is 8 marks)

D1-4.3

Algorithm for finding the critical path. Earliest and latest event times. Earliest and latest start and finish times for activities. Identification of critical activities and critical path(s).

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

The forward pass sets the earliest event time of the start event to $0$ and then gives each event the largest value of earliest time plus duration over the activities entering it.
The backward pass sets the latest event time of the finish event equal to its earliest time and then gives each event the smallest value of latest time minus duration over the activities leaving it.
For an activity from event $i$ to event $j$ with duration $d$ , the earliest start is $e_i$ , the earliest finish is $e_i+d$ , the latest finish is $l_j$ and the latest start is $l_j-d$ .
An activity is critical when its earliest start equals its latest start, which happens exactly when $e_i=l_i$ , $e_j=l_j$ and $l_j-e_i=d$ ; a critical path is a chain of critical activities running from the start event to the finish event, and there may be more than one.
Since every activity needs one worker, the least number of workers that could finish the project in the critical time is $\left\lceil\dfrac{\text{sum of all durations}}{\text{project duration}}\right\rceil$ .

Worked example

A project has $A$ of duration $4$ with no predecessors, $B$ of duration $6$ with no predecessors, $C$ of duration $3$ after $A$ , and $D$ of duration $5$ after $B$ and $C$ . Find the project duration and the critical path.

1.Forward pass: earliest times are $0$ at the start, $4$ after $A$ , and $\max(6, 4+3)=7$ before $D$ .
2.The project duration is $7+5=12$ .
3.Backward pass: the latest time before $D$ is $12-5=7$ , and the latest time after $A$ is $7-3=4$ .
4. $A$ has $4=4$ and $C$ has $7-4=3$ , so both are critical; $B$ has latest start $7-6=1$ but earliest start $0$ , so it has float $1$ .

Answer: The project takes $12$ and the critical path is $A$ , $C$ , $D$ .

Common mistakes

Don't fall into the trap of taking the minimum on the forward pass or the maximum on the backward pass.
Don't fall into the trap of calling an activity critical because both of its events are critical, without checking that $l_j-e_i$ equals the duration.
Don't fall into the trap of assuming there is only one critical path when two chains have the same length.

Exam tip

Do the whole forward pass before starting the backward pass, and check that the latest time at the start event comes out as $0$ ; if it does not, there is an arithmetic error.

Tier 1 · Easy

ORIGINAL

1.

An activity runs from event

3

to event

6

and has duration

7

. The earliest event time at event

3

is

9

and the latest event time at event

6

is

20

. Write down the earliest start, earliest finish, latest finish and latest start of the activity.

(4)

(Total for Question 1 is 4 marks)

Tier 2 · Standard

ORIGINAL

1.

A project has activities with durations

A=5

,

B=4

,

C=6

,

D=3

,

E=7

,

F=2

,

G=4

,

H=5

and precedence

A

: none;

B

: none;

C

:

A

;

D

:

A

and

B

;

E

:

C

;

F

:

C

;

G

:

D

and

E

;

H

:

F

and

G

. Find the project duration and the critical path.

(7)

(Total for Question 1 is 7 marks)

Tier 3 · Hard

ORIGINAL

1.

A project has durations

A=5

,

B=7

,

C=4

,

D=6

,

E=3

,

F=8

,

G=2

,

H=5

and precedence

A

: none;

B

: none;

C

:

A

;

D

:

A

;

E

:

B

;

F

:

C

and

D

;

G

:

D

and

E

;

H

:

F

and

G

. Find the project duration, the critical path, and a lower bound for the number of workers needed to finish in that time.

(9)

(Total for Question 1 is 9 marks)

D1-4.4

Calculation of the total float of an activity. Construction of Gantt (cascade) charts.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

The total float of an activity from event $i$ to event $j$ with duration $d$ is $F(i, j)=l_j-e_i-d$ , where $e_i$ is the earliest time for event $i$ and $l_j$ is the latest time for event $j$ . Equivalently it is the latest start minus the earliest start, or the latest finish minus the earliest finish.
Critical activities are exactly those with zero total float. A Gantt or cascade chart draws time along the horizontal axis, one row per activity.
Critical activities are drawn as solid blocks in a single unbroken line across the top, since they cannot move. Each non-critical activity is drawn as a block starting at its earliest start, followed by a lightly shaded rectangle of length equal to its total float, showing the window in which the block may slide.
The chart makes it easy to read off which activities may be under way at a given time: draw a vertical line at that time and read every row it crosses.
Total floats may not be used independently, because two activities in the same chain can share the same float.

Worked example

An activity of duration $6$ runs from event $2$ to event $5$ . The earliest time at event $2$ is $9$ and the latest time at event $5$ is $20$ . Find its total float and describe its bar on a Gantt chart.

1.Total float $=l_5-e_2-d=20-9-6=5$ .
2.The earliest start is $9$ and the earliest finish is $15$ .
3.The latest start is $20-6=14$ and the latest finish is $20$ .
4.The bar is drawn from $9$ to $15$ , followed by a float rectangle from $15$ to $20$ .

Answer: The total float is $5$ , and the activity is drawn as a block from $9$ to $15$ with a float window extending to $20$ .

Common mistakes

Don't fall into the trap of using the latest time at the start event instead of at the end event in the float formula.
Don't fall into the trap of sliding two activities on the same chain by their full floats at once, which double counts shared float.
Don't fall into the trap of drawing the critical activities with gaps between them on the cascade chart.

Exam tip

Write $F=l_j-e_i-d$ at the top of your working and substitute the three numbers explicitly; nearly all float errors come from picking the wrong event time.

Tier 1 · Easy

ORIGINAL

1.

An activity of duration

4

runs from event

2

to event

6

. The earliest time at event

2

is

7

and the latest time at event

6

is

15

. Calculate the total float of the activity.

(2)

(Total for Question 1 is 2 marks)

Tier 2 · Standard

ORIGINAL

1.

For a project of duration

24

with activities

A=5

,

B=7

,

C=4

,

D=6

,

E=3

,

F=8

,

G=2

,

H=5

and precedence

A

: none;

B

: none;

C

:

A

;

D

:

A

;

E

:

B

;

F

:

C

and

D

;

G

:

D

and

E

;

H

:

F

and

G

, calculate the total float of every activity.

(7)

(Total for Question 1 is 7 marks)

Tier 3 · Hard

ORIGINAL

1.

For a project with durations

A=6

,

B=9

,

C=7

,

D=4

,

E=5

,

F=8

,

G=3

,

H=6

and precedence

A

: none;

B

: none;

C

:

A

;

D

:

A

;

E

:

B

and

D

;

F

:

C

;

G

:

E

;

H

:

F

and

G

, calculate the total float of every activity and describe the Gantt chart.

(9)

(Total for Question 1 is 9 marks)

D1-4.5

Construct resource histograms (including resource levelling) based on the number of workers required to complete each activity.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

A resource histogram plots time along the horizontal axis and the number of workers in use along the vertical axis. Here the number of workers required by each activity is given and need not be one.
To draw the histogram, first fix a schedule, usually every activity at its earliest start time, then for each time interval add up the workers of every activity in progress. The height of the histogram at a given time is that total,
and the area under the histogram equals the total number of worker-days in the project, whatever schedule is chosen.
Resource levelling means using the floats of non-critical activities to shift them within their windows so that the peak height falls and the profile is flatter, without extending the project.
Critical activities cannot move, so the critical profile is a floor beneath which no levelling can go. A useful check is that $\left\lceil\dfrac{\text{total worker-days}}{\text{project duration}}\right\rceil$ is a lower bound for the peak, but the true minimum peak is often larger because of precedence constraints.

Worked example

In a project of duration $6$ , activity $P$ needs $2$ workers on days $1$ to $3$ and activity $Q$ needs $3$ workers on days $2$ to $5$ . Find the histogram heights and the peak.

1.Day $1$ : only $P$ is running, so the height is $2$ .
2.Days $2$ and $3$ : both are running, so the height is $2+3=5$ .
3.Days $4$ and $5$ : only $Q$ is running, so the height is $3$ .
4.Day $6$ : nothing is running, so the height is $0$ .

Answer: The heights are $2, 5, 5, 3, 3, 0$ and the peak is $5$ workers, on days $2$ and $3$ .

Common mistakes

Don't fall into the trap of counting activities instead of workers when several activities need more than one worker each.
Don't fall into the trap of moving a critical activity while levelling.
Don't fall into the trap of assuming the peak can always be brought down to the worker-day lower bound.

Exam tip

Tabulate the interval each activity occupies before drawing anything; the histogram is then a column-by-column addition and mistakes are easy to spot.

Tier 1 · Easy

ORIGINAL

1.

In a project, activity

P

needs

2

workers and runs on days

1

to

4

, and activity

Q

needs

3

workers and runs on days

3

to

6

. Write down the height of the resource histogram on each of days

1

to

6

.

(3)

(Total for Question 1 is 3 marks)

Tier 2 · Standard

ORIGINAL

1.

A project has activities

A

of duration

3

needing

2

workers,

B

of duration

4

needing

1

worker,

C

of duration

2

needing

3

workers,

D

of duration

5

needing

2

workers and

E

of duration

3

needing

1

worker, with precedence

A

: none;

B

: none;

C

:

A

;

D

:

B

;

E

:

C

and

D

. Find the project duration and the critical activities.

(5)

(Total for Question 1 is 5 marks)

Tier 3 · Hard

ORIGINAL

1.

For the project with

A

of duration

3

needing

2

workers,

B

of duration

4

needing

1

,

C

of duration

2

needing

3

,

D

of duration

5

needing

2

and

E

of duration

3

needing

1

, and precedence

A

: none;

B

: none;

C

:

A

;

D

:

B

;

E

:

C

and

D

, determine the smallest possible peak of the resource histogram if the project must still finish in

12

days.

(9)

(Total for Question 1 is 9 marks)

D1-4.6

Scheduling the activities using the least number of workers required to complete the project.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

A scheduling diagram assigns each activity to a named worker and a time slot, so that no worker does two activities at once and every activity starts only after all of its predecessors have finished.
Start from the lower bound $\left\lceil\dfrac{\text{sum of the durations}}{\text{critical time}}\right\rceil$ , since each activity needs one worker and the project cannot be shorter than the critical path.
That bound is not always achievable, so the method is to try to construct a schedule with that many workers and, if the attempt provably fails, to argue that one more is needed and construct a schedule with that many.
A good construction puts the whole critical path on one worker, since those activities run end to end with no gaps, and then fits the non-critical activities into the remaining workers inside their float windows.
Always check each activity against its earliest start and latest finish, and state the schedule as a table of worker, activity and time interval.

Worked example

A project of critical time $10$ has activities totalling $18$ days of work, with critical path $P$ from $0$ to $6$ and $Q$ from $6$ to $10$ , and non-critical activities $R$ of duration $5$ with window $0$ to $8$ and $S$ of duration $3$ with window $2$ to $10$ . Find the least number of workers and give a schedule.

1.The lower bound is $\lceil18\div10\rceil=2$ workers.
2.Worker $1$ takes the critical path: $P$ from $0$ to $6$ and $Q$ from $6$ to $10$ .
3.Worker $2$ takes $R$ from $0$ to $5$ , which lies inside its window $0$ to $8$ .
4.Worker $2$ then takes $S$ from $5$ to $8$ , which lies inside its window $2$ to $10$ .

Answer: Two workers suffice, with worker $1$ on $P$ then $Q$ and worker $2$ on $R$ then $S$ .

Common mistakes

Don't fall into the trap of starting an activity before all of its predecessors have finished.
Don't fall into the trap of treating the lower bound as the answer without exhibiting a schedule that attains it.
Don't fall into the trap of splitting one activity between two workers, which is not allowed.

Exam tip

Give the critical path to a single worker first; that worker is then fully occupied for the whole project and the remaining activities are much easier to place.

Tier 1 · Easy

ORIGINAL

1.

A project has a critical time of

20

days and its activities have durations totalling

54

days. Each activity requires one worker. Calculate a lower bound for the number of workers needed to complete the project in

20

days.

(2)

(Total for Question 1 is 2 marks)

Tier 2 · Standard

ORIGINAL

1.

A project has durations

A=5

,

B=4

,

C=6

,

D=3

,

E=7

,

F=2

,

G=4

,

H=5

with precedence

A

: none;

B

: none;

C

:

A

;

D

:

A

and

B

;

E

:

C

;

F

:

C

;

G

:

D

and

E

;

H

:

F

and

G

. The critical time is

27

and the critical path is

A

,

C

,

E

,

G

,

H

. Find a lower bound for the number of workers and construct a schedule attaining it.

(8)

(Total for Question 1 is 8 marks)

Tier 3 · Hard

ORIGINAL

1.

A project has durations

A=5

,

B=7

,

C=4

,

D=6

,

E=3

,

F=8

,

G=2

,

H=5

and precedence

A

: none;

B

: none;

C

:

A

;

D

:

A

;

E

:

B

;

F

:

C

and

D

;

G

:

D

and

E

;

H

:

F

and

G

. The critical time is

24

with critical path

A

,

D

,

F

,

H

. Find the least number of workers needed and give a full schedule.

(9)

(Total for Question 1 is 9 marks)

Modelling of a project by an activity network, from a precedence table.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Completion of the precedence table for a given activity network.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Algorithm for finding the critical path. Earliest and latest event times. Earliest and latest start and finish times for activities. Identification of critical activities and critical path(s).

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Calculation of the total float of an activity. Construction of Gantt (cascade) charts.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Construct resource histograms (including resource levelling) based on the number of workers required to complete each activity.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Scheduling the activities using the least number of workers required to complete the project.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Want help turning these notes into marks?