Assignment Problem Using Hungarian Method

Download as pdf or txt
Download as pdf or txt
You are on page 1of 5

Assignment Problem Using Hungarian Method

Assignment Problem – assigns one agent to only one task to optimize a stated objective. It is a special case of
transportation problem.

Example: Fowle Marketing Research has three available project leaders and three new clients and needs to
minimize the total number of days required to complete all three projects.

Agents – 3 Project leaders: Terry, Carle, McClymonds

Tasks – Clients 1, 2, and 3

Objective - to minimize the total number of days required to complete all three projects

Given: The estimated project completion times in days are summarized in Table 6.3.

1 2 3
Terry 10 15 9
Carle 9 18 5
McClymonds 6 14 3
Table 6.3 Estimated project completion times in days

• A BALANCE ASSIGNMENT PROBLEM


1. First check whether the number of rows is equal to the number of columns, if it is so, the assignment
problem is said to be balanced.
2. Then proceed to step 1. If it is not balanced, then it should be balanced before applying the
algorithm.
3. We have in here 3 rows/agents = 3 columns/tasks then it is a balanced assignment.
• Step 1: ROW REDUCTION
Subtract the smallest value or element of each row from all the elements in the row of the given table.
See that each row contains at least one zero.
1. Based on the given table above, in the first row, we have 9 as the smallest value then we are
going to subtract this element from the other elements in its row which are 10, 15, and including
9.
2. 10 – 9 = 1; 15 – 9 = 5; 9 – 9 = 0. Apply this to the other rows. Below is the computed table after
doing this step.

1 2 3
Terry 1 6 0
Carle 4 13 0
McClymonds 3 11 0
2nd Table
• Step 2: COLUMN REDUCTION
Subtract the smallest value or element of each column from all the elements in the column of the
resulting table obtained by step 1 and make sure each column contains at least one zero.
1. Now we will base on the second table that we have computed. We can see in the first column that
the smallest value is 1, then we are going to subtract this element from the other elements in its
column which are 4, 3, and including 1.
2. 4 – 1 = 3; 3 – 1 = 2; and 1 – 1 = 0. Apply this to other columns. Below is the computed table
after doing this step.

1 2 3
Terry 0 0 0
Carle 3 7 0
McClymonds 2 5 0
3rd Table.1
• Step 3: ASSIGNING ZEROS
1. ROW SCANNING
• Using the 3rd table, examine the rows and box only one zero. If you see two or more zeros, skip it
and proceed to the next row.
• If you found only one zero, then box that zero, and since we are doing row scanning, we will cross
out other values vertically or the column of the boxed zero.
• The crossed-out values will not be considered for future assignments. Continue in this way until
all the rows have been examined.
▪ In the 3rd table.1, we have to skip the first row because it has three zeros. In the second row,
we can see that it has only one zero, hence, we boxed it and crossed out the values in that
column. In the third row, you can see that there is no zero available because it has been
crossed out already.

1 2 3
Terry 0 0 0
Carle 3 7 0
McClymonds 2 5 0
3rd Table.2

2. COLUMN SCANNING
• Using the 3rd table, examine the columns and box only one zero. If you see two or more zeros, skip
it to the next column.
• If you found only one zero, then box that zero, and since we are doing column scanning, we will
cross out other values horizontally or the row of the boxed zero.
• The crossed-out values will not be considered for future assignments. Continue in this way until
all the rows have been examined.
▪ After row scanning, we will begin the column scanning in the first column. It can be seen
that there is only one zero in the column. We boxed one zero and crossed out the values
horizontally or the values in the row.
▪ Note: that we crossed out values in the opposite way we scan. If we scan and box a zero in
a row, then we cross out values in that column and vice versa.
▪ In the second column, there is only one zero, but we cannot consider the value of it because
it has been crossed out already.

1 2 3
Terry 0 0 0
Carle 3 7 0
McClymonds 2 5 0
3rd Table.3
• Step 4: OPTIMAL TEST
• If each row and each column contain exactly one encircled zero, then the current assignment is
optimal.
• If at least one row or column is without an assignment (i.e. if there is at least one row or column
without one encircled zero), then the current assignment is not optimal.
• If it is not optimal then go to step 5, to make each row and column have one zero.
▪ It can be seen in the 3rd Table.3 that there are only 2 zeros boxed. Row 1 and column 1 has
a zero; row 2 and column 3 has a zero; but row 3 and column 2 has a missing zero. We
must have three zeros.
▪ 2 zeros are not equal to 3 zeros. Hence, we go to step 5.
• Step 5: DETERMINE THE SMALLEST VALUE UNCROSSED IN THE TABLE.
• Create another table or matrix.

1 2 3
Terry
Carle
McClymonds
• Find or determine the smallest value not covered by the straight lines.
• Add this smallest value to the value under the intersection point of the straight lines.
• Subtract this smallest value from all the uncovered elements.
• Copy the rest of the values that have been crossed out or covered by the straight lines.
▪ Base from the 3rd Table.3, the smallest number not covered by the straight lines is 2.

1 2 3
Terry 0 0 0
Carle 3 7 0
McClymonds 2 5 0
▪ Add 2 to the value under the intersection point of the straight lines which is 0. 2+0=2.

1 2 3 Intersection point value

Terry 0 0 0
Carle 3 7 0
McClymonds 2 5 0
▪ Subtract 2 to the uncrossed out values that are not covered by the straight lines.

1 2 3 Intersection point value

Terry 0 0 0
Uncrossed out value
Carle 3 7 0
McClymonds 2 5 0
▪ 3 – 2 = 1; 7 – 2 = 5; 5 – 2 = 3; and 2 – 2 = 0.
▪ After that, just copy the numbers that have been crossed out.
▪ The 4th table will look like this:

1 2 3
Terry 0 0 2
Carle 1 5 0
McClymonds 0 3 0
4th Table
• Step 6: REPEAT STEPS 3 and 4.
• Row scanning, Column Scanning, then Optimized Test.
▪ Using the 4th Table, we assign zeros by scanning first by row. The table will look like
this:

1 2 3
Terry 0 0 2
Carle 1 5 0
McClymonds 0 3 0
4th Table.1
▪ After row scanning, we assign zeros again by column scanning. The same 4th table will
look like this:

1 2 3
Terry 0 0 2
Carle 1 5 0
McClymonds 0 3 0
4th Table.2
▪ Next is to optimize and test the table. We need to find three zeros, and as we can see we
have already assigned at least one zero for each row and column.
▪ 3 = 3. It is now optimized.
• Step 7: OPTIMAL SOLUTION
• In the 4th Table.2, each boxed zero determines the client assigned to each of the project leaders. It
is determined as:
▪ Project leader 1 named Terry is assigned to client 2.
▪ Project leader 2 named Carle is assigned to client 3.
▪ Project leader 3 named McClymonds is assigned to client 1.
• Go back to the given table at the beginning. Align the boxed zeros to the given completion
timetable to determine the estimated completion time in days in each client. It is determined as:

1 2 3
Terry 10 15 9
Carle 9 18 5
McClymonds 6 14 3

▪ Project leader 1 named Terry is assigned to client 2 estimated to complete in 15 days.


▪ Project leader 2 named Carle is assigned to client 3 estimated to complete in 5 days.
▪ Project leader 3 named McClymonds is assigned to client 1estimated to complete in 6
days.
• Add the estimated completion days: 15, 5, and 6 to get the optimal value or the minimum total
number of days required to complete all three projects.
• The Optimal Solution is written as follows:
Project Leader Client Days
Terry 1 15
Carle 2 5
McClymonds 3 6
Total 26 days

You might also like