The Setting
A cut through a full three-machine schedule separates the jobs before its boundary triple from those after it. The issue is the size of a Boolean description of these regions inside a parent window. The library states a bound for the target of an edge structural certificate, together with constructions of split vertices and their reversals.
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 the condition for a full precedence-respecting layout are given by (1). (1) For boundary slots and , the open scheduling window is the job set in (2). (2)✦ Times and ranks refer to the working frame, which may reverse original precedence and time. The ranks in opposite frames sum to .
Boundaries and Boolean Descriptions
A job triple is a set of three jobs.✦ A scheduling triple boundary of a layout is an actual triple or one of the endpoints .✦ The boundary time of a scheduling triple boundary of a layout is at and at ; for an actual triple , the boundary time is when and .✦
The strict predecessor and successor cones of an actual triple, and their weak versions, are the sets in (3). At both predecessor cones are empty and both successor cones are ; at these assignments are reversed. (3) For a boundary and a job set , the boundary prefix set is defined by (4). (4)✦ A boundary separates a job set at slot using a cutoff when every earlier than and outside belongs to , and every later than and inside belongs to .✦
An atomic family on is an indexed family of subsets of , with one subset assigned to each atom. A Boolean structural formula over an atomic family is a signed atom or a conjunction or disjunction of two such formulas.✦ The job set denoted by a Boolean structural formula over is written : a positive atom denotes and a negative atom its complement in , while conjunction and disjunction denote intersection and union.✦ The leaf count of a Boolean structural formula is one at an atom and the sum of the two counts at either binary operation.✦ For a leaf bound , the collection of globally described subsets of and the collection of subsets with a relative description in are defined by (5). (5) The rank upper tail at threshold for the rank on is the set of jobs whose ranks are at least .✦ An expressive atomic family for the precedence relation and rank on is an atomic family for which , the empty set, every rank upper tail, every triple, and all four cones of every boundary belong to .✦
A scheduling split vertex of is a partition of into pairwise disjoint regions, where is a triple that is an antichain for . No precedence edge goes from to , from to , or from to , and , with the fixed allowance . Write for the set of these vertices.
Edge Certificates
An indexed global set family on is a sequence of subsets of with a finite set of listed indices.✦ The entry union of an indexed global set family with listed indices is the job set given by .✦ The membership indices of a job are the indices in whose entries in contain ; the last membership index is the maximum membership index of , with default zero. Lexicographic list priority orders jobs by .✦ A set is upward closed when and imply .✦ The family with listed indices has upward closed entries when every with is upward closed.✦ The injection entries of with listed indices are disjoint in when the sets , for listed , are pairwise disjoint.✦
A rank threshold run certificate for in consists of bases , thresholds , and a second set , subject to (6). (6)✦ For a boundary at slot , the past boundary invariant requires every with to belong to .✦
A layout is unchanged outside a job set relative to when for every .✦ Exchanging two jobs trades their positions and leaves all other positions fixed.✦ The forbidden exchange invariant on at requires the following condition for every precedence-respecting layout unchanged outside : if , has , and has list priority over , then exchanging violates precedence feasibility.✦
An edge structural certificate uses a full layout , the parent , and boundaries at slots , respectively, with actual and the slot conditions in (7). (7) Its cutoff and final cutoff satisfy . The boundary separates at using ; the boundaries and separate at and using . Its global family has a rank threshold run certificate, upward closed entries and second set, disjoint injection entries in , and . It satisfies the past boundary invariant at and the forbidden exchange invariant on at . A global cutoff and a downward closed lower extension both agree with inside ; downward closure means that every predecessor of a job in belongs to .
The Claim
Theorem 1. For an expressive atomic family, any boundary and any satisfy the boundary prefix bound (8)✦ Let an edge structural certificate be given for an expressive atomic family, with its one-leaf final cutoff. There is a global job set such that (9)✦ Let be full, , and . Suppose the actual boundary triple is at slot , , , , and . The time-induced split vertex has as its left region the jobs of before slot , as its middle triple , and as its right region the jobs of after slot . (10)✦ For any split vertex , reversing the precedence relation gives the reversed split vertex (11)✦
In the paper, the result reads: every marked slot in a node has a relative description of its earlier jobs in its producing working direction and in original time, in the permitted atomic language and with fewer than leaves.
What Is Checked
The bounds (8) and (9) are stated over finite job sets, precedence relations and ranks with expressive atomic families, using boundary prefix sets and edge structural certificates, respectively; the constructions (10) and (11) concern full layouts with the stated interior boundary and description hypotheses, and arbitrary scheduling split vertices, respectively.