Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915816059961344 |
|---|---|
| author | Lindermayr, Alexander Schlöter, Jens |
| author_facet | Lindermayr, Alexander Schlöter, Jens |
| contents | We study the problem of preemptively scheduling jobs online over time on a single machine to minimize the total flow time.
In the traditional clairvoyant scheduling model, the scheduler learns about the processing time of a job at its arrival, and scheduling at any time the job with the shortest remaining processing time (SRPT) is optimal. In contrast, the practically relevant non-clairvoyant model assumes that the processing time of a job is unknown at its arrival, and is only revealed when it completes. Non-clairvoyant flow time minimization does not admit algorithms with a constant competitive ratio. Consequently, the problem has been studied under speed augmentation (JACM'00) or with predicted processing times (STOC'21, SODA'22) to attain constant guarantees.
In this paper, we consider $α$-clairvoyant scheduling, where the scheduler learns the processing time of a job once it completes an $α$-fraction of its processing time. This naturally interpolates between clairvoyant scheduling ($α=0$) and non-clairvoyant scheduling ($α=1$). By elegantly fusing two traditional algorithms, we propose a scheduling rule with a competitive ratio of $\mathcal{O}(\frac{1}{1-α})$ whenever $0 \leq α< 1$. As $α$ increases, our competitive guarantee transitions nicely (up to constants) between the previously established bounds for clairvoyant and non-clairvoyant flow time minimization. We complement this positive result with a tight randomized lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21827 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis Lindermayr, Alexander Schlöter, Jens Data Structures and Algorithms We study the problem of preemptively scheduling jobs online over time on a single machine to minimize the total flow time. In the traditional clairvoyant scheduling model, the scheduler learns about the processing time of a job at its arrival, and scheduling at any time the job with the shortest remaining processing time (SRPT) is optimal. In contrast, the practically relevant non-clairvoyant model assumes that the processing time of a job is unknown at its arrival, and is only revealed when it completes. Non-clairvoyant flow time minimization does not admit algorithms with a constant competitive ratio. Consequently, the problem has been studied under speed augmentation (JACM'00) or with predicted processing times (STOC'21, SODA'22) to attain constant guarantees. In this paper, we consider $α$-clairvoyant scheduling, where the scheduler learns the processing time of a job once it completes an $α$-fraction of its processing time. This naturally interpolates between clairvoyant scheduling ($α=0$) and non-clairvoyant scheduling ($α=1$). By elegantly fusing two traditional algorithms, we propose a scheduling rule with a competitive ratio of $\mathcal{O}(\frac{1}{1-α})$ whenever $0 \leq α< 1$. As $α$ increases, our competitive guarantee transitions nicely (up to constants) between the previously established bounds for clairvoyant and non-clairvoyant flow time minimization. We complement this positive result with a tight randomized lower bound. |
| title | Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.21827 |