ASSIGNMENT METHOD. First Printing wants to find the minimum total cost assignment of 3 jobs to 3 typesetters.
APPROACH \blacktriangleright The cost table shown earlier in this section is repeated here, and steps 1 through 4 are applied.
| JOB | TYPESETTER | ||
| A | B | C | |
| R-34 | $11 | $14 | $ 6 |
| S-66 | $ 8 | $10 | $11 |
| T-50 | $ 9 | $12 | $ 7 |
SOLUTION \blacktriangleright
Step 1A: Using the previous table, subtract the smallest number in each row from every number in the row. The result is shown in the table on the left.
| JOB | TYPESETTER | ||
| A | B | C | |
| R-34 | 5 | 8 | 0 |
| S-66 | 0 | 2 | 3 |
| T-50 | 2 | 5 | 0 |
| JOB | TYPESETTER | ||
| A | B | C | |
| R-34 | 5 | 6 | 0 |
| S-66 | 0 | 0 | 3 |
| T-50 | 2 | 3 | 0 |
Step 1B: Using the above left table, subtract the smallest number in each column from every number in the column. The result is shown in the table on the right.
Step 2: Draw the minimum number of vertical and horizontal straight lines needed to cover all zeros. Because two lines suffice, the solution is not optimal. See Figure 15.EX.4a.
Step 3: Subtract the smallest uncovered number (2 in this table) from every other uncovered number and add it to numbers at the intersection of two lines.
| JOB | TYPESETTER | ||
| A | B | C | |
| R-34 | 3 | 4 | 0 |
| S-66 | 0 | 0 | 5 |
| T-50 | 0 | 1 | 0 |
Return to step 2. Cover the zeros with straight lines again. See Figure 15.EX.4b
Because three lines are necessary, an optimal assignment can be made (see Step 4). Assign R-34 to person C, S-66 to person B, and T-50 to person A. Referring to the original cost table, we see that:
Minimum cost = $6 + $10 + $9 = $25
INSIGHT \blacktriangleright If we had assigned S-66 to typesetter A, we could not assign T-50 to a zero location.
LEARNING EXERCISE \blacktriangleright If it costs $10 for Typesetter C to complete Job R-34 (instead of $6), how does the solution change? [Answer: R-34 to A, S-66 to B, T-50 to C; cost = $28.]
RELATED PROBLEMS \blacktriangleright 15.3–15.9 (15.11–15.14 are available in MyOMLab)
EXCEL OM Data File Ch15Ex4.xls can be found in MyOMLab.
