The Setting
Consider a finite set of unit jobs with precedence relation , and put . Structural completeness concerns recursive decompositions of schedules that fill all three machines at every slot, with a fixed allowance for Boolean formula leaves.
A layout of is a bijection to the positions , read in consecutive triples.✦ Its time assignment is given by (1). (1)✦ A layout respects precedence if implies .✦ A full layout of is a layout that respects precedence and satisfies ; its deadline is , so .✦
A boundary of a layout of is a left endpoint, a right endpoint, or a triple with .✦ The endpoints occur at times and .✦ An actual boundary is at when and .✦ For boundary times and , the open window is the subset of in (2). (2)✦
The predecessor and successor cones of an actual boundary , and their weak versions, are defined by (3). (3) At the left endpoint both predecessor cones are empty and both successor cones are ; at the right endpoint these choices are reversed. A boundary at separates a set in when (4) holds; write this condition as . (4)✦
Descriptions and Recursive Acceptance
An atomic assignment assigns a subset of to each atom in a set . A Boolean structural formula over is a signed atomic leaf, or a conjunction or disjunction of two such formulas.✦ Its interpretation and leaf count are given by (5), where is either or . (5) A global description of with allowance is a Boolean structural formula satisfying the conditions in (6); denotes its existence. A relative -leaf description of a set in is a representation for some with . $$\mathsf D_k(S)\quad\Longleftrightarrow\quad \exists\varphi,\quad \llbracket\varphi\rrbracket_\alpha=S\quad\hbox{and}\quad\ell(\varphi)\le k.$$(6)✦
A working frame for is a choice of either forward precedence with rank , or reversed precedence with rank . Original time always means . For ranks numbering one order and its reversal, the convention is . The canonical atomic assignment interprets Boolean constants as and ; its threshold atoms are and , where and is the rank of the chosen frame. Its remaining atoms are , , , and in either frame.
An assignment has atomic support for if , , every rank tail , every boundary cone and every triple have a description with one leaf.✦ Recursive structural acceptance for requires at every depth, where . At depth zero it also requires . At depth , recursive structural acceptance requires either or a possibly empty chain of allowed structural splits of , with the initial left region, final right region and every intervening gap accepted at depth .
Global Families and Certificates
An indexed global family consists of a finite set and sets .✦ Its union is .✦ For an indexed global family and a job , the membership indices of form the set .✦ The last index of a job in this indexed global family is the maximum of its membership indices, with value zero when this set is empty.✦ List priority for jobs in the indexed global family is lexicographic order on .✦ A global upset of is a subset of closed under successors for ; a downset of is an upset for .✦ An indexed global family has upward-closed entries when every with is an upset.✦ An indexed global family has injection entries disjoint in when for distinct with .✦
A rank threshold run for on is a family of subsets of , rank thresholds and a distinguished subset of satisfying (7). $$\begin{aligned} E_i&=C_i\cap\{x:k_i\le\rho(x)\} &&(i\in I),\\ \mathsf D_{24}(C_0),\qquad \mathsf D_2(C_i)&\quad(i\in I,\ i\ne0),& C_1&=S_1,\qquad\mathsf D_1(S_1),\\ W\setminus S_1&\subseteq C_0,\\ 0\in I,\ x\in W\cap S_1&\ \Longrightarrow\ 1\in I\ \hbox{and}\ x\in E_1. \end{aligned}$$(7)✦
For a layout , an indexed global family with union , and a boundary at time , the past boundary invariant is the condition that every with lies in .✦ A layout agrees with outside when for every .✦ Exchanging in swaps their positions.✦ The forbidden exchange invariant for is the condition that swapping the positions of in violates precedence whenever respects precedence and agrees with outside , , and has and list priority greater than that of .✦ The job exchange of in a layout is the layout obtained by interchanging their positions and leaving every other job in place.
A reverse induction seed for at boundary and time is a downset satisfying (8). (8)✦ A node certificate for is a choice of boundaries at , a rank threshold run and a reverse induction seed at , with full and subject to (9). Its entries and are upsets, its injection entries are disjoint in , and it satisfies the past and forbidden exchange invariants at on . (9)
An edge certificate for is a choice of boundaries at , respectively, for a full layout with and , where is actual. Its cutoffs , a global cutoff , and a downset satisfy (10). (10) Its rank threshold run has upset entries and an upset , with injection entries disjoint in and . The past invariant holds at ; the forbidden exchange invariant holds there on .
The Claim
Theorem 1 (Structural completeness and description bounds).
Let be transitive. Suppose are injective, increase strictly along , respectively, and are both less than a common positive bound . Suppose has atomic support in both frames. For a node certificate on and any depth , the acceptance conclusion is (11). (11)✦
For the canonical assignment , let be transitive and let the forward and reverse ranks be injective, bounded above by , and strictly increasing along their respective precedence relations. These ranks may be chosen independently. Acceptance and existence of a full layout satisfy (12). (12)✦
Suppose has atomic support for . Let be the union of an indexed global family, with , and let hold. For boundaries and sets , assume the child decomposition identities (13). (13) The resulting global bound is (14). (14)✦
Suppose has atomic support for , and let an edge certificate have target boundary at . The target cut admits the relative description in (15). $$\exists F\subseteq J,\qquad \mathsf D_{210}(F)\quad\hbox{and}\quad W\cap F=\{x\in W:t_p(x)<b'\}.$$(15)✦
In the paper, the result reads: every feasible full three-machine schedule has a bounded-description hierarchy whose global node predicates and relative split predicates all have fewer than leaves.
What Is Checked
The claims are stated over finite job layouts and job sets, with transitive precedence and bounded injective ranks for completeness, and with atomic support and the specified decompositions or certificates for the description bounds.