§5, p. 772 — equals the unit-capacity problem on the aggregate batch jobs
ProvedBurnInBatch.BatchLPT.reduction_to_unit_capacityLet jobs with positive processing times be scheduled on identical batch machines of capacity . Rank the jobs in nonincreasing order of processing time (ties in any order) and let , , be the successive groups of jobs of the ranked list. View each batch as a single aggregate job of length . Then the optimal makespan of the batch problem equals the optimal makespan of the ordinary (unit-capacity) parallel-machine problem on the aggregate jobs:
This is the reduction the paper draws from Proposition 2; it is what allows Graham's analysis of LPT for to be transferred to the batch problem.
Formalization Note. The right-hand side is the published optMakespan on the item sequence of batch times of blptBatches B l; the left-hand side optBatchMakespan ranges over every valid batching.
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 reduction_to_unit_capacity {n m B : ℕ} (hm : 0 < m) (hB : 0 < B) (p : Fin n → ℝ)
(hp : ∀ j, 0 < p j) (l : List (Fin n)) (hl : IsLPTList p l) :
optBatchMakespan n m B p =
optMakespan (blptBatches B l).length m (BurnInBatch.ListSched.batchTimes p (blptBatches B l)) := by sorry
end BurnInBatch.BatchLPT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.