The Setting
A local scheduling change concerns both precedence constraints within an interval and constraints involving jobs outside it.
A job layout of a finite job set is a bijection to its position indices, numbered from zero, as in (1); jobs are read in groups of three consecutive positions. (1)✦ The time slot of a job in a layout is its position divided by three, rounded down, plus one, as in (2): (2)✦
A precedence-feasible layout for a relation on is a job layout in which related jobs occupy strictly increasing time slots, as specified by (3): (3)✦
A reordering of a job layout is fixed outside a subset if it is a job layout with the same position for every job outside , as in (4): (4)✦
The open interval of a layout , for nonnegative integer boundaries and , is the set of jobs strictly between those slots: (5)
The Claim
Theorem 1. Let and be job layouts of a finite job set , and let be a relation on . Let be the open interval of defined by (5). Suppose that is precedence feasible for , that is fixed outside relative to , and that assigns every related pair of jobs in to strictly increasing time slots. Then (6)✦
In the paper, the result reads: replacing the schedule inside an open interval by any full schedule of its job set preserves feasibility of the complete schedule.
What Is Checked
The claim (6) is stated over bijective layouts of a finite job set and a relation on , subject to the interval and precedence hypotheses in the theorem.