An organization has four technicians and four service calls. Every call needs one technician, each technician can take one call during the planning window, and the travel or service cost depends on the pairing. Picking the lowest-cost technician for each call independently may assign the same person to several jobs. A useful plan must consider all assignments together.
This is an assignment problem, one of the most approachable families in combinatorial optimization. It appears in staff scheduling, machine-task allocation, logistics, matching jobs to equipment and many other settings. Its simplicity makes it an excellent example of how modeling reveals dependencies between choices.
Why a local choice can be wrong
Suppose Technician A is the best individual match for calls 1 and 2. Assigning A to call 1 uses up their availability and may force an expensive alternative for call 2. Assigning A to call 2 could lead to a lower total cost even if it looks slightly worse for the first call.
The objective is to minimize the total cost of all assignments, not to minimize each decision in isolation. Each assignment changes the remaining choices, which is what makes the problem more than a collection of independent lookups.
In a basic one-to-one model, binary variables indicate whether each person is assigned to each job. Constraints ensure every job gets exactly one person and every person gets at most one job. A cost table gives the objective. The formulation can be remarkably compact even when the number of possible pairings is enormous.
The objective is to minimize the total cost of all assignments, not to minimize each decision in isolation.
A tiny example
Three workers, A, B and C, must cover three tasks. The illustrative costs are:
| Worker | Task 1 | Task 2 | Task 3 |
|---|---|---|---|
| A | 1 | 2 | 9 |
| B | 2 | 8 | 3 |
| C | 9 | 3 | 1 |
Assigning each task independently to its cheapest worker would choose A for task 1, A for task 2 and C for task 3, which is invalid because A cannot take two tasks. One valid assignment is A→1, B→2, C→3 at cost 10. A better assignment is A→1, B→3, C→2 at cost 7. Better still is A→2, B→1, C→3 at total cost 5, the global minimum for this example.
That improvement does not require mysterious mathematics. It requires viewing the decision as a whole. Even small examples reveal why the best pairings are not necessarily the collection of individually cheapest pairings.
When assignment stops being simple
The classic assignment problem has special mathematical structure and can be solved efficiently with established algorithms. Real-world applications often complicate it. A worker may handle several jobs, tasks may require teams, qualifications may rule out certain assignments and timing may create dependencies. Costs may vary with the order in which tasks are performed.
The output must also be interpretable: users need to know why an apparently attractive pairing was not chosen and whether changing one assignment would affect several others.
At that point, the model can evolve toward generalized assignment, vehicle routing, workforce scheduling or other related problems. The label matters less than accurately recording the interaction. What initially looks like a matching task can become a scheduling problem as soon as time and shared resources enter the picture.
What a deployment needs
The necessary data includes eligibility, capacity, assignment costs and any rules that cannot be violated. The output must also be interpretable: users need to know why an apparently attractive pairing was not chosen and whether changing one assignment would affect several others.
A credible evaluation compares the proposed plan with a relevant baseline, checks all hard rules and measures the outcomes that matter. If travel costs are estimated from unreliable locations or qualifications are outdated, a mathematically optimal match can still be a poor operational recommendation.
Assignment models show the value of thinking globally while acting locally. Each job is assigned once, but the choice is made with an understanding of the alternatives it prevents and enables.
The cheapest choice can block another good choice
Imagine two tasks and two people. Person A can perform task 1 at a cost of 1 and task 2 at a cost of 2; person B costs 2 for task 1 but 100 for task 2. Assigning task 1 to its cheapest individual choice, person A, forces the remaining task to person B for a total of 101. The other assignment costs only 4. This tiny example shows why independent local rankings can fail when each person may take only one task. A matching algorithm considers the choices jointly, and that principle extends to assigning jobs to machines, crews to flights, or requests to computing resources.