Реферат: 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.

Библиографическая ссылка: 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

Даты:

Поступила в редакцию:	6 дек. 2022 г.
Принята к публикации:	5 апр. 2023 г.
Опубликована online:	30 апр. 2023 г.
Опубликована в печати:	15 авг. 2024 г.

Идентификаторы БД:

Web of science:	WOS:000978558100001
Scopus:	2-s2.0-85154592474
РИНЦ:	61318632
OpenAlex:	W4367394234

Цитирование в БД:

БД	Цитирований
OpenAlex	1

Альметрики: