Standard

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. ed. / Michael Khachay; Panos Pardalos; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. p. 187-201 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Chernykh, I & Lgotina, E 2019, How the difference in travel times affects the optima localization for the routing open shop. in M Khachay, P Pardalos & Y Kochetov (eds), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11548 LNCS, Springer-Verlag GmbH and Co. KG, pp. 187-201, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russian Federation, 08.07.2019. https://doi.org/10.1007/978-3-030-22629-9_14

APA

Chernykh, I., & Lgotina, E. (2019). How the difference in travel times affects the optima localization for the routing open shop. In M. Khachay, P. Pardalos, & Y. Kochetov (Eds.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (pp. 187-201). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-22629-9_14

Vancouver

Chernykh I, Lgotina E. How the difference in travel times affects the optima localization for the routing open shop. In Khachay M, Pardalos P, Kochetov Y, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 187-201. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-22629-9_14

Author

Chernykh, Ilya ; Lgotina, Ekaterina. / How the difference in travel times affects the optima localization for the routing open shop. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. editor / Michael Khachay ; Panos Pardalos ; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. pp. 187-201 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@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",

}

RIS

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