Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PROOF, p. 689 (claim quoted on p. 687) — under SRPT the number in system at every time is ≤ that under any other schedule of the same arrival stream

Proved
SchrageSRPT.Opt.srpt_optimal

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

number-in-systemp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pathwise-optimalityschedulingsrpt

Let {A(n),P(n)}n≥0\{A(n), P(n)\}_{n \ge 0}{A(n),P(n)}n≥0​ be an arrival stream in which only finitely many jobs arrive by any given time: {n:A(n)≤t}\{n : A(n) \le t\}{n:A(n)≤t} is finite for every t∈Rt \in \mathbb Rt∈R. Let δs\delta_sδs​ be a schedule of this stream that follows the Shortest Remaining Processing Time discipline (at every time at which some job is in system, the processor serves a job in system with the smallest remaining processing time), and let δ\deltaδ be any schedule of the same stream. Then at every time ttt,

Ns(t)≤N(t),N_s(t) \le N(t),Ns​(t)≤N(t),

where Ns(t)N_s(t)Ns​(t) and N(t)N(t)N(t) are the numbers of jobs in system at time ttt under δs\delta_sδs​ and δ\deltaδ.

In the letter's words: "the number in system at any point in time under the SRPT discipline is always less than or equal to the number in system at the same point in time for the same arrival stream under a non-SRPT discipline". No assumption is made on the distribution of interarrival or processing times: the comparison is pathwise, for every arrival stream. By Little's law it implies that SRPT minimizes the mean number in system and the mean response time in any single-server queue.

Formalization Note. The competitor δ\deltaδ ranges over every schedule of the stream (measurable, {0,1}\{0,1\}{0,1}-valued, no service before arrival, at most one job at a time); it may idle, preempt arbitrarily, or serve jobs that have completed. Including SRPT schedules among the competitors also covers the comparison between two tie-breaking choices. SRPT is the verbal rule of p. 687, which forces the processor to work whenever a job is in system; the displayed condition of p. 688 alone is satisfied by the schedule that never processes anything, for which the claim is false. The comparison holds at every time ttt, not almost every ttt. A job is in system on [A(n),C(n))[A(n), C(n))[A(n),C(n)). Local finiteness of arrivals is added so that the number in system is a genuine count. Jobs are indexed from 000.

Preamble
import Mathlib
import Definitions.Def_SchrageSRPT_Opt_Model
Formal statement
namespace SchrageSRPT.Opt
theorem srpt_optimal (A P : ℕ → ℝ) (hfin : ∀ t : ℝ, {n | A n ≤ t}.Finite)
    (δs δ : ℕ → ℝ → ℝ) (hs : IsSRPT A P δs) (hδ : IsSchedule A δ) :
    ∀ t : ℝ, numInSystem A P δs t ≤ numInSystem A P δ t := by sorry
end SchrageSRPT.Opt
Source
Schrage, A proof of the optimality of the shortest remaining processing time discipline, Oper. Res. 16 (1968), p. 689, PROOF (last sentence); statement quoted from Miller–Schrage (1966) on p. 687
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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