Name
Abstract | ||
|---|---|---|
Many modern schedulers can dynamically adjust their service capacity to match the incoming workload. At the same time, however, variability in service capacity often incurs operational and infrastructure costs. In this paper, we propose distributed algorithms that minimize service capacity variability when scheduling jobs with deadlines. Specifically, we show that Exact Scheduling minimizes service capacity variance subject to strict demand and deadline requirements under stationary Poisson arrivals. We also characterize the optimal distributed policies for more general settings with soft demand requirements, soft deadline requirements, or both. Additionally, we show how close the performance of the optimal distributed policy is to that of the optimal centralized policy by deriving a competitive-ratio-like bound.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3308897.3308925 | ACM SIGMETRICS Performance Evaluation Review |
Keywords | Field | DocType |
deadline scheduling, exact scheduling, online algorithms, service capacity control | Online algorithm,Computer science,Scheduling (computing),Workload,Distributed algorithm,Poisson distribution,Distributed computing | Journal |
Volume | Issue | ISSN |
46 | 3 | 0163-5999 |
Citations | PageRank | References |
1 | 0.35 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yorie Nakahira | 1 | 18 | 4.54 |
| Andrés Ferragut | 2 | 85 | 14.23 |
| Adam Wierman | 3 | 1635 | 106.57 |