@incollection{BBB+16,
  title =	 {Precedence-constrained scheduling problems
                  parameterized by partial order width},
  author =	 {René van Bevern and Robert Bredereck and Laurent
                  Bulteau and Christian Komusiewicz and Nimrod Talmon
                  and Gerhard J. Woeginger},
  url_Preprint = {http://arxiv.org/abs/1605.00901},
  doi =		 {10.1007/978-3-319-44914-2_9},
  url_Slides =	 {http://rvb.su/pdf/p-prec-cmax-door16.pdf},
  year =	 {2016},
  date =	 {2016-09-19},
  booktitle =	 {DOOR 2016},
  editor =	 {Yury Kochetov and Michael Khachay and Vladimir
                  Beresnev and Evgeni Nurminski and Panos Pardalos},
  publisher =	 {Springer},
  abstract =	 {Negatively answering a question posed by Mnich and
                  Wiese (Math. Program. 154(1-2):533-562), we show
                  that P2|prec,pj∈{1,2}|Cmax, the problem of finding a
                  non-preemptive minimum-makespan schedule for
                  precedence-constrained jobs of lengths 1 and 2 on
                  two parallel identical machines, is W[2]-hard
                  parameterized by the width of the partial order
                  giving the precedence constraints. To this end, we
                  show that Shuffle Product, the problem of deciding
                  whether a given word can be obtained by interleaving
                  the letters of k other given words, is W[2]-hard
                  parameterized by k, thus additionally answering a
                  question posed by Rizzi and Vialette (CSR
                  2013). Finally, refining a geometric algorithm due
                  to Servakh
                  (Diskretn. Anal. Issled. Oper. 7(1):75-82), we show
                  that the more general Resource-Constrained Project
                  Scheduling problem is fixed-parameter tractable
                  parameterized by the partial order width combined
                  with the maximum allowed difference between the
                  earliest possible and factual starting time of a
                  job. },
  pages =	 {105-120},
  volume =	 {9869},
  series =	 {Lecture Notes in Computer Science},
  keywords =	 {NP-hard, parameterized complexity, scheduling}
}

{"_id":"AKLZtYfDgMBtRMoxF","bibbaseid":"vanbevern-bredereck-bulteau-komusiewicz-talmon-woeginger-precedenceconstrainedschedulingproblemsparameterizedbypartialorderwidth-2016","downloads":1,"creationDate":"2016-08-14T04:37:13.697Z","title":"Precedence-constrained scheduling problems parameterized by partial order width","author_short":["van Bevern, R.","Bredereck, R.","Bulteau, L.","Komusiewicz, C.","Talmon, N.","Woeginger, G. J."],"year":2016,"bibtype":"incollection","biburl":"http://rvb.su/rvb.bib","bibdata":{"bibtype":"incollection","type":"incollection","title":"Precedence-constrained scheduling problems parameterized by partial order width","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Robert"],"propositions":[],"lastnames":["Bredereck"],"suffixes":[]},{"firstnames":["Laurent"],"propositions":[],"lastnames":["Bulteau"],"suffixes":[]},{"firstnames":["Christian"],"propositions":[],"lastnames":["Komusiewicz"],"suffixes":[]},{"firstnames":["Nimrod"],"propositions":[],"lastnames":["Talmon"],"suffixes":[]},{"firstnames":["Gerhard","J."],"propositions":[],"lastnames":["Woeginger"],"suffixes":[]}],"url_preprint":"http://arxiv.org/abs/1605.00901","doi":"10.1007/978-3-319-44914-2_9","url_slides":"http://rvb.su/pdf/p-prec-cmax-door16.pdf","year":"2016","date":"2016-09-19","booktitle":"DOOR 2016","editor":[{"firstnames":["Yury"],"propositions":[],"lastnames":["Kochetov"],"suffixes":[]},{"firstnames":["Michael"],"propositions":[],"lastnames":["Khachay"],"suffixes":[]},{"firstnames":["Vladimir"],"propositions":[],"lastnames":["Beresnev"],"suffixes":[]},{"firstnames":["Evgeni"],"propositions":[],"lastnames":["Nurminski"],"suffixes":[]},{"firstnames":["Panos"],"propositions":[],"lastnames":["Pardalos"],"suffixes":[]}],"publisher":"Springer","abstract":"Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1-2):533-562), we show that P2|prec,pj∈1,2|Cmax, the problem of finding a non-preemptive minimum-makespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W[2]-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of k other given words, is W[2]-hard parameterized by k, thus additionally answering a question posed by Rizzi and Vialette (CSR 2013). Finally, refining a geometric algorithm due to Servakh (Diskretn. Anal. Issled. Oper. 7(1):75-82), we show that the more general Resource-Constrained Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job. ","pages":"105-120","volume":"9869","series":"Lecture Notes in Computer Science","keywords":"NP-hard, parameterized complexity, scheduling","bibtex":"@incollection{BBB+16,\n title =\t {Precedence-constrained scheduling problems\n parameterized by partial order width},\n author =\t {René van Bevern and Robert Bredereck and Laurent\n Bulteau and Christian Komusiewicz and Nimrod Talmon\n and Gerhard J. Woeginger},\n url_Preprint = {http://arxiv.org/abs/1605.00901},\n doi =\t\t {10.1007/978-3-319-44914-2_9},\n url_Slides =\t {http://rvb.su/pdf/p-prec-cmax-door16.pdf},\n year =\t {2016},\n date =\t {2016-09-19},\n booktitle =\t {DOOR 2016},\n editor =\t {Yury Kochetov and Michael Khachay and Vladimir\n Beresnev and Evgeni Nurminski and Panos Pardalos},\n publisher =\t {Springer},\n abstract =\t {Negatively answering a question posed by Mnich and\n Wiese (Math. Program. 154(1-2):533-562), we show\n that P2|prec,pj∈{1,2}|Cmax, the problem of finding a\n non-preemptive minimum-makespan schedule for\n precedence-constrained jobs of lengths 1 and 2 on\n two parallel identical machines, is W[2]-hard\n parameterized by the width of the partial order\n giving the precedence constraints. To this end, we\n show that Shuffle Product, the problem of deciding\n whether a given word can be obtained by interleaving\n the letters of k other given words, is W[2]-hard\n parameterized by k, thus additionally answering a\n question posed by Rizzi and Vialette (CSR\n 2013). Finally, refining a geometric algorithm due\n to Servakh\n (Diskretn. Anal. Issled. Oper. 7(1):75-82), we show\n that the more general Resource-Constrained Project\n Scheduling problem is fixed-parameter tractable\n parameterized by the partial order width combined\n with the maximum allowed difference between the\n earliest possible and factual starting time of a\n job. },\n pages =\t {105-120},\n volume =\t {9869},\n series =\t {Lecture Notes in Computer Science},\n keywords =\t {NP-hard, parameterized complexity, scheduling}\n}\n\n","author_short":["van Bevern, R.","Bredereck, R.","Bulteau, L.","Komusiewicz, C.","Talmon, N.","Woeginger, G. J."],"editor_short":["Kochetov, Y.","Khachay, M.","Beresnev, V.","Nurminski, E.","Pardalos, P."],"key":"BBB+16","id":"BBB+16","bibbaseid":"vanbevern-bredereck-bulteau-komusiewicz-talmon-woeginger-precedenceconstrainedschedulingproblemsparameterizedbypartialorderwidth-2016","role":"author","urls":{" preprint":"http://arxiv.org/abs/1605.00901"," slides":"http://rvb.su/pdf/p-prec-cmax-door16.pdf"},"keyword":["NP-hard","parameterized complexity","scheduling"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":1,"html":""},"search_terms":["precedence","constrained","scheduling","problems","parameterized","partial","order","width","van bevern","bredereck","bulteau","komusiewicz","talmon","woeginger"],"keywords":["np-hard","parameterized complexity","scheduling"],"authorIDs":["2fwXJtKDCNhaSNr5s"],"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}