The Setting
A domain of jobs may be classified as low or high without following their order in a schedule. A shared cutoff constrains the jobs whose classification falls on the other side of their scheduling time. The question is how this classification describes the part of the domain before the cutoff.
Let be a job set, a precedence relation, and a time assignment. A time assignment respects precedence when every pair of jobs and in with satisfies . Let be the domain, and let be the prescribed low set, with jobs outside called high. A set is a candidate description of the low jobs on .
For a time assignment on a job set , the cutoff predecessor set , cutoff successor set and cutoff set at time are the subsets of defined in (1). (1)
Earlier high job coverage on a finite domain is the first condition in (2)✦; later low job coverage is the second.✦ A shared cutoff separator for , relative to , and , is a cutoff satisfying both conditions in (2), each required for every job . (2)✦
The cutoff prefix test for a set of jobs in at cutoff is the subset of defined by (3). (3)✦
Triple Boundaries
A job triple is a set of cardinality three.✦ A scheduling triple boundary is a left endpoint , an actual job triple , or a right endpoint .✦ The strict predecessor cone , strict successor cone and weak successor cone of a scheduling triple boundary on are the subsets of in (4), all taken under . (4)
A boundary is at cutoff for time assignment and horizon when (5) holds. (5)✦
A boundary separates at cutoff relative to when the conditions in (6) hold for every job .✦ Write for this separation condition. (6)
The boundary prefix set consists of the strict predecessors of together with the jobs of outside its weak successor cone, as in (7). (7)✦
Reversal
For a finite job set of size , a layout is a bijection from to the positions , read in consecutive triples.✦ For a layout of a finite job set of size and a job in , the time slot is the positive integer defined in (8). The reversed layout of a layout on is the bijection from to the positions defined in (8). (8)
The reversed precedence relation on is the relation given by when . The reversed boundary of a scheduling triple boundary is the boundary obtained by exchanging and and fixing every actual triple.✦ The reversed working frame uses and time , in place of the original precedence and layout time .
The Claim
Theorem 1. Let be finite. Suppose respects , is a shared cutoff separator for relative to , and . For each , the cutoff description is (9). (9)✦
Suppose instead that for every , respects , is at cutoff for horizon , separates at relative to , and . For each , the boundary description is (10). (10)✦
Let be finite with , let be a layout, and let . If separates at relative to , using precedence and time , then (11) holds. (11)✦
In the paper, the result reads: if an actual separator for has cutoff set and , then is exactly the domain jobs strictly before , and reversing order and time while exchanging low with high preserves separation.
What Is Checked
The descriptions concern sets agreeing with on and time assignments respecting precedence, with a finite domain and a shared cutoff separator for (9), or positive times bounded by and a separating boundary at the cutoff for (10); (11) concerns layouts on jobs, a separating boundary and .