CaltechAUTHORS
  A Caltech Library Service

Generalized Exact Scheduling: a Minimal-Variance Distributed Deadline Scheduler

Nakahira, Yorie and Ferragut, Andres and Wierman, Adam (2020) Generalized Exact Scheduling: a Minimal-Variance Distributed Deadline Scheduler. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20201014-143948343

[img] PDF - Submitted Version
See Usage Policy.

1096Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20201014-143948343

Abstract

Many modern schedulers can dynamically adjust their service capacity to match the incoming workload. At the same time, however, unpredictability and instability in service capacity often incur operational and infrastructure costs. In this paper, we seek to characterize optimal distributed algorithms that maximize the predictability, stability, or both when scheduling jobs with deadlines. Specifically, we show that Exact Scheduling minimizes both the stationary mean and variance of the service capacity subject to strict demand and deadline requirements. For more general settings, we characterize the minimal-variance distributed policies with soft demand requirements, soft deadline requirements, or both. The performance of the optimal distributed policies is compared to that of the optimal centralized policy by deriving closed-form bounds and by testing centralized and distributed algorithms using real data from the Caltech electrical vehicle charging facility and many pieces of synthetic data from different arrival distribution. Moreover, we derive the Pareto-optimality condition for distributed policies that balance the variance and mean square of the service capacity. Finally, we discuss a scalable partially-centralized algorithm that uses centralized information to boost performance and a method to deal with missing information on service requirements.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2004.12280arXivDiscussion Paper
ORCID:
AuthorORCID
Nakahira, Yorie0000-0003-3324-4602
Ferragut, Andres0000-0003-0134-5548
Alternate Title:Minimal-Variance Distributed Deadline Scheduling
Subject Keywords:Deadline scheduling, Service capacity control, Exact Scheduling, Online distributed algorithm
Record Number:CaltechAUTHORS:20201014-143948343
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20201014-143948343
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106068
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:14 Oct 2020 21:45
Last Modified:14 Oct 2020 21:45

Repository Staff Only: item control page