Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2018 | Published
Journal Article Open

Minimal-variance distributed scheduling under strict demands and deadlines


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 abstract, we characterize an optimal distributed algorithm that minimizes 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. Moreover, we show how close the performance of the optimal distributed algorithm is to that of the optimal centralized algorithm by deriving a competitive-ratio-like bound.

Additional Information

© 2018 is held by author/owner(s).

Attached Files

Published - p12-nakahira.pdf


Files (841.9 kB)
Name Size Download all
841.9 kB Preview Download

Additional details

August 19, 2023
August 19, 2023