## René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz,
Nimrod Talmon, and Gerhard J. Woeginger.
Precedence-constrained scheduling problems parameterized by partial
order width.
In *Proceedings of the 9th International Conference on Discrete
Optimization and Operations Research (DOOR'16), Vladivostok, Russian
Federation*, volume 9869 of *Lecture Notes in Computer Science*, pages
105–120. Springer, 2016.

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.

[ bib |
DOI |
slides |
http ]
Back

*This file was generated by
bibtex2html 1.98.*