A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. van Bevern, R., Niedermeier, R., & Suchý, O. *Journal of Scheduling*, Springer, 2016. In pressPaper doi abstract bibtex 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[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 σ.

@article{BNSxx,
title = {A parameterized complexity view on non-preemptively
scheduling interval-constrained jobs: few machines,
small looseness, and small slack},
author = {René van Bevern and Rolf Niedermeier and Ondřej Suchý},
url = {http://arxiv.org/abs/1508.01657},
doi = {10.1007/s10951-016-0478-9},
slides = {http://rvb.su/pdf/looseness-slack-door16.pdf},
issn = {1094-6136},
year = 2016,
date = {2016-04-08},
journal = {Journal of Scheduling},
publisher = {Springer},
abstract = {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[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 σ.},
note = {In press}
}

Downloads: 0

{"_id":"G9r6c62TAGZuADHbX","bibbaseid":"vanbevern-niedermeier-such-aparameterizedcomplexityviewonnonpreemptivelyschedulingintervalconstrainedjobsfewmachinessmallloosenessandsmallslack-2016","downloads":0,"creationDate":"2016-03-07T11:48:39.126Z","title":"A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack","author_short":["van Bevern, R.","Niedermeier, R.","Suchý, O."],"year":2016,"bibtype":"article","biburl":"http://rvb.su/bibtex/rvb.bib","bibdata":{"bibtype":"article","type":"article","title":"A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Rolf"],"propositions":[],"lastnames":["Niedermeier"],"suffixes":[]},{"firstnames":["Ondřej"],"propositions":[],"lastnames":["Suchý"],"suffixes":[]}],"url":"http://arxiv.org/abs/1508.01657","doi":"10.1007/s10951-016-0478-9","slides":"http://rvb.su/pdf/looseness-slack-door16.pdf","issn":"1094-6136","year":"2016","date":"2016-04-08","journal":"Journal of Scheduling","publisher":"Springer","abstract":"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[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 σ.","note":"In press","bibtex":"@article{BNSxx,\n title =\t {A parameterized complexity view on non-preemptively\n scheduling interval-constrained jobs: few machines,\n small looseness, and small slack},\n author =\t {René van Bevern and Rolf Niedermeier and Ondřej Suchý},\n url =\t\t {http://arxiv.org/abs/1508.01657},\n doi =\t\t {10.1007/s10951-016-0478-9},\n slides =\t {http://rvb.su/pdf/looseness-slack-door16.pdf},\n issn =\t {1094-6136},\n year =\t 2016,\n date =\t {2016-04-08},\n journal =\t {Journal of Scheduling},\n publisher =\t {Springer},\n abstract =\t {We study the problem of non-preemptively scheduling n\n jobs, each job j with a release time t_j, a deadline\n d_j, and a processing time p_j, on m parallel\n identical machines. Cieliebak et al. considered the\n two constraints |d_j-t_j| ≤ λp_j and |d_j-t_j| ≤ p_j+σ\n and showed the problem to be NP-hard for any λ>1 and\n for any σ≥2. We complement their results by\n parameterized complexity studies: we show that, for\n any λ>1, the problem remains weakly NP-hard even for\n m=2 and strongly W[1]-hard parameterized by m. We\n present a pseudo-polynomial-time algorithm for\n constant m and λ and a fixed-parameter tractability\n result for the parameter m combined with σ.},\n note =\t {In press}\n}\n\n","author_short":["van Bevern, R.","Niedermeier, R.","Suchý, O."],"key":"BNSxx","id":"BNSxx","bibbaseid":"vanbevern-niedermeier-such-aparameterizedcomplexityviewonnonpreemptivelyschedulingintervalconstrainedjobsfewmachinessmallloosenessandsmallslack-2016","role":"author","urls":{"Paper":"http://arxiv.org/abs/1508.01657"},"downloads":0,"html":""},"search_terms":["parameterized","complexity","view","non","preemptively","scheduling","interval","constrained","jobs","few","machines","small","looseness","small","slack","van bevern","niedermeier","suchý"],"keywords":[],"authorIDs":[],"dataSources":["CfvrNWxobMKHHMw8Y"]}