Allocation problems

Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.

Each worker can 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 R.

The time, in minutes, that each worker takes to complete each task is shown in the table below.

The Hungarian algorithm is to be used to find an allocation that minimises the 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.

Calculate the least total time to complete all four tasks.

Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each task must be assigned to just one worker and each worker must do only one task.

The cost of assigning each worker to each task is shown in the table below.

The total cost is to be minimised.

Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total cost. You must make your method clear and show the table after each stage.

State the minimum total cost.

Four workers, A, B, C and D, are to be assigned to three tasks, 1, 2 and 3. Each task must be assigned to just one worker and each worker can do one task only.

Worker A cannot do task 2 and worker D cannot do task 3

The cost of assigning each worker to each task is shown in the table below.

The total cost is to be minimised.

Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to exactly one task and each task must be done by exactly one worker.

Worker A cannot do task 3 and worker B cannot do task 4

The table below shows the profit, in pounds, that each worker would earn if assigned to each of the tasks.

Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.

Determine the resulting total profit.

Four workers, Ted (T), Harold (H), James (J) and Margaret (M), are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.

Determine the resulting total profit.