The Setting
In three-machine unit-job scheduling, exchanging two jobs can change their slots without changing the number of jobs assigned to any slot. The question is whether rearranging later jobs can enable an exchange that brings a better-priority job forward.
A layout of a finite job set is a bijection from to the positions ; its jobs are read in consecutive triples.✦ The time slot of a job is the integer defined by (1). (1)✦ A layout is precedence feasible for a relation on if every pair has .✦
A priority assignment assigns a natural number to each job, with smaller numbers representing better priority. The priority signature of a layout is the list in (2), compared with other signatures in lexicographic order. (2)✦ A normalized layout for and is a precedence feasible layout whose priority signature is lexicographically no greater than that of every precedence feasible layout.✦
For layouts of and a set , the layout is unchanged outside relative to if for every .✦ A locally normalized layout on for and is a precedence feasible layout whose priority signature is lexicographically no greater than that of every precedence feasible layout unchanged outside relative to .✦
The exchange of jobs in a layout is the layout in which and trade positions and every other job keeps its position.✦
The Claim
Theorem 1. Let be a normalized layout for and , and let satisfy and . Then (3)✦
Let be locally normalized on for and , let , and let be a layout unchanged outside relative to . Suppose that at every position , that , and that . Then (4)✦
In the paper, the result reads: in a normalized schedule, a feasible exchange putting a better-priority job in an earlier slot is impossible, and after any feasible reordering confined strictly after a slot , exchanging a job at with a better-priority later job is still impossible.
What Is Checked
The claims (3) and (4) are stated over finite job sets, layouts grouped into consecutive triples, a precedence relation and natural-number priorities; the second also uses local normalization on , an unchanged exterior and an initial segment fixed through position .