Assignment Problem

Example 2

The Winner Publishing Company employs typists on hourly basis. There are five typists for service and their charges and speeds are different. According to an earlier understanding only one job is given to one typist and the typist is paid for full hour even if he works for a fraction of an hour. Find the least cost allocation for the following data:

Solution.

The following matrix gives the cost incurred if the ith typist (i = A, B, C, D & E) executes the jth job (j = P, Q, R, S & T):

Identify the minimum element in each row and subtract it from every element of that row.

Table

Identify the minimum element in each column and subtract it from every element of that column.

Table

Make the assignments for the reduced matrix

Table

Job
Typist	P	Q	R	S	T
A	2	2		4
B	6	4		10	2
C		1		1	2
D	2	4		4	2
E	2				2

Table

Repeating the usual process as explained in the previous example, we get the following matrix:

Table

Job
Typist	P	Q	R	S	T
A	2	2	2	4
B	4	2		8
C		1	2	1	2
D		2		2
E	2		2		2

The number of assigned cells is not equal to the number of rows (and columns). Therefore, we draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix

Table

Final Table

Job
Typist	P	Q	R	S	T
A	2	1	2	3
B	4	1		7
C			2		2
D		1		1
E	3		3		3

Since the number of assignments is equal to the number of rows (& columns), this is the optimal solution.

Substituting the values from original table:
75 + 66 + 114 + 80 + 64 = Rs. 399.