Algorithms to Live By · ch.5 · scheduling
📋 Chapter 5 · First things first

Scheduling:
what to do first

You can't do everything at once, so the only question is order — and the right order depends entirely on what you're trying to minimise. Pick your metric and the algorithm falls out.

Chapter 4 was about what to keep close. This one is about what to touch next. It's the most quotidian chapter in the book — it's literally your to-do list — and also the one with the sharpest teeth, because scheduling theory has an answer your productivity app doesn't: there is no such thing as a good schedule until you say what “good” means.

Say it, and the algorithm shows up unannounced. Most of them are one line long.

1One person, many tasks

Here's Tuesday. Six things need doing: a reply someone's waiting on, an expense report, a broken build, a slide deck, a quarterly review, an RFC you promised to read. Each takes some amount of time. Each has a moment by which it should be done. And there is exactly one of you.

Notice what you can't do. You can't make the work smaller — three hours of build-fixing is three hours whatever order you fix it in. You can't clone yourself. You can't stop the clock. Strip away everything you have no control over and precisely one lever is left in your hand: order.

Which sounds like a thin lever, and isn't. Order won't change when you finish everything — that's the sum of the durations, fixed. But it changes almost every other thing you might care about: how late the worst offender is, how many things slip at all, how long everyone else spends waiting on you. Move the eight-hour review to the front of the day and five people wait eight hours. Move it to the back and they don't wait at all. Same work. Same day. Wildly different Tuesday.

So the good news is there's a right answer. The catch is in the next section.

🧮
The setup has a name in the literature — single-machine scheduling — and the “machine” is you. One worker, a pile of jobs, each with a duration and a deadline. It's the simplest scheduling problem there is, which is exactly why its results are so unreasonably useful: they're about the constraint you actually live under.

2Name your goal first

Ask a scheduling theorist for the optimal schedule and they'll ask you a question back: optimal at what? Not to be difficult. Because the question is genuinely unanswerable until you say.

Pick any of these and you've picked a different day:

  • Nothing should be embarrassingly late. You care about the single worst overshoot — one thing three weeks overdue is a disaster; six things an hour late is Tuesday.
  • Miss as few deadlines as possible. You don't care how late; you care about the count. Four broken promises is worse than one broken promise, even if the one is worse.
  • Don't make people wait. Nothing has a hard deadline, but every hour a task sits undone is an hour somebody is blocked on you.

Those are three different goals and they have three different algorithms, and — this is the part worth pinning to a wall — a schedule that's optimal for one is usually mediocre for the others. There is no schedule that wins everything. There isn't even a schedule that's a decent compromise across all three, most days.

Which relocates the entire difficulty. You probably assumed the hard part of scheduling was finding the good order — the searching, the tetris, the app with the drag handles. It isn't. Once the goal is named, the answer is almost always a sort, and you'll have it in a second. The hard part is the naming. That's the work. Everything after it is sortBy.

🎯
If you've ever reorganised your to-do list for forty minutes and felt no better, this is why: you were optimising without an objective function. You can't sort a list until you know what you're sorting by, and “important-ish, soon-ish” is not a key. Name the metric — even out loud, even badly — and the list mostly sorts itself.

3Earliest Due Date

Goal: nothing embarrassingly late. Minimise the worst overshoot across everything on the list.

Do things in the order they're due. That's the algorithm. That's the whole algorithm.

It sounds like a shrug and it's a theorem: sorting by due date and grinding straight through, no cleverness, no exceptions, provably minimises the maximum lateness of the set. Nothing beats it. Not a smarter heuristic, not a solver, not an afternoon of agonising. The proof is a swap argument you can do in your head — if two adjacent tasks are out of due-date order, swapping them can't make the worst offender worse — but the useful thing is the shape of the result: a sort you already know how to do is already the best you can do.

And you do already do it. The evening before a deadline pile-up, when you stop deliberating and just do the thing due soonest, then the next thing due soonest — that panic is well-calibrated. Waiters clearing a section, ER triage nurses working a queue, everyone at the DMV: earliest due date, all the way down. The formal name is Earliest Due Date, and the reason to know it isn't to start doing it. It's to stop second-guessing yourself when you already are.

