Two-Machine Routing Open Shop: How Long Is the Optimal Makespan?

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


We consider a routing open shop problem being a natural generalization of the metric TSP and the classic open shop scheduling problem. The maximal possible ratio of the optimal makespan and the standard lower bound for the routing open shop has already been investigated in the last few years. The two-machine case is mostly covered. It is constructively proven in 2013 that the ratio mentioned above cannot be greater than 4/3, however, we do not know of any problem instance with the value of that ratio greater than 6/5. The latter ratio is achievable for a simplest case with two nodes. On the other hand, it is known that optimal makespan is at most 6/5 of the standard lower bound for at least a few special cases of the transportation network: one is with at most three nodes, and another is a tree. In this paper, we introduce an ultimate instance reduction technique, which allows reducing the general problem into a case with at most four nodes and at most six jobs. As a by-product, we propose a new polynomially solvable case of the two-machine routing open shop problem.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings
РедакторыPanos Pardalos, Michael Khachay, Alexander Kazakov
ИздательSpringer Science and Business Media Deutschland GmbH
Число страниц14
ISBN (печатное издание)9783030778750
СостояниеОпубликовано - 2021
Событие20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021 - Irkutsk, Российская Федерация
Продолжительность: 5 июл 202110 июл 2021

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

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


Конференция20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021
СтранаРоссийская Федерация

Предметные области OECD FOS+WOS



Подробные сведения о темах исследования «Two-Machine Routing Open Shop: How Long Is the Optimal Makespan?». Вместе они формируют уникальный семантический отпечаток (fingerprint).