  Scheduling is a critical part of practical computer systems, and scheduling
has also been extensively studied from a theoretical perspective.
Unfortunately, there is a gap between theory and practice, as the optimal
scheduling policies presented by theory can be difficult or impossible to
perfectly implement in practice. In this work, we use recent breakthroughs in
queueing theory to begin to bridge this gap. We show how to translate
theoretically optimal policies -- which provably minimize mean response time
(a.k.a. latency) -- into near-optimal policies that are easily implemented in
practical settings. Specifically, we handle the following real-world
constraints:
  - We show how to schedule in systems where job sizes (a.k.a. running time)
are unknown, or only partially known. We do so using simple policies that
achieve performance very close to the much more complicated theoretically
optimal policies.
  - We show how to schedule in systems that have only a limited number of
priority levels available. We show how to adapt theoretically optimal policies
to this constrained setting and determine how many levels we need for
near-optimal performance.
  - We show how to schedule in systems where job preemption can only happen at
specific checkpoints. Adding checkpoints allows for smarter scheduling, but
each checkpoint incurs time overhead. We give a rule of thumb that
near-optimally balances this tradeoff.
