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
ProvedSchrageSRPT.Opt.srpt_optimalLet be an arrival stream in which only finitely many jobs arrive by any given time: is finite for every . Let 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 be any schedule of the same stream. Then at every time ,
where and are the numbers of jobs in system at time under and .
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 ranges over every schedule of the stream (measurable, -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 , not almost every . A job is in system on . Local finiteness of arrivals is added so that the number in system is a genuine count. Jobs are indexed from .
import Mathlib import Definitions.Def_SchrageSRPT_Opt_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.