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)) · |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.
Original language | English |
---|---|
Pages (from-to) | 42-84 |
Number of pages | 43 |
Journal | Сибирские электронные математические известия |
Volume | 16 |
DOIs | |
Publication status | Published - 1 Jan 2019 |
Keywords
- FPT-algorithm
- Open Shop problem
- Parameterized complexity
- Routing
- Scheduling
- UET
- routing
- scheduling
- parameterized complexity
- SETUP
OECD FOS+WOS
- 1.01 MATHEMATICS