The Setting
A boundary in a schedule separates low jobs from high jobs through the precedence constraints incident to its slot. The question is whether a boundary can serve two priority prefixes when one job changes from high to low.
Let be a job set, let denote precedence, and let assign jobs to time slots. Let be a finite domain, and let assign priorities, with smaller numbers coming first. Relative to a set , the low jobs are and the high jobs are .
A domain is slot-closed for when it contains every job sharing a slot with one of its jobs.✦ An admissible position for is either the slot of a job in or a position strictly before every job in .✦
The cutoff predecessor cone consists of the jobs preceding some job in slot ✦, and the cutoff successor cone consists of the jobs following some job in that slot, as in (1). (1)
Earlier high job coverage at a cutoff for in is the condition that every with belongs to .✦ Later low job coverage at a cutoff for in is the condition that every with belongs to .✦ A separator for in is a cutoff satisfying earlier high job coverage and later low job coverage for in ; write for this property.✦
Priority Prefixes and Exception Advances
A relative precedence ideal on is a set of jobs such that, whenever , and , one has .✦ A priority prefix on is a set of jobs for which whenever and .✦ The numeric priority cut at is the set of jobs in with priority less than , as in (2). (2)✦
The local priority obstruction property on is the condition that (3) holds for every pair with and . (3)✦
An exceptional job at for is a job in scheduled after and outside , such that every with belongs to .✦ An advance path is a finite sequence , with , whose next position is for an exceptional job at for .✦
The Claim
Theorem 1. Let precedence be transitive, and suppose implies for all jobs in . Let be a finite slot-closed domain satisfying the local priority obstruction property. Suppose and are relative precedence ideals and priority prefixes on , and let satisfy for every . If is an admissible position separating , then (4)✦
For arbitrary finite , precedence, time assignment and cutoff , let agree on . Then (5)✦
For numeric cuts, retain the transitivity, time, closure and local obstruction assumptions, and suppose is injective on and satisfies whenever and . If is an admissible position separating , then (6)✦
In the paper, the result reads: fix a normalized full schedule of a domain and consecutive priority prefixes differing by promoting one job from high to low; from a separator of , internal or at the exterior left boundary, some is reached by advancing only to domain slots on the right and separates both and , with permitted when the promoted job lies outside the domain.
What Is Checked
The shared cutoff assertions (4) and (6) are stated over finite slot-closed domains with time assignments respecting transitive precedence and the local priority obstruction property, while separator extensionality (5) is stated for arbitrary finite domains, relations and time assignments.