ARC Colloquium: Debmalya Panigrahi, Microsoft Research

Primary tabs

Title: Energy-efficient Scheduling in the Non-clairvoyant model


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.)


  • Workflow Status:
  • Created By:
    Elizabeth Ndongi
  • Created:
  • Modified By:
    Fletcher Moore
  • Modified:


    No keywords were submitted.

Target Audience

    No target audience selected.