*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Energy-efficient Scheduling in the Non-clairvoyant model
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.)
