Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
How the difference in travel times affects the optima localization for the routing open shop. / Chernykh, Ilya; Lgotina, Ekaterina.
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. ред. / Michael Khachay; Panos Pardalos; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. стр. 187-201 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11548 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - How the difference in travel times affects the optima localization for the routing open shop
AU - Chernykh, Ilya
AU - Lgotina, Ekaterina
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Optima localization
KW - Routing open shop
KW - Scheduling
KW - Unrelated travel times
UR - http://www.scopus.com/inward/record.url?scp=85067669280&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-22629-9_14
DO - 10.1007/978-3-030-22629-9_14
M3 - Conference contribution
AN - SCOPUS:85067669280
SN - 9783030226282
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 187
EP - 201
BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
A2 - Khachay, Michael
A2 - Pardalos, Panos
A2 - Kochetov, Yury
PB - Springer-Verlag GmbH and Co. KG
T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
Y2 - 8 July 2019 through 12 July 2019
ER -
ID: 20643595