Precedence-constrained scheduling problems parameterized by partial order width

René van Bevern, Robert Bredereck, Laurent Bulteau +3

Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1-2):533-562), we show that P2|prec,$p_j\in \{1,2\}$|$C_{\max }$, the problem of finding a non-preempti…