Top

Journal of Scheduling

30-04-2023

An exact solution with an improved running time for the routing flow shop problem with two machines

Authors: Ilya Chernykh, Alexander Kononov, Sergey Sevastyanov

Published in: Journal of Scheduling

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

search-config

AI-assisted search

Off

Abstract

We present an improved analysis of the running time of a dynamic program for the routing flow shop problem with two machines on an asymmetric network. Our analysis is based on structural properties of optimal schedules and significantly improves the bound on the running time of the algorithm obtained in the conference version of our paper (Chernykh, Kononov, and Sevastyanov, in: Kononov, A. et al. (eds) Mathematical optimization theory and operations research. MOTOR 2020. Lecture notes in computer science, Springer, Switzerland, 2020). To the best of our knowledge, our polynomial-time algorithm (under the assumption that the number of network nodes is bounded by any constant) 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 contrasts with the complexity of the two-machine routing open shop problem, which is 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 "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

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.

The possibility of designing a polynomial-time algorithm for the special case, when the transportation network is symmetric, was announced in Chernykh et al. (2018) (although, without a proof).

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

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

Averbakh, I., Berman, O., & Chernykh, I. (2006). The routing open-shop problem on a network: complexity and approximation. European Journal of Operational Research, 173(2), 531–539. https://doi.org/10.1016/j.ejor.2005.01.034CrossRef

Chernykh, I., Kononov, A., & Sevastyanov, S. (2020). A polynomial-time algorithm for the routing flow shop problem with two machines: an asymmetric network with a fixed number of nodes. In: Kononov, A. et al. (eds.) Mathematical optimization theory and operations research. MOTOR 2020. Lecture Notes in Computer Science, vol. 12095, pp. 301–312. Springer. https://doi.org/10.1007/978-3-030-49988-4_21

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

Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129. https://doi.org/10.1287/moor.1.2.117CrossRef

Johnson, S.M. (1953). Optimal Two- and Three-stage Production Schedules with Setup Times Included. P-402, the RAND Corporation, Santa Monica, California. https://www.rand.org/pubs/papers/P402.html

Józefczyk, J., & Markowski, M. (2014). Heuristic solution algorithm for routing flow shop with buffers and ready times. In: Swiatek, J. et al. (eds.) Advances in intelligent systems and computing, vol. 240, pp. 531–541. Springer. https://doi.org/10.1007/978-3-319-01857-7_52

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., & Shmoys, D.B. (1993). Chapter 9. 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. https://doi.org/10.1016/S0927-0507(05)80189-6

Yu, W., & Zhang, G. (2011). Improved approximation algorithms for routing shop scheduling. In: Asano, T. et al. (eds.) Algorithms and computation. ISAAC 2011. Lecture notes in computer science, vol. 7074, pp. 30–39. Springer. https://doi.org/10.1007/978-3-642-25591-5_5

Yu, W., Liu, Z., Wang, L., & Fan, T. (2011). Routing open shop and flow shop scheduling problems. European Journal of Operational Research, 213(1), 24–36. https://doi.org/10.1016/j.ejor.2011.02.028CrossRef

Yu, V. F., Lin, S., & Chou, S. (2010). The museum visitor routing problem. Applied Mathematics and Computation, 216(3), 719–729. https://doi.org/10.1016/j.amc.2010.01.066CrossRef

Title: An exact solution with an improved running time for the routing flow shop problem with two machines
Authors: Ilya Chernykh
Alexander Kononov
Sergey Sevastyanov
Publication date: 30-04-2023
Publisher: Springer US
Published in: Journal of Scheduling
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-023-00784-8