Discrete Mathematics 5: Critical path analysisAQA A-Level Further Maths: Topic test

1. 1
   A school hall refit has seven activities, $P$ to $V$. The durations in days and the immediate predecessors are: $P$ 3 (none), $Q$ 5 (none), $R$ 4 ($P$), $S$ 6 ($P$, $Q$), $T$ 2 ($R$), $U$ 5 ($R$, $S$), $V$ 3 ($T$, $U$).

   (a)

   What is the earliest start time of activity $U$?

   [1 mark]

   • A7 days
   • B11 days
   • C6 days
   • D16 days

   (b)

   What is the total float of activity $R$?

   [1 mark]

   • A2 days
   • B7 days
   • C0 days
   • D4 days

   (c)

   The project takes 19 days when everything goes to plan. Activity $S$ is delayed by 3 days. Separately, activity $R$ is delayed by 3 days. State the effect of each delay on the project duration, giving a reason in each case.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A project has seven activities, $H$ to $O$. The durations in days and the immediate predecessors are: $H$ 5 (none), $J$ 4 (none), $K$ 3 ($H$), $L$ 6 ($H$, $J$), $M$ 4 ($K$, $L$), $N$ 2 ($L$), $O$ 3 ($M$, $N$).

   (a)

   What is the latest finish time of activity $K$ that does not delay the project?

   [1 mark]

   • A11 days
   • B8 days
   • C15 days
   • D5 days

   (b)

   Which is the critical path?

   [1 mark]

   • A$H$, $K$, $M$, $O$
   • B$J$, $L$, $M$, $O$
   • C$H$, $L$, $M$, $O$
   • D$H$, $L$, $N$, $O$

   (c)

   The duration of activity $M$ is reduced from 4 days to 2 days. Find the new minimum project duration and state the critical path or paths.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A project has five activities. $T1$ takes 4 days, needs 3 workers and has no predecessors. $T2$ takes 3 days, needs 2 workers and has no predecessors. $T3$ takes 5 days, needs 2 workers and needs $T1$. $T4$ takes 4 days, needs 3 workers and needs $T2$. $T5$ takes 3 days, needs 1 worker and needs $T3$ and $T4$. Every activity starts as early as possible and its workers are needed for the whole of the activity.

   (a)

   Find the number of workers needed in each period of the project and state the largest number needed at any time.

   [3 marks]

   (b)

   Only 5 workers are available. Show that delaying $T4$ by one day allows the project to be completed in 12 days using no more than 5 workers at any time.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A fitting-out project has six activities. The durations in days, the workers needed and the immediate predecessors are: $A$ 4 days, 3 workers (none); $B$ 6 days, 2 workers (none); $C$ 3 days, 2 workers ($A$); $D$ 5 days, 2 workers ($A$); $E$ 4 days, 3 workers ($B$, $C$); $F$ 2 days, 1 worker ($D$, $E$). The workers are needed for the whole of each activity.

   (a)

   Carry out a forward pass and a backward pass. Find the minimum project duration, the critical activities and the floats of $B$ and $D$.

   [6 marks]

   (b)

   Each activity starts as early as possible. Find the number of workers needed in each period and show that 6 are needed at some time. Only 5 workers are available. Show how the schedule can be levelled so that the project is still completed in 13 days with at most 5 workers at any time.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A project has six activities, $J$ to $O$. The durations in days and the immediate predecessors are: $J$ 2 (none), $K$ 4 (none), $L$ 5 ($J$), $M$ 3 ($J$, $K$), $N$ 4 ($L$, $M$), $O$ 3 ($M$).

   (a)

   What is the minimum duration of the project?

   [1 mark]

   • A10 days
   • B21 days
   • C7 days
   • D11 days

   (b)

   What is the total float of activity $O$?

   [1 mark]

   • A1 day
   • B0 days
   • C2 days
   • D3 days

   (c)

   Management suggest reducing the duration of activity $L$ by 2 days to shorten the project. Explain why this will not shorten the project.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A project schedule has four activities. Each activity needs the stated number of workers for the whole of its time, and times are measured in days from the start of the project. $P$ runs from time 0 to time 4 and needs 2 workers. $Q$ runs from time 2 to time 6 and needs 3 workers. $R$ runs from time 4 to time 8 and needs 1 worker. $S$ runs from time 6 to time 9 and needs 2 workers.

   (a)

   How many workers are needed between time 4 and time 5?

   [1 mark]

   • A6
   • B4
   • C3
   • D5

   (b)

   What is the total number of worker-days used by the project?

   [1 mark]

   • A9
   • B8
   • C30
   • D15

   (c)

   Only 4 workers are available at any one time. State when this schedule needs more than 4 workers and how many are needed then.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A project has five activities, each needing one worker for the whole of its duration. The durations in days are: $S$ 5, $T$ 4, $U$ 3, $V$ 6, $W$ 2. $S$, $T$ and $U$ have no predecessors. $V$ needs $S$. $W$ needs $T$ and $U$. A worker can only do one activity at a time.

   (a)

   Find the minimum time in which the project can be completed, and use the total work to find a lower bound for the number of workers needed to complete the project in this time.

   [3 marks]

   (b)

   Show that 2 workers can complete the project in the minimum time, and state how long the project would take with only 1 worker.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A refit project has five activities. $X$ takes 4 days, needs 3 workers and has no predecessors. $Y$ takes 5 days, needs 2 workers and needs $X$. $N$ takes 3 days, needs 3 workers and has no predecessors. $W$ takes 2 days, needs 1 worker and needs $N$. $Z$ takes 3 days, needs 2 workers and needs $Y$ and $W$. The workers are needed for the whole of each activity.

   (a)

   Find the minimum project duration, the critical activities and the floats of $N$ and $W$. Activity $Y$ takes 3 days longer than planned. State the effect on the project duration.

   [6 marks]

   (b)

   Each activity starts as early as possible. Find the number of workers needed in each period and show that more than 5 workers are needed at some time. Only 5 workers are available. Show how the schedule can be levelled so that the project is still completed in 12 days using at most 5 workers at any time.

   [6 marks]

   Total for question 8: 12 marks

End of questions