Dummy Assignment¶

Definition¶

A dummy assignment makes a rectangular assignment matrix square by adding fictitious agents or tasks with zero assignment costs. Add dummy agents when there are fewer agents than tasks; add dummy tasks when there are fewer tasks than agents.

Interpretation¶

A dummy assignment turns an assignment problem with unequal numbers of agents and tasks into a square one: an agent paired with a dummy task stays idle, and a task paired with a dummy agent is left undone.

A 3 by 2 cost table made square by adding a dummy task column of zeros; the agent assigned to the dummy task stays idle.

The original $3\times2$ table has one agent too many. The zero column $T_{\mathrm{dummy}}$ makes it square; whichever agent receives it is the idle one. The minimum $5$ is reached with $A_2$ idle, as in the Examples, but also with $A_1$ idle, $A_2\to T_1$ and $A_3\to T_2$ $T_{2}$ .

The zero costs say that leaving an entity unused costs nothing, so each complete assignment of the square table costs exactly as much as its real pairs. The Hungarian algorithm can then run on the square table, and the dummy pairs in its result only record who is idle or which task stays open.

Key Results¶

Use zero dummy costs under the course assumption that leaving the corresponding entity unused has no additional penalty.
A dummy agent leaves its assigned real task unperformed.
A real agent assigned to a dummy task remains unused.

Examples¶

In the figure, one optimal assignment is $A_1\to T_2$ at cost 2, $A_3\to T_1$ at cost 3 and $A_2$ to the dummy task. Thus $A_2$ is idle and the total cost is 5.

Three agents and four tasks require one dummy-agent row.
Five machines and four jobs require one dummy-job column if machines are the rows.

Prerequisites¶

Assignment Problem

Sources¶

OR Modelling · Week 5

Last updated: 20 October 2026 03:02