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

Ilya Chernykh; Alexander Kononov; Sergey Sevastyanov

doi:10.1007/978-3-030-49988-4_21

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

Ilya Chernykh, Alexander Kononov, Sergey Sevastyanov

Кафедра теоретической кибернетики ММФ

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

Аннотация

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	https://doi.org/10.1007/978-3-030-49988-4_21
Состояние	Опубликовано - 1 янв 2020
Событие	19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 - Novosibirsk, Российская Федерация Продолжительность: 6 июл 2020 → 10 июл 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.2020 → 10.07.2020

Доступ к документу

10.1007/978-3-030-49988-4_21

Link to publication in Scopus

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

Chernykh, Ilya ; Kononov, Alexander ; Sevastyanov, Sergey. / A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines : An Asymmetric Network with a Fixed Number of Nodes. Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. редактор / Alexander Kononov ; Michael Khachay ; Valery A. Kalyagin ; Panos Pardalos. Springer Gabler, 2020. стр. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0e129074c9d54044b760f0da89125cd4,

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

abstract = "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.",

keywords = "Dynamic programming, Flow shop, Polynomially-solvable case, Routing flow shop, Scheduling",

author = "Ilya Chernykh and Alexander Kononov and Sergey Sevastyanov",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/978-3-030-49988-4_21",

language = "English",

isbn = "9783030499877",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Gabler",

pages = "301--312",

editor = "Alexander Kononov and Michael Khachay and Kalyagin, {Valery A.} and Panos Pardalos",

booktitle = "Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings",

address = "Germany",

note = "19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 ; Conference date: 06-07-2020 Through 10-07-2020",

}

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, VA Kalyagin & P Pardalos (ред.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), том. 12095 LNCS, Springer Gabler, стр. 301-312, 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020, Novosibirsk, Российская Федерация, 06.07.2020. https://doi.org/10.1007/978-3-030-49988-4_21

A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines : An Asymmetric Network with a Fixed Number of Nodes. / Chernykh, Ilya ; Kononov, Alexander ; Sevastyanov, Sergey.

Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. ред. / Alexander Kononov; Michael Khachay; Valery A. Kalyagin; Panos Pardalos. Springer Gabler, 2020. стр. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12095 LNCS).

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

TY - GEN

T1 - A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines

T2 - 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020

AU - Chernykh, Ilya

AU - Kononov, Alexander

AU - Sevastyanov, Sergey

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Dynamic programming

KW - Flow shop

KW - Polynomially-solvable case

KW - Routing flow shop

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85087787371&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-49988-4_21

DO - 10.1007/978-3-030-49988-4_21

M3 - Conference contribution

AN - SCOPUS:85087787371

SN - 9783030499877

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 301

EP - 312

BT - Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings

A2 - Kononov, Alexander

A2 - Khachay, Michael

A2 - Kalyagin, Valery A.

A2 - Pardalos, Panos

PB - Springer Gabler

Y2 - 6 July 2020 through 10 July 2020

ER -

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