The Setting
A recursive scheduling subproblem consists of the jobs between two occupied slots of a full schedule. Its boundary conditions constrain jobs outside the subproblem as well as jobs inside it. The library states the root, center and edge constructions using structural certificates for these conditions.
Let be the padded job set, with jobs and deadline . A layout is a bijection from to the positions , read in consecutive triples.✦ Its slot assignment and its open window are given by (1). (1) For a precedence relation on , a layout is precedence feasible when entails ; a full schedule is a feasible layout whose number of jobs is divisible by three.✦ Times and precedence are measured in the working frame, which may have the direction opposite to the original schedule.
A boundary is the left endpoint, the right endpoint, or a triple of three jobs.✦ The endpoint slots are and ; an actual boundary at slot has and consists exactly of the jobs scheduled at .✦ For an actual triple , its strict predecessor cone consists of jobs preceding some member of , and its strict successor cone consists of jobs preceded by some member of . For an actual boundary triple of , the weak predecessor cone is the set of jobs in or preceding some member of , and the weak successor cone is the set of jobs in or preceded by some member of . At the left endpoint the predecessor cones are empty and the successor cones are ; at the right endpoint these assignments are reversed.
A boundary separates a job set relative to a set at slot when the two conditions in (2) hold.✦ Write this condition as . (2)
Lists and Certificates
A Boolean structural formula over an atomic family of subsets of is built from atoms or their complements using conjunction and disjunction.✦ The interpretation of a Boolean structural formula over is the job set obtained by interpreting signed atoms as their sets and replacing conjunction and disjunction by intersection and union. Each signed atom counts as one leaf, and the leaf counts add at either binary operation.✦ Write when a formula with at most leaves denotes .✦ For a job set and a window in , a relative description of in is a Boolean structural formula denoting a global job set such that . For a rank function on , the atomic family is expressive for when , the empty set, every rank upper tail , every strict or weak boundary cone, and every job triple each have a one-leaf description.✦
An indexed global list consists of a finite set and global job sets .✦ Its union, membership indices and last membership index are defined in (3); the maximum defaults to zero. Lexicographic list priority compares ✦, while is its numeric key at scale . (3) A global upset of is a job set containing every successor of each of its jobs. An indexed global list has upset entries when every listed is a global upset.✦ The injection entries of an indexed global list are disjoint in a window when is empty for distinct listed indices .✦ The pruning of an indexed global list at a window is the indexed global list obtained by retaining precisely the indices whose entries meet and leaving the entries themselves unchanged.✦ The singleton list of a set has sole listed index and entry .✦
A rank threshold run for on consists of bases , thresholds , and a second set , subject to (4).✦ Here is listed wherever an entry condition is imposed. (4)
For a left boundary at slot , the past boundary invariant requires every job of scheduled at or before to lie in .✦ The forbidden exchange invariant on at concerns every feasible layout agreeing with outside . For and with , if has smaller lexicographic list priority than , exchanging their positions in must violate precedence feasibility.✦ For jobs in a layout of , their job exchange is the layout in which and trade positions and every other job keeps its position.
A reverse seed at a right boundary at slot is a downward closed job set with , containing , whose jobs all occur before .✦ A switch seed at a left boundary at slot is an upset with , containing , whose jobs all occur after .✦
A node certificate for consists of a full schedule, boundaries at slots with , and a global list with a rank threshold run on . Its listed entries and second set are upsets, its injection entries are disjoint in , and it has at most five listed indices. The confinement and window description conditions are (5). (5) The certificate also requires the past and forbidden exchange invariants at and a reverse seed at . Let denote the collection of these node certificates, with and understood.
An edge certificate uses a full schedule , parent window , and boundaries at slots . Its target is an actual triple, and its slots satisfy (6). (6) It has a cutoff and a final cutoff with : separates relative to , and separate relative to at their respective slots. Its cutoff jobs in belong to . The edge list has a rank threshold run on , upset entries and second set, and disjoint injection entries in ; its union agrees in with the complement of . It satisfies the past invariant at and the forbidden exchange invariant on at that boundary. There are global sets and agreeing with in , with and , and is downward closed. Write for the collection of these certificates.
Priorities and Recursive Acceptance
For a priority assignment , the priority signature of a layout lists the priorities of its jobs in position order.✦ A normalized layout on a job set for a priority assignment is a feasible layout whose priority signature is lexicographically minimal among feasible layouts agreeing with outside .✦ For a priority assignment on , the numeric cut at threshold is the job set .✦ Write for the same-direction priority determined by , and for the direction-change priority determined by .
A relative ideal on a finite job set is a job set containing every predecessor in of each of its jobs in .✦ A priority prefix on a finite job set is a job set whose jobs in precede all other jobs in in priority order.✦ The cutoff descendants at slot are the jobs preceded by some job scheduled at .✦ An earliest exceptional job for a set in a finite job set after slot is a job in that occurs after and is outside the cutoff descendants, with every job of at an intervening slot a cutoff descendant.✦ An exception cutoff walk on a finite job set with a specified priority order and final cut is a sequence of slots that starts at a cutoff and, at each step, chooses a relative ideal that is a priority prefix and is contained in the final cut within , then moves to the slot of an earliest exceptional job for .✦ A walk may have no steps.
Structural acceptance has fixed allowance . At depth zero it requires and . At depth it requires and either an empty window or structural split vertices joined by a possibly empty chain of admissible split transitions. The left region of , the right region of , and every intervening gap must have acceptance at depth .
The Claim
Theorem 1. Assume that is expressive for . For a full schedule , the root construction has the property (7). (7)✦
Let be transitive and let have nonempty window , endpoints and right boundary . There are a layout , a slot and a boundary satisfying (8). (8)✦
For the edge constructions assume transitivity, expressiveness for , for every job, and strict increase of along . Let , let be boundaries at , and let be boundaries at satisfying (6), with actual.
In the same-direction case, take a node certificate with these endpoints and right boundary , and assume . Let , take , and put . Assume separates relative to , is normalized on for , and separate that window relative to . If there is an exception cutoff walk from to on the finite set with final cut , then (9) holds. (9)✦
In the direction-change case, let be full, assume , and take a switch seed at . Take and put . Assume separates relative to , is normalized on for , and separate that window relative to . Then (10) holds. (10)✦
For an edge certificate , transitivity and expressiveness for give the child construction in (11). (11)✦ Every edge certificate satisfies the strict inclusion (12). (12)✦
Let be transitive and let be injective ranks, strictly increasing along and reversed , respectively. Suppose both ranks are below a positive bound , and is expressive in both frames. For and , recursive acceptance satisfies (13). (13)✦
In the paper, the result reads: starting from any feasible full schedule, the marking and list construction is defined at every node, its pruned lists are global upset lists of length at most five with fewer than leaves per entry satisfying all three invariants, and every branch terminates.
What Is Checked
The statements concern finite full layouts, global lists and their rank threshold runs, boundary cones and Boolean descriptions, with the transitivity and rank hypotheses specified for each construction. Whenever holds, the singleton list of has a root rank threshold run on every window , for the given rank function and atomic family; a run on restricts to a run for the pruned list on every smaller window .✦