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

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

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



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






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


Сибирские электронные математические известия, 2019, том 16, страницы 42–84
DOI: https://doi.org/10.33048/semi.2019.16.003
(Mi semr1059)
 

Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)

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

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).
Поступила 2 октября 2018 г., опубликована 27 января 2019 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.854.2
MSC: 90B35
Язык публикации: английский
Образец цитирования: 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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000462268100003}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr1059
  • https://www.mathnet.ru/rus/semr/v16/p42
  • Эта публикация цитируется в следующих 8 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:382
    PDF полного текста:164
    Список литературы:35
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024