The Setting
The interval construction records which jobs may occur near either boundary of a scheduling window and which exchanges remain forbidden after its interior is reordered. For an instance with original jobs and valid deadline , let be the padded job set, with jobs, and let be the precedence relation. A job layout is a bijection from to the positions , read in consecutive triples.✦ The slot assignment of a job layout is the function in (1); a full layout for precedence is a job layout satisfying the two conditions there, the second of which is precedence feasibility. (1)
A job triple is a set of three jobs.✦ A scheduling triple boundary is an endpoint or , or a job triple.✦ The boundary time relation for a scheduling triple boundary and slot is the condition in (2). (2)✦ The strict predecessor cone , strict successor cone , and weak predecessor cone are the sets in (3). (3) For boundary slots in a job layout , the open scheduling window is the job set in (4). (4)✦
Fix an atomic family of subsets of . A Boolean structural formula over the atomic family is an expression built from atoms or their complements by conjunction and disjunction.✦ The interpretation of a Boolean structural formula is the job set obtained by interpreting conjunction as intersection and disjunction as union.✦ The leaf count of a Boolean structural formula is the natural number equal to one at a leaf and to the sum of the two operand counts at either operation.✦ Bounded leaf describability of a job set with allowance is the condition in (5). (5)✦
The Definition
Definition 1. An indexed global set family on is a pair consisting of a finite set of natural indices and a sequence of subsets of , as in (6). (6)✦ The global entry union of an indexed global set family on is the set in (7), whose members are called qualifying jobs. (7)✦ For a job , the membership index set is the set in (8), and its last membership index is the natural number given there, with default zero when the membership index set is empty. (8) For a rank function and an indexed global set family on , lexicographic list priority is the relation on jobs in (9). (9)✦ The numerical global list key of a job , with natural parameter , is the natural number in (10). (10)✦ For a job set , the same-list priority is a function from jobs to natural numbers, with parameters as in (11). (11)✦ For a job set , the list-switch priority is a function from jobs to natural numbers, with parameters as in (12). (12)✦
A global upset is a set closed under successors: whenever and , also .✦ The entries of are upward closed when every with is a global upset.✦ An indexed global set family on has injection disjointness within when the sets , for listed indices , are pairwise disjoint.✦
The rank upper tail at is the job set .✦ A rank threshold run certificate for in is a family of base sets and natural thresholds , together with a second set , satisfying (13). (13)✦ A reverse induction seed at boundary and slot is a set closed under predecessors and satisfying (14). (14)✦
At a boundary and slot , the past boundary invariant is the condition in (15). (15)✦ A layout is fixed outside relative to when for every .✦ For jobs , the job exchange of a layout is the layout that interchanges the positions of and and keeps every other position fixed.✦ The forbidden exchange invariant is the condition that (16) holds for every precedence-feasible layout fixed outside , every , and every with and . (16)✦
A node structural certificate for consists of boundary slots , boundaries , a global list , a rank threshold run certificate for that list in , and a reverse induction seed at , subject to (17). (17)✦
In the paper, the result reads: a node in its tag frame, a working frame that may reverse precedence and time, has an ordered list of global upsets whose qualifier union selects the local old-high set , a qualifying job’s key is its largest membership index followed by rank, and the invariants are and , every qualifying job scheduled at or before lies in , and after every feasible reordering of no job in with a better key can feasibly exchange with a qualifying job at , with same and switched sides using the cutoffs and priorities of §5.2.
What Is Checked
These definitions are stated over a finite job set with precedence , a natural-valued rank , an assignment of job sets to atoms, layouts, and scheduling triple boundaries.