Four new machines M1, M2, M3 and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be placed at A. The cost matrix is given below.
Machines | Places | ||||
A | B | C | D | E | |
M1 | 4 | 6 | 10 | 5 | 6 |
M2 | 7 | 4 | – | 5 | 4 |
M3 | – | 6 | 9 | 6 | 2 |
M4 | 9 | 3 | 7 | 2 | 3 |
Find the optimal assignment schedule.
Solution
Step 1:
Here, number of rows and columns are not equal.
∴ The problem is unbalanced.
∴ It is balanced by introducing dummy machine M5 with zero cost.
Also, M2 cannot be placed at C and M3 cannot be placed at A.
Let a very high cost (`oo`) be assigned to corresponding elements.
∴ Matrix obtained is as follows:
Machines | Places | ||||
A | B | C | D | E | |
M1 | 4 | 6 | 10 | 5 | 6 |
M2 | 7 | 4 | `oo` | 5 | 4 |
M3 | `oo` | 6 | 9 | 6 | 2 |
M4 | 9 | 3 | 7 | 2 | 3 |
M5 | 0 | 0 | 0 | 0 | 0 |
Step 2:
Row minimum Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:
Machines | Places | ||||
A | B | C | D | E | |
M1 | 0 | 2 | 6 | 1 | 2 |
M2 | 3 | 0 | `oo` | 1 | 0 |
M3 | `oo` | 4 | 7 | 4 | 0 |
M4 | 7 | 1 | 5 | 0 | 1 |
M5 | 0 | 0 | 0 | 0 | 0 |
Step 3:
Column minimum
Here, each column contains element zero.
∴ Matrix obtained by column minimum is same as above matrix.
Step 4:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.
Machines | Places | ||||
A | B | C | D | E | |
M1 | 0 | 2 | 6 | 1 | 2 |
M2 | 3 | 0 | `oo` | 1 | 0 |
M3 | `oo` | 4 | 7 | 4 | 0 |
M4 | 7 | 1 | 5 | 0 | 1 |
M5 | 0 | 0 | 0 | 0 | 0 |
Step 5:
From step 4, minimum number of lines covering all the zeros are 5, which is equal to order of the matrix, i.e., 5.
∴ Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:
Machines | Places | ||||
A | B | C | D | E | |
M1 | 0 | 2 | 6 | 1 | 2 |
M2 | 3 | 0 | `oo` | 1 | 0 |
M3 | `oo` | 4 | 7 | 4 | 0 |
M4 | 7 | 1 | 5 | 0 | 1 |
M5 | 0 | 0 | 0 | 0 | 0 |
Step 6:
The matrix obtained in step 5 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:
Machines | Place | Cost |
M1 | A | 4 |
M2 | B | 4 |
4M3 | E | 2 |
M4 | D | 2 |
M5 | C | 0 |
∴ The total minimum cost = 4 + 4 + 2 + 2 + 0 = ₹ 12.