n Tasks + n People / Machines — Who Do I Assign To What So Total Cost or Time Is Minimum?

Editor’s note

In plain speech this problem is called “task distribution”, “staff allocation”, “job assignment” or “resource allocation”. In the academic literature it is the Assignment Problem; the classical solution is the Hungarian Method, also known as the Kuhn-Munkres algorithm, an O(n³) polynomial-time combinatorial algorithm. The name comes from the bipartite-matching theorems developed in the early 1900s by the Hungarian mathematicians Dénes König and Jenő Egerváry; Harold Kuhn built the algorithm on that base in his 1955 paper, and James Munkres recast it into a formal polynomial-time procedure in 1957. Not to be confused with #072 (Stable Matching): stable matching works with two-sided preference lists — candidate A prefers institution X, institution X prefers candidate A, the matching is constructed so that no blocking pair exists. In assignment there is only a one-way cost matrix — the person has a cost on the task, the task has no preference ordering; there is no payment but there is a cost, and the optimisation objective is total cost (social optimum) — the strategic-manipulation analysis is different. Not to be confused with #094 (Transportation Problem): in transportation m sources and n destinations can differ (m≠n), each source can send a divisible amount to several destinations, supply/demand balance constraints differ. In assignment each resource goes to exactly one destination, each destination receives from exactly one source — a square 0/1 assignment. Transportation generalises assignment.

Most-skipped point in the sector: dummy extension for the rectangular case (m≠n). Kuhn’s original Hungarian Method requires an n×n square matrix; in practice the field arrives with 7 staff + 12 tasks, or 15 staff + 9 tasks. The fix is simple but practitioners do not know it: extend the matrix to square with dummy rows/columns. (a) m<n (fewer staff than tasks): add (n-m) dummy staff, each dummy’s cost on every task is M (very large) — used when ’every task must be assigned’; if ’extra tasks can stay unassigned’ is acceptable, the cost is set to 0 and unassigned tasks ‘go’ to dummy staff (i.e. remain unassigned in reality). (b) m>n (more staff than tasks): conversely add dummy tasks; staff assigned to a dummy task means ’this week no task is taken’. Practitioners do not know this procedure and ’leftover staff’ or ’leftover task’ is treated as a manual remainder — the optimum loss is 10-25%. Second skipped point: maximisation ↔ minimisation conversion. Some problems are in ‘maximise total benefit’ form (e.g. skill + client fit); the Hungarian Method is a minimisation algorithm, but replacing each cost with -benefit, or applying a (max_benefit - benefit) transformation, converts it to minimisation; the same algorithm runs. Third skipped point: cost-matrix estimation drift. For the algorithm to deliver the optimum, C[i,j] must be estimated correctly; bad estimates yield bad assignments. How the matrix is estimated (historical duration data, a skill formula, a transfer-distance tariff) is a modelling problem that precedes the algorithm — practitioners usually do this intuitively, and the system’s output quality is bounded by estimation quality. Fourth skipped point: confusion with Quadratic Assignment (QAP). In classical linear assignment each cell is independent (C[i,j] depends only on i and j); in QAP two assignments interact (if persons i and i’ are both assigned to the same region, a transfer cost is incurred, etc.) — NP-hard, a separate algorithm class (Koopmans-Beckmann 1957). Mixing linear assignment with QAP produces the ‘why is the algorithm taking so long?’ surprise.

A step-by-step path for an SMB

Stage 1 — Measure the cost matrix first and make it explicit. At least 6-12 months of history: for each person-task pair the actual duration, quality score, transfer distance, client/project fit. Cost formula in writing: C[i,j] = α × estimated_duration[i,j] × hourly_rate[i] + β × transfer_distance[i,j] + γ × skill_mismatch[i,j] + δ × client_continuity_penalty[i,j]. Weights (α, β, γ, δ) are a management decision; at least an initial α=1, β=0.5, γ=2 (heavy), δ=0.3 as a starting point. After each assignment the actual-vs-estimated deviation is logged.

