One fact, one missing number

Why is total busy time fixed under every work-conserving policy, and which number would make ordering easy?

CaseConstructed case · Lena at Brightlane

A 2-second query that waits 40 minutes

Three things look wrong on Hub in the same week.

A dashboard query that takes 2 seconds when the cluster is quiet waits 40 minutes at 10:00, because a big nightly-style report was submitted just before it.
Omar submits a training job that needs 64 machines at once. The cluster shows 30% idle, yet the job sits in "pending" for hours.
The finance team has a promised floor of 30% of the cluster. At month end they submit work, and it takes an hour before they actually get their share, even though the policy says "guaranteed."

None of these is a bug. Each is a known property of a scheduling policy. This article goes through the policies one by one. Remember the key fact from What scheduling is: the best ordering (shortest first) needs the run time, and the run time is the one number we do not have.

How it ends →

The fact. For any work-conserving policy, total busy time is the same (see the 1-minute and 100-minute example in Work is conserved). Only mean flow time changes.

The missing number. To run the short job first, you must know which job is the short one. SRPT (shortest-remaining-processing-time) is provably optimal for mean flow time. You cannot run it, because job duration is unknown at admission.

Every policy below is a different answer to the question: "What do I do without that number?"