Question

A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the time each man would take to perform each task is given below:

		Tasks
		1	2	3	4
Subordinates	P	8	26	17	11
	Q	13	28	4	26
	R	38	19	18	15
	S	9	26	24	10

How should the tasks be allocated to subordinates so as to minimize the total manhours?

Answer 1

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced.

Step 1: Select the smallest element in each row and subtract this from all the elements in its row.

		Tasks
		1	2	3	4
Subordinates	P	0	18	9	3
	Q	9	24	0	22
	R	23	4	3	0
	S	0	17	15	1

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
	S	0	13	15	1

Step 3: (Assignment)
Examine the rows with exactly one zero Mark the zero by □. Mark other zeros in its row by X.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
	S	0	13	15	1

Step 4: Now examine the columns with exactly one zero. Mark the zero by □. Mark other zeros in its row by X.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
	S	0	13	15	1

Step 5: Cover all the zeros of table 4 with three lines, since three assignments were made check (✓) row S since it has no assignment.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
✓	S	0	13	15	1

Step 6: Develop the new revised tableau. Examine those elements that are not covered by a line in table 5.

Take the smallest element.

This is 1 (one) our case.

By subtracting 1 from the uncovered cells.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	10	20	0	22
	R	24	0	3	0
	S	0	12	14	0

[Adding 1 to elements (Q, S, R) that line at the intersection of two lines]

Step 7: Go to step 3 and repeat the procedure until you arrive at an optimal assignment.

Step 8: Determine an assignment.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	10	20	0	22
	R	24	0	3	0
	S	0	12	14	0

Thus all the four assignment have been made.

The optimal assignment schedule and total time is

Subordinates	Tasks	Time
P	1	8
Q	3	4
R	2	19
S	4	10
Total		41

The optimum time (minimum) = 41 Hrs.