Solve the following minimal assignment problem and hence find minimum time where $^{'} -^{'}$ indicates that job cannot be assigned to the machine:
Machines Processing time in hours
$A$ $B$ $C$ $D$ $E$
$M_{1}$ $9$ $11$ $15$ $10$ $11$
$M_{2}$ $12$ $9$ - $10$ $9$
$M_{3}$ - $11$ $14$ $11$ $7$
$M_{4}$ $14$ $8$ $12$ $7$ $8$

Open in App

Solution

Add dummy row ( $M_{5}$ )
A B C D E
$M_{1}$ 9 11 15 10 11
$M_{2}$ 12 9 - 10 9
$M_{3}$ - 11 14 11 7
$M_{4}$ 14 8 12 7 8
$M_{5}$ 0 0 0 0 0
Now apply row reduction
A B C D E
$M_{1}$ 0 2 6 1 2
$M_{2}$ 3 0 - 1 0
$M_{3}$ - 4 7 4 0
$M_{4}$ 7 1 5 0 1
$M_{5}$ 0 0 0 0 0
Number of crosed(bold rows and columns) line $= 4$
order of matrix $= 5$
$4 < 5$ (not optimal solution)
Now Modify matrix by subtracting minimum uncrossed(unbolded ) element from uncrossed element (unbolded ) element and adding same at T-point(element lying at junction of bolded rows and columns )
Modified element
A B C D E
$M_{1}$ 0 1 5 1 2
$M_{2}$ 4 0 - 2 1
$M_{3}$ - 3 6 4 0
$M_{4}$ 7 0 4 0 1
$M_{5}$ 1 0 0 1 0
Number of crossed line(bolded rows and column) $= 5$
order of matrix $= 5$
$55$ (optimal solution)
assignment
$M_{1} \to A$
$M_{2} \to B$
$M_{3} \to E$
$M_{4} \to D$
$M_{5} \to C$ ( $C$ cannot be ssigned to any one)
Optical solution $= 9 + 9 + 7 + 7 = 32$

Suggest Corrections