1 Search Results for "Papadigenopoulos, Orestis"

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.17

Malleable Scheduling Beyond Identical Machines

Authors: Dimitris Fotakis, Jannik Matuschke, and Orestis Papadigenopoulos

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract

In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S for j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e/(e-1), unless P = NP. On the positive side, we present polynomial-time algorithms with approximation ratios 2e/(e-1) for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding and result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1+phi for unrelated speeds (phi is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms (i) for minimizing the sum of weighted completion times; and (ii) a variant where we determine the effective speed of a set of allocated machines based on the L_p norm of their speeds.

Cite as

Dimitris Fotakis, Jannik Matuschke, and Orestis Papadigenopoulos. Malleable Scheduling Beyond Identical Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.APPROX-RANDOM.2019.17,
  author =	{Fotakis, Dimitris and Matuschke, Jannik and Papadigenopoulos, Orestis},
  title =	{{Malleable Scheduling Beyond Identical Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.17},
  URN =		{urn:nbn:de:0030-drops-112324},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.17},
  annote =	{Keywords: malleable, jobs, moldable, machines, unrelated, uniform, parallel, speeds, approximation, scheduling}
}

Refine by Author
1 Fotakis, Dimitris
1 Matuschke, Jannik
1 Papadigenopoulos, Orestis

Refine by Classification
1 Theory of computation → Approximation algorithms analysis
1 Theory of computation → Scheduling algorithms

Refine by Keyword
1 approximation
1 jobs
1 machines
1 malleable
1 moldable
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Papadigenopoulos, Orestis"

Malleable Scheduling Beyond Identical Machines

Abstract

Cite as

Thanks for your feedback!

Could not send message