⚖️
Notice EDD ignores durations completely. It never asks how long anything takes — a two-minute email due Friday goes after a forty-hour report due Thursday, no argument. That looks like a bug and it's the point: for this metric, duration is irrelevant. It's also the first hint that it's the wrong metric for a lot of days.

4When something has to go

Goal: miss as few deadlines as possible. Now you don't care how late a thing is — an hour or a month, it's one broken promise either way. You want the count down.

Start out like EDD: go by due date, adding tasks to your plan one at a time. But now watch the clock as you go. The moment the plan can't fit the task you just added — you'd finish it after it's due — throw out the biggest task you've scheduled so far. Not the one that broke the plan. The longest one in it. Then carry on.

Read that twice, because it's counterintuitive and it's correct. The task that just tipped you over the edge may be small and harmless; the thing actually eating your calendar might be something you cheerfully scheduled two steps ago. Dropping the giant buys back the most room for the least damage — one broken promise, and everything downstream fits again. That's Moore's algorithm, and it's optimal: no plan misses fewer deadlines.

What it says out loud is the thing calendars are too polite to: when you're over capacity, the move isn't working harder or resequencing more cleverly. It's deleting the one that eats the calendar. And the dropped tasks aren't magically gone — they go to the end, done late, in whatever order you like. They're already late; their order can't make things worse.

🪓
Be honest about the assumption, because it's a big one: Moore's algorithm treats late as late. A millisecond overdue and a month overdue score identically. That's true of some things (a flight, a submission window, a birthday) and grotesquely false of others (rent). If overshoot size matters, you wanted EDD. Choosing between them is choosing between “how bad is the worst one” and “how many are there” — and that choice is yours, not the algorithm's.

5Do the quick thing first

Goal: don't make anyone wait. Drop deadlines entirely — nothing's due, but every hour a task sits unfinished is an hour of somebody drumming their fingers. Add up all that sitting-around time across every task. Minimise the total.

Do the quickest thing first. Then the next quickest. All the way down.

The intuition is that finishing a task doesn't just help that task — it stops the clock for it, permanently, and every task still in the queue behind a long job is paying for that job with its own waiting time. A five-minute job in front of a five-hour job costs the queue five minutes. Reverse them and it costs five hours. So you front-load the cheap wins, not out of cowardice but because each one you retire is one fewer thing accruing wait. Shortest Processing Time, and it's optimal for this metric — nothing does better.

This is the closest thing to a universal productivity law in the chapter, and it's the mathematical vindication of every “just knock out the two-minute stuff first” blog post ever written. That advice is usually justified with something about momentum and dopamine. It doesn't need to be. It's a theorem.

The obvious objection — but some things matter more than others — is already handled. Give each task an importance weight, and divide it by how long the task takes. Do the highest ratio first. It's a bang-for-the-buck sort: importance per hour spent. A task twice as important as another but three times as long goes second. This is weighted Shortest Processing Time, and if you want one sentence to run your working life on, it is: only prioritise a task that takes twice as long if it's more than twice as important.

💸
You already run weighted SPT on money — it's the debt avalanche, paying down the highest interest per dollar rather than the biggest balance. Same sort, different units. It's also, less flatteringly, why an inbox of one-line replies feels so productive: those are genuinely the highest-ratio items on the list. The trap isn't doing them. It's that the ratio ranks them above the thing that mattered, and the ratio isn't wrong — your weights are.

Four goals, four sorts, one Tuesday. Below is that Tuesday — the six real tasks, with real durations and real deadlines. Hit each policy and watch all four scorecards at once. The point isn't which one wins. It's that each one wins exactly its own metric and loses the rest, every time, and no amount of dragging finds an order that wins them all. Drag the rows to try.

Interactive · drag rows to reorder · click to edit Every metric recomputed live · ✓ marks the metric this order wins
editing takes 0h due 0h weight 0
Max lateness
Things late
Total waiting
Weighted waiting
work lateness (past the flag) ▼ due date policy: Earliest Due Date
🧷
Try it and the pattern is stubborn: EDD owns max lateness, Moore owns the count of late things (by cheerfully wrecking max lateness — the dropped giants land very late), SPT owns total waiting, weighted SPT owns weighted waiting. Four optimal schedules. Four different orders. The only question you get to answer is which column you're reading.

6The mattress in the road

July 1997. The Mars Pathfinder is on the surface, it works, everyone is delighted — and then it starts resetting itself. Total system reboots, data lost, for no reason anyone on Earth can see. The rover is fine. The science is fine. The scheduler is eating itself alive.

Here's what was happening, in human terms. A high-priority task needed a shared resource — a bus, a lock, a thing only one task can hold at a time. A low-priority task had it. Fine: high waits for low to finish and hand it over. Except low never got to finish, because a swarm of medium-priority tasks kept preempting it — they outranked low, so they ran, over and over, while low sat there holding the one lock the most important task in the system was waiting on. The highest-priority task in the machine was effectively the lowest, blocked forever behind work that mattered less than it did. A watchdog timer noticed the important thing hadn't happened and did the only thing watchdogs do: reboot.

The name is priority inversion. The fix, once you say it, is almost insultingly obvious: if an important task is blocked on a trivial one, the trivial one is no longer trivial. Let the lock-holder temporarily inherit the priority of the task it's blocking. Low gets promoted to high, sails past the medium swarm, finishes in a blink, drops the lock, and reverts. That's priority inheritance, and it's what JPL uploaded to a computer on another planet to save the mission.

It transfers to a life directly, and painfully. The mattress lying in the road is not important. It is a mattress. But if it's between you and everywhere you need to go, it just became the most important object in your life, and no amount of correctly ranking your goals will move it. Whatever is blocking your top priority inherits your top priority. The unreturned phone call, the form nobody will sign, the three-line config change gating the whole quarter — those aren't small tasks you'll get to. They're your most important task wearing a disguise.

Interactive · three tasks, one lock A real tick-by-tick scheduler · watch HIGH starve
LOW takes the lock first. HIGH will want it.
HIGH finishes at
HIGH blocked for
Lock held by
With inheritance
running blocked on the lock ready, preempted 🔒 holds the lock
🛰️
Play it with inheritance off and the shape of the disaster is right there: HIGH sits in a red bar doing nothing for most of the timeline while MEDIUM — work nobody would call urgent — runs happily to completion. Flip inheritance on and LOW gets promoted the instant HIGH blocks, the medium swarm loses its window, and HIGH finishes roughly twice as early. Nothing got faster. Nothing got dropped. The order changed.

7When switching eats the day

