Introduction

You have a stack of jobs to run — render these frames, compile these files, process these orders — and several identical machines to run them on. Each job takes some amount of time. The work isn't finished until the last machine stops. How do you split the jobs so that moment comes as early as possible?

That finishing time has a name: the makespan. Minimizing it is the classic multiprocessor scheduling problem, and it sits at the heart of everything from data-center load balancing to packing a dishwasher efficiently.

It sounds like the kind of thing you could just eyeball. Sometimes you can. But the moment the jobs and machines grow, finding the perfectly balanced split turns out to be one of the genuinely hard problems in computer science — even though, surprisingly, a one-line rule comes remarkably close.

Balance the Load

Below are seven jobs (the numbered bars) and three identical machines. Click a job, then click a machine to send it there. The makespan is whatever the busiest machine reads — try to push it as low as you can.

<p class="hint">You have a set of jobs (the bars) and <b>3 identical machines</b>.
    Click a job, then click a machine to move it there. The <b>makespan</b> is when the
    busiest machine finishes — your goal is to make that number as small as possible.</p>
<div id="pool" class="pool"></div>
<div id="machines" class="machines"></div>
<div class="status" id="status">Makespan: —</div>
<div class="btns">
  <button id="greedy" type="button">Run greedy (LPT)</button>
  <button id="optimal" type="button">Show optimal</button>
  <button id="reset" type="button" class="ghost">Reset</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; }
