The Setting
A child scheduling interval may later have all its jobs reordered. The exchange condition concerns a job inside that interval and a job on its left boundary, with the comparison determined by a global list of job sets.
Let be a finite job set of size , with precedence relation , written . A layout is a bijection from to its zero-based positions.✦ Its jobs are read in consecutive triples, with slot map given by (1). (1)✦ A feasible layout of is a layout in which requires . A full schedule is a feasible layout with , where is its deadline.✦ For layouts and a job set , write when every job outside has the same position in both layouts.✦ The exchange interchanges the positions of and and leaves all other positions fixed.✦ The open window is the set of jobs with .✦
A job triple of is a three-element subset of .✦ A boundary is a left endpoint , an actual triple , or a right endpoint .✦ For a full schedule, these boundaries occur at slots , , and , respectively; an actual triple occurs at when and .✦ The strict predecessor and successor cones are the sets in (2). (2) The weak cones and include itself; at endpoints the weak and strict cones agree.
For job sets , a separating boundary for by at slot in layout is a boundary such that every job of earlier than belongs to , and every job of later than belongs to .✦ Write this condition as .
Lists and Local Normalization
An indexed global set family consists of a finite index set and job sets .✦ The membership indices of are the listed indices containing ; their maximum, with default zero, is its last membership index . The global entry union , lexicographic list priority for a rank , and numeric priority key for a scale are defined by (3). (3) The pruned list of a global set family is the indexed set family that retains exactly those indices for which and keeps every global entry unchanged.
The signature of a natural-number priority in a layout is the sequence of priorities in position order.✦ A locally normalized layout on a job set for priority is a feasible layout whose signature satisfies (4) for every feasible with . (4)✦ Write for this condition. The same-list priority is the natural-number assignment specified by , rank , scale , and distinguished set . The direction-change priority is the natural-number assignment specified by , , and a distinguished set .
For a natural-number threshold , the priority cut and rank upper tail are the sets in (5). (5)
The exchange invariant is the following condition on a layout, a job set, a global list, and a boundary: for every feasible with , jobs and with and have an infeasible exchange .✦ The past boundary invariant requires every job of scheduled at or before to belong to .✦
Descriptions and Structural Certificates
A Boolean structural formula over an atomic family of job sets is a signed atom or a conjunction or disjunction of two formulas.✦ The interpretation of a Boolean structural formula over an atomic family is the job set obtained by assigning an atom its job set, a negative atom its complement, and conjunction and disjunction intersection and union.✦ The leaf count of a Boolean structural formula is the natural number that is one at an atom and adds across either binary operation.✦ A bounded description of a job set over an atomic family with allowance , denoted , is the condition in (6). (6) A relative description of is an equality with globally described. The fixed description allowance is . Atomic predicate expressiveness means that , , every rank upper tail, every strict or weak boundary cone, and every job triple each have a description with one leaf.✦
An upward-closed job set contains every successor of each of its jobs; a downward-closed set contains every predecessor.✦ A list has upward-closed entries when every listed entry is upward closed.✦ The injection entries of a global list are disjoint in when for distinct listed .✦ A rank threshold run certificate for on consists of base sets , thresholds , and a second set , with the factorization in (7). (7) Every listed nonzero base has a description with at most two leaves; has one with at most leaves and one with at most one. The certificate also requires and, whenever and , requires and .
A reverse induction seed for at a right boundary and slot is a downward-closed set with a description of at most leaves, containing , all of whose jobs occur before .✦ A switch seed for at a left boundary and slot is an upward-closed set with a description of at most leaves, containing , all of whose jobs occur after .✦
A node structural certificate for and consists of a full schedule, boundaries at , and a global list with a rank threshold run certificate on . Its listed entries and second set are upward closed, its injection entries are disjoint in , and . Its confinement conditions are (8). (8) It requires and , a description of with at most leaves, and a reverse induction seed at .
An edge structural certificate belongs to the collection when is full, , the boundaries occur at , and is an actual triple, with the inequalities in (9). (9) It has cutoff sets , with , such that holds and both and separate by at their respective slots. The certificate contains a global list with a rank threshold run certificate on , upward-closed entries and second set, and injection entries disjoint in . Its cutoff coverage and labels satisfy (10). (10) It also requires and . A global cutoff with at most description leaves and a downward-closed extension with at most description leaves satisfy .
Exception Cutoff Walks
The cutoff descendants at slot form the set in (11). (11)✦ An earliest exceptional job for a finite window , a low set , and cutoff is a job satisfying later than such that every strictly between slots and belongs to . A relative order ideal on a finite window is a job set that contains each predecessor in of every job in .✦ A priority prefix on a finite window for priority is a job set satisfying for every and .✦ An exception cutoff walk on a finite window from to for priority and final set is a finite sequence of cutoffs beginning at and ending at . Each step chooses an order ideal on that is a priority prefix, with , and moves to the slot of an earliest exceptional job for at the current cutoff. A walk of zero steps is allowed.
The Claim
Theorem 1. Let be a layout of a finite job set with precedence and rank .
Suppose and , with . Let be locally normalized on for priority . Suppose and that, for and at slot in , the comparison requires . Then (12) holds. (12)✦
Let , and let be an indexed global set family. Suppose holds, , and . Assume that for and , requires . Then (13) holds. (13)✦
Suppose holds. Pruning gives (14). (14)✦
Let . Suppose is full, is transitive, has atomic predicate expressiveness, for every job, and requires . Let , , with and . Let occur at , respectively, with an actual triple.
Suppose a node structural certificate has boundaries and list , and . Let and , where . Suppose holds, is locally normalized on for , and separate by at . If there is an exception cutoff walk on from to for and final set , then (15) holds. (15)✦
Suppose and there is a switch seed at . Let and , with . Suppose holds, is locally normalized on for , and separate by at . Then (16) holds. (16)✦
In the paper, the result reads: the pruned child list satisfies the exchange invariant, quantifying over every feasible reordering of in its existing slots.
What Is Checked
The assertions concern finite job layouts and global job sets, with local normalization and list comparison hypotheses for exchange preservation, and with transitive precedence, increasing bounded ranks, atomic expressiveness, and the stated boundary and seed conditions for edge certificate existence.