Lemma 1 — an on-time schedule can be rearranged into batch-EDD order
ProvedBurnInBatch.ReleaseTmax.lemma_1Consider one batch machine of capacity and jobs with common processing time , release times and due dates , where release times and due dates are agreeable: implies .
If there is a batch schedule of all jobs in which every job is on time (), then there is a batch schedule of all jobs in which every job is on time and the batches are in batch-EDD order: whenever batch is processed before batch , no and satisfy .
The lemma is the exchange argument that makes the batches of an on-time schedule respect the due-date order; it is the first step toward the consecutive structure that Algorithm DP1 exploits.
Formalization Note The paper prints agreeability as " implies ", which read literally forces equal due dates for equal release times. The strict form used here is a weaker hypothesis, so the Lean statement implies the printed one. Lemma 1 itself needs no assumption on the job indexing.
import Mathlib import Definitions.Def_BurnInBatch_ReleaseTmax_Model
namespace BurnInBatch.ReleaseTmax
/-- Lemma 1 (p. 767). One batch machine of capacity `B`, `n` jobs with common processing time
`p`, release times `r` and due dates `d` that are agreeable (`r_i < r_j → d_i ≤ d_j`). If some
batch schedule of all `n` jobs has every job on time (`T_max = 0`), then some batch schedule of
all `n` jobs has every job on time and is in batch-EDD order. -/
theorem lemma_1 {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ)
(hagree : ∀ i j : Fin n, r i < r j → d i ≤ d j)
(hfeas : ∃ S : List (Finset (Fin n)),
IsBatchSchedule B Finset.univ S ∧ AllOnTime p r d Finset.univ S) :
∃ S : List (Finset (Fin n)),
IsBatchSchedule B Finset.univ S ∧ AllOnTime p r d Finset.univ S ∧ IsBatchEDD d S := by sorry
end BurnInBatch.ReleaseTmax
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.