Proposition 3 — on parallel batch machines
ProvedBurnInBatch.BatchLPT.proposition_3Consider jobs with positive processing times , all available at time , on identical batch processing machines, each processing up to jobs at a time, a batch taking as long as its longest job. Let be the optimal makespan of this problem , the minimum over all ways of forming batches and assigning them to machines. Let be the makespan produced by Algorithm BLPT: rank the jobs in nonincreasing order of processing time, group successive blocks of jobs into batches, order the batches in nonincreasing order of batch time and assign each in turn to a machine that becomes free first. Then
For one machine the factor is , so BLPT is then optimal. The proposition transfers Graham's worst-case bound for the LPT rule on ordinary parallel machines to batch machines.
Formalization Note. The bound is claimed for every run of BLPT: every ranking l nonincreasing in (ties arbitrary) and every ordering bl of its batches nonincreasing in batch time. "Assign them to the machines as they become free" is the published least-loaded list-scheduling rule. "" in the paper is . ranges over all valid batchings, not only the consecutive ones of Step 1.
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_3 {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)
(bl : List (Finset (Fin n))) (hbl : IsBLPTOrder p B l bl) :
blptMakespan m p bl ≤ (4 / 3 - 1 / (3 * (m : ℝ))) * optBatchMakespan n m B p := by sorry
end BurnInBatch.BatchLPT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.