Proposition 5 — relative error of BLPT is at most
ProvedBurnInBatch.BatchLPT.proposition_5Consider jobs with positive processing times and nonnegative due dates , all available at time , on identical batch machines of capacity . Let be the maximum lateness of the schedule produced by Algorithm BLPT, the optimal maximum lateness of (over all batchings, assignments and processing orders), and . Then
The ratio is used because may be negative; under the hypotheses , so both fractions are well defined. Proposition 5 is the counterpart of Proposition 3.
Formalization Note. The hypothesis is not printed in the paper; its proof needs it (it uses and divides by ), and it guarantees : for a job with , every schedule has . The bound is claimed for every BLPT run (every ranking l and every batch order bl, as in Proposition 3), with job completion times given by least-loaded list scheduling of the ordered batches.
import Mathlib import Definitions.Def_NumStochOpt_ListScheduling_ListSchedule import Definitions.Def_NumStochOpt_ListScheduling_Makespan import Definitions.Def_BurnInBatch_BatchLPT_Model import Definitions.Def_BurnInBatch_BatchLPT_BLPT
namespace BurnInBatch.BatchLPT
open NumStochOpt.ListScheduling
theorem proposition_5 {n m B : ℕ} (hn : 0 < n) (hm : 0 < m) (hB : 0 < B)
(p d : Fin n → ℝ) (hp : ∀ j, 0 < p j) (hd : ∀ j, 0 ≤ d j)
(l : List (Fin n)) (hl : IsLPTList p l)
(bl : List (Finset (Fin n))) (hbl : IsBLPTOrder p B l bl) :
(blptLmax m p d bl - optLmax n m B p d) / (optLmax n m B p d + dMax d) ≤
(1 / 3 - 1 / (3 * (m : ℝ))) + dMax d / (optLmax n m B p d + dMax d) := by sorry
end BurnInBatch.BatchLPT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.