Theorem 3.3: with c_i/s_i constant on m machines, the weighted flow time is κ/2 (∑ s_i² + S²/m + ∑_j δ_j²), so minimizing it is minimizing ∑_j δ_j²
ProvedAllocationIndices.weighted_flow_time_equal_ratiosflow-timeparallel-machinesscheduling
Theorem 3.3. For machines and deterministic jobs with the same for all jobs, minimization of weighted flow time is equivalent to minimization of , where is the total process time for machine , and .
Formally, as the identity behind it: for every schedule of jobs on machines, service times and weights for a common ,
where is the completion time of job under and the excess of machine 's load over . The first two terms do not depend on the schedule, so minimizing the weighted flow time over schedules is minimizing , which is the theorem; the identity also shows that the order of the jobs on a machine is irrelevant when all ratios agree.
Preamble
import Definitions.Def_AllocationIndices_Jobs open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem weighted_flow_time_equal_ratios {n m : ℕ} (σ : Schedule n m) (s c : Fin n → ℝ)
(hm : 0 < m) {κ : ℝ} (hc : ∀ i, c i = κ * s i) :
weightedFlowTime σ s c =
κ / 2 * (∑ i, s i ^ 2 + (∑ i, s i) ^ 2 / m + ∑ j, loadDeviation σ s j ^ 2) := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §3.4.3 p. 64, Theorem 3.3 (proof left as Exercise 3.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.