Even though the assignment algorithm is primarily a minimization model, it can be suitably modified and used for maximization models also; whenever the objective of the firm / decision maker is to maximize the return of the allocation, you have to modify the problem in the initial table and use the same Hungarian Algorithm to solve. We will solve one example here.
Variations in Assignment
Problem- Case 1: Maximization Models
Even though the assignment algorithm is primarily a minimization model,
it can be suitably modified and used for maximization models also; whenever the
objective of the firm / decision maker is to maximize the return of the
allocation, you have to modify the problem in the initial table and use the
same Hungarian Algorithm to solve. We will solve one example here.
Example-1
The student internship
director needs as much coverage as possible in the office next week. The more
hours that can be put in each day, the better. She has asked the students to
provide a list of how many hours they are available each day of the week. Each
student can be there on only one day and there must be a student in the office
each day of the week. Use the table below and the tables provided to determine
the schedule that gives the most
coverage. [Note that the objective of
this problem is to maximize the hours
worked, not minimize].As you know, the Hungarian Algorithm is primarily
developed to handle minimization models; we need to modify the given problem as
an ‘equivalent’ minimization model. We will convert the given problem as a
minimization model in the following steps. 1. You have
to identify the largest number in the entire matrix / table – [which is 8] 2. Subtract all the entries from this highest number-8 and write down the new
reduced table. 3. This
reduced table is in the form of ‘opportunity time’ of not allocating a day to a
student; thus, the aim of the problem, which is in the new-reduced format,
after subtracting all the entries from the highest, can be viewed as a minimization
model.
4. Then the
Hungarian method is applied, which is given in the following steps. 1. Convert to a minimization problem by subtracting each
value from 8
4.
Now
conduct the line test: draw minimum number of straight lines to cover all the
zeros 1. The first
line is drawn at Row-4, which is having maximum number zeros (3 zeros are there
in the row)
2. The
second line is drawn at Row-5, which is having maximum number zeros after
removing Row-4 from further consideration (2 zeros are there in the row)
3. Now the
third line is drawn at Column-3, which is having maximum number zeros after
removing Row-3, Row-4 from further consideration (2 zeros are there in the
column)
The last
line is drawn at Row-3 / Column-2; you may draw the line in any manner; here,
we consider the Row-3
Since, the number of straight lines=4, which is
less than the number of row=5, it is an indication of sufficient number of
zeros are not available in the last table to do the optimum allocation. Thus,
we do the following steps, in the last table obtained. 1. Subtract
the smallest uncovered number, which is here, 2 in the above table, [not
covered by any straight lines] from every uncovered number in the table.
2. We have
to add this two to the numbers at intersections of covering lines; and should
not make any changes for those numbers which are covered by straight lines but
not crossed out by lines.
3. By doing
so, we get the following table.
We now
proceed to make optimum allocation with available zero entries; in the new
matrix, jot down all the zeros in their respective positions. 1. The first
unique zero is found in Row-3 and it is marked; then the column-2 is strike
out;
2. The next
unique zero is found in row-5 and marked; column-1 is removed
3. Since,
there is no unique zero in any row or any column, you may randomly assign any
zero as allocation; we allocate randomly Row-1 to Column-5. The Row-1 to
Column-5 is removed from further considerations
4. Again
doing, row search, unique zeros are found in Row-2 and Row-4 and marked. Thus,
optimum allocation is arrived. Third
unique zero was found again in the row search at row-1; fourth unique zero was
found at row-3 and finally the last unique zero was found in row-4.
Thus, the
optimum allocation is made by taking the times from original table.
While selecting third allocation, there was no
unique zero, we randomly broken the tie; so there is a possibility of more than
one solution. If you choose some other zero, you may get different allocation, but the
total hours will be the same as 31. You may try and check the answers, which is
given below. Tags : Operations Management - Transportation / Assignment & Inventory Management
Last 30 days 2097 views