Speaker: Prof. Jiri Sgall       Mathematical Institute, Academy of Sciences of Czech Republic

Abstract:　Our main result is an optimal online algorithm for
preemptive scheduling on uniformly related machines with the
objective to minimize makespan.  The algorithm is deterministic,
yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various  special cases. Together with a new lower bound it follows that the  overall competitive ratio of this optimal algorithm is between  $2.054$ and $e \approx 2.718$ Joint with Tomas Ebenlendr and Wojciech Jawor