Top

Published in:

2020 | OriginalPaper | Chapter

A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodes

Authors : Ilya Chernykh, Alexander Kononov, Sergey Sevastyanov

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the routing flow shop problem with two machines on an asymmetric network. For this problem we discuss properties of an optimal schedule and present a polynomial time algorithm assuming the number of nodes of the network to be bounded by a constant. To the best of our knowledge, this is the first positive result on the complexity of the routing flow shop problem with an arbitrary structure of the transportation network, even in the case of a symmetric network. This result stands in contrast with the complexity of the two-machine routing open shop problem, which was shown to be NP-hard even on the two-node network.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Makespan Minimization for Parallel Jobs with Energy Constraint

next chapter Optimal Location of Welds on the Vehicle Wiring Harness: P-Median Based Exact and Heuristic Approaches

The relationship between the routing flow shop problem and the problem of planning the construction of country houses in England was proposed by Natalia Shakhlevich in a private communication.

Averbakh, I., Berman, O.: Routing two-machine flowshop problems on networks with special structure. Transp. Sci. 30(4), 303–314 (1996). https://doi.org/10.1287/trsc.30.4.303CrossRefMATH

Averbakh, I., Berman, O.: A simple heuristic for \(m\)-machine flow-shop and its applications in routing-scheduling problems. Oper. Res. 47(1), 165–170 (1999). https://doi.org/10.1287/opre.47.1.165CrossRefMATH

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

Chernykh, I., Kononov, A., Sevastyanov, S.: A polynomial-time algorithm for the routing flow shop problem with two machines: an asymmetric network with a fixed number of nodes. http://arxiv.org/abs/2004.03942

Chernykh, I., Kononov, A., Sevastyanov, S.: Exact polynomial-time algorithm for the two-machine routing flow shop problem with a restricted transportation network. In: Optimization problems and their applications (OPTA-2018), Abstracts of the VII International Conference, Omsk, Russia, 8–14 July 2018, pp. 37–37. Omsk State University (2018)

Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1(2), 117–129 (1976). https://www.jstor.org/stable/3689278MathSciNetCrossRef

Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Rand Corporation (1953). https://www.rand.org/pubs/papers/P402.html

Józefczyk, J., Markowski, M.: Heuristic solution algorithm for routing flow shop with buffers and ready times. In: Swiątek, J., Grzech, A., Swiątek, P., Tomczak, J.M. (eds.) Advances in Systems Science. AISC, vol. 240, pp. 531–541. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-01857-7_52CrossRef

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. In: Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, vol. 4, pp. 445–522. Elsevier (1993). https://doi.org/10.1016/S0927-0507(05)80189-6

10.

Yu, V.F., Lin, S., Chou, S.: The museum visitor routing problem. Appl. Math. Comput. 216(3), 719–729 (2010). https://doi.org/10.1016/j.amc.2010.01.066CrossRefMATH

11.

Yu, W., Liu, Z., Wang, L., Fan, T.: Routing open shop and flow shop scheduling problems. Eur. J. Oper. Res. 213(1), 24–36 (2011). https://doi.org/10.1016/j.ejor.2011.02.028MathSciNetCrossRefMATH

12.

Yu, W., Zhang, G.: Improved approximation algorithms for routing shop scheduling. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 30–39. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25591-5_5CrossRef

Title: A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodes
Authors: Ilya Chernykh
Alexander Kononov
Sergey Sevastyanov
Publisher: Springer International Publishing
Book: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-49987-7

Electronic ISBN: 978-3-030-49988-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-49988-4_21

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner