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.

Cite: Chernykh I. , Kononov A. , Sevastyanov S.
An exact solution with an improved running time for the routing flow shop problem with two machines
Journal of Scheduling. 2024. V.27. N4. P.329–340. DOI: 10.1007/s10951-023-00784-8 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Dec 6, 2022
Accepted:	Apr 5, 2023
Published online:	Apr 30, 2023
Published print:	Aug 15, 2024

Identifiers:

Web of science:	WOS:000978558100001
Scopus:	2-s2.0-85154592474
Elibrary:	61318632
OpenAlex:	W4367394234

Citing:

DB	Citing
OpenAlex	1

Altmetrics: