Unbalanced Assignment Problem (Dummy Rows/Columns): Step by Step
An unbalanced assignment problem occurs when the number of workers and jobs are different (a rectangular cost matrix). The standard Hungarian-algorithm fix is to add a dummy row or dummy column to make the matrix square, then interpret dummy assignments as “idle worker” or “unfilled job.”
For the full Hungarian method (after balancing), see Hungarian algorithm explained.
On this page
Quick takeaway: If jobs > workers, add dummy workers (rows). If workers > jobs, add dummy jobs (columns). Solve the square matrix with Hungarian; dummy assignments represent unused capacity.
Why the matrix must be square for Hungarian
The classic assignment constraints require exactly one choice per row and per column. If the matrix is rectangular, you cannot satisfy both sets of equalities without adding dummy capacity.
For the step-by-step method after balancing, see Hungarian algorithm explained.
How to balance (dummy row/column rules)
Rule 1 — If jobs > workers
Add dummy workers (rows) so rows = columns.
Rule 2 — If workers > jobs
Add dummy jobs (columns) so rows = columns.
Rule 3 — Choose dummy costs correctly
- 0 dummy cost means “no penalty” for leaving job unfilled / worker idle.
- Penalty dummy cost models a real cost (lost revenue, overtime replacement, service-level penalty).
- Avoid unrealistically huge penalties (can create numeric/interpretation issues).
If your “unfilled job” is not allowed at all, you may need a different model (or constraints) rather than just dummy zeros. That can become an ILP/MILP.
How to interpret dummy assignments
- Job assigned to dummy worker: that job is unfilled.
- Worker assigned to dummy job: that worker is idle/unassigned.
Always report results with this interpretation explicitly (especially if dummy penalties were used).
Worked examples
Worked example
Example 1: 3 workers, 4 jobs → add 1 dummy worker (0 penalty)
Costs (minimize):
J1 J2 J3 J4 W1 8 6 7 9 W2 6 7 5 8 W3 7 8 6 7
Step 1 — Add dummy worker W4*
Jobs > workers, so add one dummy row. If leaving a job unfilled has no penalty, set dummy costs to 0:
J1 J2 J3 J4 W1 8 6 7 9 W2 6 7 5 8 W3 7 8 6 7 W4* 0 0 0 0
Step 2 — Solve with Hungarian algorithm
Solve the 4×4 assignment using: Hungarian algorithm. The job assigned to W4* is interpreted as “unfilled.”
Worked example
Example 2: 3 workers, 4 jobs → add dummy worker with penalty
Same matrix as Example 1, but suppose leaving a job unfilled costs 20 units (service-level penalty). Use dummy row costs = 20:
J1 J2 J3 J4 W1 8 6 7 9 W2 6 7 5 8 W3 7 8 6 7 W4* 20 20 20 20
Now the model will only leave a job unfilled if every real assignment alternative is worse than paying the penalty.
Worked example
Example 3: 5 workers, 3 jobs → add 2 dummy jobs (idle workers)
When workers > jobs, add dummy columns so that extra workers are assigned to “idle.” Any worker matched to a dummy job is interpreted as unused capacity.
If “idle” should be discouraged, add an idle penalty in dummy columns.
Questions people ask
Questions people ask
Should dummy costs always be 0?
No. Use 0 only if unassigned/unfilled truly has no cost. Otherwise use a penalty that matches the real-world impact.
Questions people ask
What if every job must be filled (no unfilled jobs allowed)?
Then adding a dummy row with 0 cost is not appropriate. You need enough workers, overtime/outsourcing options, or an ILP/MILP that models additional hiring/overtime decisions.
Questions people ask
Does balancing with dummy change the meaning of the objective?
It can—depending on dummy costs. Dummy costs are part of the objective, so choose them to reflect your operational interpretation.
Questions people ask
Can Hungarian algorithm solve rectangular matrices without padding?
Standard Hungarian is described for square matrices; padding with dummy rows/columns is the standard way to handle rectangular cases.
Questions people ask
Is unbalanced assignment the same as transportation?
Not exactly. Unbalanced assignment is still a one-to-one selection model after you add dummy capacity. Transportation is a quantity-shipping model with general supplies/demands. See assignment vs transportation.
What to do next
- Learn full steps: Hungarian algorithm explained.
- Practice sets: assignment problem examples.
- Graph viewpoint: bipartite matching.
Disclaimer
This guide is for educational purposes. Dummy penalties should be chosen using real operational meaning (service level, lost revenue, overtime, legal staffing rules). If your application includes additional constraints, you may need a broader ILP/MILP model rather than a simple unbalanced assignment fix. Read the full disclaimer.