Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor.

Chandra Chekuri, Sungjin Im, Benjamin MoseleyTheory of Computing 2012 · OpenReview

Introduction

In online scheduling environments, jobs arrive dynamically, and a scheduler must make immediate decisions without knowledge of future requests. While minimizing average response time is a common objective, it often leads to "starvation," where specific jobs are delayed indefinitely. To ensure fairness and meet quality-of-service guarantees, researchers focus on "maximum" metrics: maximum response time (the longest duration any job remains in the system) and maximum delay factor (the worst-case ratio of a job's wait time to its relative urgency or "slack").

These metrics are notoriously difficult. In standard competitive analysis, where an online algorithm is compared to an optimal offline adversary on equal footing, strong lower bounds often exist. This is particularly true in broadcast scheduling, where a single transmission can satisfy multiple pending requests for the same data simultaneously. This paper addresses these challenges by introducing the first "scalable" online algorithms for these metrics.

The Resource Augmentation Framework

To overcome the inherent limitations of online scheduling, the authors utilize the resource augmentation model. In this model, the online algorithm is given a slight advantage—specifically, a processor that is $(1+\epsilon)$ times faster than the adversary's. An algorithm is considered scalable if its competitive ratio remains a constant (possibly depending on $\epsilon$) as the speedup $\epsilon$ approaches zero. This framework allows for a more nuanced distinction between algorithms that are truly robust and those that fail under worst-case scenarios.

Algorithmic Innovations

The paper proposes several key strategies tailored to different scheduling environments:

1. Shortest Slack First (SSF)

For unicast (one-to-one) scheduling, the system prioritizes the job with the least "slack" (the time remaining until its deadline relative to its processing time). The authors prove that SSF is highly effective for minimizing the maximum delay factor when given a speed advantage.

2. SSF with Waiting (SSF-W)

Broadcast scheduling presents a unique challenge: being "greedy" can be counterproductive. If an algorithm satisfies a request immediately, it might miss the chance to satisfy a similar request arriving moments later. SSF-W introduces strategic waiting. It forces the scheduler to wait until a request's delay factor reaches a specific threshold before it is eligible for broadcast. This intentional delay allows more requests for the same data to accumulate, maximizing the efficiency of each transmission and turning the fundamental challenge of broadcasting into a strength.

3. FIFO for Non-Uniform Pages

The authors re-evaluate the classic First-In-First-Out (FIFO) strategy for broadcast scheduling. They extend previous results to show that FIFO is 2-competitive even when data "pages" have varying sizes, providing a robust and simple baseline for complex broadcast environments.

Key Results and Insights

The theoretical analysis yields several significant performance guarantees:

  • Unicast Scalability: With $(1+\epsilon)$-speed, the system achieves an $O(1/\epsilon)$-competitive ratio for the maximum delay factor.
  • Broadcast Efficiency: For uniform page sizes, SSF-W achieves an $O(1/\epsilon^2)$-competitive ratio. For non-uniform sizes, a simulation of a "fractional" schedule yields an $O(1/\epsilon^3)$-competitive ratio.
  • Necessity of Speedup: The authors establish strong lower bounds, proving that without resource augmentation, no deterministic algorithm can achieve better than a $\Delta^{0.4}/2$ ratio in unicast (where $\Delta$ is the ratio of max/min slack) or $n/4$ in broadcast.

A critical insight is the failure of the "Longest-Wait-First" (LF) greedy approach. While LF is effective for other metrics, it fails to be competitive for the maximum delay factor even with extra speed. This highlights that "urgency" (slack) is a more critical priority signal than "age" (wait time) for these specific objectives.

Conclusion and Future Work

This work provides a theoretical foundation for fair and efficient real-time scheduling. By combining resource augmentation with strategic waiting, the authors demonstrate that it is possible to provide robust guarantees for maximum response time and delay factor.

Several open questions remain. The current SSF-W algorithm requires knowing the exact speedup $\epsilon$ to set its waiting threshold; finding a "speed-oblivious" scalable algorithm is a key challenge. Additionally, it remains unknown if any non-trivial approximation for the maximum delay factor exists that does not rely on resource augmentation.

Summary updated

BibTeX
@inproceedings{chekuri2012online,
  author = {Chandra Chekuri and Sungjin Im and Benjamin Moseley},
  title = {{Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor.}},
  booktitle = {Theory of Computing},
  year = {2012},
  url = {https://openreview.net/forum?id=VpNmMMCNsqrx},
}
Figure