|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
An exact solution with an improved running time for the routing flow shop problem with two machinesстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Chernykh I., Kononov A., Sevastyanov S.
- Журнал: Journal of Scheduling
- Том: 27
- Год издания: 2024
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 329
- Последняя страница: 340
- DOI: 10.1007/s10951-023-00784-8
- Аннотация: 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 complexityof 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.
- Добавил в систему: Кононов Александр Вениаминович