1. The question
Three identical machines must complete a collection of jobs. Every job takes one unit of time, but some jobs must finish before others can start. What is the shortest possible completion time?
The simplicity of the ingredients is deceptive. If there are no dependencies, divide the jobs into groups of three. If every job depends on the preceding one, execute them in a single chain. General dependency patterns sit between these extremes: a locally sensible choice can leave machines idle later, while postponing an available job can help another part of the schedule finish sooner.
The question is about exact optimization for arbitrary precedence constraints. It asks for the mathematically best schedule, not merely one whose duration is close to optimal. With two machines, classical polynomial algorithms are known. With an unrestricted number of machines supplied as input, the general problem is NP-complete. The fixed case of three machines has long occupied the gap between these two facts.
This manuscript claims a uniform deterministic polynomial-time solution for three machines. Its explicit polynomial has an enormous exponent, so the proposed resolution concerns computational complexity rather than practical scheduling speed.
2. Background and essential definitions
Represent the jobs by the vertices of a directed acyclic graph . An edge means that job must finish before job starts. Acyclicity excludes contradictory requirements such as a job indirectly preceding itself. Write .
For a deadline , a schedule assigns each job a slot:
It is feasible when no slot contains more than three jobs and
Slot corresponds to the interval . The makespan is the latest completion time. Jobs are nonpreemptive: once started, each occupies one machine for its entire unit of processing.
Two elementary lower bounds are the longest chain of dependent jobs and , the capacity bound. Neither alone describes the interactions among different branches of the precedence graph. The optimization problem must account for those interactions throughout the schedule.
An antichain is a set of mutually incomparable jobs: no job in the set precedes another through any directed path. Each slot is an antichain of size at most three. A linear extension is a total ordering of the jobs that respects every precedence relation. It supplies a consistent priority order, but simply placing jobs in that order need not produce an optimal schedule.
The manuscript assumes an explicitly listed finite graph. Input length includes the binary encoding of its vertices, edges, and any deadline. Polynomial time is measured in this full input length.
3. Development history and previous partial results
Fujii, Kasami, and Ninomiya studied optimal scheduling on two processors in the late 1960s. Coffman and Graham subsequently gave their influential optimal two-processor algorithm. These results established that unrestricted precedence constraints do not by themselves force intractability when the number of machines is two.
Ullman’s 1975 complexity results showed NP-completeness when the machine count is part of the input. This does not settle a fixed value such as three: a reduction may use an increasing number of machines. The fixed-three question consequently appeared among the open problems in Garey and Johnson’s classic book on NP-completeness.
Several restricted cases became tractable. Garey, Johnson, Tarjan, and Yannakakis obtained efficient algorithms for special precedence structures called opposing forests. Dolev and Warmuth gave a bound depending on the height of the precedence graph and the number of machines. When both are fixed, their bound is polynomial; arbitrary graphs can have height growing with the number of jobs. Their bounded-height work also developed structural normalization of schedules.
More recently, Nederlof, Swennenhuis, and Węgrzycki obtained a subexponential exact algorithm. For three machines, its time is of the form . This improves substantially on unrestricted exponential search, but remains above every fixed polynomial.
Approximation developed alongside exact algorithms. Levey and Rothvoß used linear-programming hierarchies, followed by quasipolynomial approximation schemes and simpler combinatorial approaches. A representative account is Das and Wiese’s scheduling scheme. These methods can approach the optimal makespan arbitrarily closely under fixed parameters. They do not automatically decide whether a particular integer deadline is achievable.
The new manuscript builds on the structural decomposition viewpoint: identify small boundaries in a schedule, then describe and combine the portions between them. Its claimed additional step is to keep every relevant subproblem describable with bounded information, regardless of recursion depth.
4. What the new manuscripts claim
For an explicitly listed directed acyclic graph of unit jobs, the manuscript states that a single deterministic algorithm constructs a minimum-makespan schedule on three identical machines. Given a deadline , it also decides feasibility exactly and returns a schedule when one exists.
If denotes total binary input length, the stated multitape Turing-machine bound is
The large exponent is part of the claim’s interpretation. It establishes a fixed polynomial independent of the input; it does not describe an algorithm suitable for current industrial instances. Both deciding feasibility and writing an optimal schedule are included.
No release dates, communication delays, machine eligibility rules, or additional resources are present. All processing times equal one. The machines are identical, and a job may run on any of them. The graph may otherwise contain arbitrary precedence constraints.
The use of integer slots is also justified within this model. Starting from any feasible real-time schedule, fix each machine’s job order. Add those order constraints to the precedence graph, then start each job as early as its predecessors permit. Because durations are integral, the resulting starts are integral and completion times do not increase. Thus restricting attention to slots does not lose a better schedule hidden at fractional starting times.
5. Why the advance matters
Provisional importance: 4/5. The claim resolves a longstanding exact-complexity question for a basic scheduling model. Three machines are the first fixed machine count beyond the classical two-machine theory, making this boundary especially informative.
The conceptual importance extends beyond whether one particular exponent is useful. A polynomial algorithm says that the enormous set of potential schedules has enough structure to admit a finite description of manageable asymptotic size. It identifies information that can be discarded while preserving the possibility of an optimal completion.
The contribution also illustrates the distinction between a classification theorem and an efficient implementation. A degree of 150020 is prohibitive, but replacing a superpolynomial search with a polynomial one can reveal a structural principle that later algorithms improve. Such improvements are prospects, not consequences already supplied by the manuscript.
The score reflects the central scheduling question and the proposed decomposition method. It does not imply that arbitrary scheduling problems become easy, or that the same method already handles four or more fixed machines.
6. The main idea
Fill empty capacity with harmless jobs
For a deadline , first reject if . Otherwise add isolated dummy jobs. They have no precedence constraints, so they can occupy unused capacity without obstructing real jobs.
A feasible schedule then consists of exactly antichain triples. Deleting the dummy jobs recovers a schedule for the original instance. This conversion makes the combinatorial object more regular: every time slot has the same size.
Describe an interval by its relation to a few boundaries
Suppose selected slots divide a feasible schedule into intervals. If the set of jobs belonging to one interval is known, any feasible reordering of that set preserves its temporal relationship to all jobs outside the interval. This suggests dynamic programming: solve smaller intervals and concatenate compatible solutions.
The obstacle is identifying the interval’s job set. Naming the triples at its endpoints is not enough. Many jobs can be unrelated to those boundary jobs, and repeated subdivisions can accumulate an ever-longer record of earlier choices. Without additional structure, there could be exponentially many distinguishable subproblems.
The manuscript claims that a suitably normalized feasible schedule admits global descriptions of bounded size. The descriptions use simple tests: whether a job precedes or follows a member of a selected triple, whether it belongs to the triple, and whether it lies before a cutoff in a fixed linear extension. Boolean combinations of these tests specify a subset of all jobs.
“Global” matters here. A formula must identify the intended jobs throughout the original instance, not merely behave correctly inside an interval whose membership is already assumed known. Otherwise hidden information about the ancestors of the interval would remain necessary.
Prevent descriptions from growing with recursion
The structural argument moves separators through a schedule while adjusting a priority cutoff. It also treats the two sides of a central slot by reversing time and precedence. Short lists of upward-closed sets carry the information needed at a boundary: if a job belongs to such a set, its successors in the current direction belong as well.
According to the manuscript, exchange conditions and boundary conditions allow obsolete information to be removed. When the direction changes, a paired representation prevents the previous history from expanding the description indefinitely. The final description has a fixed upper bound on its number of logical tests.
The algorithm enumerates all descriptions within a fixed allowance, evaluates the corresponding job sets, and solves them in increasing size. Compatible accepted pieces provide a larger schedule; predecessor records recover an explicit solution. The allowance is extremely generous, producing the huge polynomial exponent, but remains independent of .
One subtlety is that normalized schedules are used as existence witnesses. The algorithm does not first compute an optimal schedule in order to normalize it. It searches the finite family of descriptions, while the structural theorem claims that some successful decomposition must occur in that family whenever the deadline is feasible.
7. Scope, limitations, and open questions
The result is exact and deterministic in the stated encoding, but its running time is theoretical. Reducing the description family, the exponent, or the overhead of searching it would be necessary before practical relevance could be assessed.
The assumptions are substantial. Different job lengths change which exchanges preserve feasibility. Release dates and communication delays can couple an interval to its surroundings. Machine-dependent processing or eligibility rules destroy the symmetry among the three slots available at a time. None of those variants follows from this theorem.
The claim also does not establish a polynomial algorithm for every fixed machine count. The structural bounds exploit triples and the way three-machine boundaries limit inherited information. Extending them would require additional arguments.
Finally, approximation and exact optimization answer different questions. Earlier approximation schemes remain meaningful even if their assumptions overlap, particularly when their computational costs are more reasonable. This manuscript’s stated advance is a complexity classification and an explicit exact construction, reported here without independent proof verification.
8. Sources and further reading
The historical papers linked above trace the progression from two-processor algorithms through restricted precedence classes, approximation schemes, and subexponential exact search. The source manuscript below provides the precise input model, bounded-description theorem, and explicit polynomial-time accounting. Its introduction distinguishes these earlier advances from the claimed fixed-three resolution.
Source manuscripts
- M1. OpenAI, A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling (2026).
Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.