Scheduling on a machine with varying speed: Minimizing cost and energy via dual schedules
Jose Verschae
Universidad de Chile
AG1 Mittagsseminar (own work)
José Verschae received his Mathematical Engineering degree in 2009 at Universidad de
Chile. He received his Ph.D. this year from the Institute of Mathematics at TU Berlin with a thesis about on online algorithms with recourse, and graduated suma cum laude. He is now a Post-doc fellow at Universidad de Chile, where he works mostly on approximation and online algorithms with an emphasis in scheduling and network design.
I will present two types of problems related to scheduling on a machine of varying speed. In a static model, the speed function is (through an oracle) part of the input and we ask for a schedule minimizing the sum of weighted completion times. In a dynamic model, deciding upon the speed is part of the scheduling problem and we are interested in the tradeoff between scheduling cost and speed-scaling cost, that is energy consumption.
I will shortly introduce the problem and show how it can be interpreted as a problem of minimizing a generalized global cost function on a unit speed machine. After, I'll present the main ideas of a PTAS for the static and dynamic cases. Instead of focusing in the technical details, I'll try to give intuition and explain how the notion of dual schedules can be used to derive such a result. Our results are best possible since this problem is strongly NP-hard. I will also mention other complexity results and more efficient algorithms for special cases.