Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On the Capture Time of Cops and Robbers Game on a Planar Graph Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Scheduling with Interjob Communication on Parallel Processors

verfasst von : Jürgen König, Alexander Mäcker, Friedhelm Meyer auf der Heide, Sören Riechers

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Consider a scheduling problem in which a set of jobs with interjob communication, canonically represented by a weighted tree, needs to be scheduled on m parallel processors interconnected by a shared communication channel. In each time step, we may allow any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in parallel. The goal is to find a schedule with minimum length in which communication demands of all jobs are satisfied.
We show that this problem is NP-hard in the strong sense even if the number of processors and the maximum degree of the underlying tree is constant. Consequently, we design and analyze simple approximation algorithms with asymptotic approximation ratio https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-48749-6_41/432347_1_En_41_IEq1_HTML.gif in case of paths and a ratio of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-48749-6_41/432347_1_En_41_IEq2_HTML.gif in case of arbitrary trees.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel On-Line Pattern Matching on Uncertain Sequences and Applications
Nächstes Kapitel Cost-Efficient Scheduling on Machines from the Cloud
Literatur
1.
2.
Brinkmann, A., Kling, P., auf der Heide, F.M., Nagel, L., Riechers, S., Süß, T.: Scheduling shared continuous resources on many-cores. In: Proceedings of the 26th ACM Symposium on Parallelism inAlgorithms and Architectures (SPAA 2014), pp. 128–137. ACM (2014)
3.
Chung, F., Graham, R., Mao, J., Varghese, G.: Parallelism versus memory allocation in pipelined router forwarding engines. Theory Comput. Syst. 39(6), 829–849 (2006)MathSciNetCrossRefMATH
4.
de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1+epsilon in linear time. Combinatorica 1(4), 349–355 (1981)MathSciNetCrossRefMATH
5.
Dósa, G., Li, R., Han, X., Tuza, Z.: Tight absolute bound for first fit decreasing bin-packing: FFD(l) \(\le \) 11/9 OPT(L) + 6/9. Theoret. Comput. Sci. 510, 13–61 (2013)MathSciNetCrossRefMATH
6.
Epstein, L., Levin, A., van Stee, R.: Approximation schemes for packing splittable items with cardinality constraints. Algorithmica 62(1–2), 102–129 (2012)MathSciNetCrossRefMATH
7.
Epstein, L., van Stee, R.: Approximation schemes for packing splittable items with cardinality constraints. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol. 4927, pp. 232–245. Springer, Heidelberg (2008)CrossRef
8.
9.
Happe, M., auf der Heide, F.M., Kling, P., Platzner, M., Plessl, C.: On-the-fly computing: a novel paradigm for individualized IT services. In: Proceedings of the 16th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing (ISORC 2013), pp. 1–10. IEEE Computer Society (2013)
10.
Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), pp. 312–320. IEEE Computer Society (1982)
Metadaten
Titel
Scheduling with Interjob Communication on Parallel Processors
verfasst von
Jürgen König
Alexander Mäcker
Friedhelm Meyer auf der Heide
Sören Riechers
Copyright-Jahr
2016
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-48749-6_41