A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack

René van Bevern, Rolf Niedermeier, Ondřej Suchý

Результат исследования: Научные публикации в периодических изданияхстатья

10 Цитирования (Scopus)

Аннотация

We study the problem of non-preemptively scheduling n jobs, each job j with a release time tj, a deadline dj, and a processing time pj, on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints | dj- tj| ≤ λpj and | dj- tj| ≤ pj+ σ 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 σ.

Язык оригиналаанглийский
Страницы (с-по)255-265
Число страниц11
ЖурналJournal of Scheduling
Том20
Номер выпуска3
DOI
СостояниеОпубликовано - 1 июн 2017

Fingerprint Подробные сведения о темах исследования «A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать