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:
Buchtitelbild

2018 | OriginalPaper | Buchkapitel

Semi-online Machine Covering on Two Hierarchical Machines with Discrete Processing Times

verfasst von : Gangxiong Wu, Weidong Li

Erschienen in: Theoretical Computer Science

Verlag: Springer Singapore

Einloggen

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

search-config
loading …

Abstract

In this paper, we study the semi-online machine covering problem on two hierarchical machines, whose objective is to maximize the minimum machine load. When the processing times are discrete by \(\{1,2,2^{2},\ldots ,2^{k}\}\) with \(k\ge 2\), we prove that no algorithm can have a competitive ratio less than \(2^{k}\) and present an optimal semi-online algorithm with competitive ratio \(2^{k}\).

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
Nächstes Kapitel Improved Algorithms for Properly Learning Mixture of Gaussians
Literatur
1.
Chassid, O., Epstein, L.: The hierarchical model for load balancing on two machines. J. Comb. Optim. 15(4), 305–314 (2008)MathSciNetCrossRef
2.
Hwang, H.C., Chang, S.Y., Lee, K.: Parallel machine scheduling under a grade of service provision. Comput. Oper. Res. 31(12), 2055–2061 (2004)CrossRef
3.
Jiang, Y., He, Y., Tang, C.: Optimal online algorithms for scheduling two identical machines under a grade of service. J. Zhejiang Univ. Sci. A. 7(3), 309–314 (2006)CrossRef
4.
Li, J., Li, W., Li, J.: Polynomial approximation schemes for the max-min allocation problem under a grade of service provision. Discret. Math. Algorithms Appl. 1(3), 355–368 (2009)MathSciNetCrossRef
5.
Luo, T., Xu, Y.: Semi-online hierarchical load balancing problem with bounded processing times. Theor. Comput. Sci. 607, 75–82 (2015)MathSciNetCrossRef
6.
Li, W., Li, J., Zhang, T.: Two approximation schemes for scheduling on parallel machines under a grade of service provision. Asia-Pac. J. Oper. Res. 29(5), Article No. 1250029 (2012)MathSciNetCrossRef
7.
Ou, J., Leung, J.Y.T., Li, C.L.: Scheduling parallel machines with inclusive processing set restrictions. Nav. Res. Logist. 55(4), 328–338 (2008)MathSciNetCrossRef
8.
Park, J., Chang, S.Y., Lee, K.: Online and semi-online scheduling of two machines under a grade of service provision. Oper. Res. Lett. 34(6), 692–696 (2006)MathSciNetCrossRef
9.
Wu, Y., Cheng, T.C.E., Ji, M.: Optimal algorithm for semi-online machine covering on two hierarchical machines. Theor. Comput. Sci. 531, 37–46 (2014)MathSciNetCrossRef
10.
Wu, Y., Ji, M., Yang, Q.: Optimal semi-online scheduling algorithm on two parallel identical machines under a grade of service provision. Int. J. Prod. Econ. 135(1), 367–371 (2012)CrossRef
11.
Zhang, A., Jiang, Y., Fan, L., Hu, J.: Optimal online algorithms on two hierarchical machines with tightly-grouped processing times. J. Comb. Optim. 29(4), 781–795 (2015)MathSciNetCrossRef
Metadaten
Titel
Semi-online Machine Covering on Two Hierarchical Machines with Discrete Processing Times
verfasst von
Gangxiong Wu
Weidong Li
Copyright-Jahr
2018
Verlag
Springer Singapore
Buch
Theoretical Computer Science

Print ISBN: 978-981-13-2711-7

Electronic ISBN: 978-981-13-2712-4

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-981-13-2712-4_1