Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

09.11.2016 | Ausgabe 2/2018

Theory of Computing Systems 2/2018

Scheduling Parallel Jobs Online with Convex and Concave Parallelizability

Zeitschrift:
Theory of Computing Systems > Ausgabe 2/2018
Autoren:
Roozbeh Ebrahimi, Samuel McCauley, Benjamin Moseley
Wichtige Hinweise
This research was supported in part by NSF grants CNS 1408695, CCF 1439084, IIS 1247726, IIS 1251137, and CCF 1217708. Samuel McCauley was also supported in part by Sandia National Laboratories.

Abstract

Online scheduling of parallelizable jobs has received a significant amount of attention recently. Scalable algorithms are known—that is, algorithms that are (1 + ε)-speed O(1)-competitive for any fixed ε>0. Previous research has focused on the case where each job’s parallelizability can be expressed as a concave speedup curve. However, there are cases where a job’s speedup curve can be convex. Considering convex speedup curves has received attention in the offline setting, but, to date, there are no positive results in the online model. In this work, we consider scheduling jobs with convex or concave speedup curves for the first time in the online setting. We give a new algorithm that is (1 + ε)-speed O(1)-competitive. There are strong lower bounds on the competitive ratio if the algorithm is not given resource augmentation over the adversary, and thus this is essentially the best positive result one can show for this setting.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2018

Theory of Computing Systems 2/2018 Zur Ausgabe

Premium Partner

    Bildnachweise