Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

09-12-2019 | Issue 2/2020

Journal of Scheduling 2/2020

An optimal online algorithm for scheduling with general machine cost functions

Journal:
Journal of Scheduling > Issue 2/2020
Authors:
Islam Akaria, Leah Epstein
Important notes
Partially supported by a grant from GIF—the German-Israeli Foundation for Scientific Research and Development (Grant Number I-1366-407.6/2016).

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

We present two deterministic online algorithms for the problem of scheduling with a general machine cost function. In this problem, every machine has a cost that is given by a nonnegative cost function, and the objective function is the sum of makespan and the cost of the purchased machines. In previous work by Imreh, it was shown that no deterministic algorithm has competitive ratio below 2, and an algorithm whose competitive ratio does not exceed \((3+\sqrt{5})/2 \approx 2.618\) was presented. Our first algorithm imitates an optimal offline solution with respect to the number of machines used, and we show that its competitive ratio is exactly 2.5. Then, we modify our algorithm by imitating a preemptive optimal offline solution instead of a non-preemptive one. This leads to the design of a 2-competitive algorithm, which is the best possible.

Please log in to get access to this content

To get access to this content you need the following product:

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.

Literature
About this article

Other articles of this Issue 2/2020

Journal of Scheduling 2/2020 Go to the issue

Premium Partner

    Image Credits