nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

How the Difference in Travel Times Affects the Optima Localization for the Routing Open Shop

verfasst von : Ilya Chernykh, Ekaterina Lgotina

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The routing open shop problem, being a generalization of the metric TSP and the open shop scheduling problem, is known to be NP-hard even in case of two machines with a transportation network consisting of two nodes only. We consider a generalization of this problem with unrelated travel times of each machine. We determine a tight optima localization interval for the two-machine problem in the case when the transportation network consists of at most three nodes. As a byproduct of our research, we present a linear time \(\frac{5}{4}\)-approximation algorithm for the same problem. We prove that the algorithm has the best theoretically possible approximation ratio with respect to the standard lower bound.

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 The Local and Global Searches in Bilevel Problems with a Matrix Game at the Lower Level

Nächstes Kapitel Inland Waterway Efficiency Through Skipper Collaboration and Joint Speed Optimization

Averbakh, I., Berman, O., Chernykh, I.: A 6/5-approximation algorithm for the two-machine routing open shop problem on a 2-node network. Eur. J. Oper. Res. 166(1), 3–24 (2005). https://doi.org/10.1016/j.ejor.2003.06.050MathSciNetCrossRefMATH

Averbakh, I., Berman, O., Chernykh, I.: The routing open-shop problem on a network: complexity and approximation. Eur. J. Oper. Res. 173(2), 521–539 (2006). https://doi.org/10.1016/j.ejor.2005.01.034MathSciNetCrossRefMATH

Brucker, P., Knust, S., Edwin Cheng, T.C., Shakhlevich, N.: Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Ann. Oper. Res. 129, 81–106 (2004). https://doi.org/10.1023/b:anor.0000030683.64615.c8MathSciNetCrossRefMATH

Chernykh, I.: Routing open shop with unrelated travel times. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 272–283. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_22CrossRef

Chernykh, I., Kononov, A., Sevastyanov, S.: Efficient approximation algorithms for the routing open shop problem. Comput. Oper. Res. 40(3), 841–847 (2013). https://doi.org/10.1016/j.cor.2012.01.006MathSciNetCrossRefMATH

Chernykh, I., Lgotina, E.: The 2-machine routing open shop on a triangular transportation network. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 284–297. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_23CrossRef

Chernykh, I., Pyatkin, A.: Refinement of the optima localization for the two-machine routing open shop. In: Proceedings of the 8th International Conference on Optimization and Applications (OPTIMA 2017), vol. 1987, pp. 131–138. CEUR Workshop Proceedings (2017)

Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburg, PA (1976)

Gonzalez, T., Sahni, S.: Open shop scheduling to minimize finish time. J. Assoc. Comput. Mach. 23, 665–679 (1976). https://doi.org/10.1145/321978.321985MathSciNetCrossRefMATH

10.

Kononov, A., Sevastianov, S., Tchernykh, I.: When difference in machine loads leads to efficient scheduling in open shops. Ann. Oper. Res. 92, 211–239 (1999). https://doi.org/10.1023/a:1018986731638MathSciNetCrossRefMATH

11.

Kononov, A.: On the routing open shop problem with two machines on a two-vertex network. J. Appl. Ind. Math. 6(3), 318–331 (2012). https://doi.org/10.1134/s1990478912030064MathSciNetCrossRefMATH

12.

Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Shmoys, G.B.: Sequencing and scheduling: algorithms and complexity. In: Graves, S.S., Rinnooy-Kan, A.H.G., Zipkin, P. (eds.) Logistics of Production and Inventory. Elsevier, Amsterdam (1993)

13.

Serdyukov, A.: On some extremal routes in graphs. Upravlyaemye Sistemy 17, 76–79 (1978). (in Russian)MATH

14.

Sevastianov, S.V., Tchernykh, I.D.: Computer-aided way to prove theorems in scheduling. In: Bilardi, G., Italiano, G.F., Pietracaprina, A., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 502–513. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-68530-8_42CrossRef

Titel: How the Difference in Travel Times Affects the Optima Localization for the Routing Open Shop
verfasst von: Ilya Chernykh
Ekaterina Lgotina
Verlag: Springer International Publishing
Buch: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-22628-2

Electronic ISBN: 978-3-030-22629-9

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-22629-9_14

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner