Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

27.11.2018 | Ausgabe 2/2019

Journal of Scheduling 2/2019

Scheduling problems over a network of machines

Zeitschrift:
Journal of Scheduling > Ausgabe 2/2019
Autoren:
Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, Yifeng Zhang
Wichtige Hinweise
A preliminary version of this paper appears in the Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’2017).

Abstract

We consider scheduling problems in which jobs must be processed through a (shared) network of machines. The network is given in the form of a graph, the edges of which represent the machines. We are also given a set of jobs, each specified by its processing time and a path in the graph. Every job must be processed in the order of edges specified by its path. We assume that jobs can wait between machines and preemption is not allowed; that is, once a job starts processing on a machine, it must be completed without interruption. Every machine can only process one job at a time. The makespan of a schedule is the earliest time by which all the jobs have finished processing. The completion time of a job in a schedule is defined as the time it finishes processing on its last machine. The total completion time refers to the sum of completion times of all the jobs. Our focus is on finding schedules with the minimum sum of completion times or minimum makespan. In this paper, we develop several algorithms (both approximate and exact) for the problem both on general graphs and when the underlying graph of machines is a tree. Even in the very special case when the underlying network is a simple star, the problem is very interesting as it models a biprocessor scheduling with applications to data migration.

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.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2019

Journal of Scheduling 2/2019 Zur Ausgabe

Premium Partner

    Bildnachweise