Proposition 2 — some optimal schedule uses exactly the full batches of consecutive longest jobs
ProvedBurnInBatch.BatchLPT.proposition_2Consider jobs with positive processing times on identical batch processing machines of capacity , all jobs available at time . Re-index the jobs in nonincreasing order of processing time, (ties in any order), and let
be the successive groups of consecutive jobs, the last one possibly smaller.
Proposition 2. There is an optimal schedule of , that is, a valid batching and an assignment of its batches to machines with makespan equal to , whose batches are exactly (in some order).
Being exactly these sets is the paper's statement that "all batches will contain consecutive jobs" and "all batches, except possibly the one containing the highest indexed job, will be full": a partition of the ranked list into intervals of consecutive jobs, all of size except the one containing the last job, is exactly . The result fixes the batch structure of an optimal schedule in advance.
Formalization Note. The ranking is any list l of all jobs, nonincreasing in ; the statement holds for every such list. ranges over all valid batchings (any sizes , any grouping), not only over consecutive ones.
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_2 {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) :
∃ S : List (Finset (Fin n)), ∃ σ : Fin S.length → Fin m,
IsBatching n B S ∧ S.Perm (blptBatches B l) ∧
makespan (BurnInBatch.ListSched.batchTimes p S) σ = optBatchMakespan n m B p := by sorry
end BurnInBatch.BatchLPT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.