Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline Scheduler

Yorie Nakahira (), Andres Ferragut () and Adam Wierman ()
Additional contact information
Yorie Nakahira: Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Andres Ferragut: School of Engineering, Universidad ORT Uruguay, Montevideo, Departamento de Montevideo 11100, Uruguay
Adam Wierman: Computing and Mathematical Sciences, California Institute of Technology, Pasadena, California 91125

Operations Research, 2023, vol. 71, issue 2, 433-470

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 infrastructural 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 with 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 distributions. 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.

Keywords: Stochastic Models; deadline scheduling; service capacity control; exact scheduling; online distributed algorithm; optimal control; optimization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2232 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:2:p:433-470

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().