The Setting
Let be a finite set of unit jobs with precedence relation , and let be a scheduling domain. A set designates the low jobs; the high jobs are . Separation concerns jobs whose temporal side of a cutoff disagrees with their low or high classification.
A job triple is a set of cardinality three.✦ A scheduling boundary for the job set is a left endpoint , a job triple of , or a right endpoint .✦ The strict predecessor cone , strict successor cone , and weak successor cone of a scheduling boundary are the sets defined by (1). (1)
For a time assignment and a cutoff , the cutoff predecessor cone and cutoff successor cone are the sets in (2). (2) Earlier high coverage and later low coverage are the conditions in (3). (3)
A job layout of is a bijection from to the positions , read in consecutive groups of three.✦ The time slot of a job in a layout of is the natural number given by (4). (4)✦ A precedence-feasible layout of is a layout for which whenever .✦ A layout of is fixed outside relative to a layout of if for every .✦
For a priority function , the priority signature of a layout of is the sequence in (5); signatures are compared lexicographically. (5)✦
The Definition
Definition 1. A relative order ideal on is a subset of whose restriction to satisfies (6). (6)✦
A shared cutoff separator for and is a cutoff satisfying (7). (7)✦
A separating boundary for in at cutoff is a scheduling boundary satisfying (8). (8)✦
The boundary prefix set of a scheduling boundary relative to a set is the set in (9). (9)✦
A normalized layout of for priority is a layout satisfying (10). (10)✦
A locally normalized layout of on for priority is a layout satisfying (11). (11)✦
In the paper, the result reads: for an ideal of low jobs in a contiguous domain, a separator has every earlier high job in and every later low job in ; an exterior left boundary separates when all low domain jobs descend from it; ; a normalized schedule is lexicographically least after each triple is sorted by a precedence-extending priority order.
What Is Checked
The separation definitions are stated for a finite domain , subsets , a precedence relation, a natural-number time assignment and scheduling boundaries; the normalization definitions range over layouts of finite and natural-number priority functions.