  By executing jobs serially rather than in parallel, size-based scheduling
policies can shorten time needed to complete jobs; however, major obstacles to
their applicability are fairness guarantees and the fact that job sizes are
rarely known exactly a-priori. Here, we introduce the Pri family of size-based
scheduling policies; Pri simulates any reference scheduler and executes jobs in
the order of their simulated completion: we show that these schedulers give
strong fairness guarantees, since no job completes later in Pri than in the
reference policy. In addition, we introduce PSBS, a practical implementation of
such a scheduler: it works online (i.e., without needing knowledge of jobs
submitted in the future), it has an efficient O(log n) implementation and it
allows setting priorities to jobs. Most importantly, unlike earlier size-based
policies, the performance of PSBS degrades gracefully with errors, leading to
performances that are close to optimal in a variety of realistic use cases.
