(24), Lemma 4.2, p. 21 — ∑ⱼ wⱼCⱼ ≥ ∑ⱼ wⱼ ∑_{i,k} a_{i_k j} p_ij for every preemptive schedule
ProvedSkutellaCQP.Preempt.lemma_4_2_24lower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1preemptionschedulingweighted-completion-time
Consider an instance of : jobs with weights , processing times and release dates on unrelated machines . Let be a feasible preemptive schedule with completion times , and let be the fraction of job processed on machine within the time slot . Then
This is the second bound (24) of Lemma 4.2. The right-hand side is the weighted sum of the processing times spent on each job in the schedule; it is the right-hand side of constraint (27) of the relaxation .
Formalization Note The schedule, the fractions and are those of SkutellaCQP.Preempt.Setting. Feasibility includes that a job is never processed on two machines at once; this bound needs it.
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_Preempt_Setting
Formal statement
namespace SkutellaCQP.Preempt
open Finset
theorem lemma_4_2_24 {m n : ℕ} (p : Fin m → Fin n → ℝ) (w : Fin n → ℝ) (r : Fin m → Fin n → ℝ)
(hp : ∀ i j, 0 < p i j) (hw : ∀ j, 0 ≤ w j) (hr : ∀ i j, 0 ≤ r i j)
(P : PSched m n) (hP : PFeasible p r P) :
rhs24 p w (frac p r P) ≤ pval w P := by sorry
end SkutellaCQP.Preempt
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 21, Lemma 4.2, display (24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.