How the difference in travel times affects the optima localization for the routing open shop

Ilya Chernykh, Ekaterina Lgotina

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

1 Цитирования (Scopus)

Аннотация

The routing open shop problem, being a generalization of the metric TSP and the open shop scheduling problem, is known to be NP-hard even in case of two machines with a transportation network consisting of two nodes only. We consider a generalization of this problem with unrelated travel times of each machine. We determine a tight optima localization interval for the two-machine problem in the case when the transportation network consists of at most three nodes. As a byproduct of our research, we present a linear time 5/4 -approximation algorithm for the same problem. We prove that the algorithm has the best theoretically possible approximation ratio with respect to the standard lower bound.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
РедакторыMichael Khachay, Panos Pardalos, Yury Kochetov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы187-201
Число страниц15
ISBN (печатное издание)9783030226282
DOI
СостояниеОпубликовано - 1 янв 2019
Событие18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Российская Федерация
Продолжительность: 8 июл 201912 июл 2019

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

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

Конференция

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

Fingerprint Подробные сведения о темах исследования «How the difference in travel times affects the optima localization for the routing open shop». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Chernykh, I., & Lgotina, E. (2019). How the difference in travel times affects the optima localization for the routing open shop. В M. Khachay, P. Pardalos, & Y. Kochetov (Ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (стр. 187-201). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11548 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-22629-9_14