Question

A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R and S. The processing cost of each job for each machine is given in the following table:

Jobs	Machines (Processing Cost in ₹)
	P	Q	R	S
A	31	25	33	29
B	25	24	23	21
C	19	21	23	24
D	38	36	34	40

Find the optimal assignment to minimize the total processing cost.

Answer 1

Step 1: Row minimum
Subtract the smallest element in each row from every element in its row. The matrix obtained is given below:

Jobs	Machines (Processing Cost in ₹)
	P	Q	R	S
A	6	0	8	4
B	4	3	2	0
C	0	2	4	5
D	4	2	0	6

Step 2: Column minimum
Subtract the smallest element in each column of assignment matrix obtained in step 1 from every element in its column.

Jobs	Machine (Processing Cost in ₹)
	P	Q	R	S
A	6	0	8	4
B	4	3	2	0
C	0	2	4	5
D	4	2	0	6

Step 3:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.

Jons	Machines (Processing Cost in ₹)
	P	Q	R	S
A	6	0	8	4
B	4	3	2	0
C	0	2	4	5
D	4	2	0	6

Step 4:
From step 3, minimum number of lines covering all the zeros are 4, which is equal to order of the matrix, i.e., 4
∴ 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:

Jobs	Machines (Processing Cost in ₹)
	P	Q	R	S
A	6	0	8	4
B	4	3	2	0
C	0	2	4	5
D	4	2	0	6

Step 5:
The matrix obtained in step 4 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:

Jobs	Machines	Processing cost (₹)
A	Q	25
B	S	21
C	P	19
D	R	34

∴ Total minimum processing cost = 25 + 21 + 19 + 34 = ₹ 99.