Question

A department store has four workers to pack goods. The times (in minutes) required for each worker to complete the packings per item sold is given below. How should the manager of the store assign the jobs to the workers, so as to minimize the total time of packing?

Workers	Packing of
	Books	Toys	Crockery	Cutlery
A	3	11	10	8
B	13	2	12	12
C	3	4	6	1
D	4	15	4	9

Answer 1

Step 1: Subtract the smallest element of each row from the every element of that row.

Packing	Books	Toys	Crockery	Cutlery
Workers
A	0	8	7	5
B	11	0	10	0
C	2	3	5	0
D	0	11	0	5

Step 2: Since each column contains minimum element 0, subtracting it from every element of each column will given the same table as above.

Step 3: Drawing horizontal and vertical lines to cover all zeros.

Packing	Books	Toys	Crockery	Cutlery
Workers
A	0	0	7	5
B	11	0	10	0
C	2	3	5	0
D	0	11	0	5

Step 4: Number of horizontal lines (4) = order of matrix (4), optimal solution has reached.

Assigning through zeroes, we get

Packing	Books	Toys	Crockery	Cutlery
Workers
A	`bb(0)`	8	7	5
B	11	`bb(0)`	10	`bb(cancel(0))`
C	2	3	5	`bb(0)`
D	`bb(cancel(0))`	11	`bb(0)`	5

∴ Optimal Assignment schedule: A → Books

B → Bays, C → Cutlery, D → Crockery

Total minimum Time = 3 + 2 + 4 + 1 = 10 min