License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.392
URN: urn:nbn:de:0030-drops-47116
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4711/
Go to the corresponding LIPIcs Volume Portal

Soper, Alan J. ; Strusevich, Vitaly A.

Power of Preemption on Uniform Parallel Machines

pdf-format:
28.pdf (0.3 MB)

Abstract

For a scheduling problem on parallel machines, the power of preemption is defined as the ratio of the makespan of an optimal non-preemptive schedule over the makespan of an optimal preemptive schedule. For m uniform parallel machines, we give the necessary and sufficient conditions under which the global bound of 2-1/m is tight. If the makespan of the optimal preemptive schedule is defined by the ratio of the total processing times of r < m longest jobs over the total speed of r fastest machines, we show that the tight bound on the power of preemption is 2-1/min{r,m-r}.

BibTeX - Entry

@InProceedings{soper_et_al:LIPIcs:2014:4711,
  author =	{Alan J. Soper and Vitaly A. Strusevich},
  title =	{{Power of Preemption on Uniform Parallel Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{392--402},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4711},
  URN =		{urn:nbn:de:0030-drops-47116},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.392},
  annote =	{Keywords: Machine Scheduling, Uniform Parallel Machines, Power of Preemption}
}

Keywords: Machine Scheduling, Uniform Parallel Machines, Power of Preemption
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI