Unit-job scheduling on three identical machines

Source and verification

This article explains family 124 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Unit jobs and precedence constraints

Let a finite directed acyclic graph specify jobs and precedence edges. Every job takes one time unit, cannot be interrupted, and may use any of three identical machines. A schedule assigns a positive integer slot $\tau (v)$ to each job, with at most three jobs in each slot and $\tau (u)<\tau (v)$ on every precedence edge. Its makespan is the last occupied slot.

There are no release dates, communication delays, machine eligibility restrictions, or extra resources. The graph is explicitly listed. These modeling choices are part of the theorem.

The number of jobs divided by three and the length of a longest precedence chain are immediate lower bounds on makespan. They need not determine it. For example, take four minimal jobs, all preceding each of two final jobs. Six jobs suggest two slots by capacity, and the longest chain also has length two. But the four predecessors require two slots, so the final pair cannot run before slot three.

Real start times do not improve the optimum in this unit-length setting. Fix the machine assignments and within-machine orders from a feasible real-time schedule. Add arcs between consecutive jobs on each machine. The enlarged graph is acyclic, and starting every job as early as its predecessors permit gives integer times without increasing any completion time.

🏷️ The exact algorithmic claim

Manuscript statement

One uniform deterministic multitape Turing machine constructs a minimum-makespan schedule for every nonempty explicitly listed acyclic unit-job instance on three machines. Given $1\le T\le n$, it also decides exactly whether deadline $T$ is feasible and returns a schedule when it is. Both tasks take

$$O((L+2{)}^{150020})$$

steps, where $L$ is the binary input length. (OpenAI, 2026)

The fixed exponent establishes polynomial time but offers no practical performance claim. The result does not address arbitrary processing lengths or a variable number of machines.

The proof’s central assertion is structural: every feasible instance has a recursive schedule decomposition whose interval job sets have globally valid descriptions of bounded size. The algorithm enumerates those descriptions. It does not need to compute the lexicographically minimal schedules used as existence witnesses in the structural proof.

🏷️ Full schedules and interval replacement

For a deadline $T$, first reject if $n>3T$. Otherwise add $3T-n$ isolated dummy jobs. A feasible original schedule can fill every vacant position with a dummy, giving exactly three jobs in every slot. Conversely, deleting the dummies from such a full schedule recovers an original feasible schedule. Since $T\le n$, the padded instance has at most $3n$ jobs.

A slot is therefore an antichain triple: its jobs are pairwise incomparable in the transitive precedence order. Compute that transitive order on the entire padded job set $J$. Restricting it to a subproblem retains relations witnessed by paths passing outside the subproblem.

If an open interval between two slots has job set $W$, replace its internal schedule by any feasible full schedule of the same set. All exterior jobs remain either before the entire interval or after it, so their temporal relation to every job of $W$ stays unchanged. This elementary replacement fact supports recursive decomposition.

It does not follow that the two boundary triples determine $W$. Unrelated jobs may lie on either side of a boundary, and temporal order alone is not a precedence relation.

🏷️ A finite language for job sets

Fix a linear extension of the precedence order and give each job a rank $\lambda \in \{1,\dots ,N\}$, where $N=|J|$. Also use the reversed precedence order, time direction, and ranking.

For a triple $a$, define global predecessor and successor cones

$$\begin{array}{rl}{P}_a& =\{x:\exists y\in a,x\prec y\},\\ D_a& =\{x:\exists y\in a,y\prec x\}.\end{array}$$

Weak cones additionally include $a$ itself. Allowed atomic tests are membership in a triple or one of these cones, rank thresholds in either direction, and constants, together with their negations. There are $O(N^3)$ atoms.

Let $\mathcal{F}$ consist of truth sets of Boolean formulas with at most $K=10000$ leaves, using binary conjunction and disjunction. Here formulas are just a finite data structure for subsets, not an additional logical subject. Since $K$ is fixed, the number of tree shapes and connective choices is constant, and there are

$$O(N^{3K})$$

