Section 2, proof of the Theorem — if , then or a successor of has a deadline at least as early as 's
ProvedLawlerMoore.PrecDeadline.exists_successor_deadline_leLet jobs carry real deadlines , let be a precedence relation, and let be the modified deadlines. Assume is a small positive number in the sense
i.e. is smaller than every positive difference between two deadlines. Then for any jobs with there is a job that is itself or a successor of () with
In the proof of the §2 Theorem this is what allows two adjacent jobs with to be interchanged without making late.
Formalization Note The paper states this for a consecutive pair of a sequence; the claim does not depend on the sequence, so it is stated for any two jobs. The paper's " is a small number" is made explicit as the displayed condition; it is needed here (with a large the tie-breaking term can outweigh a difference of deadlines). No property of is used, because the definition of already counts among its own successors. Jobs are Fin n, 0-based.
import Mathlib import Definitions.Def_LawlerMoore_PrecDeadline_modifiedDeadline
namespace LawlerMoore.PrecDeadline
theorem exists_successor_deadline_le (n : ℕ) (d : Fin n → ℝ)
(ρ : Fin n → Fin n → Prop) [DecidableRel ρ]
(ε : ℝ) (hε : 0 < ε) (hgap : ∀ k k', d k < d k' → (n : ℝ) * ε < d k' - d k)
(i j : Fin n) (hlt : modifiedDeadline ρ d ε j < modifiedDeadline ρ d ε i) :
∃ k, (k = j ∨ ρ j k) ∧ d k ≤ d i := by sorry
end LawlerMoore.PrecDeadline
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.