Geodesic
An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 42-84

Voir la notice de l'article provenant de la source Math-Net.Ru

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))\cdot|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: Open Shop problem, routing, scheduling, parameterized complexity.
Mots-clés : $FPT$-algorithm, UET 
@article{SEMR_2019_16_a111,
     author = {R. A. van Bevern and A. V. Pyatkin and S. V. Sevastyanov},
     title = {An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {42--84},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a111/}
}
TY  - JOUR
AU  - R. A. van Bevern
AU  - A. V. Pyatkin
AU  - S. V. Sevastyanov
TI  - An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 42
EP  - 84
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a111/
LA  - en
ID  - SEMR_2019_16_a111
ER  - 
%0 Journal Article
%A R. A. van Bevern
%A A. V. Pyatkin
%A S. V. Sevastyanov
%T An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 42-84
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a111/
%G en
%F SEMR_2019_16_a111
R. A. van Bevern; A. V. Pyatkin; S. V. Sevastyanov. An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 42-84. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a111/