The Setting
Scheduling subproblems select jobs by their positions relative to boundary triples and by Boolean conditions on precedence cones and rank thresholds. The description size is the number of formula leaves, rather than the number of selected jobs.
Let be a finite job set with precedence relation , written . A layout is a bijection from to positions , read as consecutive triples.✦ For boundary slots , the time assignment of a layout and its open scheduling window are given by (1). (1) A layout of respects precedence when implies .✦ A full layout of is a precedence-respecting layout with , where is its deadline.✦ Write for the parent window in (1).
A job triple is a subset of of cardinality three.✦ A scheduling boundary for is a left endpoint, a job triple, or a right endpoint.✦ Their boundary times are respectively , a slot whose jobs are exactly , and .✦ For an actual boundary, represented by a job triple , the strict predecessor and successor cones and their weak versions are given by (2). (2) For the left endpoint the predecessor cones are empty and the successor cones are ; the right endpoint has the opposite conventions. A boundary separates a job set at slot with cutoff when jobs of earlier than belong to , and jobs of later than belong to .✦
Boolean Descriptions and Runs
An atomic family assigns a job set to each atom. A Boolean structural formula over an atomic family is a formula with signed atomic leaves and binary conjunctions or disjunctions.✦ The interpretation of a Boolean structural formula over is the job set obtained by assigning to a positive leaf and to a negative leaf, and interpreting the two connectives as intersection and union.✦ The leaf count of a Boolean structural formula is the number obtained by assigning one to a leaf and adding the counts of the two subformulas at either connective.✦ For a job set and a leaf budget , the families of globally described sets and of relatively described sets in are the collections of job sets defined in (3). (3) For a rank function and a threshold , the upper tail is the job set .✦ Atomic predicate expressiveness means that , the empty set, every , every boundary cone in (2), and every job triple belong to .✦
An indexed global set family is a pair consisting of a finite index set and a sequence of job sets .✦ The qualifier union of an indexed global set family is the job set .✦ For a job and an indexed global set family , the membership-index set of is , and the last membership index of in is , with default zero. Lexicographic list priority orders jobs by .✦ For an indexed global set family , an index threshold , and a rank threshold , the suffix is the family obtained by discarding listed entries before , restricting the entry at to , and retaining listed entries after .✦
A rank threshold run certificate for in consists of bases , thresholds , and a distinguished set , satisfying (4): (4)✦ A global upset is a job set closed under successors for ; a global family has upward-closed entries when every listed entry is a global upset. The injection entries with listed indices of a global family are disjoint in when is empty for distinct listed .✦
For a layout , a global family , and a boundary at time , the past boundary invariant requires every job of scheduled at or before to belong to .✦ A layout is unchanged outside a set relative to when every job outside keeps its position.✦ Exchanging and swaps their positions and fixes all other jobs.✦ The forbidden exchange invariant for requires that whenever is a precedence-respecting layout unchanged outside relative to and jobs satisfy , , , and list priority of over , exchanging and in violates precedence feasibility.✦ The job exchange of jobs and in a layout is the layout obtained by swapping their positions and leaving every other job in its position.✦
Edge Certificates and Split Vertices
An edge structural certificate uses a full layout , parent , and boundaries at times , respectively, where is actual and (5) Besides (5), it has a cutoff and a final cutoff . Boundary separates at with cutoff ; and separate at their respective times with cutoff . It requires .
Its family has a run certificate in , upward-closed entries, an upward-closed distinguished set , and disjoint injection entries in . It satisfies , the past boundary invariant at , and the forbidden exchange invariant on at that boundary. The certificate also has sets and with , where is downward closed under precedence.
A scheduling split vertex in is a partition of into pairwise disjoint regions , where is a job triple and an antichain. There is no precedence from a later region to an earlier one in the order , and with the fixed allowance . Write for the collection of these vertices.
The Claim
Theorem 1. Assume atomic predicate expressiveness for and . For a rank threshold run certificate of in with , the qualifier bound is (6): (6)✦ For the same run, every boundary and thresholds satisfy the suffix cutoff bound (7): (7)✦ Let be a global family with , and let . Suppose boundaries , a job set , and a cutoff satisfy the high and low part identities (8) The child bound under (8) is (9): (9)✦ For an edge structural certificate with target time , the target description is (10): (10)✦ Independently, let be a full layout, , and . Let be the actual boundary triple at . Suppose , , , and . The split vertex at time has left region , middle region , and right region , and belongs to the collection in (11): (11)✦
In the paper, the result reads: the global child predicates and relative marked-split predicates of Lemmas 8.1 and 8.2 have fewer than leaves, with at most for the qualifier union, for a same-direction cutoff ( allowed uniformly), and for the high and low child predicates, for their union, three for the center, for an internal split, and one additional leaf for reverse conversion.
What Is Checked
The claims are stated over finite job sets with atomic families and rank functions; the scheduling constructions additionally use full precedence-respecting layouts, boundary times and separation, and the specified run and edge structural certificates.