Polynomial-factor hardness of scheduling unit jobs on prescribed machines
An instance $I$ of unique-machine precedence scheduling with unit jobs consists of a set $J$ of $n \ge 1$ jobs, a directed acyclic graph $G = (J, E)$ of precedence constraints, and a map $M : J \to \{1, \dots, m\}$ giving the only machine on which each job may run; the number $m$ of machines is part of the input. Each job needs one unit of uninterrupted processing, and each machine processes at most one job at a time. A feasible schedule assigns start times $s(j) \ge 0$ with $s(v) \ge s(u) + 1$ for every $(u, v) \in E$, and with the intervals $[s(u), s(u) + 1)$ and $[s(v), s(v) + 1)$ disjoint for distinct jobs $u, v$ with $M(u) = M(v)$; there are no release dates or communication delays. Let $$C_{\max}(s) = \max_{j \in J} \bigl(s(j) + 1\bigr), \qquad \operatorname{OPT}(I) = \min_{s \text{ feasible}} C_{\max}(s).$$
Job shop scheduling is the special case in which $G$ is a disjoint union of chains, so this problem inherits from job shop scheduling with unit processing times NP-hardness of approximation within $5/4$ (Williamson, Hall, Hoogeveen, Hurkens, Lenstra, Sevast'janov and Shmoys). Davies, Kulkarni, Rothvoss, Sandeep, Tarnawski and Zhang reduce the problem to scheduling with non-uniform communication delays. Guruswami, Ren and Tang (2026 preprint) prove that approximating $\operatorname{OPT}$ within any constant factor is NP-hard, and that, unless NP has quasi-polynomial-time algorithms, there is no polynomial-time $(\log n)^{\gamma}$-approximation for some constant $\gamma > 0$.
Problem. Is there an absolute constant $\varepsilon \in (0, 1)$ such that it is NP-hard, under polynomial-time reductions, to approximate $\operatorname{OPT}$ within a factor $n^{\varepsilon}$, that is, to compute in time polynomial in the input length a feasible schedule $s$ with $C_{\max}(s) \le n^{\varepsilon} \operatorname{OPT}(I)$ on every instance?
Source: Davies, Kulkarni, Rothvoss, Sandeep, Tarnawski and Zhang (2022), Conjecture 1.1 (Conjecture 2 in the arXiv version), for unit-length jobs.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, hardness of approximation, precedence constraints, scheduling
References
@inproceedings{davies2022,
author = {Davies, Sami and Kulkarni, Janardhan and Rothvoss, Thomas and Sandeep, Sai and Tarnawski, Jakub and Zhang, Yihao},
title = {On the hardness of scheduling with non-uniform communication delays},
booktitle = {Proceedings of the 2022 Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})},
publisher = {SIAM},
address = {Philadelphia, PA},
year = {2022},
pages = {316--328},
doi = {10.1137/1.9781611977073.15},
eprint = {2105.00111},
archivePrefix = {arXiv},
}
@article{williamson1997,
author = {Williamson, D. P. and Hall, L. A. and Hoogeveen, J. A. and Hurkens, C. A. J. and Lenstra, J. K. and Sevast'janov, S. V. and Shmoys, D. B.},
title = {Short shop schedules},
journal = {Oper. Res.},
volume = {45},
number = {2},
year = {1997},
pages = {288--294},
doi = {10.1287/opre.45.2.288},
}
@misc{guruswami2026,
author = {Guruswami, Venkatesan and Ren, Xuandi and Tang, Shaoxuan},
title = {Inapproximability of unique-machine precedence scheduling for unit-length jobs},
year = {2026},
eprint = {2607.26590},
archivePrefix = {arXiv},
}
@misc{aim-unit-job-unique-machine-hardness,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-factor hardness of scheduling unit jobs on prescribed machines}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/339-unit-job-unique-machine-hardness.md},
note = {Entry 339 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00487, "Polynomial-factor hardness of scheduling unit jobs on prescribed machines", clopen.solutions.