A Proof of the Optimality of the Shortest Remaining Processing Time Discipline: SRPT Minimizes the Number of Jobs in System at Every Time, for Every Arrival Stream and Every ScheduleResearch Paper
A single processor receives jobs over time, each with a known amount of work, and may interrupt a job at any moment to work on another. Which rule should decide what to process? For the number of jobs waiting or in service, the answer is the Shortest Remaining Processing Time (SRPT) rule: at every moment, work on the job in system that is closest to…