The Setting
A scheduling construction may retain several global sets of jobs as the region of interest changes. The issue is how a boundary of jobs constrains the number of sets that remain relevant. The library states the comparison for two subsets and of a job set , with precedence relation on .
A global list on is an indexed family of job sets, with a finite set of listed indices and an entry at every natural-number index.✦ The global entry union of a global list on is the set of jobs belonging to at least one listed entry, as in (1). (1)✦
A job set is globally upward closed for when every successor under of a job in also belongs to .✦ A global list on has upward-closed entries for when each of its listed entries is a globally upward-closed subset of for .✦
The injection entries of a global list on are its listed job sets with indices at least two. The injection entries of a global list on are disjoint within when the condition in (2) holds. (2)✦
The pruning of a global list on relative to is the global list on with listed indices from (3) and the same entry at every index. (3)✦
A job triple in is a finite subset of of cardinality three.✦
The Claim
Theorem 1. Let be a global list on with upward-closed entries for . Let and let be finite. Suppose that every job in precedes some job in under .
Let be a set of indices whose entries each meet and whose restrictions to are pairwise disjoint. Then (4)✦
If is a job triple and the injection entries of are disjoint within , then the pruned list satisfies (5)✦
In the paper, the result reads: every pruned list produced by the construction has at most five entries, of which at most three are injections from its current run.
What Is Checked
The bounds (4) and (5) are stated over finite indexed families of job sets with upward-closed entries, two arbitrary job subsets, and a finite boundary set that each relevant job precedes, specialized to a job triple for (5).