How to use the assignment optimizer
- Choose whether you want the lowest or the highest total.
- Paste a table of numbers, one row per line, with one row per person and one column per job. The example shows a 4 by 4 table of costs.
- Optionally type row names and column names, separated by commas.
- Read the matching, the value of each pair and the total. If the table is not square, some rows or columns are left without a match, and the page lists them.
Formula
choose one cell in each row and each column to minimize the total of the chosen cells
subtract the smallest value from each row, then from each column, to create zeros
cover all zeros with the fewest lines; if that takes fewer lines than rows, adjust and repeat
when n lines are needed, a full set of zero cells gives the best matching
This is the Hungarian method. It finds the best matching in a number of steps that grows with the cube of the table size, instead of trying every one of n! arrangements. To maximize, the values are negated first.
Four people and four jobs
With the costs 82, 83, 69, 92 / 77, 37, 49, 92 / 11, 69, 5, 86 / 8, 9, 98, 23, the lowest total is 140: Ana does Ship at 69, Ben does Pack at 37, Cleo does Print at 11 and Dev does Label at 23. All 24 possible arrangements give a total of 140 or more.
Asking for the highest total instead gives 344, by matching Ana with Pack (83), Ben with Print (77), Cleo with Label (86) and Dev with Ship (98). A table with 2 rows and 3 columns, 4 1 3 / 2 0 5, gives a lowest total of 3 and leaves the third column unmatched.
What the numbers can mean
The values can be costs, times, distances or scores. Use the lowest total for costs and times, and the highest total for scores and profits. Each row can be matched to only one column and each column to only one row, so the model does not suit cases where one person can take several jobs.
When several matchings tie, the tool shows one of them. A table does not capture skills, schedules or preferences beyond the numbers, so treat the answer as a starting point. For other planning problems, try the Linear Programming Solver or the Decision Matrix Calculator.
Tables that are not square
With more rows than columns, the extra rows are left unmatched, and with more columns than rows, the extra columns are. The tool picks the matching that gives the best total for the pairs it makes. To force every row to be matched, add dummy columns with a high cost or a low score.
More planning and optimization tools
For related planning and optimization problems, try the Shortest Route Calculator, Linear Programming Solver and NPK Blend Calculator.
Assumptions and limits
- Each row is matched to at most one column and each column to at most one row.
- All entries are numbers below 1,000,000,000 in size, and negative numbers are allowed.
- Up to 30 rows and 30 columns can be entered.
- Example data are shown until you replace them.
Frequently asked questions
What is the assignment problem?
It is matching rows to columns, such as workers to jobs, one each, so that the total cost is lowest or the total score is highest.
What is the Hungarian algorithm?
It is a method that finds the best matching by adjusting row and column values until zeros show where the best pairs are. It avoids trying every arrangement.
Can I maximize instead of minimize?
Yes. Choose the highest total and the tool negates the table, finds the lowest total of that, and converts the answer back.
What happens if the table is not square?
The tool matches as many rows and columns as it can, which is the smaller of the two counts, and lists the rows or columns left over.