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

Ilya Chernykh, Olga Krivonogova

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review


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.

Original languageEnglish
Title of host publicationOptimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
EditorsMilojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin
PublisherSpringer Gabler
Number of pages15
ISBN (Print)9783030386023
Publication statusPublished - 1 Jan 2020
Event10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Montenegro
Duration: 30 Sep 20194 Oct 2019

Publication series

NameCommunications in Computer and Information Science
Volume1145 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937


Conference10th International Conference on Optimization and Applications, OPTIMA 2019


  • Instance reduction
  • Optima localization
  • Polynomially solvable subcase
  • Routing open shop
  • Unrelated travel times


Dive into the research topics of 'Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti'. Together they form a unique fingerprint.

Cite this