RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сиб. электрон. матем. изв., 2019, том 16, страницы 42–84 (Mi semr1059)  

Вычислительная математика

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

Аннотация: 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.

Ключевые слова: $FPT$-algorithm, Open Shop problem, routing, scheduling, UET, parameterized complexity.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 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

Полный текст: PDF файл (349 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.854.2
MSC: 90B35
Поступила 2 октября 2018 г., опубликована 27 января 2019 г.
Язык публикации: английский

Образец цитирования: 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”, Сиб. электрон. матем. изв., 16 (2019), 42–84

Цитирование в формате AMSBIB
\RBibitem{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 Сиб. электрон. матем. изв.
\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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr1059
  • http://mi.mathnet.ru/rus/semr/v16/p42

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:21
    Полный текст:8
    Литература:2

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019