Scheduling

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

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">{{hint}}</p>
<div class="tray-label">{{tray_label}}</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">{{btn_auto}}</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 .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; }

// Code not found

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.

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.

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.

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.