The power of migration in online machine minimization

Lin Chen, Nicole Megow, Kevin Schewior

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

In this paper we investigate the power of migration in online scheduling on multiple parallel machines. The problem is to schedule preemptable jobs with release dates and deadlines on a minimum number of machines. We show that migration, that is, allowing that a preempted job is continued on a different machine, has a huge impact on the performance of a schedule. More precisely, let m be the number of machines required by a migratory solution; then the increase in the number of machines when disallowing migration is unbounded in m. This complements and strongly contrasts previous results on variants of this problem. In both the offline variant and a model allowing extra speed, the power of migration is limited as the increase of number of machines and speed, respectively, can be bounded by a small constant. In this paper, we also derive the first non-trivial bounds on the competitive ratio for non-migratory online scheduling to minimize the number of machines without extra speed. We show that in general no online algorithm can achieve a competitive ratio of f(m), for any function f, and give a lower bound of Ω(log n). For agreeable instances and instances with "loose" jobs, we give O(1)-competitive algorithms and, for laminar instances, we derive an O(log m)-competitive algorithm.

Original languageEnglish
Title of host publicationSPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages175-184
Number of pages10
ISBN (Electronic)9781450342100
DOIs
StatePublished - Jul 11 2016
Event28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016 - Pacific Grove, United States
Duration: Jul 11 2016Jul 13 2016

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures
Volume11-13-July-2016

Conference

Conference28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016
CountryUnited States
CityPacific Grove
Period07/11/1607/13/16

Fingerprint Dive into the research topics of 'The power of migration in online machine minimization'. Together they form a unique fingerprint.

  • Cite this

    Chen, L., Megow, N., & Schewior, K. (2016). The power of migration in online machine minimization. In SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 175-184). (Annual ACM Symposium on Parallelism in Algorithms and Architectures; Vol. 11-13-July-2016). Association for Computing Machinery. https://doi.org/10.1145/2935764.2935786