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-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.