The Setting
An interval in a three-machine schedule contains the jobs between two boundary slots. A cutoff set divides its jobs into a high part and a low part. Their descriptions involve predecessor and successor cones at boundary triples.
Let be the job set, let be its precedence relation, and let assign slots to jobs, with deadline . For boundary slots and , the open scheduling window is the job set in (1). (1) A job triple of is a finite subset of of cardinality three. A scheduling boundary for the slot assignment is a left endpoint, a job triple, or a right endpoint.✦ The boundary time of a scheduling boundary is at the left endpoint and at the right endpoint. An actual boundary triple has boundary time when and its jobs are exactly those assigned slot .
For a boundary at slot , write and for its strict predecessor and successor cones, and and for its weak cones. At an actual boundary triple , the strict predecessor and successor cones and and the weak cones and are the job sets defined by (2). (2) At the left endpoint, both predecessor cones are empty and both successor cones are ; at the right endpoint, both predecessor cones are and both successor cones are empty.
A boundary at separates a job set relative to a set when the conditions in (3) hold. (3)✦
An indexed global set family consists of a finite set of listed indices and a job set for every .✦ The qualifier union of an indexed global set family is the job set defined in (4). (4) The past boundary invariant for at boundary time is the condition in (5). (5)✦
The Claim
Theorem 1. Suppose assigns every job a slot from through and respects precedence: implies .
Let boundaries have times and , and put . Let be an indexed global set family and a cutoff set. Suppose membership in agrees with membership outside on , every job in belongs to , and satisfies the past boundary invariant at . Then the high part has the global description (6). (6)✦
Let boundaries have times , , , and , with , and put and . Let . Suppose agrees with on and . Suppose the boundary at separates relative to , and the boundary at separates relative to . If every job in belongs to , then the low part has the global description (7). (7)✦
In the paper, the result reads: in a valid construction with child of , parent center , cutoff , new pruned list , and global cutoff agreeing with throughout , the edge frame, a working frame in which precedence and time may be reversed, satisfies and .
What Is Checked
The identities are stated over a precedence relation with a bounded, precedence-respecting slot assignment, endpoint or triple boundaries at the specified slots, and job subsets and finite indexed global set families satisfying the stated conditions.