@article{BNS17,
  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_Preprint = {http://arxiv.org/abs/1508.01657},
  doi =		 {10.1007/s10951-016-0478-9},
  url_Slides =	 {http://rvb.su/pdf/looseness-slack-door16.pdf},
  issn =	 {1094-6136},
  year =	 2017,
  date =	 {2017-06-01},
  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 σ.},
  volume =	 20,
  number =	 3,
  pages =	 {255–265}
}

{"_id":"rWEPK7iGkDwvFoo2n","bibbaseid":"vanbevern-niedermeier-such-aparameterizedcomplexityviewonnonpreemptivelyschedulingintervalconstrainedjobsfewmachinessmallloosenessandsmallslack-2017","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Niedermeier, R.","Suchý, O."],"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_preprint":"http://arxiv.org/abs/1508.01657","doi":"10.1007/s10951-016-0478-9","url_slides":"http://rvb.su/pdf/looseness-slack-door16.pdf","issn":"1094-6136","year":"2017","date":"2017-06-01","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 σ.","volume":"20","number":"3","pages":"255–265","bibtex":"@article{BNS17,\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\n Suchý},\n url_Preprint = {http://arxiv.org/abs/1508.01657},\n doi =\t\t {10.1007/s10951-016-0478-9},\n url_Slides =\t {http://rvb.su/pdf/looseness-slack-door16.pdf},\n issn =\t {1094-6136},\n year =\t 2017,\n date =\t {2017-06-01},\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\n deadline d_j, and a processing time p_j, on m\n parallel identical machines. Cieliebak et\n al. considered the two constraints |d_j-t_j| ≤ λp_j\n and |d_j-t_j| ≤ p_j+σ and showed the problem to be\n NP-hard for any λ>1 and for any σ≥2. We complement\n their results by parameterized complexity studies:\n we show that, for any λ>1, the problem remains\n weakly NP-hard even for m=2 and strongly W[1]-hard\n parameterized by m. We present a\n pseudo-polynomial-time algorithm for constant m and\n λ and a fixed-parameter tractability result for the\n parameter m combined with σ.},\n volume =\t 20,\n number =\t 3,\n pages =\t {255–265}\n}\n\n","author_short":["van Bevern, R.","Niedermeier, R.","Suchý, O."],"key":"BNS17","id":"BNS17","bibbaseid":"vanbevern-niedermeier-such-aparameterizedcomplexityviewonnonpreemptivelyschedulingintervalconstrainedjobsfewmachinessmallloosenessandsmallslack-2017","role":"author","urls":{" preprint":"http://arxiv.org/abs/1508.01657"," slides":"http://rvb.su/pdf/looseness-slack-door16.pdf"},"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":1,"html":""},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.484Z","downloads":1,"keywords":[],"search_terms":["parameterized","complexity","view","non","preemptively","scheduling","interval","constrained","jobs","few","machines","small","looseness","small","slack","van bevern","niedermeier","suchý"],"title":"A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack","year":2017,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}