Introduction

You have a stack of jobs of different lengths and a few machines (or workers, or processors) to run them. Every machine works in parallel, but each job sits on exactly one machine. When does the last job finish? You want that moment — the makespan — to be as early as possible.

That's the heart of the scheduling problem. Split the work evenly and everyone finishes together; split it badly and one machine groans under a pile while another sits idle.

It feels like something you'd balance by eye, and for a handful of jobs you can. But finding the provably earliest finish, every time, is one of the classic hard problems — the same difficulty that hides in bin packing.

The Greedy Rule

The natural strategy is list scheduling: take the jobs one by one and put each on whichever machine is currently least busy. Simple, and it never leaves a machine idle while work waits.

As with bin packing, the order matters — and the same fix works wonders. Longest Processing Time (LPT) sorts the jobs from longest to shortest first, then runs list scheduling. The big jobs are placed while everything is empty, and the small jobs fill the gaps to even things out.

LPT is provably good: its makespan is never worse than about 4/3 of the best possible. For a rule you could run in your head, that's impressively close. But "close" still isn't "optimal".

Balance the Machines

Try it. Below are several jobs and three machines. Click a job, then click a machine to run it there. Your goal is to make the finish time — the moment the busiest machine is done — as early as possible.

Watch the timeline: a single long job dropped on an already-busy machine pushes the finish line out. The dashed marker is the lower bound, the earliest any schedule could possibly finish.

<p class="hint">Three machines run in parallel. Click a job, then click a machine to run it there.
    Make the <b>finish time</b> — when the busiest machine is done — as early as possible. Or press
    <b>Auto (LPT)</b> to let the longest-job-first rule balance the load.</p>
