A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling
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.
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}
}