@inproceedings{28b91451601040e789035d06707dfba4,

title = "How the difference in travel times affects the optima localization for the routing open shop",

abstract = "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.",

keywords = "Approximation algorithm, Optima localization, Routing open shop, Scheduling, Unrelated travel times",

author = "Ilya Chernykh and Ekaterina Lgotina",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-22629-9_14",

language = "English",

isbn = "9783030226282",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "187--201",

editor = "Michael Khachay and Panos Pardalos and Yury Kochetov",

booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings",

address = "Germany",

note = "18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

}