1 · The essentials
Imagine a collection of tasks that each take one unit of time, with some tasks required to finish before others can start. There are three identical machines available, and each task must run without interruption on one machine. The goal is to finish all the tasks as early as possible while respecting every required order. The manuscript presents a deterministic algorithm that finds the best possible finishing time and constructs a schedule achieving it. It also answers exactly whether all tasks can finish by a specified deadline. Its running time is bounded by a polynomial in the size of the explicitly supplied task-and-order information. The main result has a Lean formalization, although the supplied description does not identify the exact scope of that formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect everyday image, picture three identical ovens and a collection of baking steps, each taking exactly the same time, with some steps waiting for others to finish. The problem is to arrange the steps so the last oven finishes as early as possible; the image is imperfect because the mathematical setting includes only the stated timing, machine, and ordering rules.
Why it matters
The repository summary describes this result as resolving the three-processor unit-job scheduling problem of Garey and Johnson. It provides both an exact answer to a deadline question and an actual schedule, rather than only an estimate of what might be possible. The guarantee applies to arbitrary precedence constraints, under the specific assumptions of three identical machines and uninterrupted unit-length jobs.
2 · Going further
The input is an explicitly given precedence graph describing unit-length jobs and their required ordering. Jobs are nonpreemptive: once started, each runs without interruption. On three identical parallel machines, the objective is to minimize the makespan, the time when the last job finishes. The associated decision problem asks whether a schedule with makespan at most a specified deadline exists.
The repository summary identifies this as the three-processor unit-job scheduling problem of Garey and Johnson and describes it as resolved by the result. The main manuscript presents a uniform deterministic polynomial-time algorithm that both constructs an optimal schedule and decides deadline feasibility exactly. No particular polynomial running-time bound is given in the supplied abstract.
The argument described in the abstract reorganizes feasible schedules into intervals whose job sets admit bounded-size descriptions. A dynamic program searches a family containing only polynomially many such descriptions. Global boundary conditions and simplification of inherited information keep these descriptions bounded throughout the decomposition; the abstract does not provide the detailed definitions or transitions.
Only the main manuscript is supplied, so no relationship to companion manuscripts can be described from this material. The main result has a Lean formalization, but the supplied information does not specify which individual claims or algorithmic details it covers.
Useful notions
- Jobs and precedence constraints
- Graphs as representations of ordering requirements
- Makespan and deadline feasibility
- Polynomial-time algorithms
- Dynamic programming
What was known before / what is new
Before
The repository summary identifies the target as the three-processor unit-job scheduling problem of Garey and Johnson. The supplied material does not describe earlier algorithms, partial results, or the history of the problem.
New
The manuscript presents a uniform deterministic polynomial-time algorithm for the stated three-machine problem, with both optimal schedule construction and exact deadline decisions. Its described structural approach uses bounded-size descriptions of intervals and a dynamic program over a polynomially sized family. Boundary conditions and simplification of inherited information are the stated mechanisms for maintaining those bounds.
Limits and assumptions
The result concerns exactly three identical parallel machines, unit-length jobs, nonpreemptive execution, and explicitly given precedence information. It permits arbitrary precedence constraints, but the supplied text gives no guarantee for different job lengths, different machine settings, or other input representations. The main result has a Lean formalization; its precise coverage is not specified here, so verification should not be assumed for every manuscript claim or implementation detail. The supplied material states no remaining open questions.
Mini glossary
- Precedence graph —
- A graph representing jobs and the requirements that certain jobs finish before others start.
- Nonpreemptive —
- Requiring each job to run without interruption once it starts.
- Makespan —
- The time at which the last job in a schedule finishes.
- Deadline feasibility —
- Whether there is a schedule in which all jobs finish by a specified deadline.
- Polynomial-time algorithm —
- An algorithm whose running time is bounded by a polynomial in the size of its input.
- Dynamic program —
- Here, the algorithmic search over the bounded-size interval descriptions used to organize schedules.
Keywords : Scheduling · Precedence constraints · Dynamic programming
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling
24/09/2026We 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.