What is an Assignment Problem?

Suppose a workshop has four machines and four jobs waiting to be processed. Each machine can do any of the jobs, but the cost (or time) of doing a particular job differs from machine to machine — one machine is fast at drilling but slow at grinding, another is the reverse. In how many ways, and at what cost, can we hand out the jobs so that each job goes to exactly one machine and each machine gets exactly one job, and the total cost is as small as possible? This is the assignment problem.

An assignment problem is a special kind of allocation problem in which a set of $n$ agents (workers, machines, salesmen, teams) must be matched one-to-one with a set of $n$ tasks (jobs, territories, routes). The data is an $n \times n$ cost matrix $[c_{ij}]$, where $c_{ij}$ is the cost of assigning agent $i$ to task $j$. Because the matching is one-to-one, choosing an assignment amounts to choosing one entry in every row and every column, no two in the same row or column.

The three standing assumptions.

1. The number of agents equals the number of tasks (the matrix is square, $n \times n$) — a problem where they differ is unbalanced and is first made square (§4).
2. Each agent is assigned to one and only one task, and each task to one and only one agent.
3. The cost figures $c_{ij}$ are known constants and are additive — the total cost of an assignment is just the sum of the chosen entries.

Why not just try every possibility? With $n$ agents and $n$ tasks there are $n!$ possible assignments. For $n = 5$ that is $120$; for $n = 10$ it is already $3\,628\,800$. Enumerating them is hopeless for anything but the tiniest problem, so we need a systematic algorithm — the Hungarian method (§2).

These are the standard operations-research allocation principles that underpin the national mathematics-and-statistics curriculum as well as this Std XII (HSC) Commerce course; the treatment here follows the level and notation of the Maharashtra Std XII syllabus.