OctoInformBeta

OpenAI preprint, September 2026 · §2. Full schedules, frames, and descriptions

§2 (setting): full schedules, reachability, intervals, and the two frames: Reachability and boundary cones for jobs grouped into time slots of three

Full schedules and their reversed layouts.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A schedule of unit jobs on three machines assigns jobs to time slots subject to directed precedence constraints. Grouping a job order into consecutive triples supplies such slots; windows and boundary cones select jobs by their time coordinates and precedence relations, respectively.

The Definition

Definition 1. An instance on the original job set I={0,…,n−1}I=\{0,\ldots,n-1\} is a finite list EE of ordered pairs of jobs.✦ A directed constraint x→Eyx\to_E y means that (x,y)(x,y) occurs in EE.✦ The precedence relation ≺E\prec_E of the instance EE is positive-length directed reachability, as in (1). x≺Ey⇔∃k≥1∃x0,…,xk∈I:x0=x,xk=y,xi→Exi+1(0≤i<k).x\prec_E y \quad\Longleftrightarrow\quad \exists k\geq 1\ \exists x_0,\ldots,x_k\in I: \ x_0=x,\ x_k=y,\ x_i\to_E x_{i+1}\ (0\leq i<k).(1)✦

For a relation rr on II and any nonnegative integer mm, the padded relation rmr_m on Jm={0,…,m−1}J_m=\{0,\ldots,m-1\} is the relation obtained by matching numerical labels in (2). For a deadline TT, write N=3TN=3T and J=JNJ=J_N. rm(u,v)⇔∃x,y∈I:u=x∧v=y∧r(x,y),u,v∈Jm.r_m(u,v) \quad\Longleftrightarrow\quad \exists x,y\in I:\ u=x\ \land\ v=y\ \land\ r(x,y), \qquad u,v\in J_m.(2)✦

For the layout and boundary constructions, let JJ be any finite job set and let rr be a relation on JJ. A layout pp of JJ is a bijection from jobs to consecutive positions starting at zero, as in (3). p:J→∼{0,…,|J|−1}.p:J\xrightarrow{\ \sim\ }\{0,\ldots,|J|-1\}.(3)✦ The time slot tp(x)t_p(x) of a job xx in layout pp is assigned by grouping consecutive positions into triples, as in (4). tp(x)=⌊p(x)3⌋+1.t_p(x)=\left\lfloor\frac{p(x)}{3}\right\rfloor+1.(4)✦ A layout pp of JJ respects rr when each related pair occupies strictly increasing slots, as in (5). Respects⁡r(p)⇔∀x,y∈J,r(x,y)⇒tp(x)<tp(y).\operatorname{Respects}_r(p) \quad\Longleftrightarrow\quad \forall x,y\in J,\quad r(x,y)\Longrightarrow t_p(x)<t_p(y).(5)✦ A full schedule for rr on JJ is a layout pp satisfying (6). Full⁡r(p)⇔3∣|J|∧Respects⁡r(p).\operatorname{Full}_r(p) \quad\Longleftrightarrow\quad 3\mid |J|\ \land\ \operatorname{Respects}_r(p).(6)✦

For a time assignment t:J→ℕt:J\to\mathbb N and natural boundary slots a,ba,b, the open time window Wt=(a,b)W_t=(a,b) is the set of jobs strictly between those slots in (7); write WW when the time assignment is fixed. Wt=(a,b)={x∈J:a<t(x)<b}.W_t=(a,b)=\{x\in J:a<t(x)<b\}.(7)✦

