Standard

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs : few machines, small looseness, and small slack. / van Bevern, René; Niedermeier, Rolf; Suchý, Ondřej.

In: Journal of Scheduling, Vol. 20, No. 3, 01.06.2017, p. 255-265.

Research output: Contribution to journal › Article › peer-review

Harvard

van Bevern, R, Niedermeier, R & Suchý, O 2017, 'A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack', Journal of Scheduling, vol. 20, no. 3, pp. 255-265. https://doi.org/10.1007/s10951-016-0478-9

APA

van Bevern, R., Niedermeier, R., & Suchý, O. (2017). 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. https://doi.org/10.1007/s10951-016-0478-9

Vancouver

van Bevern R, Niedermeier R, Suchý O. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. Journal of Scheduling. 2017 Jun 1;20(3):255-265. doi: 10.1007/s10951-016-0478-9

Author

van Bevern, René ; Niedermeier, Rolf ; Suchý, Ondřej. / A parameterized complexity view on non-preemptively scheduling interval-constrained jobs : few machines, small looseness, and small slack. In: Journal of Scheduling. 2017 ; Vol. 20, No. 3. pp. 255-265.

BibTeX

@article{adcaad824c8646a59db3abe33fea7abd,
title = "A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack",
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 σ.",
keywords = "Fixed-parameter tractability, Machine minimization, NP-hard problem, Release times and deadlines, Sequencing within intervals, Shiftable intervals, NUMBER, MULTIVARIATE ALGORITHMICS",
author = "{van Bevern}, Ren{\'e} and Rolf Niedermeier and Ond{\v r}ej Such{\'y}",
note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",
year = "2017",
month = jun,
day = "1",
doi = "10.1007/s10951-016-0478-9",
language = "English",
volume = "20",
pages = "255--265",
journal = "Journal of Scheduling",
issn = "1094-6136",
publisher = "Springer New York",
number = "3",

}

RIS

TY - JOUR

T1 - A parameterized complexity view on non-preemptively scheduling interval-constrained jobs

T2 - few machines, small looseness, and small slack

AU - van Bevern, René

AU - Niedermeier, Rolf

AU - Suchý, Ondřej

N1 - Publisher Copyright: © 2016, Springer Science+Business Media New York.

PY - 2017/6/1

Y1 - 2017/6/1

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

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

KW - Fixed-parameter tractability

KW - Machine minimization

KW - NP-hard problem

KW - Release times and deadlines

KW - Sequencing within intervals

KW - Shiftable intervals

KW - NUMBER

KW - MULTIVARIATE ALGORITHMICS

UR - http://www.scopus.com/inward/record.url?scp=84963995311&partnerID=8YFLogxK

U2 - 10.1007/s10951-016-0478-9

DO - 10.1007/s10951-016-0478-9

M3 - Article

AN - SCOPUS:84963995311

VL - 20

SP - 255

EP - 265

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 3

ER -

ID: 9087777