Lemma 3 — with agreeable processing times and due dates, a schedule with can be taken in batch-EDD order
ProvedBurnInBatch.AgreeTmax.lemma_3Consider jobs on a single batch processing machine of capacity , all available at time , with processing times and due dates that are agreeable: implies . A batch takes the processing time of its longest job, and batches run back to back.
If some batch schedule of all jobs has maximum tardiness , then some batch schedule of all jobs has
that is, whenever batch is processed before batch , no , have .
This is the structural property that turns the search for a feasible schedule into a search over sequences ordered by due date, on which Algorithm DP2 is built.
Formalization Note The paper states agreeability as " implies "; the hypothesis here is the strict form , which is weaker, so this statement implies the printed lemma. No indexing assumption is needed.
import Mathlib import Definitions.Def_BurnInBatch_AgreeTmax_Model
namespace BurnInBatch.AgreeTmax
/-- Lemma 3 of Lee, Uzsoy & Martin-Vega (1992), p. 769: in `1/B/T_max` with agreeable processing
times and due dates (strict form `p i < p j → d i ≤ d j`), if some valid batch schedule of all `n`
jobs has `T_max = 0`, then some valid batch schedule with `T_max = 0` is in batch-EDD order. -/
theorem lemma_3 {n B : ℕ} (hB : 0 < B) (p d : Fin n → ℕ) (hagr : Agreeable p d)
(hfeas : ∃ S : List (Finset (Fin n)), IsValid B Finset.univ S ∧ Tmax p d S = 0) :
∃ S : List (Finset (Fin n)), IsValid B Finset.univ S ∧ Tmax p d S = 0 ∧ IsBatchEDD d S := by sorry
end BurnInBatch.AgreeTmax
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.