Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline Scheduler

DOI10.1287/OPRE.2021.2232MaRDI QIDQ6152471OpenAlexFDO

Authors Yorie Nakahira, Andres Ferragut, Adam Wierman

Publication date 12 March 2024

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.12280

zbMATH Keywords

optimizationoptimal controlstochastic modelsdeadline schedulingexact schedulingonline distributed algorithmservice capacity control

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

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.

Recommendations

• Stochastically Minimizing Total Delay of Jobs Subject to Random Deadlines
• Optimal Stochastic Allocation of Machines under Waiting-Time Constraints
• Routing jobs with deadlines to heterogeneous parallel servers
• Scheduling for a processor sharing system with linear slowdown
• Nearly optimal perfectly-periodic schedules

Cited in

(2)

• Optimal differentiated threshold characterization for multi-task stochastic deadline scheduling with queuing
• A scheduling framework for distributed key-value stores and its application to tail latency minimization

This page was built for publication: Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline Scheduler

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6152471)