Question

In the modification of a plant layout of a factory four new machines M₁, M₂, M₃ and M₄ 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 M₂ cannot be placed at C and M₃ cannot be placed at A. The cost of locating a machine at a place (in hundred rupees) is as follows.

Machines	Location
	A	B	C	D	E
M1	9	11	15	10	11
M2	12	9	–	10	9
M3	–	11	14	11	7
M4	14	8	12	7	8

Find the optimal assignment schedule.

Answer 1

Here, number of rows and columns are not equal.

∴ The problem is unbalanced.

∴ It is balanced by introducing dummy job machine M₅ with zero cost.

Also, M₂ cannot be placed at C and M₃ cannot be placed at A.

Let a very high cost (`oo`) be assigned to corresponding elements.

∴ Matrix obtained is as follows:

Machines	Location
	A	B	C	D	E
M1	9	11	15	10	11
M2	12	9	`oo`	10	9
M3	`oo`	11	14	11	7
M4	14	8	12	7	8
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	Location
	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 minimu

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	Location
	A	B	C	D	E
M1	`cancel(0)`	`cancel(2)`	`cancel(6)`	`cancel(1)`	`cancel(2)`
M2	`cancel(3)`	`cancel(0)`	`cancel(oo)`	`cancel(1)`	`cancel(0)`
M3	`oo`	4	7	4	`cancel(0)`
M4	`cancel(7)`	`cancel(1)`	`cancel(5)`	`cancel(0)`	`cancel(1)`
M5	`cancel(0)`	`cancel(0)`	`cancel(0)`	`cancel(0)`	`cancel(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	Location
	A	B	C	D	E
M1	0	2	6	1	2
M2	3	0	`oo`	1	`cancel(0)`
M3	`oo`	4	7	4	0
M4	7	1	5	0	1
M5	`cancel(0)`	`cancel(0)`	0	`cancel(0)`	`cancel(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	Location	Cost (in hundred rupees)
M1	A	9
M2	B	9
M3	E	7
M4	D	7
M5	C	0

The total minimum cost (in hundred rupees) = 9 + 9 + 7 + 7 + 0 = 32.