OP-00728 Solution claimed

Exact complexity of unit-job precedence scheduling on three processors

Let $G = (J, E)$ be a directed acyclic graph with $n$ vertices, one for each job, and let $T$ be a nonnegative integer given in binary. Every job takes exactly one unit of time on any of three identical processors, a job must finish before any of its successors begins, jobs cannot be interrupted, each processor runs at most one job at a time, and all jobs are available at time zero. A schedule completing all jobs by time $T$ exists if and only if there is a map $s : J \to \{0, \dots, T - 1\}$ with $$s(v) \ge s(u) + 1 \quad ((u, v) \in E), \qquad |\{j \in J : s(j) = t\}| \le 3 \quad (0 \le t < T).$$ This decision problem is written $P3 \mid \mathrm{prec}, p_j = 1 \mid C_{\max}$. Coffman and Graham gave a polynomial-time algorithm for an optimal schedule on two processors, and Ullman proved the problem NP-complete when the number of processors is part of the input. Nederlof, Swennenhuis and Węgrzycki gave an exact algorithm running in time $(1 + n/m)^{O(\sqrt{nm})}$ on $m$ processors, which is subexponential in $n$ for three processors.

Problem. Determine the computational complexity of deciding, for a given $G$ and $T$, whether such a schedule exists. In particular, is the problem solvable by a deterministic algorithm running in time polynomial in the input length, or is it NP-complete under polynomial-time many-one reductions? The two outcomes are not assumed to exhaust the possibilities. The number of processors is fixed at three, the job graph and the deadline are arbitrary input, and exact feasibility is asked, not an approximation of the minimum completion time.

Source: Garey and Johnson (1979), Appendix A13, OPEN8; recalled by Nederlof, Swennenhuis and Węgrzycki (2025), Open Question 1. Stated in this form by AIM — Open Applied Problems.

Imported from github.com/MColbrook/AIM.

Classification

Primary: OC — Optimization and Control
Secondary: CO
Keywords: AIM Open Applied Problems, computational complexity, makespan, precedence-constrained scheduling

References

@book{garey1979,
  author    = {Garey, Michael R. and Johnson, David S.},
  title     = {Computers and Intractability: A Guide to the Theory of {NP}-Completeness},
  publisher = {W. H. Freeman},
  address   = {San Francisco},
  year      = {1979},
}
@inproceedings{nederlof2025,
  author        = {Nederlof, Jesper and Swennenhuis, C{\'e}line M. F. and W{\k{e}}grzycki, Karol},
  title         = {A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints},
  booktitle     = {Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  publisher     = {SIAM},
  year          = {2025},
  pages         = {535--552},
  doi           = {10.1137/1.9781611978322.16},
  eprint        = {2312.03495},
  archivePrefix = {arXiv},
}
@article{coffman1972,
  author  = {Coffman, E. G. and Graham, R. L.},
  title   = {Optimal scheduling for two-processor systems},
  journal = {Acta Inform.},
  volume  = {1},
  number  = {3},
  year    = {1972},
  pages   = {200--213},
  doi     = {10.1007/BF00288685},
}
@article{ullman1975,
  author  = {Ullman, J. D.},
  title   = {{NP}-complete scheduling problems},
  journal = {J. Comput. System Sci.},
  volume  = {10},
  number  = {3},
  year    = {1975},
  pages   = {384--393},
  doi     = {10.1016/S0022-0000(75)80008-0},
}
@misc{aim-three-processor-unit-scheduling,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Exact complexity of unit-job precedence scheduling on three processors}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/1b7c7fd251c1643bb41f0e3cef38704bcef410fd/problems/301-three-processor-unit-scheduling.md},
  note         = {Entry 301 at commit 1b7c7fd, 2026-10-13},
}

Resolution claims

A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling v1 GitHub ↗

OpenAI

We give a uniform deterministic polynomial-time algorithm for scheduling unit-length jobs with arbitrary precedence constraints on three identical parallel machines. The algorithm constructs a schedule of minimum makespan and decides exactly whether all jobs can finish by a specified deadline. The proof reorganizes feasible schedules into intervals whose job sets have descriptions of bounded size. A dynamic program searches a …

Full resolution · not verified · fidelity not established · posted on GitHub 6 Oct 2026

Status history

When	Change	By	Reason
2026-10-16	Needs verification → Solution claimed	—	Recorded here: math @ 1581d4c, build/paper.tex.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00728, "Exact complexity of unit-job precedence scheduling on three processors", clopen.solutions.