The Setting
A schedule of unit jobs on three machines assigns jobs to time slots subject to directed precedence constraints. Grouping a job order into consecutive triples supplies such slots; windows and boundary cones select jobs by their time coordinates and precedence relations, respectively.
The Definition
Definition 1. An instance on the original job set is a finite list of ordered pairs of jobs.✦ A directed constraint means that occurs in .✦ The precedence relation of the instance is positive-length directed reachability, as in (1). (1)✦
For a relation on and any nonnegative integer , the padded relation on is the relation obtained by matching numerical labels in (2). For a deadline , write and . (2)✦
For the layout and boundary constructions, let be any finite job set and let be a relation on . A layout of is a bijection from jobs to consecutive positions starting at zero, as in (3). (3)✦ The time slot of a job in layout is assigned by grouping consecutive positions into triples, as in (4). (4)✦ A layout of respects when each related pair occupies strictly increasing slots, as in (5). (5)✦ A full schedule for on is a layout satisfying (6). (6)✦
For a time assignment and natural boundary slots , the open time window is the set of jobs strictly between those slots in (7); write when the time assignment is fixed. (7)✦
A job triple of is a subset containing exactly three jobs; the family of triples is in (8). (8)✦ A boundary of is an actual triple or a virtual left or right endpoint, denoted and ; its possible values form the disjoint union in (9). (9)✦ The predecessor cone of a boundary is the subset of specified in (10). (10)✦ The successor cone of a boundary is the subset of specified in (11). (11)✦ The weak predecessor cone of a boundary is the subset of formed by adjoining an actual boundary triple to its predecessor cone, with the virtual endpoint values in (12). (12)✦ The weak successor cone of a boundary is the subset of formed by adjoining an actual boundary triple to its successor cone, with the virtual endpoint values in (13). (13)✦
The reversed layout of a layout on is the layout with positions specified by (14). Write for original time and for time in the reversed working layout. (14)✦
For a key from a finite job set to a totally ordered set, the rank of a job is one plus the number of jobs with smaller key, as in (15). (15)✦ On the numerically labelled job set , the predecessor count of a job is the number of jobs with ✦, and its predecessor count key is the lexicographically ordered pair in (16). (16) The predecessor count rank of a job is the rank of under its predecessor count key , as in (17). (17)✦ The reversed predecessor rank of a job is the complementary rank defined in (18). (18)✦
In the paper, the result reads: after rejecting , add isolated jobs to obtain with ; a full schedule partitions into ordered antichain triples respecting positive-length reachability; restrictions use this transitive order, including paths through exterior vertices; the reversed frame reverses precedence, time, and a fixed linear extension, with the two ranks summing to ; actual triples have predecessor and successor cones, whose weak versions include the triple, with virtual left boundary values and , and virtual right boundary values and .
What Is Checked
These definitions are stated over finite directed instances and finite job sets with an arbitrary relation, with numerical job labels for padding in (2) and for the predecessor count ranks in (17) and (18).