Assignment Method (Hungarian Method)

The Assignment Method is an Operations Management tool typically used for minimizing the amount of cost, time or effort by assigning tasks to the proper person. It can also be used for maximization problems, but it requires an extra step. The Hungarian Method for solving this type of problem has you set up a problem into a matrix of values that we will work with until we find the optimal solution. This type of optimization has been pretty much made moot by software, but this will still demonstrate the logic behind this process.

In this example, we are going to have 5 team members stating about how much time they would estimate the 4 available projects should take them. Everyone provided a time in hours with a few team members stating that they wouldn't be able to work on a few of the projects. If you are using computations and need a way to represent the "impossible" projects, assign it an obnoxiously high value.

Step 1. Balancing the matrix

With the Hungarian Method, the first step would be to balance the matrix. The number of rows must equal the number of columns. Since we have 5 team members, we have to have 5 projects. To do this, we will add a Dummy column with all of the values being 0.

Step 2. Reduce Rows

Find the minimum value in each row and subtract the row by that minimum value. Each row is done separately. In this example, the 0s in the Dummy row are the smallest value, so there will be no change for this step.

Step 3. Reduce Columns

Similar to the previous step, you will need to find the smallest value in each column. Subtract all the values in that column by that smallest value. Those would be the 16 for GraphDB, 18 for Python, 25 for SQL, 14 for Tableau, and 0 for Dummy. When complete, you new matrix should look like the following.

Step 4. Cover 0s with Fewest Lines

You will be complete modifying the matrix when you are able to cover all the 0s with the fewest number of lines and that number is equal to the number of rows you have. The best way to do that is to find the rows or columns with the most exposed 0s and put a line there. If the lines match the number of rows, then skip to Step 6.

In this example, the Dummy column has 5 exposed 0s. Then Danielle has 2 exposed 0s to cover. Then that leaves the Amy row and the SQL column both with single 0s to cover. If you have only a single 0, it does not matter if you cover the row or column. It is your choice.

Step 5. Adjust the Matrix

In this step, you will search for the smallest number that is currently uncovered in the matrix. Then, you will subtract that value from all of the uncovered values and add it to values that have an intersection of the lines. For the values that are covered by a line, but not at an intersection, you will leave those alone. Once this is complete, you will jump back to Step 4.

For this example, 2 is the smallest one. The modified matrix will now appear as below.

These steps are repeated iterations since the first pass did not provide the condition we were looking for.

Now we are back at Step 4 to find the fewest lines. We see that the Dummy column has 3 exposed 0s, so that will be the first line. Danielle has 2 exposed 0s, then Python has 2 exposed 0s, leaving Brian and Edward with a single exposed 0 to cover. That gives us 5 lines which matches the 5 columns. We can now proceed to Step 6.

Step 6. Find unique 0s

Look at the matrix again without any lines on it. You will want to find the unique zeros. The easiest way is to find a row or column with a single 0 in it. Then, mark out all of the other values in that row and column associated with that 0.

For this example, we start with a clean matrix. We see that Amy has a single 0 in her row. So we lock that task down to her.

You now can see that Charles has a single 0 in the Dummy column. that task will be locked to him.

Brian now has a single 0 in his row in the GraphDB project since the other 0 in the Dummy column was eliminated.

The next single 0 you will run across will be Danielle for Tableau.

And that leaves Edward with the SQL project.

You are now complete.

If you want to see the total time your team will need to complete the projects, just overlay the results over the original matrix.

For this example, we will see that Charles should sit out this round of projects and the other 4 people will need about 75 man-hours to complete everything.

Note: It is possible for some problems to have multiple solutions. This will only provide one of the results, but the effective "cost" will still be the same.