@inproceedings{a06b4338fa6649af92b88405feb5d669,
title = "Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti",
abstract = "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.",
keywords = "Instance reduction, Optima localization, Polynomially solvable subcase, Routing open shop, Unrelated travel times",
author = "Ilya Chernykh and Olga Krivonogova",
year = "2020",
month = "1",
day = "1",
doi = "10.1007/978-3-030-38603-0_1",
language = "English",
isbn = "9783030386023",
series = "Communications in Computer and Information Science",
publisher = "Springer Gabler",
pages = "1--15",
editor = "Milojica Jaćimović and Michael Khachay and Vlasta Malkova and Mikhail Posypkin",
booktitle = "Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers",
address = "Germany",
}