Preemptive Online Scheduling: Optimal Algorithms for All Speeds
Jiri Sgall, Academy of Sciences of the Czech Republic
February 1, 2008, 3:30PM, Wean 7220

Abstract:
In this talk, we describe an optimal online algorithm for a large class of scheduling problems.

We are interested in an online version of the classical problem of preemptive scheduling on uniformly related machines. We are given machines with different speeds and a sequence of jobs, each described by its processing time (length). The objective is to find a schedule of all jobs in which the maximal completion time (makespan) is minimized. In the preemptive version, each job may be divided into several pieces, which can be assigned to different machines in disjoint time slots. In the online problem, jobs arrive one-by-one and we need to assign each incoming job to some time slots on some machines, without any knowledge of the jobs that arrive later.

Our new algorithm is optimal for any fixed combination of speeds of the machine, and thus our results subsume all the previous work on various special cases. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. Together with previous results and a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between $2.054$ and $e \approx 2.718$. Finally, our algorithm can be extended into various semi-online settings, where some partial information about the input instance is known, e.g., the maximal processing time or the sum of all the processing times.

This work is based on the following paper:

T. Ebenlendr, W. Jawor, J. Sgall: Preemptive Online Scheduling: Optimal Algorithms for All Speeds, To appear in Algorithmica. Proc. of the 14th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 4168, pages 327-339, Springer, 2006.