Question

Solve the following problem :

A plant manager has four subordinates, and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. This estimate of the time each man would take to perform each task is given in the effectiveness matrix below.

	I	II	III	IV
A	7	25	26	10
B	12	27	3	25
C	37	18	17	14
D	18	25	23	9

How should the tasks be allocated, one to a man, as to minimize the total man hours?

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:

	I	II	III	IV
A	0	18	19	3
B	9	24	0	22
C	23	4	3	0
D	9	16	14	0

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

	I	II	III	IV
A	0	14	19	3
B	9	20	0	22
C	23	0	3	0
D	9	12	14	0

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.

	I	II	III	IV
A	0	14	19	3
B	9	20	0	22
C	23	0	3	0
D	9	12	14	0

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:
Assigning through zeroes, we get,

	I	II	III	IV
A	0	14	19	3
B	9	20	0	22
C	23	0	3	0
D	9	12	1	0

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

Job	Subordination	Time (hrs)
A	I	7
B	III	3
C	II	18
D	IV	9

∴ Total minimum time = 7 + 3 + 18 + 9 = 37 hrs.