## René van Bevern, Rolf Niedermeier, and Ondřej Suchý.
A parameterized complexity view on non-preemptively scheduling
interval-constrained jobs: few machines, small looseness, and small slack.
*Journal of Scheduling*, 20(3):255–265, 2017.

We study the problem of non-preemptively scheduling
n jobs, each job j with a release time t_j, a
deadline d_j, and a processing time p_j, on m
parallel identical machines. Cieliebak et
al. considered the two constraints |d_j-t_j| ≤ λp_j
and |d_j-t_j| ≤ p_j+σ and showed the problem to be
NP-hard for any λ>1 and for any σ≥2. We complement
their results by parameterized complexity studies:
we show that, for any λ>1, the problem remains
weakly NP-hard even for m=2 and strongly W[1]-hard
parameterized by m. We present a
pseudo-polynomial-time algorithm for constant m and
λ and a fixed-parameter tractability result for the
parameter m combined with σ.

[ bib |
DOI |
slides |
http ]
Back

*This file was generated by
bibtex2html 1.98.*