# Precedence-constrained scheduling problems parameterized by partial order width

arXiv: https://arxiv.org/abs/1605.00901 · HTML: https://mlsanity.com/paper/1605.00901/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2016.

## Built on by (most cited first, 1 of 1)

- [A Structural Complexity Analysis of Hierarchical Task Network Planning](https://mlsanity.com/paper/2401.14174/) (2024)

## Abstract (arXiv)

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.