| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2019 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Critical Path Analysis |
| Type | Find range for variable duration |
| Difficulty | Standard +0.3 This is a standard critical path analysis question requiring routine application of forward/backward pass algorithms and finding when an activity becomes critical. While it has multiple parts, each step follows textbook procedures with no novel insight required, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Activity | A | B | C | D | E | F | G | H |
| Duration | 2 | 4 | 5 | 4 | 3 | 3 | 2 | 4 |
| Immediate predecessors | - | A | - | A, C | B, C | B, D | D, E | F, G |
| Answer | Marks | Guidance |
|---|---|---|
| Activity on arc network with 8 activities A to H | M1 [3.1a] | |
| Correct, with directed arcs and no extra dummies. Durations need not be shown | A1 [1.1] | |
| Forward pass attempted | M1 [1.1] | M1 may be implied from 16 as length of longest path |
| Forward and backward passes correct, follow through their activity on arc network with at least one burst and at least one merge | A1ft [1.1] | |
| Longest path \(C - D - F - H\) | B1 [3.2a] | Or equivalent description |
| Evidence of Dijkstra (at vertices) | M1 [1.1] | M1 may be implied from 8 as length of shortest path |
| Follow through their network with at least one vertex updated | A1ft [1.1] | |
| Shortest path \(A - G - H\) | B1 [3.2a] | Or equivalent description |
| Answer | Marks | Guidance |
|---|---|---|
| Minimum completion time | B1 [3.2a] | Referring to time for critical activities (or equivalent) |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | B1 [3.2a] | Units may be implied |
# Question 4:
## Part (a)
Activity on arc network with 8 activities A to H | **M1** [3.1a] |
Correct, with directed arcs and no extra dummies. Durations need not be shown | **A1** [1.1] |
Forward pass attempted | **M1** [1.1] | M1 may be implied from 16 as length of longest path
Forward and backward passes correct, follow through their activity on arc network with at least one burst and at least one merge | **A1ft** [1.1] |
Longest path $C - D - F - H$ | **B1** [3.2a] | Or equivalent description
Evidence of Dijkstra (at vertices) | **M1** [1.1] | M1 may be implied from 8 as length of shortest path
Follow through their network with at least one vertex updated | **A1ft** [1.1] |
Shortest path $A - G - H$ | **B1** [3.2a] | Or equivalent description
## Part (b)
Minimum completion time | **B1** [3.2a] | Referring to time for critical activities (or equivalent)
## Part (©)
1 | **B1** [3.2a] | Units may be implied
---4 The table shows the activities involved in a project, their durations in hours and their immediate predecessors. The activities can be represented as an activity network.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
Activity & A & B & C & D & E & F & G & H \\
\hline
Duration & 2 & 4 & 5 & 4 & 3 & 3 & 2 & 4 \\
\hline
Immediate predecessors & - & A & - & A, C & B, C & B, D & D, E & F, G \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use standard algorithms to find the activities that form
\begin{itemize}
\item the longest path(s)
\item the shortest path(s)\\
through the activity network.
\end{itemize}
You must show working to demonstrate the use of the algorithms.
Only one of the paths from part (a) has a practical interpretation.
\item What is the practical interpretation of the total weight of that path?
The duration of activity E can be changed. No other durations change.
\item What is the smallest increase to the duration of E that will make activity E become part of a longest path through the network?
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2019 Q4 [10]}}