Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.
OAI-26 family 124: polynomial-time three-machine precedence scheduling
Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This documentary article describes a claim in the pinned publisher overview, not an independently validated scheduling algorithm.
The question in plain language
A collection of jobs must be scheduled across three identical machines. Every job takes one unit of time, can run on only one machine at a time, and cannot be interrupted. Certain jobs must finish before others can begin. The goal is to finish everything as early as possible, minimizing the makespan.
Family 124 claims a deterministic polynomial-time algorithm for this three-machine precedence-constrained unit-job problem, resolving a scheduling question attributed to Garey and Johnson.
A small example
Consider five unit-length jobs: \(A\) and \(B\) must finish before \(D\) starts, while \(C\) must finish before \(E\). With three identical machines, \(A,B,C\) may occupy the first time slot, followed by \(D,E\) in the second. A two-slot schedule meets all precedence constraints.
On a larger instance, choosing which available jobs to run now affects which successors become eligible later. Simply filling idle machines greedily does not by itself prove an optimal schedule.
What is known
The protected Family 124 catalogue identifies one manuscript, A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling.
The pinned publisher overview claims that for three identical parallel machines, nonpreemptive unit-length jobs, and arbitrary precedence constraints, there is a deterministic polynomial-time algorithm that minimizes makespan.
For an explicitly given precedence graph, the overview separately claims that the algorithm determines whether a deadline is feasible and constructs a feasible schedule when one exists. Deadline feasibility and minimum makespan are related but distinct output specifications; the conversion between them must be verified, including its time horizon and input encoding.
The claim does not automatically extend to variable job lengths, more than three machines, unrelated machines, release dates, or additional resource constraints. The number three and unit processing times are structural assumptions, not illustrative details.
GCL verification state
Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The source catalogue identifies the manuscript and the pinned overview specifies its deterministic complexity claim and scheduling model.
This documentary pass has not independently checked the algorithm, recurrence or decomposition, correctness proof, runtime polynomial, precedence-cycle handling, or schedule reconstruction. No Family 124-specific accepted proof-critical review, Lean elaboration, Comparator result, or MATHCERT certificate is asserted.
What remains
Read the pinned PDF and extract its exact model: precedence graph representation, possible cyclic inputs, integer time slots, treatment of idle time, and whether precedence is strict completion-before-start. Reconstruct the decision algorithm and its polynomial runtime on the full encoded input size.
Verify correctness in both directions for deadline feasibility, then check the construction of an explicit schedule and the reduction to optimal makespan. Audit exceptional small cases and ensure the proof covers arbitrary partial orders rather than only a subclass of precedence graphs.
Complete mathematical Markdown/MkDocs regression, source-critical editorial review, and protected merge/readback. Editorial acceptance would not certify the scheduling algorithm.
Sources and claim boundaries
Boundary: NO_CERTIFICATION. The deterministic polynomial-time scheduling result remains a publisher-reported claim pending independent verification.
Indexed primary manuscript paths:
- A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling —
preprints/A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling-September-24-2026/paper.pdf