Standard

Routing open shop with two nodes, unit processing times and equal number of jobs and machines. / Golovachev, Mikhail; Pyatkin, Artem V.

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. 264-276 (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 proceedingConference contributionResearchpeer-review

Harvard

Golovachev, M & Pyatkin, AV 2019, Routing open shop with two nodes, unit processing times and equal number of jobs and machines. 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. 264-276, 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_19

APA

Golovachev, M., & Pyatkin, A. V. (2019). Routing open shop with two nodes, unit processing times and equal number of jobs and machines. In M. Khachay, P. Pardalos, & Y. Kochetov (Eds.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (pp. 264-276). (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_19

Vancouver

Golovachev M, Pyatkin AV. Routing open shop with two nodes, unit processing times and equal number of jobs and machines. 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. 264-276. (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_19

Author

Golovachev, Mikhail ; Pyatkin, Artem V. / Routing open shop with two nodes, unit processing times and equal number of jobs and machines. 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. 264-276 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{500be20c7c9943539a9f9e63be57fdce,
title = "Routing open shop with two nodes, unit processing times and equal number of jobs and machines",
abstract = "In the Routing Open Shop problem n jobs are located in the nodes of an edge-weighted graph G=(V,E) and m machines must process all jobs in such a way that each machine processes only one job at a time and each job is processed by only one machine at a time. The goal is to minimize the makespan, i.{\^A} e. the time when the last machine comes back to the initial node called a depot (at the beginning all machines are in the depot). This problem is NP-hard even when the graph contains only two nodes. In this paper we consider the case of G=K2 when all processing times and travel times are unit. We pose the conjecture that the problem is polynomially solvable in this case, i.e. that the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time O(log mn). We provide some bounds on the makespan for the case of m=n depending on the loads distribution.",
keywords = "Complexity, Makespan bounds, Polynomial time, Routing Open Shop, Scheduling, Unit processing times, COMPLEXITY, ALGORITHM",
author = "Mikhail Golovachev and Pyatkin, {Artem V.}",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-22629-9_19",
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 = "264--276",
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 - Routing open shop with two nodes, unit processing times and equal number of jobs and machines

AU - Golovachev, Mikhail

AU - Pyatkin, Artem V.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - In the Routing Open Shop problem n jobs are located in the nodes of an edge-weighted graph G=(V,E) and m machines must process all jobs in such a way that each machine processes only one job at a time and each job is processed by only one machine at a time. The goal is to minimize the makespan, i. e. the time when the last machine comes back to the initial node called a depot (at the beginning all machines are in the depot). This problem is NP-hard even when the graph contains only two nodes. In this paper we consider the case of G=K2 when all processing times and travel times are unit. We pose the conjecture that the problem is polynomially solvable in this case, i.e. that the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time O(log mn). We provide some bounds on the makespan for the case of m=n depending on the loads distribution.

AB - In the Routing Open Shop problem n jobs are located in the nodes of an edge-weighted graph G=(V,E) and m machines must process all jobs in such a way that each machine processes only one job at a time and each job is processed by only one machine at a time. The goal is to minimize the makespan, i. e. the time when the last machine comes back to the initial node called a depot (at the beginning all machines are in the depot). This problem is NP-hard even when the graph contains only two nodes. In this paper we consider the case of G=K2 when all processing times and travel times are unit. We pose the conjecture that the problem is polynomially solvable in this case, i.e. that the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time O(log mn). We provide some bounds on the makespan for the case of m=n depending on the loads distribution.

KW - Complexity

KW - Makespan bounds

KW - Polynomial time

KW - Routing Open Shop

KW - Scheduling

KW - Unit processing times

KW - COMPLEXITY

KW - ALGORITHM

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

U2 - 10.1007/978-3-030-22629-9_19

DO - 10.1007/978-3-030-22629-9_19

M3 - Conference contribution

AN - SCOPUS:85067656044

SN - 9783030226282

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 264

EP - 276

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: 20643507