Nakahira Accepted to Operations Research

Nakahira's paper on Generalized Exact Scheduling: a Minimal-Variance Distributed Deadline Scheduler has been accepted to the INFORMS Journal Operations Research. The team of researchers showed the well-known exact scheduling algorithm is the solution to the optimization problem of maximizing service capacity predictability.

"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," says Yorie Nakahira, assistant professor of electrical and computer engineering. "Further, we provide a novel performance bound that describes the gap between the performance of optimal distributed policies and the performance of optimal centralized policies."

The team found a stochastic counterpart of the valley-filling algorithms in deterministic scheduling problems by solving the optimization problem to maximize service capacity stability in a stochastic system. Generalizing these two observations, the paper presents how to optimally trade-off the penalties of unmet demands vs. deadline extension and integrate exact scheduling and valley-filling to Pareto-optimality balance system predictability and stability.

"Our finding can ultimately lead to more efficient power distribution networks, which optimally match the energy supply to changing demand," says Nakahira. "It can also lead to more efficient cloud computing services by allowing the computing capacity to be optimally adjusted based on incoming loads."