|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodesтезисы доклада
- Авторы: Chernykh I., Kononov A., Sevastyanov S.
- Сборник: Mathematical Optimization Theory and Operations Research. MOTOR 2020
- Серия: Lecture Notes in Computer Science
- Том: 12095
- Тезисы
- Год издания: 2020
- Место издания: Springer, Cham Cham
- Первая страница: 301
- Последняя страница: 312
- DOI: 10.1007/978-3-030-49988-4_21
- Аннотация: We consider the routing flow shop problem with two machines on an asymmetric network. For this problem we discuss properties of an optimal schedule and present a polynomial time algorithm assuming the number of nodes of the network to be bounded by a constant. To the best of our knowledge, this 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 stands in contrast with the complexity of the two-machine routing open shop problem, which was shown to be NP-hard even on the two-node network.
- Добавил в систему: Кононов Александр Вениаминович