Research Project

Algorithms for cost aware scheduling

Speaker:Janardhan Kulkarni
kulkarni at
Date: Monday, May 14, 2012
Time: 2:45pm - 3:45pm
Location: North 311, Duke
Bruce Maggs, John Reif


In this talk, we consider generalized classical single-machine pre-emptive scheduling problems, when there is an additional cost of processing jobs that varies with time. We motivate this in terms of scheduling jobs in a data center with time-varying electricity costs, or with time- varying spot-prices on resources. We show that these problems erent from their counterparts without processing costs. We consider the online problem of optimizing weighted flow time, and present natural online algorithms with near-optimal competitive ratios.

In the online setting, technically interesting aspect of this work is in handling the adversarial nature of both the cost function (which is non-monotone in time), as well as the job arrivals.We also consider the online problem of optimizing weighted completion time, and present several approximation algorithms.

Advisor(s): Kamesh Munagala