Proof of Proposition 4 — sub-instance lateness lower bound
ProvedBurnInBatch.ListSched.lateness_lower_boundbatch-processingmaximum-latenessp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be a nonempty subset of the jobs, with positive processing times, batch capacity , and parallel machines. Let be the least maximum lateness achievable for , let be its least makespan, and let be the greatest due date among all jobs. Then
The estimate connects a lateness optimum on the prefix sub-instance with the makespan bound of Proposition 1.
Formalization Note The full instance has at least one job so its maximum due date is defined. This item needs no sign condition on due dates; the goal theorem separately assumes nonnegative due dates.
Preamble
import Mathlib import Definitions.Def_BurnInBatch_ListSched_Model
Formal statement
namespace BurnInBatch.ListSched
/-- Proof of Proposition 4, p. 773: the lateness optimum on a sub-instance
is at least its makespan optimum minus the full instance's largest due date. -/
theorem lateness_lower_bound {n : ℕ} (p d : Fin n → ℝ) (B m : ℕ)
(J : Finset (Fin n)) (hn : 0 < n) (hJ : J.Nonempty)
(hB : 0 < B) (hm : 0 < m) (hp : ∀ j, 0 < p j) :
CmaxStar p B m J - maxDue d hn ≤ LStar p d B m J := by sorry
end BurnInBatch.ListSched
Source
Lee, Uzsoy & Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Oper. Res. 40(4) (1992), p. 773, proof of Proposition 4, display “L*(S_k) ≥ C_max*(S_k) − d_max”; https://doi.org/10.1287/opre.40.4.764
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.