Five men are available to do five different jobs. The time taken by them is shown in the following matrix. Find the assignment of the men to jobs to minimize the total time taken.

MEN	-	-	JOBS	-	-
-	I	II	III	IV	V
A	2	9	2	7	1
B	6	8	7	6	1
C	4	6	5	3	1
D	4	2	7	3	1
E	5	3	9	5	1

997views

written 7.8 years ago by

Consider the matrix of numbers:

2	9	2	7	1
6	8	7	6	1
4	6	5	3	1
4	2	7	3	1
5	3	9	3	1

Column reduction (directly as a shortcut, instead of row reduction first, since all value in the fifth column are ‘1’): subtracting the minimum number in each column, from all the other numbers in that column:

enter image description here

Allocations can be made as shown above. However, each row and column does not have an allocation. So drawing minimum number of lines through the zeros:

enter image description here

Number of lines = 4, while order of the matrix = 5. So solution is not optimal.

From all uncovered elements, we take the minimum of these elements (here 2) and subtract it from all the uncovered elements, while we add it to the elements where two lines intersect:

enter image description here

Allocations can be made as shown above.

Making the same allocations is the main matrix:

enter image description here

So minimum total time taken: 4 + 2 + 2 + 3 + 1 = 12

NOTE: To make allocations, follow this rule:

Starting from the 1st row, make an allocation to a 0, if it is the only zero present in that row.
- After making an allocation in a row, cancel the other 0s in the column where the allocation was made (since only one allocation per row and column is allowed). Make sure to do this before you move to the next row.
- When you move to the next row, do not allocate a 0 that has been cancelled in the previous step.
- In case there are more than one 0s in any row, do not make any allocation, & go to the next row.
- Continue till you reach the last row.
After considering rows, now consider columns. Starting from the 1st column, make an allocation to a 0, if it is the only zero present in that column, and it is not cancelled.
- After making an allocation in a column, cancel the other 0s in the rowwhere the allocation was made (since only one allocation per row and column is allowed). Make sure to do this before you move to the next column.
- When you move to the next column, do not allocate a 0 that has been cancelled in the previous step.
- In case there are more than one 0s in any column, do not make any allocation, & go to the next column.
- Continue till you reach the last column.
Repeat steps 1 & 2 in sequence till it is not possible to make any more allocations.

ADD COMMENT EDIT