A job triple ZZ of JJ is a subset containing exactly three jobs; the family of triples is 𝒯(J)\mathcal T(J) in (8). 𝒯(J)={Z⊆J:|Z|=3}.\mathcal T(J)=\{Z\subseteq J:|Z|=3\}.(8)✦ A boundary BB of JJ is an actual triple or a virtual left or right endpoint, denoted 𝖫\mathsf L and 𝖱\mathsf R; its possible values form the disjoint union in (9). ℬ(J)={𝖫}⊔𝒯(J)⊔{𝖱}.\mathcal B(J)=\{\mathsf L\}\sqcup\mathcal T(J)\sqcup\{\mathsf R\}.(9)✦ The predecessor cone Pr(B)P_r(B) of a boundary BB is the subset of JJ specified in (10). Pr(B)={⌀,B=𝖫,{x∈J:∃z∈Z,r(x,z)},B=Z∈𝒯(J),J,B=𝖱.P_r(B)= \begin{cases} \varnothing,&B=\mathsf L,\\ \{x\in J:\exists z\in Z,\ r(x,z)\},&B=Z\in\mathcal T(J),\\ J,&B=\mathsf R. \end{cases}(10)✦ The successor cone Dr(B)D_r(B) of a boundary BB is the subset of JJ specified in (11). Dr(B)={J,B=𝖫,{x∈J:∃z∈Z,r(z,x)},B=Z∈𝒯(J),⌀,B=𝖱.D_r(B)= \begin{cases} J,&B=\mathsf L,\\ \{x\in J:\exists z\in Z,\ r(z,x)\},&B=Z\in\mathcal T(J),\\ \varnothing,&B=\mathsf R. \end{cases}(11)✦ The weak predecessor cone P¯r(B)\overline P_r(B) of a boundary BB is the subset of JJ formed by adjoining an actual boundary triple to its predecessor cone, with the virtual endpoint values in (12). P¯r(B)={⌀,B=𝖫,Pr(Z)∪Z,B=Z∈𝒯(J),J,B=𝖱.\overline P_r(B)= \begin{cases} \varnothing,&B=\mathsf L,\\ P_r(Z)\cup Z,&B=Z\in\mathcal T(J),\\ J,&B=\mathsf R. \end{cases}(12)✦ The weak successor cone D¯r(B)\overline D_r(B) of a boundary BB is the subset of JJ formed by adjoining an actual boundary triple to its successor cone, with the virtual endpoint values in (13). D¯r(B)={J,B=𝖫,Dr(Z)∪Z,B=Z∈𝒯(J),⌀,B=𝖱.\overline D_r(B)= \begin{cases} J,&B=\mathsf L,\\ D_r(Z)\cup Z,&B=Z\in\mathcal T(J),\\ \varnothing,&B=\mathsf R. \end{cases}(13)✦

The reversed layout prevp^{\mathrm{rev}} of a layout pp on JJ is the layout with positions specified by (14). Write tpt_p for original time and tprevt_{p^{\mathrm{rev}}} for time in the reversed working layout. prev(x)=|J|−1−p(x).p^{\mathrm{rev}}(x)=|J|-1-p(x).(14)✦

For a key kk from a finite job set JJ to a totally ordered set, the rank Rk(x)R_k(x) of a job xx is one plus the number of jobs with smaller key, as in (15). Rk(x)=1+|{y∈J:k(y)<k(x)}|.R_k(x)=1+\bigl|\{y\in J:k(y)<k(x)\}\bigr|.(15)✦ On the numerically labelled job set J=JNJ=J_N, the predecessor count cr(x)c_r(x) of a job xx is the number of jobs yy with r(y,x)r(y,x)✦, and its predecessor count key kr(x)k_r(x) is the lexicographically ordered pair in (16). cr(x)=|{y∈J:r(y,x)}|,kr(x)=(cr(x),x)in lexicographic order.c_r(x)=\bigl|\{y\in J:r(y,x)\}\bigr|, \qquad k_r(x)=(c_r(x),x)\quad\text{in lexicographic order}.(16) The predecessor count rank ρr(x)\rho_r(x) of a job x∈JNx\in J_N is the rank of xx under its predecessor count key krk_r, as in (17). ρr(x)=Rkr(x).\rho_r(x)=R_{k_r}(x).(17)✦ The reversed predecessor rank ρrrev(x)\rho_r^{\mathrm{rev}}(x) of a job x∈JNx\in J_N is the complementary rank defined in (18). ρrrev(x)=N+1−ρr(x).\rho_r^{\mathrm{rev}}(x)=N+1-\rho_r(x).(18)✦

In the paper, the result reads: after rejecting n>3Tn>3T, add 3T−n3T-n isolated jobs to obtain JJ with N=3TN=3T; a full schedule partitions JJ into ordered antichain triples respecting positive-length reachability; restrictions use this transitive order, including paths through exterior vertices; the reversed frame reverses precedence, time, and a fixed linear extension, with the two ranks summing to N+1N+1; actual triples have predecessor and successor cones, whose weak versions include the triple, with virtual left boundary values P=P¯=⌀P=\overline P=\varnothing and D=D¯=JD=\overline D=J, and virtual right boundary values P=P¯=JP=\overline P=J and D=D¯=⌀D=\overline D=\varnothing.

What Is Checked

These definitions are stated over finite directed instances and finite job sets with an arbitrary relation, with numerical job labels for padding in (2) and for the predecessor count ranks in (17) and (18).