The Setting
Let be a finite set of unit jobs with precedence relation . A layout of is a bijection from to the positions .✦ Jobs are grouped into consecutive triples, and the slot of a job is given by (1). (1)✦
A precedence-feasible layout of is a layout satisfying (2). (2)✦ A full schedule of for is a precedence-feasible layout with divisible by three. For a full schedule write .
A relative precedence ideal on a set is a set of jobs from satisfying (3). (3)✦
For a time assignment and a cutoff , the cutoff predecessor and successor cones and are the sets in (4). (4)
Earlier high job coverage for on at cutoff is the condition (5). (5)✦ Later low job coverage for on at cutoff is the condition (6). (6)✦ A shared cutoff separator for on is a cutoff satisfying both (5) and (6); write .✦ An actual separator for on is a shared cutoff separator whose cutoff is occupied by a job.
For a time assignment and boundary slots , the open scheduling window is the set of jobs with ; for the time assignment of a layout , it is given by (7). (7) A layout of is unchanged outside relative to when (8) holds. (8)✦
The Claim
Theorem 1. Let be a transitive precedence relation on a finite job set , and let be a full schedule for .
Suppose is nonempty and is a precedence ideal on . There are a full schedule for and a cutoff satisfying (9). (9)✦
Suppose is a nonempty open scheduling window of and is a relative precedence ideal on . There are a full schedule for and a cutoff satisfying (10). (10)✦
In the paper, the result reads: every ideal of a nonempty set with a full schedule has an actual separator in some full schedule of .
What Is Checked
The statements concern full schedules for transitive precedence relations on finite job sets, with a nonempty domain consisting of the whole job set or of an open scheduling window, and relative precedence ideals on that domain.