| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2002 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm with a small 4×4 matrix. The question explicitly tells students which method to use and even specifies to reduce rows first. It requires only mechanical execution of a standard algorithm with no problem-solving insight or decision-making about approach. The arithmetic is simple and the matrix size is minimal for this topic. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | Job 1 | Job 2 | Job 3 | Job 4 |
| Machine 1 | 14 | 5 | 8 | 7 |
| Machine 2 | 2 | 12 | 6 | 5 |
| Machine 3 | 7 | 8 | 3 | 9 |
| Machine 4 | 2 | 4 | 6 | 10 |
5. An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & Job 1 & Job 2 & Job 3 & Job 4 \\
\hline
Machine 1 & 14 & 5 & 8 & 7 \\
\hline
Machine 2 & 2 & 12 & 6 & 5 \\
\hline
Machine 3 & 7 & 8 & 3 & 9 \\
\hline
Machine 4 & 2 & 4 & 6 & 10 \\
\hline
\end{tabular}
\end{center}
Use the Hungarian algorithm, reducing rows first, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time.\\
\hfill \mbox{\textit{Edexcel D2 2002 Q5 [11]}}