TY - GEN

T1 - On the value of job migration in online makespan minimization

AU - Albers, Susanne

AU - Hellwig, Matthias

PY - 2012

Y1 - 2012

N2 - Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of n jobs has to be scheduled non-preemptively on m machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range [1.88,1.9201]. Currently no randomized online algorithm with a smaller competitiveness is known, for general m. In this paper we explore the power of job migration, i.e. an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel processing environments. As our main result we settle the performance that can be achieved by deterministic online algorithms. We develop an algorithm that is α m -competitive, for any m ≥ 2, where α m is the solution of a certain equation. For m = 2, α 2 = 4/3 and lim m → ∞ α m = W -1(-1/e 2)/(1 + W -1(-1/e 2)) ≈ 1.4659. Here W -1 is the lower branch of the Lambert W function. For m ≥ 11, the algorithm uses at most 7m migration operations. For smaller m, 8m to 10m operations may be performed. We complement this result by a matching lower bound: No online algorithm that uses o(n) job migrations can achieve a competitive ratio smaller than α m. We finally trade performance for migrations. We give a family of algorithms that is c-competitive, for any 5/3 ≤ c ≤ 2. For c = 5/3, the strategy uses at most 4m job migrations. For c = 1.75, at most 2.5m migrations are used.

AB - Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of n jobs has to be scheduled non-preemptively on m machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range [1.88,1.9201]. Currently no randomized online algorithm with a smaller competitiveness is known, for general m. In this paper we explore the power of job migration, i.e. an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel processing environments. As our main result we settle the performance that can be achieved by deterministic online algorithms. We develop an algorithm that is α m -competitive, for any m ≥ 2, where α m is the solution of a certain equation. For m = 2, α 2 = 4/3 and lim m → ∞ α m = W -1(-1/e 2)/(1 + W -1(-1/e 2)) ≈ 1.4659. Here W -1 is the lower branch of the Lambert W function. For m ≥ 11, the algorithm uses at most 7m migration operations. For smaller m, 8m to 10m operations may be performed. We complement this result by a matching lower bound: No online algorithm that uses o(n) job migrations can achieve a competitive ratio smaller than α m. We finally trade performance for migrations. We give a family of algorithms that is c-competitive, for any 5/3 ≤ c ≤ 2. For c = 5/3, the strategy uses at most 4m job migrations. For c = 1.75, at most 2.5m migrations are used.

UR - http://www.scopus.com/inward/record.url?scp=84866719392&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-33090-2_9

DO - 10.1007/978-3-642-33090-2_9

M3 - Conference contribution

AN - SCOPUS:84866719392

SN - 9783642330896

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 84

EP - 95

BT - Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings

T2 - 20th Annual European Symposium on Algorithms, ESA 2012

Y2 - 10 September 2012 through 12 September 2012

ER -