Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

23.07.2021 | Ausgabe 4/2021

Journal of Scheduling 4/2021

A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing

Zeitschrift:
Journal of Scheduling > Ausgabe 4/2021
Autoren:
Antonina P. Khramova, Ilya Chernykh
Wichtige Hinweise
This research was supported by the program of fundamental scientific researches of the SB RAS No I.5.1., project No 0314-2019-0014, and by the Russian Foundation for Basic Research, project 20-01-00045.

Publisher's Note

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

Abstract

The two-machine open shop problem was proved to be solvable in linear time by Teofilo Gonzalez and Sartaj Sahni in 1976. Several algorithms for solving that problem have been proposed since that time. We introduce another optimal algorithm for that classical problem with an interesting property: it allows to process jobs in almost arbitrary order, unlike the Gohzalez–Sahni algorithm where jobs have to be partitioned into two specific subsets. This new algorithm in turn helps us to solve a much more general problem: the easy-TSP version of the routing open shop with a variable depot, in which unmovable jobs are located in the nodes of a transportation network (with optimal route known), and mobile machines have to travel between the nodes to process jobs in the open shop environment. The common initial location of the machines is not fixed but has to be chosen, and all machines have to return to that location—the depot—to minimize finish time. We also consider the generalization of this problem in which travel times are individual for each machine. This contributes to the discussion on the differences between different scheduling models with transportation delays: classic transportation delays (in our terms, with no depot at all), with a variable depot, and with a fixed depot. It turns out that the depot makes the difference and makes the problem harder to solve.

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 4/2021

Journal of Scheduling 4/2021 Zur Ausgabe

Premium Partner

    Bildnachweise