Online Scheduling on Identical Machines using SRPT

Kyle Fox, Benjamin Moseley

TL;DR

This paper resolves a decade-old open problem in scheduling theory by proving that the Shortest Remaining-Processing-Time (SRPT) algorithm is "scalable" on multiple identical machines. The authors show that with just a tiny bit of extra processing speed (resource augmentation), SRPT achieves a constant competitive ratio for both average flow time and the more fairness-oriented $\ell_k$-norms of flow time.

What Problem Does This Paper Address?

In the world of online scheduling, jobs arrive at unpredictable times, and a scheduler must decide which jobs to run on which machines to minimize "flow time"—the total time a job spends in the system (waiting time + processing time).

On a single machine, SRPT is the undisputed king; it is mathematically optimal for minimizing average flow time. However, the story gets complicated with $m$ identical machines. While SRPT was known to be a strong performer, a significant theoretical gap persisted: researchers didn't know if SRPT was scalable.

An algorithm is "scalable" if, when given machines that are slightly faster (by a factor of $1+\epsilon$) than an optimal offline adversary, it can maintain a performance within a constant factor of that adversary. This paper specifically tackles Open Problem 2.9 from a well-known 2004 survey, asking if SRPT is $(1+\epsilon)$-speed $O(1)$-competitive.

Methods

The authors use potential function analysis, a standard but powerful technique for analyzing online algorithms.

  1. The Framework: They define a potential function $\Phi(t)$ that represents the "distance" or "debt" between the state of the SRPT algorithm and the state of an optimal offline scheduler (OPT) at any time $t$.
  2. The Innovation: The core contribution is the design of two novel potential functions—one for average flow time and a more complex one for $\ell_k$-norms. These functions are designed to "absorb" the changes that happen when new jobs arrive or when the machines are running, ensuring that the total cost of SRPT plus the change in potential remains bounded.
  3. Resource Augmentation: By assuming SRPT has $(1+\epsilon)$ speed, the authors can show that the algorithm "pays off" its debt to the potential function faster than the adversary can create it.

Datasets

Not discussed in the paper. As a theoretical computer science paper, the results are proven mathematically for all possible job sequences rather than tested against specific empirical datasets.

Key Insights and Ideas

  • SRPT is Scalable: The most important takeaway is that SRPT is indeed scalable. This confirms the long-held intuition that SRPT is the "best possible" online algorithm for this setting when job migration (moving a job from one machine to another) is allowed.
  • Balancing Efficiency and Fairness: While average flow time is a standard metric, it can lead to "starvation" (where a large job waits forever). The authors show that SRPT also performs well under $\ell_k$-norms, which penalize long wait times more heavily, thus providing a theoretical guarantee for fairness.
  • Potential Functions as Structural Maps: The paper suggests that their new potential functions capture the underlying structure of how SRPT manages work across multiple machines, which could be useful for analyzing other scheduling problems.

Key Results

The paper provides two main quantitative bounds:

  • Average Flow Time: SRPT is $(1+\epsilon)$-speed $4/\epsilon$-competitive. This means if SRPT's machines are 10% faster than the adversary's, its total flow time will be at most 40 times the optimal.
  • $\ell_k$-norms of Flow Time: SRPT is $(1+\epsilon)$-speed $4/\epsilon^2$-competitive for $k \ge 1$. This is the first such result for SRPT on multiple machines for this metric.

These results show that SRPT is essentially the best possible online algorithm in almost every aspect when migration is permissible.

Limitations and Future Work

  • Migration Requirement: The analysis assumes that jobs can be migrated between machines without penalty. In some real-world systems, moving a job's state between processors is expensive.
  • The "1-Competitive" Threshold: While the paper proves SRPT is $O(1)$-competitive with any speedup, it remains an open question exactly how much speed is required to make an online algorithm 1-competitive (performing exactly as well as the optimal offline adversary). Current bounds suggest this threshold lies somewhere between $22/21$ and $2$.
  • Non-Identical Machines: The results apply to identical machines; extending these scalability proofs to "unrelated" machines (where different machines have different speeds for different jobs) remains a significant challenge.

Summary updated

Abstract

Due to its optimality on a single machine for the problem of minimizing average flow time, Shortest-Remaining-Processing-Time (SRPT) appears to be the most natural algorithm to consider for the problem of minimizing average flow time on multiple identical machines. It is known that SRPT achieves the best possible competitive ratio on multiple machines up to a constant factor. Using resource augmentation, SRPT is known to achieve total flow time at most that of the optimal solution when given machines of speed . Further, it is known that SRPT's competitive ratio improves as the speed increases; SRPT is s-speed -competitive when . However, a gap has persisted in our understanding of SRPT. Before this work, the performance of SRPT was not known when SRPT is given (1 + ε)-speed when , even though it has been thought that SRPT is (1 + ε)-speed O(1)-competitive for over a decade. Resolving this question was suggested in Open Problem 2.9 from the survey “Online Scheduling” by Pruhs, Sgall, and Torng [PST04], and we answer the question in this paper. We show that SRPT is scalable on m identical machines. That is, we show SRPT is (1 + ε)-speed -competitive for ε > 0. We complement this by showing that SRPT is (1 + ε)-speed -competitive for the objective of minimizing the ℓk-norms of flow time on m identical machines. Both of our results rely on new potential functions that capture the structure of SRPT. Our results, combined with previous work, show that SRPT is the best possible online algorithm in essentially every aspect when migration is permissible.
BibTeX
@inproceedings{fox2011online,
  author = {Kyle Fox and Benjamin Moseley},
  title = {{Online Scheduling on Identical Machines using SRPT}},
  booktitle = {SODA},
  year = {2011},
  doi = {10.1137/1.9781611973082.10},
}

Loading related content...

Figure