Proof of Lemma 4.2, p. 22 — exchange inequality: ∑ⱼ xⱼwⱼ ∑_{j′≺ᵢj} x_{j′}p_{ij′} ≤ ∑ⱼ xⱼwⱼ ∑_{j′≺j} x_{j′}p_{ij′} for any total order ≺
ProvedSkutellaCQP.Preempt.slot_exchangeFix a machine of an instance with weights and processing times , and let be Smith's order on machine : if , or the ratios are equal and . Let be numbers attached to the jobs (in the paper, the fractions of one time slot ), and let be any strict total order on the jobs. Then
This is the inequality the proof of Lemma 4.2 reduces the bound (23) to, slot by slot. It is Smith's ratio rule for the "fractional jobs" of processing time and weight : ordering them by minimizes their total weighted completion time.
Formalization Note The total order is given by a permutation of the jobs, with iff ; every strict total order on a finite set arises this way. is cross-multiplied (), equal to the ratio form since .
import Mathlib import Definitions.Def_SkutellaCQP_Preempt_Setting
namespace SkutellaCQP.Preempt
open Finset
theorem slot_exchange {m n : ℕ} (p : Fin m → Fin n → ℝ) (w : Fin n → ℝ)
(hp : ∀ i j, 0 < p i j) (hw : ∀ j, 0 ≤ w j)
(i : Fin m) (x : Fin n → ℝ) (hx : ∀ j, 0 ≤ x j) (π : Equiv.Perm (Fin n)) :
∑ j, x j * w j * ∑ j' ∈ univ.filter (fun j' => SkutellaCQP.NoRel.prec p w i j' j), x j' * p i j' ≤
∑ j, x j * w j * ∑ j' ∈ univ.filter (fun j' => π j' < π j), x j' * p i j' := by sorry
end SkutellaCQP.Preempt
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.