Standard

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. ed. / Alexander Kononov; Michael Khachay; Valery A. Kalyagin; Panos Pardalos. Springer Gabler, 2020. p. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12095 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

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. in A Kononov, M Khachay, VA Kalyagin & P Pardalos (eds), 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), vol. 12095 LNCS, Springer Gabler, pp. 301-312, 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020, Novosibirsk, Russian Federation, 06.07.2020. https://doi.org/10.1007/978-3-030-49988-4_21

APA

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. In A. Kononov, M. Khachay, V. A. Kalyagin, & P. Pardalos (Eds.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings (pp. 301-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12095 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-49988-4_21

Vancouver

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. In Kononov A, Khachay M, Kalyagin VA, Pardalos P, editors, Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Springer Gabler. 2020. p. 301-312. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-49988-4_21

Author

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. editor / Alexander Kononov ; Michael Khachay ; Valery A. Kalyagin ; Panos Pardalos. Springer Gabler, 2020. pp. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@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",

}

RIS

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 -

ID: 24737065