This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Sanders, P. Articles by Skutella, M. Search for Related Content

Online Scheduling with Bounded Migration

Fakultät für Informatik, Universität Karlsruhe (TH), 76128 Karlsruhe, Germany
Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany
TU Berlin, Institut für Mathematik, 10623 Berlin, Germany
sanders{at}ira.uka.de
ns{at}mpi-sb.mpg.de
skutella{at}math.tu-berlin.de

Consider the classical online scheduling problem, in which jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by some constant times the size of the arriving job. This constant is called the migration factor. For small migration factors, we obtain several simple online algorithms with constant competitive ratio. We also present a linear time "online approximation scheme," that is, a family of online algorithms with competitive ratio arbitrarily close to 1 and constant migration factor.

Key Words: scheduling; approximation; online algorithm; sensitivity analysis
History: Received: March 16, 2007; revision received: November 28, 2008;