The Setting
A change of direction in a scheduling recursion requires a cutoff for the next child window. The cutoff is a set of jobs defined on the whole schedule, even when its coverage condition concerns only that child.
Let be the job set, its precedence relation, and a working slot assignment with deadline . A job triple is a set of three jobs.✦ A scheduling triple boundary for the job set is a left endpoint, an actual job triple, or a right endpoint.✦ A boundary has time when the left endpoint has , the right endpoint has , or an actual triple has and consists exactly of the jobs assigned to slot .✦
For boundary slots , the open scheduling window is the job set in (1): (1)✦
The strict predecessor and successor cones of a boundary are the sets and in (2); their weak versions and include the actual boundary triple. Write for the cones of . (2)
A boundary separates job sets when the two inclusions in (3) hold; denote this condition by .✦ (3)
A global upset for is a subset of containing every successor of each of its jobs.✦ A global downset for is a subset of containing every predecessor of each of its jobs; equivalently, it is a global upset for the reversed precedence , where means .
Descriptions and Seeds
A Boolean structural formula over an index set is a leaf carrying an index and a positive or negative sign, or a conjunction or disjunction of two such formulas.✦ The interpretation of a Boolean structural formula for an atomic family of subsets of is the subset of obtained by assigning to a positive leaf and to a negative leaf, and interpreting conjunction and disjunction as intersection and union.✦ The leaf count of a Boolean structural formula is the number of its leaves, given recursively by one at a leaf and the sum of the two counts at either binary operation.✦ The family of job sets with a bounded Boolean description of allowance is defined by (4).✦ (4)
A reverse induction seed for a window , a boundary , and its slot is a global downset satisfying (5).✦ Denote the family of these seeds by . (5)
The switch set associated with boundaries and a job set is the intersection in (6).✦ (6)
The Claim
Theorem 1. For transitive and a global upset , the switch set has the property (7), for arbitrary scheduling triple boundaries: (7)✦
For the assertion (9), let and , with , and let be boundaries at their indicated slots. Suppose respects , all job times lie between and , and satisfy (8) Under the conditions in (8), (9)✦
For the assertion (11), let , , and , with , and let be boundaries at their indicated slots. Suppose is transitive and respects , and all job times lie between and . Let , with a global downset, and assume the conditions in (10): (10) Then (11)✦
In the paper, the result reads: for a nonempty switched child with preceding parent and current-frame arrangement , the preceding low cutoff’s extension gives a global upset that covers and contains no job scheduled at or before .
What Is Checked
The claims are stated over precedence relations and slot assignments on , using scheduling triple boundaries with their cone and separation conditions and the bounded Boolean descriptions in (4).