Lemma 4 — an optimal schedule has on-time batches first in batch-EDD order
ProvedBurnInBatch.TardyJobs.lemma_4batch-processingexchange-argumentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Consider one batch machine of capacity , common job processing time , releases , and due dates . Suppose implies . There is an optimal complete schedule consisting of an initial list of batches whose every job is on time, followed by a list of batches whose every job is tardy; the batches in are in batch-EDD order. Thus, with ,
This structural result lets subsequent statements place all tardy jobs after the on-time part while retaining the global optimum over complete schedules.
Formalization Note The strict-release form of agreeability permits unequal due dates when releases tie. and are lists of batches, and Optimal still ranges over every valid complete schedule.
Preamble
import Mathlib import Definitions.Def_BurnInBatch_TardyJobs_Model
Formal statement
namespace BurnInBatch.TardyJobs
/-- Lemma 4, p. 770: an optimal schedule can put every on-time batch first,
with those batches in batch-EDD order, and all tardy jobs afterward. -/
theorem lemma_4 {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ)
(hB : 0 < B) (hagree : ∀ i j : Fin n, r i < r j → d i ≤ d j) :
∃ A T : List (Finset (Fin n)),
Optimal B (equalTime p) r d (A ++ T) ∧
(∀ P ∈ A, ∀ j ∈ P, jobCompletion (equalTime p) r (A ++ T) j ≤ d j) ∧
(∀ P ∈ T, ∀ j ∈ P, d j < jobCompletion (equalTime p) r (A ++ T) j) ∧
BatchEDD d A := by sorry
end BurnInBatch.TardyJobs
Source
Lee, Uzsoy & Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Oper. Res. 40(4) (1992), p. 770, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.