{"id":"openai-math/A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling","pdf":"https://github.com/openai/math/blob/main/preprints/A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling-September-24-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling-September-24-2026","tags":["scheduling","algorithms","precedence-constraints"],"score":0,"title":"A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling","domain":"Theoretical computer science","family":"124","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"Polynomial-time scheduling on three identical machines"}