Lemma 5 — on-time batches can contain consecutive jobs
ProvedBurnInBatch.TardyJobs.lemma_5Consider the equal-processing-time batch problem with capacity and jobs indexed so that release times and due dates are both nondecreasing. There is an optimal complete schedule in which every batch whose jobs all finish on time consists of consecutive indices. If such a batch has jobs and first index , its set of jobs is
This existence claim supplies the consecutive-last-batch structure used by DP3 without narrowing the optimization problem's feasible schedules.
Formalization Note The paper states agreeable releases and due dates and then fixes due-date index order for this section. Both sequences are required to be nondecreasing so a batch's last index has its latest release; tied due dates are ordered by release time.
import Mathlib import Definitions.Def_BurnInBatch_TardyJobs_Model
namespace BurnInBatch.TardyJobs
/-- Lemma 5, p. 770: in an optimum, every entirely on-time batch
consists of consecutive job indices. -/
theorem lemma_5 {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ)
(hB : 0 < B) (hd : Monotone d) (hr : Monotone r) :
∃ S : List (Finset (Fin n)),
Optimal B (equalTime p) r d S ∧
∀ P ∈ S,
(∀ j ∈ P, jobCompletion (equalTime p) r S j ≤ d j) → Consecutive P := by sorry
end BurnInBatch.TardyJobs
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.