@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}
}

{"_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"]}