Exploiting Scheduling Flexibility via State-Based Scheduling When Guaranteeing Worst-Case Services

Yike Xu; Mark S Andersland

doi:10.48550/arxiv.2604.13507

Back

Exploiting Scheduling Flexibility via State-Based Scheduling When Guaranteeing Worst-Case Services

Preprint

Open access

Exploiting Scheduling Flexibility via State-Based Scheduling When Guaranteeing Worst-Case Services

Yike Xu and Mark S Andersland

ArXiv.org

Cornell University

04/15/2026

DOI: 10.48550/arxiv.2604.13507

Files and links (1)

url

https://doi.org/10.48550/arxiv.2604.13507View

Preprint (Author's original) This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

Even when providing long-run, worst-case guarantees to competing flows of unit-sized tasks, a slot-timed, constant-capacity server's scheduler may retain significant, short-run, scheduling flexibility. Existing worst-case scheduling frameworks offer only limited opportunities to characterize and exploit this flexibility. We introduce a state-based framework that overcomes these limitations. Each flow's guarantee is modeled as a worst-case service that can be updated as tasks arrive and are served. Taking all flows' worst-case services as a collective state, a state-based scheduler ensures, from slot to slot, transitions between schedulable states. This constrains its scheduling flexibility to a polytope consisting of all feasible schedules that preserve schedulability. We fully characterize this polytope, enabling scheduling flexibility to be fully exploited. But, as our framework is general, full exploitation is computationally complex. To reduce complexity, we show: that when feasible schedules exist, at least one can be efficiently identified by simply maximizing the server's capacity slack; that a special class of worst-case services, min-plus services, can be efficiently specified and updated using the min-plus algebra; and that efficiency can be further improved by restricting attention to a min-plus service subclass, dual-curve services. This last specialization turns out to be a dynamic extension of service curves that approaches near practical viability while maintaining all features essential to our framework.

Computer Science - Performance

Computer Science - Systems and Control

Details

Title: Subtitle: Exploiting Scheduling Flexibility via State-Based Scheduling When Guaranteeing Worst-Case Services
Creators: Yike Xu
Mark S Andersland
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2604.13507
ISSN: 2331-8422
Publisher: Cornell University; Ithaca, New York
Language: English
Date posted: 04/15/2026
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9985153388402771

Metrics

1 Record Views