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

Standard

Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti. / Chernykh, Ilya; Krivonogova, Olga.

Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. ed. / Milojica Jaćimović; Michael Khachay; Vlasta Malkova; Mikhail Posypkin. Springer Gabler, 2020. p. 1-15 (Communications in Computer and Information Science; Vol. 1145 CCIS).

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

Harvard

Chernykh, I & Krivonogova, O 2020, Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti. in M Jaćimović, M Khachay, V Malkova & M Posypkin (eds), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Communications in Computer and Information Science, vol. 1145 CCIS, Springer Gabler, pp. 1-15, 10th International Conference on Optimization and Applications, OPTIMA 2019, Petrovac, Montenegro, 30.09.2019. https://doi.org/10.1007/978-3-030-38603-0_1

APA

Chernykh, I., & Krivonogova, O. (2020). Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti. In M. Jaćimović, M. Khachay, V. Malkova, & M. Posypkin (Eds.), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers (pp. 1-15). (Communications in Computer and Information Science; Vol. 1145 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-38603-0_1

Vancouver

Chernykh I, Krivonogova O. Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti. In Jaćimović M, Khachay M, Malkova V, Posypkin M, editors, Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Springer Gabler. 2020. p. 1-15. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-38603-0_1

Author

Chernykh, Ilya ; Krivonogova, Olga. / Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti. Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. editor / Milojica Jaćimović ; Michael Khachay ; Vlasta Malkova ; Mikhail Posypkin. Springer Gabler, 2020. pp. 1-15 (Communications in Computer and Information Science).

BibTeX

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

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 10th International Conference on Optimization and Applications, OPTIMA 2019 ; Conference date: 30-09-2019 Through 04-10-2019",

year = "2020",

month = jan,

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{\'c}imovi{\'c} and Michael Khachay and Vlasta Malkova and Mikhail Posypkin",

booktitle = "Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers",

address = "Germany",

}

RIS

TY - GEN

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

AU - Chernykh, Ilya

AU - Krivonogova, Olga

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Instance reduction

KW - Optima localization

KW - Polynomially solvable subcase

KW - Routing open shop

KW - Unrelated travel times

UR - http://www.scopus.com/inward/record.url?scp=85078428503&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-38603-0_1

DO - 10.1007/978-3-030-38603-0_1

M3 - Conference contribution

AN - SCOPUS:85078428503

SN - 9783030386023

T3 - Communications in Computer and Information Science

SP - 1

EP - 15

BT - Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers

A2 - Jaćimović, Milojica

A2 - Khachay, Michael

A2 - Malkova, Vlasta

A2 - Posypkin, Mikhail

PB - Springer Gabler

T2 - 10th International Conference on Optimization and Applications, OPTIMA 2019

Y2 - 30 September 2019 through 4 October 2019

ER -

ID: 23260745