Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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.
в: Journal of Scheduling, Том 20, № 3, 01.06.2017, стр. 255-265.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
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