The Generalized Assignment Problem

Imagine you run a small workshop. You have a pile of jobs waiting and a handful of machines to do them. Each machine has a budget of hours — its capacity — and each job, on each machine, takes a certain amount of that capacity and earns a certain profit. The same job might be cheap and lucrative on one machine and slow and barely worth it on another.

Your task: assign every job to at most one machine, never exceed any machine's capacity, and make the total profit as large as possible.

That is the Generalized Assignment Problem (GAP). It sounds like the kind of thing a spreadsheet should settle in a second. It isn't. GAP generalizes both the knapsack problem (one machine) and the classic assignment problem, and as soon as machines have real capacity limits, finding the best assignment becomes genuinely hard.

Below are several tasks and three agents, each with a limited budget. Click a task, then click an agent to assign it there — the cost is deducted from that agent's budget and the value is added to your score. Try to make the total value as high as you can without busting any budget.

<p class="hint">{{hint}}</p>
<div class="agents" id="agents"></div>
<div class="pool">
  <div class="pool-label">{{pool_label}}</div>
  <div id="pool" class="chips"></div>
</div>
<div class="status" id="status">{{total_value_zero}}</div>
<div class="btns">
  <button id="solve" type="button">{{solve_btn}}</button>
  <button id="reset" type="button" class="ghost">{{reset_btn}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.agents { display: grid; grid-template-columns: repeat(3, 1fr); gap: 8px; margin: .4rem 0; }
.agent { border: 1px solid #cdd9e3; border-radius: 10px; padding: .5rem; background: #f3f7fa; min-height: 90px; cursor: pointer; transition: all .1s; }
.agent:hover { background: #e8eef3; }
.agent.over { border-color: #c92f3c; background: #fdeceedd; }
.agent h4 { margin: 0 0 .3rem; font-size: .95rem; color: #1d3557; }
.bar { height: 6px; border-radius: 3px; background: #d6dee6; overflow: hidden; margin: .25rem 0 .4rem; }
.bar > span { display: block; height: 100%; background: #2a9d5c; }
.bar > span.full { background: #c92f3c; }
.meta { font-size: .75rem; color: #555; }
.chip { display: inline-flex; align-items: center; gap: .3rem; font: 600 13px system-ui, sans-serif;
        padding: .3rem .55rem; margin: .15rem; border-radius: 999px; border: 1px solid #adb1b8;
        background: #fff; color: #1d3557; cursor: pointer; }
.chip.sel { outline: 2px solid #1d3557; background: #eef3f8; }
.chip.assigned { background: #e8eef3; border-color: #cdd9e3; cursor: pointer; }
.chips { min-height: 1.8rem; }
.pool-label { font-size: .78rem; color: #555; margin: .5rem 0 .2rem; }
.status { font-size: 1.05rem; font-weight: 700; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a plan is effortless: add up the cost on each agent and confirm no budget is broken, then sum the values. Finding the best plan is the hard part — press Solve optimally and the computer simply tries every way to assign the tasks. With a handful of tasks and three agents that's already $4^{n}$ possibilities, and the count explodes the moment you add more.

How hard is GAP, really? Not the checking — the optimizing.

• Checking a candidate plan is trivial: for each agent, sum the costs of its jobs and confirm it stays within budget, then total the values.
• Brute force tries every assignment of jobs to machines (each job can go to any machine or stay unassigned) — that is exponential, hopeless past a few dozen jobs.
• It's NP-hard. GAP contains the knapsack problem as the special case of a single machine, and knapsack's decision version is NP-complete. So the decision form of GAP — "is there an assignment with total profit at least P?" — is NP-complete, and the optimization form is NP-hard. This has been folklore since the 1970s and is laid out in Martello & Toth's classic text.
• Even approximation has limits. Unless P = NP, no algorithm can guarantee a profit better than a fixed constant fraction of the optimum in the worst case; the best known polynomial-time guarantee is roughly a (1 − 1/e) fraction (Fleischer, Goemans, Mirrokni & Sviridenko, 2006).

That is the punchline: the moment capacity limits bite, GAP is a genuine instance of the same wall behind P vs NP. The "obvious best plan" you feel should exist may take exponential time to actually find.

"Pack valuable work onto limited resources" is one of the most common shapes a real problem takes, and GAP is its purest form:

• Logistics and routing: deciding which truck carries which order, under each truck's weight and volume limits, is GAP at its heart — it even appears as a subproblem inside vehicle-routing solvers.
• Cloud and computing: placing virtual machines or jobs onto physical servers with limited CPU and memory is assignment-under-capacity.
• Scheduling and staffing: matching tasks to workers or machines, each with finite hours, while maximizing throughput.
• Telecom and networks: assigning users to base stations or channels with capacity caps.

Understand GAP and you've met the core of resource allocation — the same combinatorial engine under knapsack, bin packing and large-scale integer programming.

The Generalized Assignment Problem hides a humbling lesson: a question as ordinary as "which job goes on which machine?" is NP-hard. Checking a plan stays instant, but finding the provably best one can take exponential time — and even getting close has theoretical limits.

That is why the world's warehouses, fleets and data centers don't compute the perfect assignment. They lean on heuristics and approximations that find very good plans fast, and accept that "optimal" may forever be out of reach. Behind the delivery truck and the cloud scheduler sits P vs NP, quietly setting the price of every decision.