§5, p. 772 — Graham's LPT bound for , as quoted
ProvedBurnInBatch.BatchLPT.graham_lpt_boundThis is Graham's theorem on the LPT rule (R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math. 17 (1969)), quoted by Lee, Uzsoy and Martin-Vega.
Let be the processing times of jobs listed in nonincreasing order, and the number of identical machines. List scheduling takes the jobs in this order and assigns each to a machine of currently least load; write for the resulting makespan (largest machine load). Let be the optimal makespan, the minimum of the largest machine load over all assignments of the jobs to the machines. Then
In the paper this is the bound transferred to batch machines through Proposition 2 to give Proposition 3.
Formalization Note. Stated purely on the published definitions listMakespan M m q and optMakespan M m q, which only read . Ties among least-loaded machines go to the lowest index (published rule); the bound holds for any tie rule. Nonnegative (rather than positive) times are allowed; zero-length jobs change nothing.
import Mathlib import Definitions.Def_NumStochOpt_ListScheduling_ListSchedule import Definitions.Def_NumStochOpt_ListScheduling_Makespan
namespace BurnInBatch.BatchLPT
open NumStochOpt.ListScheduling
theorem graham_lpt_bound {M m : ℕ} (hm : 0 < m) (q : ℕ → ℝ)
(hq_nonneg : ∀ k, k < M → 0 ≤ q k)
(hq_noninc : ∀ k k', k ≤ k' → k' < M → q k' ≤ q k) :
listMakespan M m q ≤ (4 / 3 - 1 / (3 * (m : ℝ))) * optMakespan M m q := by sorry
end BurnInBatch.BatchLPT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.