.pool { display: flex; flex-wrap: wrap; gap: 6px; min-height: 40px; padding: 8px;
        border: 1px dashed #adb1b8; border-radius: 8px; margin-bottom: .8rem; }
.machines { display: flex; gap: 10px; align-items: flex-end; }
.machine { flex: 1; display: flex; flex-direction: column-reverse; gap: 3px;
           min-height: 150px; padding: 5px; background: #eef2f6; border: 1px solid #cdd9e3;
           border-radius: 8px; cursor: pointer; }
.machine .label { writing-mode: horizontal-tb; text-align: center; font-size: .72rem;
                  color: #1d3557; font-weight: 700; margin-bottom: 4px; cursor: default; }
.job { color: #fff; font: 700 13px ui-monospace, monospace; border-radius: 5px;
       display: flex; align-items: center; justify-content: center; cursor: pointer;
       user-select: none; }
.job.sel { outline: 3px solid #ffb703; outline-offset: 1px; }
.pool .job { padding: 0 10px; height: 30px; }
.machine .job { width: 100%; }
.status { font-size: 1.05rem; font-weight: 700; margin: .7rem 0 .4rem; min-height: 1.4em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.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] ?? ''));
// Multiprocessor scheduling: place jobs on M identical machines so the LAST machine
// to finish (the "makespan") is as early as possible. Deciding the optimum is NP-hard.
// The greedy LPT rule (sort jobs largest-first, drop each on the least-loaded machine)
// is provably within 4/3 of the optimum (Graham, 1969).
const M = 3;
const JOBS = [7,6,5,4,4,3,2]; // sums to 31 -> optimal makespan here is 11
const COLORS = ['#1d3557','#457b9d','#e63946','#2a9d8f','#e9a23b','#7b2cbf','#0a7d33'];

// state: assignment[i] = machine index (0..M-1) or -1 for "in pool"
let assign = [];
let selected = -1;

function init(){ assign = JOBS.map(() => -1); selected = -1; render(); setStatus(); }

function loadOf(mi){ let s=0; for(let i=0;i<JOBS.length;i++) if(assign[i]===mi) s+=JOBS[i]; return s; }
function makespan(){ let mx=0; for(let m=0;m<M;m++) mx=Math.max(mx,loadOf(m)); return mx; }
function allPlaced(){ return assign.every(a => a>=0); }

function jobEl(i){
  const j=document.createElement('div'); j.className='job'+(selected===i?' sel':'');
  j.style.background=COLORS[i%COLORS.length]; j.textContent=JOBS[i];
  j.addEventListener('click',e=>{ e.stopPropagation(); selected = (selected===i?-1:i); render(); });
  return j;
}

function render(){
  const pool=document.getElementById('pool'); pool.innerHTML='';
  for(let i=0;i<JOBS.length;i++) if(assign[i]===-1) pool.appendChild(jobEl(i));
  pool.onclick=()=>{ if(selected>=0){ assign[selected]=-1; selected=-1; render(); setStatus(); } };

  const wrap=document.getElementById('machines'); wrap.innerHTML='';
  for(let m=0;m<M;m++){
    const col=document.createElement('div'); col.className='machine';
    const lab=document.createElement('div'); lab.className='label';
    lab.textContent=fmt('Machine %m%%v% · %loadOf%', { m: m, v: 1, loadOf: loadOf(m) }); col.appendChild(lab);
    for(let i=0;i<JOBS.length;i++) if(assign[i]===m){
      const j=jobEl(i); j.style.height=(JOBS[i]*14)+'px'; col.appendChild(j);
    }
    col.addEventListener('click',()=>{ if(selected>=0){ assign[selected]=m; selected=-1; render(); setStatus(); } });
    wrap.appendChild(col);
  }
}

function setStatus(msg,ok){
  const s=document.getElementById('status');
  if(msg){ s.textContent=msg; s.className='status'+(ok?' ok':''); return; }
  if(!allPlaced()){ s.textContent='Makespan: — (place every job first)'; s.className='status'; }
  else { s.textContent=fmt('Makespan: %makespan%', { makespan: makespan() }); s.className='status'; }
}

// Greedy LPT: sort jobs descending, assign each to the currently least-loaded machine.
function greedy(){
  const order=[...JOBS.keys()].sort((a,b)=>JOBS[b]-JOBS[a]);
  const load=new Array(M).fill(0); assign=JOBS.map(()=>-1);
  for(const i of order){ let best=0; for(let m=1;m<M;m++) if(load[m]<load[best]) best=m;
    assign[i]=best; load[best]+=JOBS[i]; }
  selected=-1; render(); setStatus(fmt('Greedy LPT makespan: %makespan%', { makespan: makespan() }),false);
}

// Optimal by exhaustive search over all M^n assignments (small n only).
function bestPossible(){
  let best=Infinity;
  const a=new Array(JOBS.length).fill(0);
  function rec(i){ if(i===JOBS.length){ const load=new Array(M).fill(0);
      for(let k=0;k<JOBS.length;k++) load[a[k]]+=JOBS[k];
      best=Math.min(best,Math.max(...load)); return; }
    for(let m=0;m<M;m++){ a[i]=m; rec(i+1); } }
  rec(0); return best;
}
function showOptimal(){
  const opt=bestPossible();
  // reconstruct one optimal assignment
  const a=new Array(JOBS.length).fill(0); let found=null;
  function rec(i){ if(found) return; if(i===JOBS.length){ const load=new Array(M).fill(0);
      for(let k=0;k<JOBS.length;k++) load[a[k]]+=JOBS[k];
      if(Math.max(...load)===opt) found=a.slice(); return; }
    for(let m=0;m<M;m++){ a[i]=m; rec(i+1); if(found) return; } }
  rec(0); assign=found; selected=-1; render();
  setStatus(fmt('Optimal makespan: %opt% (the best any split can do)', { opt: opt }),true);
}

document.getElementById('greedy').addEventListener('click',greedy);
document.getElementById('optimal').addEventListener('click',showOptimal);
document.getElementById('reset').addEventListener('click',init);
init();
Result
Console

When you're stuck, press Run greedy (LPT): it sorts the jobs largest-first and drops each one on whichever machine is currently least loaded. Then press Show optimal to see the best split any algorithm could find (computed here by brute force). For these jobs the greedy rule already hits the optimum — but in general greedy can be off, and the magic is that it is never off by more than a factor of 4/3.

The Real Complexity

So how hard is it to find the best split?

  • Checking a schedule is trivial: add up each machine's jobs and take the biggest total.
  • Finding the minimum makespan is NP-hard. Even with just two machines it already contains the partition problem — "can you split these numbers into two equal-sum halves?" — which is NP-complete. So no known algorithm finds the exact optimum quickly in the worst case.
  • Brute force tries every assignment of n jobs to m machines: mnm^{n} possibilities, hopeless past a few dozen jobs.
  • But approximation is easy and excellent. In 1969 Ron Graham analyzed list scheduling — just place jobs one by one on the least-loaded machine — and proved it always lands within a factor of 2 − 1/m of optimal. Sorting the jobs largest-first first (the Longest-Processing-Time, or LPT, rule) tightens that to 4/3 − 1/(3m): never worse than about 33% over the best possible.
  • You can get as close as you like. There is even a PTAS — for any tolerance ε you choose, a polynomial-time algorithm gets within (1 + ε) of optimal.

That is the shape of a beautiful kind of problem: deciding the exact answer is as hard as anything in NP (this is the world of P vs NP), yet getting almost the right answer is cheap and guaranteed.

Where It Matters

"Spread the work so the slowest worker still finishes early" is everywhere once you start looking:

  • Data centers and the cloud: dispatchers assign incoming tasks to servers, and greedy least-loaded placement is exactly the LPT idea in disguise.
  • Build and render farms: compiling a huge codebase or rendering a film means splitting thousands of independent jobs across a cluster.
  • Manufacturing and operations: assigning orders to identical machines, or jobs to workers, is makespan minimization on the factory floor.
  • Everyday parallelism: loading dishwashers, balancing checkout lines, planning who cooks what for dinner — all the same shape.

The practical lesson is liberating: you almost never need the perfect schedule. Understand multiprocessor scheduling and you've met its cousins bin packing and load balancing — a whole family where greedy heuristics carry guarantees.

Conclusion

Multiprocessor scheduling captures a hopeful truth about hard problems. Pinning down the exact minimum makespan is NP-hard — even on two machines it hides the partition problem. And yet a child-simple rule, put the next-biggest job on the emptiest machine, never strays more than a factor of 4/3 from perfect, and you can do even better if you're willing to work a little harder.

So when a problem is NP-hard, the right question often isn't "can I solve it exactly?" but "how close can I get, cheaply, with a guarantee?" Scheduling answers that beautifully — and shows that the wall of P vs NP is one you can usually get within arm's reach of, even when you can't climb over.

Share this article

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

Comments

Loading comments...

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