possible formulas. Evaluate each on all jobs and store its truth set as a bit vector. Even duplicate removal by pairwise comparison takes polynomial time.

A global description says $W=F$ for $F\in \mathcal{F}$. A relative description says $L=W\cap F$. The difference matters: a formula agreeing with an interval’s jobs only inside a known ancestor does not automatically identify that interval among all jobs. Repeatedly intersecting ancestors would enlarge descriptions with recursion depth.

🏷️ The dynamic program

Process sets $W\in \mathcal{F}$ in increasing cardinality. Accept the empty set and reject any set whose size is not divisible by three. For each remaining $W$, enumerate states

$$W=L\dot{\cup }Z\dot{\cup }R,$$

where $Z$ is an antichain triple and $L=W\cap F$ for some $F\in \mathcal{F}$. Retain only compatible states: no job in a later part precedes a job in an earlier part.

A state is initial if $L$ was accepted and final if $R$ was accepted. Join it to a state $(L^{\prime },Z^{\prime },R^{\prime })$ when $L\cup Z\subseteq L^{\prime }$ and the intervening gap

$$A=L^{\prime }\setminus (L\cup Z)$$

was accepted. A set outside $\mathcal{F}$ is treated as unaccepted. Every consulted gap is smaller than $W$. Accept $W$ exactly when an initial state reaches a final state, allowing a path consisting of one state.

The soundness proof is direct. A path gives an ordered disjoint partition into accepted gaps and selected triples. By induction, each gap has a full schedule. Compatibility excludes backward precedences between pieces, so concatenation schedules $W$. Recording predecessors and storing one schedule for each accepted set reconstructs the answer without repeatedly expanding the recursion.

The difficult part is completeness: why should some optimal schedule admit enough useful descriptions in this restricted family?

🏷️ The bounded-description hierarchy

The manuscript’s structural theorem states that every feasible full three-machine schedule has a hierarchy in which every interval job set has a global description and every marked split has a relative description. In fact, its constructed formulas have fewer than 500 leaves; the algorithm’s allowance of 10000 leaves leaves room for conservative bookkeeping. The hierarchy may have many levels.

At each nonempty interval, mark at least one actual triple and recurse on the open gaps. If the structural theorem holds, induction on interval size proves dynamic-program completeness: the child gaps are smaller described sets and hence accepted, while the marked triples form an initial-to-final path. No logarithmic bound on recursion depth is needed.

To obtain the hierarchy, the source normalizes intervals using a priority order. At a moving cutoff, call earlier-priority jobs low and the remaining jobs high. A separator triple controls high jobs lying before it and low jobs lying after it by actual precedence relations. Successive selected triples share a cutoff: low jobs in their gap have a predecessor in the left triple, and high jobs have a successor in the right triple.

The two sides of a central slot are treated by reversing both time and precedence. Short lists of successor-closed sets record inherited constraints. Capacity three bounds how many new entries can survive a boundary. A global boundary condition excludes distant jobs, while an exchange invariant preserves that exclusion under later interval reorderings. At direction changes, paired inherited information can be simplified to a bounded formula instead of retaining the full ancestor history. (OpenAI, 2026)

These global and exchange conditions are essential. A separator valid only within one known interval would not justify memoizing its formula as a subset of the entire job set.

🏷️ Uniform polynomial work and optimization

The source gives a deliberately conservative sequential-tape implementation. With $B=O_K(N^{3K})$ descriptions and at most $B{N}^3$ states per set, repeated scans of state pairs, reachability records, and stored schedules cost

$$O_K(B^5{N}^{13})=O_K(N^{15K+13}).$$

The displayed exponent in the theorem covers preprocessing and all deadline trials. A topological order schedules one job per slot, so some deadline at most $n$ is feasible. Testing $1,\dots ,n$ and retaining the first feasible one gives the optimum, after removing dummy jobs and assigning each triple to the three machines.

This separates the proof obligations cleanly: finite enumeration and path concatenation give a uniform algorithm and soundness; the bounded-description hierarchy supplies completeness. This article reviews those interfaces and the dynamic-program argument, rather than independently verifying the complete separator and boundary proof.

