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 $2- \frac{1}{m}$. Further, it is known that SRPT's competitive ratio improves as the speed increases; SRPT is $s$-speed $\frac{1}{s}$-competitive when $s \geq 2- \frac{1}{m}$. 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+\epsilon)$-speed when $0 < \epsilon < 1-\frac{1}{m}$, even though it has been thought that SRPT is $(1+\epsilon)$-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, 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+\epsilon)$-speed $O(\frac{1}{\epsilon})$-competitive for $\epsilon >0$. We complement this by showing that SRPT is $(1+\epsilon)$-speed $O(\frac{1}{\epsilon^2})$-competitive for the objective of minimizing the $\ell_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.
Introduction
In online scheduling, jobs arrive at unpredictable times, and a scheduler must decide which jobs to run on which machines to minimize the "flow time"—the total duration a job spends in the system, including both waiting and processing time. On a single machine, the Shortest Remaining-Processing-Time (SRPT) algorithm is the undisputed optimal strategy for minimizing average flow time.
However, the problem becomes significantly more complex when extended to $m$ identical machines. While SRPT has long been recognized as a strong performer in multi-machine environments, a theoretical gap persisted for over a decade regarding its "scalability." An algorithm is considered scalable if, when provided with slightly faster machines (resource augmentation 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 resolves Open Problem 2.9 from the 2004 survey "Online Scheduling" by proving that SRPT is indeed scalable.
Methodology: Potential Function Analysis
To analyze the performance of SRPT, the authors employ potential function analysis. This technique involves defining a potential function $\Phi(t)$ that represents the "debt" or state discrepancy between the online SRPT algorithm and an optimal offline scheduler (OPT) at any given time $t$.
The Innovation
The core contribution of this work is the design of two novel potential functions:
- Average Flow Time Function: A function designed to bound the total flow time.
- $\ell_k$-Norms Function: A more complex function designed to handle higher-order norms, which are often used to measure fairness and prevent job starvation.
By assuming SRPT operates with $(1+\epsilon)$ speed, the authors demonstrate that the algorithm "pays off" its debt to the potential function faster than the adversary can create it. This ensures that the total cost incurred by SRPT, combined with the change in potential, remains bounded relative to the optimal solution.
Key Results and Insights
The paper provides the first quantitative bounds for SRPT under $(1+\epsilon)$ speedup for $0 < \epsilon < 1-\frac{1}{m}$:
- Average Flow Time: SRPT is $(1+\epsilon)$-speed $4/\epsilon$-competitive. For example, if SRPT's machines are 10% faster than the adversary's, its total flow time is guaranteed to be at most 40 times the optimal offline result.
- $\ell_k$-norms of Flow Time: SRPT is $(1+\epsilon)$-speed $4/\epsilon^2$-competitive for $k \ge 1$. This is the first result of its kind for SRPT on multiple machines for this specific metric.
These findings suggest that SRPT is the most robust online algorithm for this setting when job migration (moving a job from one machine to another) is permitted. Furthermore, the success of SRPT under $\ell_k$-norms indicates that it naturally balances efficiency with fairness, as higher-order norms more heavily penalize jobs that experience excessively long wait times.
Limitations and Future Directions
While this work settles a long-standing theoretical question, it also highlights areas for further research:
- Migration Costs: The current analysis assumes that jobs can be migrated between machines without any penalty. In practical systems, the overhead of moving a job's state between processors can be significant.
- The 1-Competitive Threshold: While the paper proves $O(1)$-competitiveness, the exact amount of speedup required to make an online algorithm 1-competitive (matching the offline optimal) remains unknown, with current estimates ranging between $22/21$ and $2$.
- Heterogeneous Environments: These results apply to identical machines. Extending scalability proofs to "unrelated" machines—where different machines have varying speeds for different types of jobs—remains a major challenge in scheduling theory.
Conclusion
By proving that SRPT is $(1+\epsilon)$-speed $O(1/\epsilon)$-competitive, this paper confirms the long-held intuition that SRPT is a near-perfect algorithm for online scheduling on identical machines. The introduction of new potential functions provides a structural map of how SRPT manages workloads, offering a foundation for future analysis of complex scheduling objectives.
Summary updated