Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti

Ilya Chernykh, Olga Krivonogova

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

Аннотация

The object of investigation is the routing open shop problem, in which a fleet of machines have to visit all the nodes of a given transportation network to perform operations on some jobs located at those nodes. Each machine has to visit each node, to process each job and to return back to the common initial location—the depot. Operations of each job can be processed in an arbitrary sequence, any machine may perform at most one operation at a time. The goal is to construct a feasible schedule to minimize the makespan. The routing open shop problem is known to be NP-hard even in the simplest two-machine case with the transportation network consisting of just two nodes (including the depot). We consider a certain generalization of this problem in which travel times are individual for each of the two machines and the structure of the transportation network is an arbitrary cactus. We generalize an instance reduction algorithm known for the problem on a tree with identical travel times, and use it to describe new polynomially solvable cases for the problem, as well as an efficient approximation algorithm for another special case with a tight approximation ratio guarantee.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
РедакторыMilojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin
ИздательSpringer Gabler
Страницы1-15
Число страниц15
ISBN (печатное издание)9783030386023
DOI
СостояниеОпубликовано - 1 янв 2020
Событие10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Черногория
Продолжительность: 30 сен 20194 окт 2019

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

НазваниеCommunications in Computer and Information Science
Том1145 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937

Конференция

Конференция10th International Conference on Optimization and Applications, OPTIMA 2019
СтранаЧерногория
ГородPetrovac
Период30.09.201904.10.2019

    Fingerprint

Цитировать

Chernykh, I., & Krivonogova, O. (2020). Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti. В M. Jaćimović, M. Khachay, V. Malkova, & M. Posypkin (Ред.), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers (стр. 1-15). (Communications in Computer and Information Science; Том 1145 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-38603-0_1