On the Optima Localization for the Three-Machine Routing Open Shop

Ilya Chernykh, Olga Krivonogova

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

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
РедакторыAlexander Kononov, Michael Khachay, Valery A. Kalyagin, Panos Pardalos
ИздательSpringer Gabler
Страницы274-288
Число страниц15
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 Подробные сведения о темах исследования «On the Optima Localization for the Three-Machine Routing Open Shop». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    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