A Caltech Library Service

Minimal-Variance Distributed Deadline Scheduling in a Stationary Environment

Nakahira, Yorie and Ferragut, Andres and Wierman, Adam (2018) Minimal-Variance Distributed Deadline Scheduling in a Stationary Environment. Performance Evaluation Review, 46 (3). pp. 56-61. ISSN 0163-5999.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Nakahira, Yorie0000-0003-3324-4602
Additional Information:© 2018 is held by author/owner(s).
Subject Keywords:Deadline scheduling, Service capacity control, Exact Scheduling, Online algorithms
Record Number:CaltechAUTHORS:20190128-091502098
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92489
Deposited By: Tony Diaz
Deposited On:29 Jan 2019 20:03
Last Modified:29 Jan 2019 20:03

Repository Staff Only: item control page