Lemma 2 — some schedule has (assuming )
ProvedBurnInBatch.ReleaseTmax.lemma_2Consider one batch machine of capacity and jobs with common processing time , release times and due dates that are agreeable ( implies ), and assume that every job can meet its due date if it is started at its release time:
Then some batch schedule of all jobs has maximum tardiness
The lemma supplies the upper end of the search interval for the bisection on (Algorithm 1).
Formalization Note The hypothesis is not in the printed statement of Lemma 2; its proof says "Since by assumption ", and the lemma is false without it (one job with , has ). The weak inequality used here is a weaker hypothesis than the strict one of the proof. "An upper bound on the value of " is read as a bound on the optimal value: some schedule achieves it, not every schedule. Agreeability is in the paper's statement and is kept. The time bound of Corollary 1 is not formalized.
import Mathlib import Definitions.Def_BurnInBatch_ReleaseTmax_Model
namespace BurnInBatch.ReleaseTmax
/-- Lemma 2 (p. 769), with the assumption `r_j + p ≤ d_j` of its proof. One batch machine of
capacity `B ≥ 1`, `n` jobs with common processing time `p`, agreeable release times and due
dates, and `r_j + p ≤ d_j` for every job. Then some batch schedule of all `n` jobs has maximum
tardiness at most `(n − 1)p`. -/
theorem lemma_2 {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ) (hB : 0 < B)
(hagree : ∀ i j : Fin n, r i < r j → d i ≤ d j)
(hrd : ∀ j : Fin n, r j + p ≤ d j) :
∃ S : List (Finset (Fin n)),
IsBatchSchedule B Finset.univ S ∧ tmax p r d Finset.univ S ≤ (n - 1) * p := by sorry
end BurnInBatch.ReleaseTmax
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.