Standard

An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. / van Bevern, René A.; Pyatkin, Artem V.; Sevastyanov, Sergey.

In: Сибирские электронные математические известия, Vol. 16, 01.01.2019, p. 42-84.

Research output: Contribution to journal › Article › peer-review

Harvard

van Bevern, RA, Pyatkin, AV & Sevastyanov, S 2019, 'An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times', Сибирские электронные математические известия, vol. 16, pp. 42-84. https://doi.org/10.33048/semi.2019.16.003

APA

van Bevern, R. A., Pyatkin, A. V., & Sevastyanov, S. (2019). An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. Сибирские электронные математические известия, 16, 42-84. https://doi.org/10.33048/semi.2019.16.003

Vancouver

van Bevern RA, Pyatkin AV, Sevastyanov S. An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. Сибирские электронные математические известия. 2019 Jan 1;16:42-84. doi: 10.33048/semi.2019.16.003

Author

van Bevern, René A. ; Pyatkin, Artem V. ; Sevastyanov, Sergey. / An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. In: Сибирские электронные математические известия. 2019 ; Vol. 16. pp. 42-84.

BibTeX

@article{1a5e5743228449519519548eb808c0e8,
title = "An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times",
abstract = "For the Routing Open Shop problem with unit execution times, the first algorithm with parameterized complexity is designed for constructing an optimal schedule. Its running time is bounded by a function (Pol(|V|) + f(m, g)) · |I|, where Pol(|V|) is a polynomial of the number of network nodes, f(m; g) is a function of the number of machines and the number of job locations, and |I| is the input length in its compact encoding.",
keywords = "FPT-algorithm, Open Shop problem, Parameterized complexity, Routing, Scheduling, UET, routing, scheduling, parameterized complexity, SETUP",
author = "{van Bevern}, {Ren{\'e} A.} and Pyatkin, {Artem V.} and Sergey Sevastyanov",
year = "2019",
month = jan,
day = "1",
doi = "10.33048/semi.2019.16.003",
language = "English",
volume = "16",
pages = "42--84",
journal = "Сибирские электронные математические известия",
issn = "1813-3304",
publisher = "Sobolev Institute of Mathematics",

}

RIS

TY - JOUR

T1 - An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times

AU - van Bevern, René A.

AU - Pyatkin, Artem V.

AU - Sevastyanov, Sergey

PY - 2019/1/1

Y1 - 2019/1/1

N2 - For the Routing Open Shop problem with unit execution times, the first algorithm with parameterized complexity is designed for constructing an optimal schedule. Its running time is bounded by a function (Pol(|V|) + f(m, g)) · |I|, where Pol(|V|) is a polynomial of the number of network nodes, f(m; g) is a function of the number of machines and the number of job locations, and |I| is the input length in its compact encoding.

AB - For the Routing Open Shop problem with unit execution times, the first algorithm with parameterized complexity is designed for constructing an optimal schedule. Its running time is bounded by a function (Pol(|V|) + f(m, g)) · |I|, where Pol(|V|) is a polynomial of the number of network nodes, f(m; g) is a function of the number of machines and the number of job locations, and |I| is the input length in its compact encoding.

KW - FPT-algorithm

KW - Open Shop problem

KW - Parameterized complexity

KW - Routing

KW - Scheduling

KW - UET

KW - routing

KW - scheduling

KW - parameterized complexity

KW - SETUP

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

U2 - 10.33048/semi.2019.16.003

DO - 10.33048/semi.2019.16.003

M3 - Article

AN - SCOPUS:85067680644

VL - 16

SP - 42

EP - 84

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

ER -

ID: 21610275