§3, p. 6 — long plus short assignments use at most on each machine
ProvedUnrelatedSched.FixedMachines.combined_load_leapproximation-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be an matrix of positive integer processing times, an integer and . Let be a partial schedule of long assignments, with long load on machine , and let be a schedule that agrees with on every job assigns. Suppose that for every machine the jobs left unassigned by that puts on take total time at most . Then for every machine
This is the step of the proof of Theorem 3 that combines the rounded schedule of short assignments with the schedule of long assignments.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_FixedMachines_LongAssignment
Formal statement
namespace UnrelatedSched.FixedMachines
open MatousekLP.Scheduling
/-- §3, p. 6: if the schedule `σ` agrees with the schedule of long assignments `L` on the long
jobs and the short assignments take at most `d - t_i + ε d` on every machine `i`, then every
machine `i` is busy for at most `t_i + d - t_i + ε d = (1 + ε) d`. -/
theorem combined_load_le {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ)
(hP : ∀ i j, 0 < P i j) (ε : ℝ) (hε : 0 < ε) (d : ℕ) (L : Fin n → Option (Fin m))
(σ : Fin n → Fin m) (hfollow : ∀ j i, L j = some i → σ j = i)
(hshort : ∀ i, shortLoad P L σ i ≤ (d : ℝ) - longLoad P L i + ε * (d : ℝ)) :
∀ i, load (fun i j => (P i j : ℝ)) σ i ≤ (1 + ε) * (d : ℝ) := by sorry
end UnrelatedSched.FixedMachines
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 6, Section 3, proof of Theorem 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.