Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

19.04.2017 | Ausgabe 1/2018

Journal of Scheduling 1/2018

Scheduling shared continuous resources on many-cores

Zeitschrift:
Journal of Scheduling > Ausgabe 1/2018
Autoren:
Ernst Althaus, André Brinkmann, Peter Kling, Friedhelm Meyer auf der Heide, Lars Nagel, Sören Riechers, Jiří Sgall, Tim Süß
Wichtige Hinweise
Supported by the Federal Ministry of Education and Research (BMBF) under Grant 01IH13004 (Project “FAST”), by the German Research Foundation (DFG) within the Collaborative Research Center “On-The-Fly Computing” (SFB 901), by the Center of Excellence—ITI (Project P202/12/G061 of GA ČR), and by the Pacific Institute of Mathematical Sciences (PIMS).

Abstract

We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement https://static-content.springer.com/image/art%3A10.1007%2Fs10951-017-0518-0/MediaObjects/10951_2017_518_IEq1_HTML.gif . The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of \(r_j\), it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete–continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this article, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include a polynomial-time algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a https://static-content.springer.com/image/art%3A10.1007%2Fs10951-017-0518-0/MediaObjects/10951_2017_518_IEq3_HTML.gif -approximation algorithm for m processors.

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 dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2018

Journal of Scheduling 1/2018 Zur Ausgabe

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Wie können Sie Stress im Fernstudium bewältigen?

Ein Fernstudium erfordert ein hohes Maß an Selbstorganisation und Disziplin. Das bedeutet oft Stress - Prüfungsstress, Abgabetermine, Zeitdruck… Stress wird dann zum Problem, wenn wir ihn nicht mehr im Griff haben. Wenn wir die Ursachen und auch Auswirkungen von Stress verstehen, ist das ein wichtiger Schritt hin zu einem erfolgreichen Stressmanagement. Lesen Sie in diesem Auszug aus dem Fachbuch "Stressmanagement im Fernstudium" wie Sie Ihren Stress effektiv bewältigen können. Inklusive Selbsttest.
Jetzt gratis downloaden!

Bildnachweise