RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sib. Èlektron. Mat. Izv., 2019, Volume 16, Pages 42–84 (Mi semr1059)  

Computational mathematics

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

R. A. van Beverna, A. V. Pyatkinb, S. V. Sevastyanovb

a Novosibirsk National Research University, 1, str. Pirogova, Novosibirsk, 630090, Russia
b Sobolev Institute of Mathematics, 4, pr. Koptyuga, Novosibirsk, 630090, Russia

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))\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: $FPT$-algorithm, Open Shop problem, routing, scheduling, UET, parameterized complexity.

Funding Agency Grant Number
Russian Foundation for Basic Research 16-31-60007_мол_а_дк
17-01-00170_а
18-01-00747_а
The first author was supported by the Russian Foundation for Basic Research (grant 16-31-60007). The second author was supported by the Russian Foundation for Basic Research (grant 17-01-00170). The third author was supported by the Russian Foundation for Basic Research (grant 18-01-00747).


DOI: https://doi.org/10.33048/semi.2019.16.003

Full text: PDF file (349 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.854.2
MSC: 90B35
Received October 2, 2018, published January 27, 2019
Language:

Citation: 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”, Sib. Èlektron. Mat. Izv., 16 (2019), 42–84

Citation in format AMSBIB
\Bibitem{VanPyaSev19}
\by R.~A.~van Bevern, A.~V.~Pyatkin, S.~V.~Sevastyanov
\paper An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
\jour Sib. \`Elektron. Mat. Izv.
\yr 2019
\vol 16
\pages 42--84
\mathnet{http://mi.mathnet.ru/semr1059}
\crossref{https://doi.org/10.33048/semi.2019.16.003}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000462268100003}


Linking options:
  • http://mi.mathnet.ru/eng/semr1059
  • http://mi.mathnet.ru/eng/semr/v16/p42

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:63
    Full text:20
    References:11

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019