Browse › Theoretical computer science › 124 Polynomial-time scheduling on three identical machines
A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
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 family containing polynomially many such descriptions. Global boundary conditions and simplification of inherited information keep the descriptions bounded throughout the decomposition.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Comments and discussion
- NotOscarWilde (Hacker News), comment in the thread Sharing AI progress in mathematics (HN item 49985622, 2026-10-06). The commenter, a self-described "TCS/scheduling person", says the paper addresses the three-machine problem open since Garey and Johnson (1979), remarks on the exponent 150020, and says they cannot check its correctness.
Formalization
- OpenAI math release, Lean scope notes for family 124 (lean/docs/124.md) (release Lean documentation, 2026-10-06). Describes the scope of the Lean formalization: one fixed deterministic machine that constructs minimum-makespan schedules and decides deadline feasibility for nonempty unit-job instances with arbitrary acyclic precedence constraints on three identical machines, in time polynomial in the binary input length. [family-level]
- OpenAI math release, ThreeMachine.lean comparator statement (release Lean comparator challenge, 2026-10-06). States the target theorem: a fixed Turing machine and a constant C give a correct schedule or a "none" answer within C·(input length + 2)^150020 steps.
Related prior literature mentioned by others
- Christina Büsing, Maurice Draeger and Corinna Mathwieser, Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints (IPEC 2025, 7:1–7:16, 2025-12-15). Cited in AIM’s entry on this scheduling problem; it studies parameterized tractability and hardness for Boolean precedence constraints, context for the paper's restriction to ordinary DAG precedence.
Possibly relevant literature (found by the agent, not checked)
- Mnich and van Bevern, Parameterized complexity of machine scheduling: 15 open problems (arXiv:1709.01670; Computers & Operations Research 100 (2018) 254–261). Section 4.2 records P3|prec,p_j=1|Cmax as open and asks, as Open Problem 6, whether it is FPT parameterized by the width of the partial order; it is not in the paper's bibliography.
- Nederlof, Swennenhuis and Węgrzycki, Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995^n) time (arXiv:2208.02664, 2022). An earlier exact-algorithm paper by these authors, noting that even for m=3 the best previous algorithms ran in O*(2^n) time; relevant to the paper's survey of exact algorithms, which cites only their SODA 2025 subexponential paper.
- Bodlaender, Groenland, Nederlof and Swennenhuis, Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space (arXiv:2105.14882, 2021/2023). Lists scheduling with precedence constraints, parameterized by the number of machines together with the partial-order width, among its XNLP-complete problems; context for the paper's claim of a polynomial algorithm for fixed m=3.
- Lenstra and Rinnooy Kan, Complexity of Scheduling under Precedence Constraints (Operations Research 26(1) (1978) 22–35, doi:10.1287/opre.26.1.22). A classical NP-completeness paper on precedence-constrained scheduling, relevant to the paper's statement of hardness when m is part of the input, which it attributes only to Ullman (1975).
Digests and expositions
- AI Proved What?, Three machines, polynomial? Scheduling unit jobs with precedence (Episode 124, October 2026; status updated 2026-10-19). Video and transcript explaining the claimed bounded-description decomposition and dynamic program, reporting small-instance experiments, and distinguishing inspection of the published Lean statements from running the checker. [AI-generated per source] [family-level]
News and blogs
- explainx.ai blog, OpenAI Math Results: 8 Claims, Lean Status, Expert Views (blog post, 2026). Summarizes this paper's claim, its O((L+2)^150020) bound and its Lean status (doc and comparator file present, absent from lean/formalization.yaml), and points to the Hacker News comment above.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 124
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling-September-24-2026,
author = {{OpenAI}},
title = {{A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling-September-24-2026/paper.pdf}{OAI:A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/124.md. The Lean statements have not been checked by people against the paper's claims.
Family 124: Polynomial-time scheduling on three identical machines
Resolves the three-processor unit-job scheduling problem of Garey and Johnson: a deterministic polynomial-time algorithm minimizes makespan for nonpreemptive unit-length jobs with arbitrary precedence constraints on three identical parallel machines. For an explicitly given precedence graph, it decides deadline feasibility exactly and constructs a feasible schedule.
This is the only paper in this family.