OctoInformBeta

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

Lemma 2.2: For bijective job layouts that agree in position outside the interval

Feasible interval reorderings preserve precedence feasibility.

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 local scheduling change concerns both precedence constraints within an interval and constraints involving jobs outside it.

A job layout pp of a finite job set JJ is a bijection to its position indices, numbered from zero, as in (1); jobs are read in groups of three consecutive positions. p:J→∼{0,…,|J|−1}.p\colon J\xrightarrow{\sim}\{0,\ldots,|J|-1\}.(1)✦ The time slot tp(x)t_p(x) of a job x∈Jx\in J in a layout pp is its position divided by three, rounded down, plus one, as in (2): tp(x)=⌊p(x)3⌋+1.t_p(x)=\left\lfloor\frac{p(x)}{3}\right\rfloor+1.(2)✦

A precedence-feasible layout pp for a relation rr on JJ is a job layout in which related jobs occupy strictly increasing time slots, as specified by (3): ∀x,y∈J,xry⇒tp(x)<tp(y).\forall x,y\in J,\qquad x\,r\,y\ \Longrightarrow\ t_p(x)<t_p(y).(3)✦

A reordering qq of a job layout pp is fixed outside a subset W⊆JW\subseteq J if it is a job layout with the same position for every job outside WW, as in (4): ∀x∈J\W,q(x)=p(x).\forall x\in J\setminus W,\qquad q(x)=p(x).(4)✦

The open interval W=(a,b)W=(a,b) of a layout pp, for nonnegative integer boundaries aa and bb, is the set of jobs strictly between those slots: W=(a,b)={x∈J:a<tp(x)<b}.W=(a,b)=\{x\in J:a<t_p(x)<b\}.(5)

The Claim

Theorem 1. Let pp and qq be job layouts of a finite job set JJ, and let rr be a relation on JJ. Let W=(a,b)W=(a,b) be the open interval of pp defined by (5). Suppose that pp is precedence feasible for rr, that qq is fixed outside WW relative to pp, and that qq assigns every related pair of jobs in WW to strictly increasing time slots. Then ∀x,y∈J,xry⇒tq(x)<tq(y).\forall x,y\in J,\qquad x\,r\,y\ \Longrightarrow\ t_q(x)<t_q(y).(6)✦

In the paper, the result reads: replacing the schedule inside an open interval W=(a,b)W=(a,b) by any full schedule of its job set preserves feasibility of the complete schedule.

What Is Checked

The claim (6) is stated over bijective layouts of a finite job set JJ and a relation rr on JJ, subject to the interval and precedence hypotheses in the theorem.