Question

Consider a small machine shop where each worker can operate all the machines but operates some of the machines better than others. On any given day there are a number of jobs which have to be completed. For this situation, the problem facing management, is how to obtain the fastest turnaround time for all jobs.

The time it takes to perform an average job for each of these workers is as follows:

	Drilling	Grinding	Lathework
Joe	5	10	6
Jack	9	13	14
John	15	11	9

Write the appropriate formulation for this as an assignment problem to determine which worker should be assigned to which machine to minimize total time for the jobs.

Answer 1

This is the original cost matrix:

5	10	6
9	13	14
15	11	9

Subtract row minima

We subtract the row minimum from each row:

0	5	1
0	4	5
6	2	0

Subtract column minima

We subtract the column minimum from each column:

0	3	1
0	2	5
6	0	0

Cover all zeros with a minimum number of line

There are 2 lines required to cover all zeros:

15 0 320 006X

Create additional zeros

The number of lines is smaller than 3. The smallest uncovered number is 1. We subtract this number from all uncovered elements and add it to all elements that are covered twice:

0	2	0
0	1	4
7	0	0

Cover all zeros with a minimum number of lines

There are 3 lines required to cover all zeros:

040 3 0

The optimal assignment

Because there are 3 lines required, the zeros cover an optimal assignment:

0 4 0 0 0 This corresponds to the following optimal assignment in the original cost matrix: 5 10 9 6 13 14 15 11 9 The optimal value equals 26

The Optimum Assignment is Jack ->Drilling ; John -> Grinding ;  Joe ->Lathework