  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.
