TY - JOUR

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

AU - Chernykh, Ilya

AU - Kononov, Alexander

AU - Sevastyanov, Sergey

N1 - The research was supported by the program of fundamental scientific researches of the SB RAS: FWNF-2022-0019.

PY - 2024/8

Y1 - 2024/8

N2 - 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.

AB - 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.

KW - Dynamic programming

KW - Polynomially solvable case

KW - Routing flow shop

KW - Scheduling

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85154592474&origin=inward&txGid=d961b2575b7103137389e4ee8b90a456

UR - https://www.mendeley.com/catalogue/152472a3-cac1-3c23-9663-3e4ff26ac75d/

U2 - 10.1007/s10951-023-00784-8

DO - 10.1007/s10951-023-00784-8

M3 - Article

VL - 27

SP - 329

EP - 340

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 4

ER -