Unbalanced Assignment Problem (Dummy Rows/Columns)
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.β
Solved result: minimum total cost 18, for example W1βJ2 (6), W2βJ1 (6), W3βJ3 (6) with J4 unfilled. This matrix has ties: W1βJ2, W2βJ3, W3βJ1 (6 + 5 + 7) also leaves J4 unfilled, and W1βJ2, W2βJ3, W3βJ4 (6 + 5 + 7) leaves J1 unfilled instead β all total 18.
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
With 3 workers and 4 jobs, one job is always left unfilled, whatever the penalty. A penalty that is the same for every job (20 here) simply adds 20 to every possible plan, so the best assignment is unchanged: total cost 18 + 20 = 38, with the same tied choices as Example 1. Penalties only change the decision when they differ between jobs. For example, with dummy costs 20, 20, 20, 30 (J4 is more costly to leave unfilled), the unique optimum becomes W1βJ2, W2βJ3, W3βJ4 with J1 unfilled, still totalling 38.
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.
Methodology: How This Guide Works
This guide explains unbalanced assignment problems using the standard textbook treatment found in operations-research courses (for example Hillier & Lieberman, Introduction to Operations Research, and Taha, Operations Research: An Introduction). Each step is written so you can repeat it by hand, and the worked examples use the same steps as the CalcTypes unbalanced assignment calculator, so you can reproduce them there.
Assumptions and Limitations
Assumptions
- Each worker is assigned to at most one task and each task to at most one worker.
- Costs (or profits) are fixed, known numbers that do not change with the other assignments.
- Zero-cost dummies are added to make the matrix square.
Limitations
- Some workers or tasks are left unassigned in the solution.
- Several optimal assignments can exist.
- Examples are small teaching problems; real problems usually need more constraints and data checks.
Related guides
Sources
- Kuhn (1955) β The Hungarian method for the assignment problem (Naval Research Logistics Quarterly)
- Munkres (1957) β Algorithms for the Assignment and Transportation Problems (SIAM)
- Burkard, DellβAmico, Martello β Assignment Problems (SIAM book page)
- Wikipedia β Assignment problem (overview)
Disclaimer
Please read before relying on this page. This page on Unbalanced Assignment Problem (Dummy Rows/Columns) explains optimisation methods for study. Worked examples use simplified models; real problems usually need extra constraints and careful validation. Check methods against your course, and validate any model before using it for real decisions.
Your responsibility. Results are estimates for general information and education only, and nothing here is professional advice. You use this page at your own risk; to the fullest extent permitted by law, CalcTypes, its authors and reviewers accept no liability for loss, injury or damage arising from reliance on it. Spotted an error? Use βReport an issueβ or our contact page. Full terms: Disclaimer Β· Terms of use.