Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline Scheduler
利用优化和控制理论，在无需近似的情况下刻画了多种场景下的最优分布式调度策略，最小化服务容量的稳态均值和方差，满足严格或软性的需求和截止时间要求，并推导了分布式策略的帕累托最优条件，最终可提升电力分配网络和云计算服务的效率。
In this paper, we adapt tools from optimization and control theory to characterize the optimal distributed policies in a broad range of settings without any approximation. 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. Moreover, we derive the Pareto-optimality condition for distributed policies that balance the variance and mean square of the service capacity. The performance of the optimal distributed policies is compared with that of the optimal centralized policy by deriving closed-form bounds. 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. Our finding can ultimately lead to more efficient power distribution networks and cloud computing services, which optimally match the service capacity to changing demands.