Unbalanced and Restricted Assignments

Two common departures from the neat $n \times n$ minimisation problem are easily handled without changing the method.

Unbalanced assignment problems. If the number of agents and tasks differ, the cost matrix is rectangular ($m \times n$ with $m \neq n$) and the Hungarian method cannot be applied directly. We first make it square by adding a dummy row or column:

• If there are more tasks than agents (fewer rows than columns), add the required number of dummy rows (dummy agents).
• If there are more agents than tasks (more rows than columns), add dummy columns (dummy tasks).

Every cost in a dummy row/column is taken as zero (a dummy agent does no real work, so it costs nothing). After balancing, run the ordinary Hungarian method. In the final answer, whatever real task is assigned to a dummy agent is the task left undone, and whatever real agent is assigned to a dummy task is the agent left idle.

Restricted (prohibited) assignments. Sometimes a particular agent simply cannot do a particular task — a machine lacks an attachment, a worker lacks a licence, a route is closed. We forbid that pairing by placing a very large cost, written $\infty$ or $M$ (a number so large it can never appear in an optimal minimum), in that cell. During row/column reduction $\infty$ is treated as untouchable — it never becomes a zero — so the optimal assignment automatically avoids the forbidden cell. (For a maximisation problem the forbidden cell is given a profit of $-\infty$, i.e. a very large cost after conversion.)