Uniform Bounds for Scheduling with Job Size Estimates

Ziv Scully, Isaac Grosof, Michael Mitzenmacher

TL;DR

This paper tackles the challenge of scheduling jobs to minimize average waiting time when only estimates of job durations are available. The authors introduce a novel scheduling policy, SRPT-B, that provides provably good performance even with imperfect estimates, a significant improvement over existing methods that can degrade drastically.

What Problem Does This Paper Address?

In many real-world systems, like cloud computing or network routing, we need to schedule tasks (jobs) to minimize the time they spend waiting to be processed (mean response time). The ideal scheduling strategy, Shortest Remaining Processing Time (SRPT), works perfectly if we know the exact processing time of each job. However, in practice, we often only have estimates of these job sizes. These estimates are usually imperfect, meaning a job with true size 's' might have an estimated size within a range [βs, αs], where α is an "upper bound" and β is a "lower bound" on the estimation error. The core problem this paper addresses is: can we design a scheduling policy that performs well (close to optimal SRPT) even with these imperfect estimates, and importantly, does this performance degrade gracefully as the estimation error increases? Ideally, this policy should also be implementable without knowing the exact error bounds (α and β).

Methods

The authors introduce and analyze several scheduling policies. They use a standard M/G/1 queue model, which assumes jobs arrive randomly (Poisson process) and have general processing time distributions. The key innovation lies in designing and analyzing new scheduling policies:

  • SRPT-E (SRPT with Estimates): A straightforward approach where SRPT uses the estimated job size instead of the true size.
  • PSJF-E (Preemptive Shortest Job First with Estimates): Similar to SRPT-E, but based on the Preemptive Shortest Job First (PSJF) policy.
  • SRPT-B (SRPT with Bounce): The paper's main contribution. This is a novel variant of SRPT that modifies the job's "rank" (priority) based on its estimated size and age. Crucially, it incorporates a "bounce" mechanism to prevent the rank from becoming excessively negative, which is a weakness of SRPT-E.
  • SRPT-SE (SRPT with Scaling Estimates): A theoretical tool used for analysis, which is not directly implementable but helps bridge the gap between SRPT and SRPT-B.

The analysis relies on two main techniques: the "work integral" method and the "tagged job" method. These methods allow for precise mathematical characterization of the mean response time under different policies.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis within a stochastic queueing model.

Key Insights and Ideas

  • SRPT-E is fundamentally flawed: The paper demonstrates that simply using estimated job sizes with the optimal SRPT policy (SRPT-E) can lead to arbitrarily bad performance, especially when estimates are consistently too low (small β). This is a crucial finding, as SRPT-E is an intuitive first attempt.
  • Graceful degradation is key: Instead of perfect robustness (guaranteed performance regardless of error), the authors focus on "graceful degradation" – ensuring performance degrades smoothly as estimation error increases. This is a more realistic and achievable goal.
  • The "bounce" in SRPT-B is critical: The novel SRPT-B policy's success hinges on its "bounce" mechanism. By capping the job's rank at its initial estimated size, it avoids the extreme delays that SRPT-E can suffer from when large jobs are severely underestimated.
  • PSJF-E offers a good balance: While SRPT-B is the primary focus for achieving consistency and graceful degradation, PSJF-E is shown to offer strong performance guarantees, particularly in terms of its approximation ratio relative to the non-estimated PSJF policy.

Key Results

  • SRPT-E's approximation ratio can be infinite: For any job size distribution, there exist estimation errors (specifically, when β < 1) such that SRPT-E's mean response time can be arbitrarily large compared to the optimal SRPT.
  • SRPT-B achieves consistency and graceful degradation:
    • Its approximation ratio is at most 3.5α/β.
  • As estimation errors (α, β) approach 1, its approximation ratio approaches 1 uniformly.
  • It performs well without needing to know α or β.
  • PSJF-E also performs well:
    • Its approximation ratio relative to PSJF is at most α/β.
  • This implies an approximation ratio of at most 1.5α/β relative to the optimal SRPT.

Limitations and Future Work

  • Robustness is unachievable: The paper proves that achieving constant-factor robustness (guaranteed performance regardless of estimation error) is impossible in this setting. This is a fundamental limitation of online scheduling with predictions.
  • Continuous distributions assumed: The analysis relies on continuous job size and estimate distributions to avoid complex tie-breaking scenarios. Handling discrete distributions would require more intricate proofs.
  • Tightening bounds: The authors suggest that the bounds on approximation ratios could potentially be tightened.
  • Other estimation models: Exploring different models of estimation error (e.g., Gaussian errors, adversarial errors) is a promising direction.
  • Practical implementation: While SRPT-B is theoretically sound, PSJF-E is recommended for practical settings due to its simplicity and strong performance. Further investigation into optimizing SRPT-B's "bounce" mechanism is also suggested.

Summary updated

Abstract

We consider the problem of scheduling to minimize mean response time in M/G/1 queues where only estimated job sizes (processing times) are known to the scheduler, where a job of true size s has estimated size in the interval [β s, α s] for some α ≥ β > 0. We evaluate each scheduling policy by its approximation ratio, which we define to be the ratio between its mean response time and that of Shortest Remaining Processing Time (SRPT), the optimal policy when true sizes are known. Our question: is there a scheduling policy that (a) has approximation ratio near 1 when α and β are near 1, (b) has approximation ratio bounded by some function of α and β even when they are far from 1, and (c) can be implemented without knowledge of α and β? We first show that naively running SRPT using estimated sizes in place of true sizes is not such a policy: its approximation ratio can be arbitrarily large for any fixed β < 1. We then provide a simple variant of SRPT for estimated sizes that satisfies criteria (a), (b), and (c). In particular, we prove its approximation ratio approaches 1 uniformly as α and β approach 1. This is the first result showing this type of convergence for M/G/1 scheduling. We also study the Preemptive Shortest Job First (PSJF) policy, a cousin of SRPT. We show that, unlike SRPT, naively running PSJF using estimated sizes in place of true sizes satisfies criteria (b) and (c), as well as a weaker version of (a).
BibTeX
@inproceedings{scully2022uniform,
  author = {Ziv Scully and Isaac Grosof and Michael Mitzenmacher},
  title = {{Uniform Bounds for Scheduling with Job Size Estimates}},
  booktitle = {ITCS},
  year = {2022},
  doi = {10.4230/lipics.itcs.2022.114},
}
Figure