Question

Solve the following problem :

A chartered accountant’s firm has accepted five new cases. The estimated number of days required by each of their five employees for each case are given below, where - means that the particular employee cannot be assigned the particular case. Determine the optimal assignment of cases of the employees so that the total number of days required to complete these five cases will be minimum. Also find the minimum number of days.

Employee	Cases
	I	II	III	IV	V
E1	6	4	5	7	8
E2	7	–	8	6	9
E3	8	6	7	9	10
E4	5	7	–	4	6
E5	9	5	3	10	–

Answer 1

Step 1:
Observe that the given problem is a restricted assignment problem. So we assign a very high number of days `oo` to the prohibited cells.

Employee	Cases
	I	II	III	IV	V
E1	6	4	5	7	8
E2	7	`oo`	8	6	9
E3	8	6	7	9	10
E4	5	7	`oo`	4	6
E5	9	5	3	10	`oo`

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

Employee	Cases
	I	II	III	IV	V
E1	2	0	1	3	4
E2	1	`oo`	2	0	3
E3	2	0	1	3	4
E4	1	3	`oo`	0	2
E5	6	2	0	7	`oo`

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

Employee	Cases
	I	II	III	IV	V
E1	1	0	1	3	2
E2	0	`oo`	2	0	1
E3	1	0	1	3	2
E4	0	3	`oo`	0	0
E5	5	2	0	7	`oo`

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.

Employee	Cases
	I	II	III	IV	V
E1	1	0	1	3	2
E2	0	`oo`	2	0	1
E3	1	0	1	3	2
E4	0	3	`oo`	0	0
E5	5	2	0	7	`oo`

Step 5:
From step 4, minimum number of lines covering all the zeros are 4, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 1 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.

Employee	Cases
	I	II	III	IV	V
E1	0	0	0	2	1
E2	0	`oo`	2	0	1
E3	0	0	0	2	1
E4	0	4	`oo`	0	0
E5	5	3	0	7	`oo`

Step 6:
Draw minimum number of vertical and horizontal lines to cover all zeros.

Employee	Cases
	I	II	III	IV	V
E1	0	0	0	2	1
E2	0	`oo`	2	0	1
E3	0	0	0	2	1
E4	0	4	`oo`	0	0
E5	5	3	0	7	`oo`

Step 7:
From step 6, 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:

Employee	Cases
	I	II	III	IV	V
E1	0	0	0	2	1
E2	0	`oo`	2	0	1
E3	0	0	0	2	1
E4	0	4	`oo`	0	0
E5	5	3	0	7	`oo`

                                                    OR

Employee	Cases
	I	II	III	IV	V
E1	0	0	0	2	1
E2	0	`oo`	2	0	1
E3	0	0	0	2	1
E4	0	4	`oo`	0	0
E5	5	3	0	7	`oo`

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

Employee	Cases	Time (days)
E1	I	6
E2	II	6
E3	III	6
E4	IV	6
E5	V	3
Total		27

                                         OR

Employee	Cases	Time (days)
E1	I	4
E2	II	6
E3	III	8
E4	IV	6
E5	V	3
Total		27

∴ Minimum Time = 27 days.