Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. / van Bevern, René A.; Pyatkin, Artem V.; Sevastyanov, Sergey.
в: Сибирские электронные математические известия, Том 16, 01.01.2019, стр. 42-84.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
AU - van Bevern, René A.
AU - Pyatkin, Artem V.
AU - Sevastyanov, Sergey
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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)) · |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.
AB - 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)) · |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.
KW - FPT-algorithm
KW - Open Shop problem
KW - Parameterized complexity
KW - Routing
KW - Scheduling
KW - UET
KW - routing
KW - scheduling
KW - parameterized complexity
KW - SETUP
UR - http://www.scopus.com/inward/record.url?scp=85067680644&partnerID=8YFLogxK
U2 - 10.33048/semi.2019.16.003
DO - 10.33048/semi.2019.16.003
M3 - Article
AN - SCOPUS:85067680644
VL - 16
SP - 42
EP - 84
JO - Сибирские электронные математические известия
JF - Сибирские электронные математические известия
SN - 1813-3304
ER -
ID: 21610275