Energy-efficient Scheduling in the Non-clairvoyant Model

Опубликовано 22 июня 2016, 0:39

A fundamental problem in energy-efficient computing is to schedule multiple jobs released over time on a single machine with adjustable speed so as to minimize the sum of flow-time (delay) and energy. Note that the two objectives are in conflict: higher speeds reduce flow-time at the cost of increased energy consumption. In this talk, motivated by datacenter applications, I will consider the non-clairvoyant version of this problem where the density (importance) of a job is known when the job arrives but its volume (processing length) is known only after the job has been completely processed. Using a novel technique called incremental analysis, we give a constant-competitive algorithm for this problem, which is the first non-trivial result for the non-clairvoyant setting. (Based on joint work with Yossi Azar, Nikhil Devanur, and Zhiyi Huang, recipient of the “Best paper” award in SPAA 2015.)