FBEDD optimally solves
ProvedBurnInBatch.AgreeTmax.fbedd_optimalbatch-processingeddp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Consider jobs on a single batch processing machine of capacity , all available at time , every job with the same processing time , and due dates indexed so that . Let be the Full-Batch EDD schedule: batches , , , processed in this order. Then is a valid batch schedule of all jobs, and for every valid batch schedule of all jobs,
With equal processing times every batch takes time , so the result says that filling batches in due-date order is optimal for maximum tardiness.
Formalization Note The common processing time is (any value, included). is , computed with truncated subtraction in .
Preamble
import Mathlib import Definitions.Def_BurnInBatch_AgreeTmax_Model import Definitions.Def_BurnInBatch_AgreeTmax_FBEDD
Formal statement
namespace BurnInBatch.AgreeTmax
/-- Algorithm FBEDD optimally solves `1/p_i = p, B/T_max` (Lee, Uzsoy & Martin-Vega 1992,
p. 769): if every job has processing time `c` and the jobs are indexed in nondecreasing order of
due dates, the full-batch EDD schedule is a valid batch schedule of all jobs, and its maximum
tardiness is at most that of every valid batch schedule of all jobs. -/
theorem fbedd_optimal {n B : ℕ} (hB : 0 < B) (c : ℕ) (d : Fin n → ℕ) (hd : Monotone d) :
IsValid B Finset.univ (fbedd n B) ∧
∀ S : List (Finset (Fin n)), IsValid B Finset.univ S →
Tmax (fun _ => c) d (fbedd n B) ≤ Tmax (fun _ => c) d S := by sorry
end BurnInBatch.AgreeTmax
Source
Lee, Uzsoy & Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Oper. Res. 40(4) (1992), p. 769, Algorithm FBEDD and the sentence preceding it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.