<div class="tray-label">Jobs to run (length in time units):</div>
<div id="tray" class="tray"></div>
<div id="machines" class="machines"></div>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="lpt" type="button">Auto (LPT)</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 .6rem; line-height: 1.45; }
.tray-label { font-size: .82rem; font-weight: 600; color: #555; margin-bottom: .25rem; }
.tray { display: flex; flex-wrap: wrap; gap: .4rem; min-height: 40px; padding: .4rem; background: #f4f4f4; border-radius: 8px; margin-bottom: .7rem; }
.job { height: 34px; border-radius: 6px; border: 2px solid rgba(0,0,0,.15); color: #fff; font: 700 13px system-ui; display: flex; align-items: center; justify-content: center; cursor: pointer; user-select: none; }
.job.sel { outline: 3px solid #111; outline-offset: 1px; }
.machines { position: relative; display: flex; flex-direction: column; gap: .4rem; }
.lane-row { display: flex; align-items: center; gap: .5rem; cursor: pointer; }
.lane-name { font-size: .8rem; font-weight: 600; color: #555; width: 78px; flex: none; }
.lane { flex: 1; display: flex; height: 32px; background: #eee; border-radius: 6px; overflow: hidden; position: relative; }
.seg { height: 100%; display: flex; align-items: center; justify-content: center; color: #fff; font: 700 12px system-ui; border-right: 1px solid rgba(255,255,255,.5); }
.lbmark { position: absolute; top: -4px; bottom: -4px; width: 0; border-left: 2px dashed #c0392b; }
.status { font-size: 1rem; font-weight: 700; min-height: 1.3em; margin: .5rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }
.bar-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Multiprocessor scheduling: assign jobs to machines to minimize the makespan
// (the finish time of the busiest machine). NP-hard; the LPT rule gets close.
const NM = 3;
const UNIT = 34;            // px per time unit
const SCALE = 11;           // lane shows up to ~11 time units wide
const COLORS = ['#e63946', '#2a9d8f', '#457b9d', '#e9c46a', '#8e7dbe', '#e07a5f', '#3d8361'];
const JOBS = [3, 1, 4, 1, 5, 2, 2].map((len, id) => ({ id, len, m: -1 }));
let selected = null;

const loadOf = m => JOBS.filter(j => j.m === m).reduce((s, j) => s + j.len, 0);
const makespan = () => Math.max(0, ...Array.from({ length: NM }, (_, m) => loadOf(m)));
const lowerBound = () => {
  const total = JOBS.reduce((s, j) => s + j.len, 0);
  return Math.max(Math.max(...JOBS.map(j => j.len)), Math.ceil(total / NM));
};

function render() {
  const tray = document.getElementById('tray');
  tray.innerHTML = '';
  JOBS.filter(j => j.m === -1).forEach(j => {
    const el = document.createElement('div');
    el.className = 'job' + (selected === j.id ? ' sel' : '');
    el.style.background = COLORS[j.id % COLORS.length];
    el.style.width = (j.len * UNIT) + 'px';
    el.textContent = j.len;
    el.addEventListener('click', () => { selected = (selected === j.id ? null : j.id); render(); });
    tray.appendChild(el);
  });
  if (!tray.children.length) tray.innerHTML = '<span style="color:#888;font-size:.85rem">All jobs assigned.</span>';

  const box = document.getElementById('machines');
  box.innerHTML = '';
  const lb = lowerBound();
  for (let m = 0; m < NM; m++) {
    const row = document.createElement('div');
    row.className = 'lane-row';
    row.innerHTML = fmt('<div class="lane-name">Machine %v%</div>', { v: m + 1 });
    const lane = document.createElement('div');
    lane.className = 'lane';
    JOBS.filter(j => j.m === m).forEach(j => {
      const seg = document.createElement('div');
      seg.className = 'seg';
      seg.style.background = COLORS[j.id % COLORS.length];
      seg.style.width = (j.len / SCALE * 100) + '%';
      seg.textContent = j.len;
      seg.title = 'Click to remove';
      seg.addEventListener('click', e => { e.stopPropagation(); j.m = -1; selected = null; render(); });
      lane.appendChild(seg);
    });
    const mark = document.createElement('div');
    mark.className = 'lbmark';
    mark.style.left = (lb / SCALE * 100) + '%';
    lane.appendChild(mark);
    row.appendChild(lane);
    row.addEventListener('click', () => { if (selected !== null) { JOBS[selected].m = m; selected = null; render(); } });
    box.appendChild(row);
  }

  const st = document.getElementById('status');
  const ms = makespan();
  const allAssigned = JOBS.every(j => j.m >= 0);
  if (!allAssigned) {
    st.className = 'status';
    st.textContent = fmt('Finish time so far: %ms%. Assign every job — the earliest possible is %lb%.', { ms: ms, lb: lb });
  } else if (ms <= lb) {
    st.className = 'status ok';
    st.textContent = fmt('Finish time: %ms% — that’s the earliest possible! 🎉', { ms: ms });
  } else {
    st.className = 'status bad';
    st.textContent = fmt('Finish time: %ms%. Can you reach %lb%?', { ms: ms, lb: lb });
  }
}

function lpt() {
  JOBS.forEach(j => j.m = -1);
  [...JOBS].sort((a, b) => b.len - a.len).forEach(j => {
    let best = 0;
    for (let m = 1; m < NM; m++) if (loadOf(m) < loadOf(best)) best = m;
    j.m = best;
  });
  selected = null;
  render();
  console.log(fmt('LPT makespan %makespan% (lower bound %lowerBound%).', { makespan: makespan(), lowerBound: lowerBound() }));
}

document.getElementById('lpt').addEventListener('click', lpt);
document.getElementById('reset').addEventListener('click', () => { JOBS.forEach(j => j.m = -1); selected = null; render(); });
render();
Result
Console

Stuck? Press Auto (LPT) to watch the longest-first rule balance the load. It's fast and usually lands right on the lower bound — but, like every greedy heuristic here, it carries no guarantee of being perfect.

The Real Complexity

How hard is scheduling?

  • Checking a schedule is trivial: add up each machine's jobs and take the largest total.
  • Minimizing the makespan on just two machines is already NP-hard — it's exactly the number partitioning problem (split a set of numbers into two equal-sum halves), a close relative of Subset Sum.
  • But approximations are excellent. LPT stays within 4/3 of optimal, and full approximation schemes get within any chosen percentage.
  • Richer versions get harder: add deadlines, precedence between jobs, or different machine speeds, and the difficulty grows — yet good heuristics keep delivering.

So scheduling sits in the familiar comfortable middle: exact optimum intractable, near-optimal cheap and reliable.

Where It Matters

Anywhere work is shared across parallel resources, scheduling decides the finish line:

  • Manufacturing: assigning jobs to machines on a factory floor to ship orders sooner.
  • Operating systems: spreading processes and threads across CPU cores.
  • Cloud clusters: distributing compute tasks over thousands of servers.
  • Airlines and transport: assigning crews and aircraft to routes within tight constraints.
  • Project management: dividing tasks among a team to hit a deadline.

Shaving the makespan means delivering faster with the same resources — a direct, measurable win, which is why "near-optimal, instantly" is exactly what these systems run on.

Conclusion

Balancing a pile of jobs across a few machines feels like common sense — until you demand the earliest possible finish, guaranteed. That guarantee is NP-hard, equivalent to splitting numbers into perfectly equal halves. And yet a rule as humble as "longest job first, least-busy machine" walks right up to the optimum almost every time.

It's the recurring bargain of this whole field: the exact answer hides behind intractability, but a clever, simple heuristic gets us almost all the way there, instantly. For the systems that keep our factories, computers and schedules moving, that's exactly the deal that makes them work.

Share this article

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

Comments

Loading comments...

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