Hungarian Method: One Job per Machine

Lesson notes

Key points

• The assignment problem pairs n workers or machines with n jobs, one each, to minimise total cost or time.
• The Hungarian method first subtracts each row's smallest value, then each column's smallest, creating zeros.
• If the minimum number of lines covering all zeros equals n, an optimal assignment exists among those zeros.
• For maximisation, such as profit, first subtract every entry from the largest entry, then minimise as usual.

Definitions

Assignment problem

Allocate n agents to n tasks one-to-one so total cost is minimised; a special transportation problem.

Takeaway: Reduce rows and columns, cover zeros; n lines means optimal.

Assignment problemRow and column reductionOptimality testMaximisation case