Question 16.1: Using the Assignment Method to Make Job Assignments Determin...
Using the Assignment Method to Make Job Assignments
Determine the optimum assignment of jobs to workers for the following data (from Table 16.1):
TABLE 16.1 A typical assignment problem showing job times for each job/ worker combination
| WORKER | |||||
| A | B | C | D | ||
| Job | 1 | 8 | 6 | 2 | 4 |
| 2 | 6 | 7 | 11 | 10 | |
| 3 | 3 | 5 | 7 | 6 | |
| 4 | 5 | 10 | 12 | 9 | |
| WORKER | ||||||
| A | B | C | D | Row Minimum |
||
| Job | 1 | 8 | 6 | 2 | 4 | 2 |
| 2 | 6 | 7 | 11 | 10 | 6 | |
| 3 | 3 | 5 | 7 | 6 | 3 | |
| 4 | 5 | 10 | 12 | 9 | 5 | |
a. Subtract the smallest number in each row from every number in the row, and enter the results in a new table. The result of this row reduction is:
| WORKER | |||||
| A | B | C | D | ||
| Job | 1 | 6 | 4 | 0 | 2 |
| 2 | 0 | 1 | 5 | 4 | |
| 3 | 0 | 2 | 4 | 3 | |
| 4 | 0 | 5 | 7 | 4 | |
| Column Minimum | 0 | 1 | 0 | 2 | |
b. Subtract the smallest number in each column from every number in the column, and enter the results in a new table. The result of this column reduction is:
| WORKER | |||||
| A | B | C | D | ||
| Job | 1 | 6 | 3 | 0 | 0 |
| 2 | 0 | 0 | 5 | 2 | |
| 3 | 0 | 1 | 4 | 1 | |
| 4 | 0 | 4 | 7 | 2 | |
c. Determine the minimum number of lines needed to cross out all zeros. (Try to cross out as many zeros as possible when drawing lines.)
d. Since only three lines are needed to cross out all zeros and the table has four rows, this is not the optimum. Note that the smallest uncovered value is 1.
e. Subtract the smallest uncovered value from every uncovered number that hasn’t been crossed out, and add it to numbers that are at the intersections of covering lines. The results are as follows:
| WORKER | |||||
| A | B | C | D | ||
| Job | 1 | 7 | 3 | 0 | 0 |
| 2 | 1 | 0 | 5 | 2 | |
| 3 | 0 | 0 | 3 | 0 | |
| 4 | 0 | 3 | 6 | 1 | |
f. Determine the minimum number of lines needed to cross out all zeros (four). Since this equals the number of rows, you can make the optimum assignment.
g. Make assignments: Start with rows and columns with only one zero. Match jobs with machines that have a zero cost.
| WORKER | |||||
| A | B | C | D | ||
| Job | 1 | 7 | 3 | 0 | 0 |
| 2 | 1 | 0 | 5 | 2 | |
| 3 | 0 | 0 | 3 | 0 | |
| 4 | 0 | 3 | 6 | 1 | |
| Assignment | Cost |
| 1-C | $ 2 |
| 2-B | 7 |
| 3-D | 6 |
| 4-A | \frac{5}{20} |
The assignment problem can also be solved using an Excel template, as seen in Table 16.2. The ones in the solution matrix denote assignments (i.e., assign C to job 1), and the zeros denote no assignment for a worker/machine and job combination.