🏷️ Key steps and proof outlines

Localizing a candidate before using a relative predicate

The proof’s “Global interval predicates and completion” section explains why bounded descriptions do not grow with recursive depth. Let $W=(a,b)$ be a parent time interval, let $W^{\prime }=(a^{\prime },b^{\prime })$ be a child, and let $S$ be the low-priority part at its cutoff. A global predicate $\tilde{S}$ is known to agree with $S$ only inside $W$. It may select unrelated jobs elsewhere. (OpenAI, 2026)

The low child jobs are described by a conjunction whose positive factors first force membership inside the parent: a candidate must succeed some job in $a^{\prime }$ and precede some job in $b$. Only then is $\tilde{S}$ applied. Further exclusions remove the weak successor cones of $b^{\prime }$ and of the parent center. The separator properties imply that a remaining low job is strictly before both boundaries, hence belongs to the child gap.

The reverse implication checks every factor on an actual low child job. This proves equality of global sets, rather than merely agreement after intersection with the already-described parent. The order of logical justification is crucial: using $\tilde{S}$ outside its known domain would make the formula invalid.

High jobs use a different test: membership in the qualifying inherited list, precedence before $b^{\prime }$, and exclusion from the weak predecessor cone of $a^{\prime }$. The global past-boundary invariant says that any earlier qualifying job would belong to that excluded cone. Thus the high formula is also globally exact. Their union describes $W^{\prime }$ without appending any ancestor-membership predicate.

A fixed formula budget survives arbitrarily many levels

The pruned inherited list contains at most five entries with fewer than forty leaves each, so its union needs at most 195 leaves. The source allows 205 leaves for either cutoff formula. The high child formula uses at most 197 leaves and the low formula at most 209, giving 406 for their union. Relative split descriptions use at most 211. These bounds are independent of depth.

This arithmetic explains the algorithm’s conservative allowance $K=10000$. The polynomial bound comes from a fixed number of leaves, not a small recursion depth. With $O(N^3)$ possible atoms, bounded binary formula shapes yield $O(N^{3K})$ descriptions. A recursion may descend through many intervals while every node remains in that one polynomial-size family.

Reversing time also requires a precise conversion. If a predicate describes jobs later than a marked triple in the original direction, complementing it includes the triple itself. Subtract the marked triple after complementation to obtain the earlier jobs. The formula language already permits this operation at constant additional cost.

The dynamic program is complete by induction on job count

Assume the structural hierarchy supplied by the source. At a node $W$, list its marked triples in time order. Every gap between them, as well as the first and last gap, has fewer jobs than $W$ and a global bounded description. The induction hypothesis therefore accepts each gap in the dynamic program. Each marked triple has a relative split description, so it occurs among the enumerated states. Consecutive triples have exactly the accepted gap required by the transition rule. They form an initial-to-final path, proving that $W$ is accepted.

Conversely, an accepted path partitions $W$ into accepted smaller gaps and antichain triples. Compatibility forbids a precedence from any later piece into an earlier one. Concatenate the smaller schedules and the triples to obtain a full schedule. This is an ordinary finite induction and uses no priority-normalization assumptions; those assumptions were needed only to guarantee that a suitable path exists.

Padding with isolated jobs reduces deadline feasibility to full schedules, and deletion of those jobs recovers the original witness. Recording one successful path and one schedule per accepted set avoids expanding an exponential derivation tree during output. The theorem thus separates its difficult structural existence claim from its explicit finite search and witness reconstruction.

See Also

• Exact matching also requires explicit witnesses and a uniform finite-machine implementation, but with randomized success and a much stronger asymptotic runtime.
• Bin packing illustrates how unit capacity and bounded items per bin lead to different complexity questions from precedence-constrained unit jobs.

🏷️ Manuscripts and verification scope

• A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope records one deterministic polynomial-time machine for exact deadline feasibility and minimum makespan in the explicit unit-job model. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling.