Standard

On the Optima Localization for the Three-Machine Routing Open Shop. / Chernykh, Ilya; Krivonogova, Olga.

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

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

Harvard

Chernykh, I & Krivonogova, O 2020, On the Optima Localization for the Three-Machine Routing Open Shop. в 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, стр. 274-288, 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_19

APA

Chernykh, I., & Krivonogova, O. (2020). On the Optima Localization for the Three-Machine Routing Open Shop. в A. Kononov, M. Khachay, V. A. Kalyagin, & P. Pardalos (Ред.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings (стр. 274-288). (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_19

Vancouver

Chernykh I, Krivonogova O. On the Optima Localization for the Three-Machine Routing Open Shop. в Kononov A, Khachay M, Kalyagin VA, Pardalos P, Редакторы, Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Springer Gabler. 2020. стр. 274-288. (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_19

Author

Chernykh, Ilya ; Krivonogova, Olga. / On the Optima Localization for the Three-Machine Routing Open Shop. Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Редактор / Alexander Kononov ; Michael Khachay ; Valery A. Kalyagin ; Panos Pardalos. Springer Gabler, 2020. стр. 274-288 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{e9940e38d569489f9369d7d424fa44b8,
title = "On the Optima Localization for the Three-Machine Routing Open Shop",
abstract = "A tight optima localization interval for the classical open shop scheduling problem with three machines was established by S. Sevastyanov and I. Chernykh in 1998. It was proved that for any problem instance its optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound. The process of proof involved massive computer-aided enumeration of the subsets of instances of the problem considered and took about 200 h of the running time to complete. This makes it seemingly impossible to use the same approach for more complicated problems, i.e. the four machine open shop for which the optima localization interval is still unknown. In this paper we apply that computer-aided approach to the three-machine routing open shop problem on a two-node transportation network. For this generalization of the plain open shop problem we derive some extreme instance properties and prove that the optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.",
keywords = "Approximation algorithm, Computer-aided proof, Open shop, Optima localization, Routing open shop",
author = "Ilya Chernykh and Olga Krivonogova",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-49988-4_19",
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 = "274--288",
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 - On the Optima Localization for the Three-Machine Routing Open Shop

AU - Chernykh, Ilya

AU - Krivonogova, Olga

PY - 2020/1/1

Y1 - 2020/1/1

N2 - A tight optima localization interval for the classical open shop scheduling problem with three machines was established by S. Sevastyanov and I. Chernykh in 1998. It was proved that for any problem instance its optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound. The process of proof involved massive computer-aided enumeration of the subsets of instances of the problem considered and took about 200 h of the running time to complete. This makes it seemingly impossible to use the same approach for more complicated problems, i.e. the four machine open shop for which the optima localization interval is still unknown. In this paper we apply that computer-aided approach to the three-machine routing open shop problem on a two-node transportation network. For this generalization of the plain open shop problem we derive some extreme instance properties and prove that the optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.

AB - A tight optima localization interval for the classical open shop scheduling problem with three machines was established by S. Sevastyanov and I. Chernykh in 1998. It was proved that for any problem instance its optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound. The process of proof involved massive computer-aided enumeration of the subsets of instances of the problem considered and took about 200 h of the running time to complete. This makes it seemingly impossible to use the same approach for more complicated problems, i.e. the four machine open shop for which the optima localization interval is still unknown. In this paper we apply that computer-aided approach to the three-machine routing open shop problem on a two-node transportation network. For this generalization of the plain open shop problem we derive some extreme instance properties and prove that the optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.

KW - Approximation algorithm

KW - Computer-aided proof

KW - Open shop

KW - Optima localization

KW - Routing open shop

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

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

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

M3 - Conference contribution

AN - SCOPUS:85087790898

SN - 9783030499877

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

SP - 274

EP - 288

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

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

Y2 - 6 July 2020 through 10 July 2020

ER -

ID: 24737005