A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodes

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
РедакторыAlexander Kononov, Michael Khachay, Valery A. Kalyagin, Panos Pardalos
ИздательSpringer Gabler
Страницы301-312
Число страниц12
ISBN (печатное издание)9783030499877
DOI
СостояниеОпубликовано - 1 янв 2020
Событие19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 - Novosibirsk, Российская Федерация
Продолжительность: 6 июл 202010 июл 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12095 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
СтранаРоссийская Федерация
ГородNovosibirsk
Период06.07.202010.07.2020

Fingerprint Подробные сведения о темах исследования «A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodes». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Chernykh, I., Kononov, A., & Sevastyanov, S. (2020). A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodes. В A. Kononov, M. Khachay, V. A. Kalyagin, & P. Pardalos (Ред.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings (стр. 301-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12095 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-49988-4_21