|
Эта публикация цитируется в 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.
Поступила 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
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1059 https://www.mathnet.ru/rus/semr/v16/p42
|
Статистика просмотров: |
Страница аннотации: | 382 | PDF полного текста: | 164 | Список литературы: | 35 |
|