Hungarian Method

Hungarian Method is for assigning jobs by a one-for-one matching to identify the lowest-cost solution. Each job must be assigned to only one machine. It is assumed that every machine is capable of handling every job, and that the costs or values associated with each assignment combination are known and fixed. The number of rows and columns must be the same.

Hungarian Method Applet will appear below in a Java enabled Internet browser.

Instructions:

1. Subtract the smallest number in each row from every number in the row. This is called a row reduction. Enter the results in a new table.
2. Subtract the smallest number in each column of the new table from every number in the column. This is called a column reduction. Enter the results in another table.
3. Test whether an optimum assignment can be made. You do this by determining the minimum number of lines needed to cover (i.e., cross out) all zeros. If the number of lines equals the number of rows, an optimum assignment is possible. In that case, go to step 6. Otherwise go on to step 4.
4. If the number of lines is less than the number of rows, modify the table in this way:
   a. Subtract the smallest uncovered number from every uncovered number in the table.
   b. Add the smallest uncovered number to the numbers at intersections of covering lines.
   c. Numbers crossed out but not at intersections of cross-out lines carry over unchanged to the next table.
5. Repeat steps 3 and 4 until an optimal table is obtained.
6. Make the assignments. Begin with rows or columns with only one zero. Match items that have zeros, using only one match for each row and each column. Cross out both the row and the column after the match.