Introduction

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.

Assign the Jobs

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">Each <b>task</b> has a cost and a value that differ per agent. Click a task, then click an agent to assign it there — its cost is taken from that agent’s budget and its value adds to your score. No agent may go over budget. Maximize the <b>total value</b>.</p>
<div class="agents" id="agents"></div>
<div class="pool">
  <div class="pool-label">Unassigned tasks (click to select):</div>
  <div id="pool" class="chips"></div>
</div>
<div class="status" id="status">Total value: 0</div>
<div class="btns">
  <button id="solve" type="button">Solve optimally</button>
  <button id="reset" type="button" class="ghost">Clear</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Generalized Assignment Problem (GAP): assign each task to at most one agent
// (machine) without exceeding any agent’s budget (capacity), maximizing total
// value (profit). Cost and value depend on BOTH the task and the agent.
// Checking a plan is a quick scan; finding the optimum is NP-hard (it contains
// the knapsack problem as the single-agent special case). Brute force tries
// (agents+1)^tasks plans — here 4^5 = 1024.
const AGENTS = [
  { name: 'Agent A', budget: 10 },
  { name: 'Agent B', budget: 8 },
  { name: 'Agent C', budget: 7 },
];
// tasks[t].cost[a] / value[a] = cost & value if task t runs on agent a.
const TASKS = [
  { id: 'T1', cost: [4, 3, 6], value: [7, 5, 9] },
  { id: 'T2', cost: [3, 5, 2], value: [6, 8, 4] },
  { id: 'T3', cost: [6, 2, 4], value: [9, 4, 7] },
  { id: 'T4', cost: [2, 4, 3], value: [3, 7, 6] },
  { id: 'T5', cost: [5, 3, 5], value: [8, 6, 8] },
];

// assign[t] = agent index, or -1 if unassigned.
let assign = TASKS.map(() => -1);
let selected = -1; // currently selected task index

function loads(a){ // total cost on agent a under current assignment
  let s = 0; for (let t = 0; t < TASKS.length; t++) if (assign[t] === a) s += TASKS[t].cost[a]; return s;
}
function totalValue(){
  let v = 0; for (let t = 0; t < TASKS.length; t++) if (assign[t] >= 0) v += TASKS[t].value[assign[t]]; return v;
}
function feasible(){
  for (let a = 0; a < AGENTS.length; a++) if (loads(a) > AGENTS[a].budget) return false; return true;
}

function render(){
  const ag = document.getElementById('agents'); ag.innerHTML = '';
  AGENTS.forEach((A, a) => {
    const used = loads(a), over = used > A.budget;
    const d = document.createElement('div');
    d.className = 'agent' + (over ? ' over' : '');
    const pct = Math.min(100, Math.round(used / A.budget * 100));
    const mine = TASKS.filter((_, t) => assign[t] === a).map(T => T.id).join(', ') || '—';
    d.innerHTML = fmt(`<h4>%name%</h4><div class="bar"><span class="%v%" style="width:%pct%%"></span></div><div class="meta">budget %used% / %budget%</div><div class="meta">tasks: %mine%</div>`, { name: A.name, v: used >= A.budget ? 'full' : '', pct: pct, used: used, budget: A.budget, mine: mine });
    d.addEventListener('click', () => { if (selected >= 0) { assign[selected] = a; selected = -1; render(); } });
    ag.appendChild(d);
  });
  const pool = document.getElementById('pool'); pool.innerHTML = '';
  TASKS.forEach((T, t) => {
    const c = document.createElement('span');
    const at = assign[t];
    c.className = 'chip' + (selected === t ? ' sel' : '') + (at >= 0 ? ' assigned' : '');
    const label = at >= 0
      ? T.id + ' → ' + AGENTS[at].name + ' (v' + T.value[at] + '/c' + T.cost[at] + ')'
      : fmt(`%id% (click to place)`, { id: T.id });
    c.textContent = label;
    c.addEventListener('click', () => {
      if (at >= 0) { assign[t] = -1; selected = t; } // unassign and pick up
      else { selected = (selected === t ? -1 : t); }
      render();
    });
    pool.appendChild(c);
  });
  const s = document.getElementById('status');
  const ok = feasible();
  s.textContent = fmt(`Total value: %totalValue%%v%`, { totalValue: totalValue(), v: ok ? '' : '  — over budget!' });
  s.className = 'status ' + (ok ? 'ok' : 'bad');
}

// Brute-force optimum: every task -> agent 0..A-1 or unassigned (A).
function solve(){
  const A = AGENTS.length, n = TASKS.length;
  let best = null, bestVal = -1, tried = 0;
  const choice = new Array(n).fill(0);
  function rec(t){
    if (t === n){
      tried++;
      // check feasibility
      const used = new Array(A).fill(0); let val = 0; let ok = true;
      for (let i = 0; i < n; i++){ const a = choice[i]; if (a < A){ used[a] += TASKS[i].cost[a]; val += TASKS[i].value[a]; } }
      for (let a = 0; a < A; a++) if (used[a] > AGENTS[a].budget) { ok = false; break; }
      if (ok && val > bestVal){ bestVal = val; best = choice.slice(); }
      return;
    }
    for (let a = 0; a <= A; a++){ choice[t] = a; rec(t + 1); }
  }
  rec(0);
  assign = best.map(a => a < A ? a : -1);
  selected = -1; render();
  const s = document.getElementById('status');
  s.textContent = fmt(`Optimal total value: %bestVal%  (checked %tried% plans)`, { bestVal: bestVal, tried: tried });
  s.className = 'status ok';
  console.log(`Optimal value`, bestVal, `assignment`, assign, `plans tried`, tried);
}

document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', () => { assign = TASKS.map(() => -1); selected = -1; render(); });
render();
Result
Console

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 4n4^{n} possibilities, and the count explodes the moment you add more.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/generalized-assignment/Content licensed under CC BY-NC 4.0.