Novel Lower Bounds on M/G/k Scheduling
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914182824198144 |
|---|---|
| author | Wang, Ziyuan Grosof, Izzy |
| author_facet | Wang, Ziyuan Grosof, Izzy |
| contents | In queueing systems, effective scheduling algorithms are essential for optimizing performance. Optimal scheduling for the M/G/k queue has been explored in the heavy traffic limit, but much remains unknown in the intermediate load regime.
In this paper, we give the first framework for proving nontrivial lower bounds on the mean response time of the M/G/k system under arbitrary scheduling policies. Our bounds tighten previous naive lower bounds by more than 60\%, yielding significant improvements particularly for moderate loads. Key to our approach is a new variable-speed queue, which more accurately captures the work completion behavior of multiserver systems. To analyze the expected work of this queue, we develop a novel manner of employing the drift method or the BAR approach, by developing test functions via the solutions to a differential equation.
We validate our results numerically for systems with up to 5 servers and a range of job size distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08804 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Novel Lower Bounds on M/G/k Scheduling Wang, Ziyuan Grosof, Izzy Performance In queueing systems, effective scheduling algorithms are essential for optimizing performance. Optimal scheduling for the M/G/k queue has been explored in the heavy traffic limit, but much remains unknown in the intermediate load regime. In this paper, we give the first framework for proving nontrivial lower bounds on the mean response time of the M/G/k system under arbitrary scheduling policies. Our bounds tighten previous naive lower bounds by more than 60\%, yielding significant improvements particularly for moderate loads. Key to our approach is a new variable-speed queue, which more accurately captures the work completion behavior of multiserver systems. To analyze the expected work of this queue, we develop a novel manner of employing the drift method or the BAR approach, by developing test functions via the solutions to a differential equation. We validate our results numerically for systems with up to 5 servers and a range of job size distributions. |
| title | Novel Lower Bounds on M/G/k Scheduling |
| topic | Performance |
| url | https://arxiv.org/abs/2502.08804 |