Multiprocessor Scheduling

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.

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">{{hint}}</p>
<div id="pool" class="pool"></div>
<div id="machines" class="machines"></div>
<div class="status" id="status">{{makespan_dash}}</div>
<div class="btns">
  <button id="greedy" type="button">{{btn_greedy}}</button>
  <button id="optimal" type="button">{{btn_optimal}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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: $m^{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.

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

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.