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ý

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

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

Original languageEnglish
Pages (from-to)255-265
Number of pages11
JournalJournal of Scheduling
Volume20
Issue number3
DOIs
Publication statusPublished - 1 Jun 2017

Keywords

  • Fixed-parameter tractability
  • Machine minimization
  • NP-hard problem
  • Release times and deadlines
  • Sequencing within intervals
  • Shiftable intervals
  • NUMBER
  • MULTIVARIATE ALGORITHMICS

Fingerprint Dive into the research topics of 'A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack'. Together they form a unique fingerprint.

Cite this