Page 331 -

ASSIGNMENT PROBLEM: A SPECIAL-PURPOSE SOLUTION PROCEDURE 311

optimal assignment – in this case, 15 for Terry to client 2, 5 for Karl to client 3
and 6 for Mustafa to client 1. So, we obtain the solution time of
15 + 5 + 6 ¼ 26 days.

Finding the Minimum Number of Lines
Sometimes it is not obvious how the lines should be drawn through rows and
columns of the matrix in order to cover all the zeros with the smallest number of
lines. In these cases, the following heuristic works well. Choose any row or column
with a single zero. If it is a row, draw a line through the column the zero is in; if it is a
column, draw a line through the row the zero is in. Continue in this fashion until you
cover all the zeros.
Can you solve an If you make the mistake of drawing too many lines to cover the zeros in the
assignment problem reduced matrix and thus conclude incorrectly that you have reached an optimal
using the Hungarian
method? Try Problem 19. solution, you will be unable to identify a zero-value assignment. So, if you think you
have reached the optimal solution, but cannot find a set of zero-value assignments,
go back to the preceding step and check to see whether you can cover all the zeros
with fewer lines.

Problem Variations
We now discuss how to handle the following problem variations with the Hungarian
method:
1 number of people not equal to number of tasks;
2 maximization objective function;
3 unacceptable assignments.

Number of People Not Equal to Number of Tasks The Hungarian method
requires that the number of rows (people) equal the number of columns (tasks).
Suppose that in the Fowle problem four project leaders had been available for
assignment to the three new clients (tasks). Fowle still faces the same basic
problem, namely, which project leaders should be assigned to which clients to
minimize the total days required. Table 7.25 shows the project completion time
estimates with a fourth project leader.
We know how to apply the Hungarian method when the number of rows and the
number of columns are equal. We can apply the same procedure if we can add a new
client. If we do not have another client, we simply add a dummy column, or a dummy
client. This dummy client is nonexistent, so the project leader assigned to the
dummy client in the optimal assignment solution, in effect, will be the unassigned
project leader.

Table 7.25 Estimated Project Completion Time (Days) for the Fowle Assignment
Problem with Four Project Leaders
Client

Project Leader 1 2 3
Terry 10 15 9
Karl 9 18 5
Mustafa 6 14 3
Helen 8 16 6

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.