Stage 2 — Build the knowledge capital. Staff skill map (skill × level matrix), task-type taxonomy (task classes + required skills + average duration per class), transfer-distance tariff (region×region matrix), client-continuity rules (which clients require the same staff member, which prefer it). This data set is the input to the cost-matrix estimation model.

Stage 3 — Pilot. 6-10 weeks. On a sub-set (e.g. a single region or a single job type) compute the optimum assignment with the Hungarian Method and present it in parallel with the current manual allocation. The planner makes the decision; the algorithm is in a recommend role. Test the dummy procedure for the rectangular case. Success criteria set in advance: total cost -10% minimum, planner allocation time -50% minimum, workload imbalance -20% minimum.

Stage 4 — Rollout. Extend to the full service scope + multi-objective (cost + fairness + continuity) optimisation over 9-15 months. Monthly allocation committee: actual-vs-optimum deviation analysis, cost-matrix calibration update (every 3 months), workload-balance report, client-continuity rate.

Risks — what can go wrong

1. Cost-matrix estimation drift. If C[i,j] is mis-estimated the algorithm finds the wrong optimum. E.g. person X on task type Y was estimated 4 hours but actually 10 hours — the assignment looks ‘optimum’ but the field breaks down. Fix: the cost matrix is updated with feedback after each assignment; a 3-month calibration cycle at minimum; cells with deviation >25% trigger further analysis.

2. Skill is multi-dimensional — a single scalar cost is insufficient. A person’s skill on a task can be ‘basic competence + specific client knowledge + language proficiency’ across several dimensions; collapsing this into a single C[i,j] loses decision information. Fix: a multi-objective formulation (total cost + fairness + continuity as separate objectives), or report the cost components separately so the manager can pick alternatives.

3. Conflicting preferences (the social dimension). The optimum assignment follows the cost matrix, but the staff-preference dimension (who wants to work on which task, who wants to see which client again) is not in the cost matrix; the optimum allocation can then score badly on staff satisfaction. Fix: introduce preference information as a preference-penalty component (γ × preference_mismatch[i,j]) in the cost matrix; or offer alternatives along the Pareto front.

4. Single-supplier workforce-management (WFM) lock-in. Without a contract clause for “annual standard-format export of cost-matrix history, assignment result archive, staff-skill record, client-continuity record and algorithm parameters”, switching the supplier means losing the operational memory of the service business. Assignment systems run 5-15 years — single-supplier dependence is a long-term risk.

Solution method — technical view

Objective-function choice:

• Objective 1 — Minimum total cost: Classical linear assignment; cost components in a weighted sum.
• Objective 2 — Minimum total time: Time-focused; identical to cost when hourly rates are equal.
• Objective 3 — Bottleneck (max-min fairness): Minimise the maximum cost assigned; fairness-focused.
• Objective 4 — Multi-objective (cost + fairness + continuity): Pareto front or weighted sum.

Assignment variants — choose by the field:

• Classical Linear Assignment (square + balanced): n×n cost matrix, one-to-one allocation, Hungarian Method O(n³).
• Rectangular Assignment (m≠n): Dummy extension + Hungarian; or LAPJV supports rectangular directly.
• Maximisation variant: Replace cost with -benefit; same algorithm.
• Bottleneck Assignment: Threshold binary search + Hungarian; max-min fairness.
• Generalized Assignment (GAP): Each resource has capacity, each task has a resource requirement — NP-hard, MIP/metaheuristic.
• Quadratic Assignment (QAP): Person-person interaction costs — NP-hard, Koopmans-Beckmann 1957.
• Dynamic Assignment: Multi-period, the task pool arrives dynamically — rolling-horizon.
• Stochastic Assignment: The cost matrix is uncertain, expected-value or CVaR optimisation.

Academic references

Listed in the page frontmatter under sources.