The Setting
A scheduling list can give a job priority according to the last entry that contains it, with rank breaking ties between jobs in the same entry. Suffix carry cuts such a list at an index and a rank threshold. The library states its membership and order properties for arbitrary ranks, and its upward closure property for ranks that increase strictly along precedence.
An indexed global set family on a job set is a family of subsets with a finite set of listed indices.β¦ The membership indices of a job are the listed indices whose entries contain β¦; its last membership index is their maximum, with default zero, as in (1).β¦ (1)
The qualifier set , also called the global entry union, is the set of jobs in that belong to at least one listed entry, as defined in (2). (2)β¦
For a rank function , the key of a job is the pair . Lexicographic list priority for an indexed global set family on and a rank function is the strict order obtained by comparing job keys lexicographically, as given by (3). (3)β¦
A global upset for a precedence relation is a set closed under passage to successors, with the condition in (4).β¦ An upset list on for a precedence relation is an indexed global set family whose listed entries are global upsets for .β¦ (4)β¦
For an indexed global set family on , a rank function , and natural numbers and , the global list suffix is the indexed family on that retains listed indices at least and restricts entry to jobs of rank at least .β¦ Write for the entry of at index , for its listed indices, for its qualifiers, and for its last membership index.
The Claim
Theorem 1. Let be an indexed global set family on , let , and let . Put . For every job , suffix membership is characterized by (5). (5)β¦ For jobs , the key orders satisfy (6). (6)β¦ Suppose also that is an upset list for a precedence relation and that whenever . Then (7) holds. (7)β¦
In the paper, the result reads: for a global upset list on a padded job set with valid deadline and size , , and , the list has exactly the old qualifiers with key at least in lexicographic order, its key order agrees with the old order on those qualifiers, and every entry remains a global upset.
What Is Checked
The statements concern arbitrary job sets and finitely indexed global set families, with natural number ranks and thresholds, and require rank to increase strictly along precedence for the upward closure conclusion.