- Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.
Each worker can only be assigned to at most one task, and each task must be done by at most one worker.
Worker B cannot be assigned to task Q and worker E cannot be assigned to task S.
The time, in minutes, that each worker takes to complete each task is shown in the table below.
| P | Q | R | S |
| A | 38 | 39 | 37 | 37 |
| B | 39 | - | 39 | 40 |
| C | 41 | 44 | 40 | 42 |
| D | 40 | 41 | 39 | 38 |
| E | 36 | 39 | 41 | - |
The Hungarian algorithm is to be used to find the least total time to complete all four tasks.
- Explain how the table should be modified so that the Hungarian algorithm can be applied.
- Use the Hungarian algorithm to obtain an allocation that minimises the total time.
- Explain how you determined if the table was optimal at each stage.
- Calculate the least total time to complete all four tasks.