Proposition 1 — BLS makespan bound
ProvedBurnInBatch.ListSched.proposition_1Let be any finite set of jobs with positive processing times, let be the batch capacity, and let be the number of identical machines. For every ordering of the jobs in , let be the makespan obtained by grouping successive jobs into batches and assigning the batches to the first available machines. If is the minimum over all valid batchings and machine assignments, then
Taking to be the full job set gives Proposition 1. When , the factor becomes Graham's list-scheduling bound. The sub-instance form is also used for prefixes in the maximum-lateness analysis.
Formalization Note The list may be any permutation of , including the empty list when is empty. The published list-scheduling rule resolves simultaneous machine availability by lowest machine index; any such tie has the same makespan. The batch optimum is taken over all valid batchings, not only BLS-style consecutive batches.
import Mathlib import Definitions.Def_BurnInBatch_ListSched_Model
namespace BurnInBatch.ListSched
/-- Proposition 1, p. 772, also valid for every sub-instance `J`. -/
theorem proposition_1 {n : ℕ} (p : Fin n → ℝ) (B m : ℕ)
(J : Finset (Fin n)) (l : List (Fin n))
(hB : 0 < B) (hm : 0 < m) (hp : ∀ j, 0 < p j)
(hl : ListsJobs J l) :
blsMakespan p B m l ≤
((B : ℝ) + 1 - 1 / (m : ℝ)) * CmaxStar p B m J := by sorry
end BurnInBatch.ListSched
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.