On the value of job migration in online makespan minimization

DOI10.1007/978-3-642-33090-2_9zbMATH Open1372.68039arXiv1111.0773OpenAlexW2516478317MaRDI QIDQ2408930FDOQ2408930

Authors: Susanne Albers, Matthias Hellwig 

Publication date: 10 October 2017

Published in: Algorithmica, Algorithms – ESA 2012 (Search for Journal in Brave)

Abstract: 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 $alph{a}_m$-competitive, for any $mgeq2$, where $alph{a}_m$ is the solution of a certain equation. For $m=2$, $alph{a}_2=4/3$ and $li{m}_{mightarrowinfty}alph{a}_m=W_{-1}(-1/e^2)/(1+W_{-1}(-1/e^2))approx1.4659$. Here $W_{-1}$ is the lower branch of the Lambert $W$ function. For $mgeq11$, 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 $alph{a}_m$. We finally trade performance for migrations. We give a family of algorithms that is $c$-competitive, for any $5/3leqcleq2$. For $c=5/3$, the strategy uses at most $4m$ job migrations. For $c=1.75$, at most $2.5m$ migrations are used.

Full work available at URL: https://arxiv.org/abs/1111.0773

Recommendations

• On the value of job migration in online makespan minimization
• Online makespan scheduling with job migration on uniform machines
• Online Makespan Scheduling with Job Migration on Uniform Machines
• scientific article
• Online minimization of the maximum starting time: migration helps
• Automata, Languages and Programming
• Online scheduling with bounded migration
• Online scheduling with migration on two hierarchical machines
• On the online min-wait relocation problem
• Makespan minimization in online scheduling with machine eligibility

zbMATH Keywords

competitive analysisschedulingonline algorithmmakespan minimizationjob migration

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• On-line scheduling revisited
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line scheduling algorithms
• An optimal algorithm for preemptive on-line scheduling
• A lower bound for randomized on-line multiprocessor scheduling
• Title not available (Why is that?)
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• New algorithms for an ancient scheduling problem.
• Online scheduling with reassignment
• Better Bounds for Online Scheduling
• Improved Bounds for the Online Scheduling Problem
• The Power of Reordering for Online Minimum Makespan Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Title not available (Why is that?)
• Online scheduling with bounded migration
• Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
• The load rebalancing problem

Cited In (14)

• A survey on makespan minimization in semi-online environments
• Online Makespan Scheduling with Job Migration on Uniform Machines
• On the value of job migration in online makespan minimization
• Online makespan minimization with parallel schedules
• Automata, Languages and Programming
• Optimal task migration in service-oriented systems: algorithms and mechanisms
• Minimizing migrations in fair multiprocessor scheduling of persistent tasks
• Average stretch without migration
• Online makespan scheduling with job migration on uniform machines
• Semi-online scheduling: a survey
• Online scheduling with bounded migration
• Online scheduling with migration on two hierarchical machines
• Station assignment with reallocation
• Parallel solutions for preemptive makespan scheduling on two identical machines

This page was built for publication: On the value of job migration in online makespan minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408930)