Loading
Research Projects
Algorithms for cost aware scheduling
|
Abstract
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
Bruce Maggs, John Reif