The Setting
For a global job set , a child subproblem in scheduling has a job set , while its lists may still refer to jobs throughout . The issue is how a priority comparison made within the child relates to the original list.
An indexed global set family on a job set consists of a finite set of indices and a set for every .✦ The membership indices of a job are the listed indices whose entries contain , as in (1). (1)✦
The last membership index of a job is the maximum of its membership indices, with default zero, as in (2). (2)✦
For a rank function , the lexicographic list priority on is the relation that compares the keys by the rule in (3). (3)✦
The pruned global job list of relative to is the indexed global set family that retains the indices whose entries meet and leaves every global entry unchanged, as in (4). (4)✦
The Claim
Theorem 1. Let be an indexed global set family on , let , and let be a rank function. Suppose and , and suppose has a smaller key than for the pruned family . Then the original priority satisfies (5). (5)✦
In the paper, the result reads: if a job is eligible for comparison in the list pruned on and is any job in eligible for comparison in that pruned list, a smaller pruned key for than for implies the same comparison before pruning.
What Is Checked
The claim is stated over indexed global set families on an arbitrary job set , an arbitrary subset , and an arbitrary natural-number rank function , with the smaller-key job required to belong to .