Abstract:

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 flowtime and energy. Note that the two objectives are in conflict: higher speeds reduce flowtime at the cost of increased energy consumption. In the clairvoyant version of the problem, the parameters of a job (volume and density) are revealed when the job is released. For this problem, a series of results culminated in a (2+epsilon)-competitive algorithm due to Bansal, Chan, and Pruhs. In this talk, I will consider the non-clairvoyant version of the problem where the density of a job is revealed on release but the volume is unknown. This version is often more practical and has been widely considered in other scheduling problems. We give a constant-competitive algorithm, which to the best of our knowledge, is the first non-trivial result for this problem.

Our algorithm is defined by simulating the clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other non-clairvoyant scheduling problems.

(Based on joint work with Yossi Azar, Nikhil Devanur, and Zhiyi Huang.)