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/

[1] A. Allahverdi, C. Ng, T.C.E. Cheng, M.Y. Kovalyov, “A survey of scheduling problems with setup times or costs”, European Journal of Operational Research, 187:3 (2008), 985–1032 | DOI | MR | Zbl

[2] R. van Bevern, A.V. Pyatkin, “Completing partial schedules for Open Shop with unit processing times and routing”, Proceedings of the 11th International Computer Science Symposium in Russia (CSR'16), Lecture Notes in Computer Science, 9691, Springer, 2016, 73–87 | DOI | MR | Zbl

[3] R. van Bevern, R. Niedermeier, M. Sorge, M. Weller, “The complexity of arc routing problems”, Arc Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization, 20, eds. A. Corberan, G. Laporte, 2014, SIAM-MOS | DOI | MR | Zbl

[4] R. van Bevern, C. Komusiewicz, M. Sorge, “A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments”, Networks, 70:3 (2017), 262–278 | DOI | MR

[5] H.J. Böckenhauer, J. Hromkovič, J. Kneis, J. Kupke, “The parameterized approximability of {TSP} with deadlines”, Theory of Computing Systems, 41:3 (2007), 431–444 | DOI | MR

[6] R. Cole, K. Ost, S. Schirra, “Edge-coloring bipartite multigraphs in {$O(E\log D)$} time”, Combinatorica, 21:1 (2001), 5–12 | DOI | MR | Zbl

[7] M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer, 2015 | DOI | MR | Zbl

[8] A. Frank, E. Tardos, “An application of simultaneous diophantine approximation in combinatorial optimization”, Combinatorica, 7:1 (1987), 49–65 | DOI | MR | Zbl

[9] T. Gonzalez, S. Sahni, “Open shop scheduling to minimize finish time”, Journal of the ACM, 23:4 (1976), 665–679 | DOI | MR | Zbl

[10] G. Gutin, M. Jones, M. Wahlström, “The mixed chinese postman problem parameterized by pathwidth and treedepth”, SIAM Journal on Discrete Mathematics, 30:4 (2016), 2177–2205 | DOI | MR | Zbl

[11] G. Gutin, M. Jones, B. Sheng, “Parameterized complexity of the $k$-arc chinese postman problem”, Journal of Computer and System Sciences, 84 (2017), 107–119 | DOI | MR | Zbl

[12] G. Gutin, M. Wahlström, A. Yeo, “Rural Postman parameterized by the number of components of required edges”, Journal of Computer and System Sciences, 83:1 (2017), 121–131 | DOI | MR | Zbl

[13] P.N. Klein, D. Marx, “A subexponential parameterized algorithm for Subset TSP on planar graphs”, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), Society for Industrial and Applied Mathematics, 2014, 1812–1830 | DOI | MR

[14] E. Lawler, J. Lenstra, A. Rinnooy Kan, D. Shmoys, “Sequencing and scheduling: algorithms and complexity”, Handbooks in operations research and management science, Logistics of production and inventory, 4, North Holland, Amsterdam, 1993, 445–522 | DOI

[15] D. Lokshtanov, New methods in parameterized algorithms and complexity, PhD thesis, University of Bergen, Norway, 2009

[16] M. Mnich, R. van Bevern, “Parameterized complexity of machine scheduling: 15 open problems”, Computers and Operations Research, 2018 (to appear) | DOI | MR

[17] C.H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Dover Publications, Inc., Mineola, New York, 1998 | MR | Zbl

[18] D. Williamson, L. Hall, J. Hoogeveen, C. Hurkens, J. Lenstra, S. Sevast'janov, D. Shmoys, “Short shop schedules”, Operations Research, 45:2 (1997), 288–294 | DOI | MR | Zbl

[19] X. Zhu, W.E. Wilhelm, “Scheduling and lot sizing with sequence-dependent setup: A literature review”, IIE Transactions, 38:11 (2006), 987–1007 | DOI