Theorem 3.7 (Baker): on m machines the flow time of deterministic jobs is minimized by scheduling in order of increasing service time, uniquely up to permuting same-level jobs between machines
ProvedAllocationIndices.spt_minimizes_flow_timeTheorem 3.7. The flow time for a set of deterministic jobs on any fixed number of machines is minimized by scheduling in order of increasing service time. Such policies are the only optimal policies, except that for every positive integer the jobs in the th position from the end of the schedule for each machine may be permuted arbitrarily between machines.
Formally, for machines and positive service times :
- the SPT list schedule (jobs dealt out in increasing order of service time, cyclically over the machines) has flow time at most that of every schedule;
- a schedule has minimal flow time if and only if there is a ranking of the jobs from the longest ( a bijection onto with , ties in any order) such that every job sits at level from the end of its machine's schedule: the longest jobs are last on their machines, the next are second to last, and so on. These are exactly the SPT schedules, for some order of the equal jobs, up to permuting the jobs of one level between machines.
The flow time of a schedule is with the level, which is what both parts use. With pairwise distinct service times the ranking is forced, , and the level is . With equal service times, exchanging two equal jobs gives the SPT schedule for the other order of those jobs, so it is still one of "such policies"; the book's uniqueness clause holds as printed and is stated in full. (Checked by enumerating every schedule for , and service times in , ties included: 4308 level profiles.)
import Definitions.Def_AllocationIndices_Jobs open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace AllocationIndices
theorem spt_minimizes_flow_time {n m : ℕ} (hm : 0 < m) (s : Fin n → ℝ) (hs : ∀ i, 0 < s i) :
(∀ σ : Schedule n m, flowTime (sptSchedule s hm) s ≤ flowTime σ s) ∧
(∀ σ : Schedule n m,
flowTime σ s = flowTime (sptSchedule s hm) s ↔
∃ e : Fin n ≃ Fin n, (∀ i j, s j < s i → e i < e j) ∧
∀ i, levelFromEnd σ i = (e i : ℕ) / m + 1) := by sorry
end AllocationIndices
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.