Every time you put one thing down and pick another up, you pay. Not metaphorically — the state you had loaded (where you were, what you'd ruled out, the shape of the thing in your head) has to be dumped and rebuilt. Ten seconds for an email. Twenty minutes for a hard bug. The cost is real, it's per switch, and it produces nothing.

Which is fine at low volume and catastrophic at high. Because the switch cost doesn't care how much work you got done between switches — it's a flat tax per transition — the fraction of your day it consumes rises with the interruption rate until it reaches all of it. And there's a second, meaner effect underneath: as the gaps between interruptions shrink, they eventually get shorter than the time it takes to get anywhere on real work. At that point you're not doing less work. You're doing none — every fragment spent loading a context you're about to lose. The machine is at 100% utilisation and its output is zero.

Operating systems have a name for this and it is perfect: thrashing. It's the state where the system is maxed out, working flat out, sweating, and achieving nothing, because all of its capacity has gone into the overhead of managing its own workload. You have felt this. You called it a bad day.

The escapes are unglamorous and they work:

  • Do things in a worse order, but actually do them. Thrashing has one bit of good news: any order beats no order. If you're thrashing, the optimal schedule you're failing to compute is worth less than a mediocre one you execute. Grab something. Anything.
  • Batch the interruptions. Don't handle each one when it lands; let them pool, then handle the pile in one go. You do the same amount of interrupt work and pay the switch tax four times instead of forty. Operating systems call this interrupt coalescing — a mouse that reported every micro-movement instantly would use a whole CPU on nothing. Your version is checking email at 11 and 4, and the reason it works isn't discipline. It's arithmetic.
  • Declare bankruptcy. Drop the queue. Announce it. The tasks were not getting done anyway; all they were doing was costing you the overhead of continuing to schedule them.

Timeboxing is interrupt coalescing for humans, and that's the whole of its magic. The block on your calendar isn't sacred and doesn't need to be. It just needs to be long enough that the tax is a rounding error instead of the bill.

Interactive · one hour of your life Drag the sliders until it goes to zero — it will
6
3 min
Useful work / hr
Lost to switching
Longest clear block
Status
real work switch overhead fragment too short to get anywhere
🔥
Push interruptions up with the cost at 3 minutes and watch for the cliff. It isn't gentle. Output declines, declines, declines — and then the gaps drop under the minimum block you need to get anywhere and the whole hour goes dead at once. That discontinuity is why thrashing feels like it arrives from nowhere: you don't get a warning, you get a wall. Now hit batching and watch the same hour come back to life.

8Preemption isn't free

Everything above has an unpriced assumption in it. Moore's algorithm, weighted SPT, priority inheritance — they all involve dropping what you're doing when something better-ranked shows up. And dropping what you're doing costs a switch. The theory bills that at zero. Your day does not.

So there's a trade you can't escape: responsiveness versus throughput. A schedule that reacts to everything is maximally responsive and finishes nothing — it's the thrashing hour, correctly prioritised the entire way down. A schedule that reacts to nothing has beautiful throughput and misses the fire. Every scheduler ever written sits somewhere on that line, and so do you, and there is no setting that is good at both. There is only a setting you chose versus one that happened to you.

The lever operating systems reach for is a floor: a minimum useful block. Below some quantum, don't switch — the overhead exceeds the benefit, so finish the slice first. Pick yours. Twenty-five minutes, ninety, an afternoon; the number matters much less than the fact that it exists and that you know it. Then honour it, and let the world queue.

Which is the chapter's last and least algorithmic point. Every rule here — do the earliest due, drop the giant, quickest first, promote the blocker — is a sort you can do in a second. What none of them will do for you is name the metric, or defend the block. That part is yours.

Note the recursion: deciding how responsive to be is itself a scheduling decision, and thinking about it costs time you could have spent working. Scheduling theorists ran into this too — some scheduling problems are so hard that solving them optimally takes longer than doing the work badly. Which is a Chapter 8 problem, and the answer there is going to be: relax the problem until it's easy, then live with the approximation.

9Every policy is one sort

Here's the claim from section 2, cashed out in code. Same Task record, same list, four goals — and each policy is a single sortBy with a different key. Not a solver. Not a search. A key.

Moore's algorithm is the only one that needs more than a line, and only because it deletes: it's a fold over the due-date order carrying the accepted set, evicting the longest job whenever the plan overflows. Flip between the languages — same shape both sides.

💡
Stare at those three one-liners. They are the same function with three different keys, and each one is provably optimal — for its own metric, and hopeless for the other two. All the intelligence in the system lives in the argument you passed. Choosing the metric is the whole job; the algorithm is what falls out afterwards, and it costs you a line.

10Check yourself

3 questions · instant feedback 0 / 3

11What's coming

Every algorithm in this chapter was handed its facts. The durations were known, the due dates were known, the weights were known — sort and go. Real Tuesdays don't work like that. You get one data point, or two, and you have to guess the rest of the distribution from it. How long will this take? How long has it already been running, and what does that tell you about how much is left?

Next chapter: how to predict from almost nothing, and why the single most useful thing you can bring to a guess isn't the evidence at all.

🎲
Up next · Chapter 6
Bayes's Rule
Predicting from thin evidence. Why a play that's run for a hundred years will probably run another hundred, why a five-minute wait suggests five more minutes, and how one number you had before you looked does most of the work.