The Setting
A recursive decomposition of a three-machine schedule assigns jobs to open intervals between boundary slots. A child interval needs the same structural conditions as a parent interval, including conditions on jobs outside it and on exchanges across its left boundary.
Let be a valid deadline and a finite job set of size , with precedence relation and rank . A layout is a bijection from to the positions , read in consecutive triples.✦ Its slot assignment and open scheduling windows are given by (1); a full layout respects precedence, meaning that requires . (1)
A scheduling triple boundary is a left endpoint, a set of three jobs, or a right endpoint.✦ Their boundary times are respectively , a slot with and , and .✦ For an actual boundary , its strict predecessor and successor cones and their weak versions are defined by (2). At the left endpoint the predecessor cones are empty and the successor cones are ; at the right endpoint these assignments are reversed. (2)
A boundary at slot separates a job set relative to a cutoff when (3) holds. (3)✦
Descriptions and Structural Conditions
An atomic family assigns a subset of to each atom. A Boolean structural formula over is a formula whose leaves are signed atoms and whose binary operations are conjunction and disjunction.✦ Its interpretation uses complement in for a negative leaf, intersection for conjunction and union for disjunction.✦ Its leaf count is one at a leaf and adds the counts of the two subformulas at either binary operation.✦ A set has description bound , written , when (4) holds. (4)✦
The family has atomic predicate expressiveness for and if , the empty set, every rank upper tail , every boundary’s strict and weak cones, and every job triple each have description bound one.✦
An indexed global set family consists of a finite index set and job sets for all natural numbers .✦ Its global entry union , membership indices and last membership index are specified in (5). Lexicographic list priority orders jobs by .✦ (5) The family obtained by pruning relative to a job set retains precisely the listed indices whose entries meet , with every global entry unchanged.
A job set is globally upward closed for when it contains every successor of each of its jobs.✦ An indexed global set family has upward-closed entries when every listed job set is globally upward closed for .✦ For a scheduling window , the injection entries of an indexed global set family are disjoint within when for distinct listed indices .✦
A rank threshold run certificate for on consists of base sets , thresholds and a distinguished second set , satisfying (6). Listed nonzero bases have description bound two, has bound , and has bound one. If and is nonempty, then and every job of belongs to . (6)
The past boundary invariant for at a boundary with time is .✦
A layout is unchanged outside relative to if for every .✦ Exchanging and in trades their positions and leaves every other position fixed.✦ The forbidden exchange invariant on at requires the following: for every precedence-respecting unchanged outside , jobs and with and have an exchange that fails precedence feasibility.✦
A reverse induction seed at a boundary with time for a window is a job set closed under predecessors, with description bound , such that and every job of has slot strictly before .✦
A node structural certificate on consists of a full layout , boundaries at slots with , and an indexed family with a rank threshold run certificate on . Its entries and second set are upward closed, its injection entries are disjoint within , and . Its confinement conditions are (7); it satisfies the past boundary and forbidden exchange invariants at , has , and has a reverse induction seed at . Write for these certificates. (7)
Edge Certificates
An edge structural certificate on a parent window has a full layout and boundaries at times respectively. The target is an actual triple and the slot bounds are (8). Set and . (8)
The certificate has a cutoff and final cutoff , with . The center separates relative to ; both and separate relative to , at their respective boundary times. It has an indexed family with a rank threshold run certificate on , upward-closed entries and second set, and injection entries disjoint within . The labels and cutoff satisfy (9). The past boundary invariant holds at and the forbidden exchange invariant holds on at that boundary. (9)
The edge certificate has a global cutoff of description bound and a lower extension of description bound . The set is closed under predecessors, and their agreement with is given by (10). (10)
The Claim
Theorem 1. Let be an edge structural certificate as above. If is transitive and has atomic predicate expressiveness for , the child node construction satisfies (11). (11)✦ For every edge structural certificate, the child window satisfies (12). (12)✦
In the paper, the result reads: at every child edge is an actual triple in and is either the boundary at or an actual triple in the open side ; for with shared cutoff , and ; every child excludes the center and is strictly smaller than its parent, and the root has no nonempty switched child.
What Is Checked
The claims concern finite job sets, full layouts and edge structural certificates; child node reconstruction also assumes transitive precedence and atomic predicate expressiveness.
For , a rank threshold run certificate for on yields a pruned run certificate for the family pruned relative to on , with the same rank and atomic family.✦