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.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

This is joint work with Nicole Megow.

Chien-Chung Huang

--email hidden

passcode not visible

logged in users only