Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
AllocationIndices.spt_minimizes_flow_time

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

flow-timeparallel-machinesschedulingshortest-processing-time

Theorem 3.7. The flow time for a set of nnn deterministic jobs on any fixed number mmm 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 rrr the jobs in the rrrth position from the end of the schedule for each machine may be permuted arbitrarily between machines.

Formally, for m≥1m \ge 1m≥1 machines and positive service times sis_isi​:

  1. 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;
  2. a schedule σ\sigmaσ has minimal flow time if and only if there is a ranking eee of the jobs from the longest (eee a bijection onto {0,…,n−1}\{0, \dots, n-1\}{0,…,n−1} with si>sj⇒e(i)<e(j)s_i > s_j \Rightarrow e(i) < e(j)si​>sj​⇒e(i)<e(j), ties in any order) such that every job iii sits at level ⌊e(i)/m⌋+1\lfloor e(i)/m \rfloor + 1⌊e(i)/m⌋+1 from the end of its machine's schedule: the mmm longest jobs are last on their machines, the next mmm 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 ∑iℓisi\sum_i \ell_i s_i∑i​ℓi​si​ with ℓi\ell_iℓi​ the level, which is what both parts use. With pairwise distinct service times the ranking is forced, e(i)=#{j:sj>si}e(i) = \#\{j : s_j > s_i\}e(i)=#{j:sj​>si​}, and the level is ⌈rank(i)/m⌉\lceil \mathrm{rank}(i)/m \rceil⌈rank(i)/m⌉. 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 n≤5n \le 5n≤5, m≤3m \le 3m≤3 and service times in {1,2,3}\{1, 2, 3\}{1,2,3}, ties included: 4308 level profiles.)

Preamble
import Definitions.Def_AllocationIndices_Jobs

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
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
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §3.5.5 p. 73, Theorem 3.7 (Baker 1974)
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me