Free Access

Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline

Linus Schrage
Linus Schrage
University of Chicago, Chicago, Illinois
Search for more papers by this author

Linus Schrage

University of Chicago, Chicago, Illinois

Search for more papers by this author

Published Online:1 Jun 1968https://doi.org/10.1287/opre.16.3.687

Cited by
- A multitasking scheduling problem of emergency medical response in mass casualty incident
  28 August 2025 | IISE Transactions, Vol. 58, No. 7
- Preemption can destabilize the system performance
  Operations Research Letters, Vol. 67
- Empirical Gittins for Data-driven M/G/1 Scheduling with Arbitrary Job Size Distributions
  8 June 2026
- Outperforming Multiserver SRPT at All Loads
  8 June 2026
- The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling
  2 March 2026 | SIAM Journal on Computing, Vol. 55, No. 2
- Hermes: Efficient Serving of LLM Applications with Probabilistic Demand Modeling
  7 April 2026 | ACM Transactions on Architecture and Code Optimization, Vol. 6
- Online Scheduling and Distribution of Quantum Circuits Over Quantum Networks
- Minimizing Weighted Flow Time
  3 April 2026 | Journal of the ACM, Vol. 28
- Empirical Gittins for data-driven M/G/1 scheduling with arbitrary job size distributions
  26 March 2026 | Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 10, No. 1
- Instability of Some LJF and LRTF Queueing Networks
  2 January 2026
- JAFC: Job-Aware Flow Control for Distributed DNN Training
  31 March 2026
- Gsched: Coordinated Flow-Control and Priority Scheduling for DNN Training in AI Cluster
  IEEE Transactions on Network Science and Engineering, Vol. 13
- Accelerating Graph Neural Network Inference in Heterogeneous Computing Environments
- Fifty years of research in scheduling — Theory and applications
  European Journal of Operational Research, Vol. 327, No. 2
- Shortest-Job-First Scheduling in Many-Server Queues with Impatient Customers and Noisy Service-Time Estimates
  Jing Dong,
  Rouba Ibrahim
  19 December 2024 | Operations Research, Vol. 73, No. 6
- Age-Based CoDel and His Friends. Improving the Linux Scheduler with 2-Level AQM Disciplines
- The Gittins Index: A Design Principle for Decision Making Under Uncertainty
  Ziv Scully,
  Alexander Terenin
  6 October 2025
- Quantitative delay analysis of GI/G/1 queues with heavy-tailed traffic by means of Alpha Theory
  Computer Networks, Vol. 269
- The Cost of Accurate Predictions in Learning-Augmented Scheduling
- Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
  25 June 2025 | Algorithms, Vol. 18, No. 7
- When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M/G/1?
  Ziv Scully; ,
  Lucas van Kreveld
  19 February 2024 | Operations Research, Vol. 73, No. 3
- Queues with service resetting
  European Journal of Operational Research, Vol. 322, No. 3
- Online Menu-Based Scheduling of Electric Vehicle Charging
  IEEE Transactions on Smart Grid, Vol. 16, No. 3
- Heavy traffic scaling limits for shortest remaining processing time queues with light tailed processing time distributions
  4 December 2024 | Queueing Systems, Vol. 109, No. 1
- A Data-Driven Approach to Dataflow-Aware Online Scheduling for Graph Neural Network Inference
  4 March 2025
- Nearly Time-Optimal Online Pick and Place Trajectory Computation using Quadratic Programming
  IFAC-PapersOnLine, Vol. 59, No. 18
- Balanced Splitting: A Framework for Achieving Zero-Wait in the Multiserver-Job Model
  IEEE Transactions on Parallel and Distributed Systems, Vol. 36, No. 1
- MLTCP: A Distributed Technique to Approximate Centralized Flow Scheduling For Machine Learning
  18 November 2024
- Fluid Limits for Longest Remaining Time First Queues
  Łukasz Kruk
  2 November 2023 | Mathematics of Operations Research, Vol. 49, No. 4
- GTCC: A Game Theoretic Approach for Efficient Congestion Control in Datacenter Networks
  IEEE Transactions on Network Science and Engineering, Vol. 11, No. 6
- An open-source simulation platform for benchmarking geo-distributed data center schedulers
  2 April 2024 | SIMULATION, Vol. 100, No. 11
- Analysis of a Queueing System of the Type Ek / El / 1 / R With a Pair of Incoming Flows of Requests, Absolute Priority, Limited Bufer and Waiting Time
  6 November 2024 | Kibernetika i vyčislitelʹnaâ tehnika, Vol. 217, No. 3(217)
- Bounds on M/G/k Scheduling Under Moderate Load Improving on SRPT-k and Tightening Lower Bounds
  6 September 2024 | ACM SIGMETRICS Performance Evaluation Review, Vol. 52, No. 2
- A “Big-Spine” Abstraction: Flow Prioritization With Spatial Diversity in The Data Center Network
- Multi-task allocation framework of coal gangue sorting robot system for the time-varying raw coal flow
  9 July 2023 | International Journal of Coal Preparation and Utilization, Vol. 44, No. 6
- Minimizing Age of Information under Arbitrary Arrival Model with Arbitrary Packet Size
  23 February 2024 | ACM SIGMETRICS Performance Evaluation Review, Vol. 51, No. 4
- Performance of the Gittins Policy in the G/G/1 and G/G/k, With and Without Setup Times
  23 February 2024 | ACM SIGMETRICS Performance Evaluation Review, Vol. 51, No. 4
- Heavy-Traffic Optimal Size- and State-Aware Dispatching
  21 February 2024 | Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 8, No. 1
- Inversion impact of approximate PIFO to Start-Time Fair Queueing
  Computer Networks, Vol. 240
- Performance of the Gittins policy in the G/G/1 and G/G/k, with and without setup times
  Performance Evaluation, Vol. 163
- Minimizing age of information under arbitrary arrival model with arbitrary packet size
  Performance Evaluation, Vol. 162
- SEH: Size Estimate Hedging Scheduling of Queues
  26 October 2023 | ACM Transactions on Modeling and Computer Simulation, Vol. 33, No. 4
- Towards Maximizing Nonlinear Delay-Sensitive Rewards in Queuing Systems
- Minimizing the mean slowdown in the M/G/1 queue
  4 September 2023 | Queueing Systems, Vol. 104, No. 3-4
- Instability of LRTF multiclass queueing networks
  Operations Research Letters, Vol. 51, No. 3
- Minimizing Age of Information under Arbitrary Arrival Model with Arbitrary Packet Size
  27 April 2023 | ACM SIGMETRICS Performance Evaluation Review, Vol. 50, No. 4
- Sensitivity Analysis for the Single-Machine Preemptive Scheduling Problem of Minimizing Flow Time
  IEEE Access, Vol. 11
- Scheduling to Minimize Age of Information With Multiple Sources
  IEEE Journal on Selected Areas in Information Theory, Vol. 4
- DIRECT AND INDIRECT EFFECTS OF AN AUTOMATIC DATA CAPTURE SYSTEM: A HOLISTIC APPROACH
- A New Toolbox for Scheduling Theory
  5 January 2023 | ACM SIGMETRICS Performance Evaluation Review, Vol. 50, No. 3
- Local edge minimality of SRPT networks with shared resources
  7 October 2022 | Mathematical Methods of Operations Research, Vol. 96, No. 3
- On the Gittins index for multistage jobs
  7 April 2022 | Queueing Systems, Vol. 102, No. 3-4
- Optimal Control Approach to Scheduling Power Supply Facilities: Theory and Heuristics
  IEEE Transactions on Control of Network Systems, Vol. 9, No. 4
- Optimal Scheduling in the Multiserver-job Model under Heavy Traffic
  8 December 2022 | Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 6, No. 3
- Scheduling to Minimize Age of Information with Multiple Sources
- Size-based scheduling vs fairness for datacenter flows
  30 August 2022 | ACM SIGMETRICS Performance Evaluation Review, Vol. 50, No. 2
- Speed Scaling on Parallel Servers With MapReduce Type Precedence Constraints
  IEEE/ACM Transactions on Networking, Vol. 30, No. 4
- Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions
  The Annals of Applied Probability, Vol. 32, No. 4
- Mitigating long queues and waiting times with service resetting
  1 July 2022 | PNAS Nexus, Vol. 1, No. 3
- Fluid limits for shortest job first with aging
  4 April 2022 | Queueing Systems, Vol. 101, No. 1-2
- Instability of SRPT, SERPT and SJF multiclass queueing networks
  17 January 2022 | Queueing Systems, Vol. 101, No. 1-2
- Size-Based Congestion Control Using Network Utility Maximization
  IEEE Transactions on Control of Network Systems, Vol. 9, No. 2
- Personalized scheduling in service systems
  16 March 2022 | Queueing Systems, Vol. 100, No. 3-4
- Minimizing the mean slowdown in a single-server queue
  28 March 2022 | Queueing Systems, Vol. 100, No. 3-4
- Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits
  19 January 2021 | Annals of Operations Research, Vol. 310, No. 2
- Minimizing the sum of makespan on multi-agent single-machine scheduling with release dates
  Swarm and Evolutionary Computation, Vol. 69
- Optimal Strategy for Pick-and-Place System with two Robots
  Journal of Physics: Conference Series, Vol. 2216, No. 1
- When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail?
  20 January 2022 | ACM SIGMETRICS Performance Evaluation Review, Vol. 49, No. 2
- Integrated Production and Outbound Distribution Scheduling: Online Problems
  20 October 2021
- Combining Simulation and Machine Learning for Response Time Prediction for the Shortest Remaining Processing Time Discipline
- Decentralized elastic electricity demand scheduling
- SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers
  Jing Dong,
  Rouba Ibrahim
  21 October 2021 | Management Science, Vol. 67, No. 12
- Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlines
  Discrete Applied Mathematics, Vol. 304
- GDSim: Benchmarking Geo-Distributed Data Center Schedulers
- Decentralized scheduling with precedence constraints
  28 May 2021 | Optimization Letters, Vol. 15, No. 8
- Atoll
  1 November 2021
- Scheduling and Control of Queueing Networks
  1 October 2021 | , Vol. 2
- When Idling is Ideal
  26 October 2021
- Loss Queueing Systems with Limited Processor Sharing and Applications to Communication Networks
- The Gittins Policy in the M/G/1 Queue
- Efficient Online Scheduling of Electric Vehicle Charging Using a Service-Price Menu
- Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion
  European Journal of Operational Research, Vol. 293, No. 1
- A Deep Reinforcement Learning-based Application Framework for Conveyor Belt-based Pick-and-Place Systems using 6-axis Manipulators under Uncertainty and Real-time Constraints
- Nudge: Stochastically Improving upon FCFS
  4 June 2021 | Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 5, No. 2
- Ergodicity bounds for the Markovian queue with time-varying transition intensities, batch arrivals and one queue skipping policy
  Applied Mathematics and Computation, Vol. 395
- Minimality of SRPT Networks With Resource Sharing
  19 March 2021 | WSEAS TRANSACTIONS ON MATHEMATICS, Vol. 20
- Frequency scaling in multilevel queues
  5 March 2021 | ACM SIGMETRICS Performance Evaluation Review, Vol. 48, No. 3
- Open problems in queueing theory inspired by datacenter computing
  27 January 2021 | Queueing Systems, Vol. 97, No. 1-2
- Joint coflow routing and scheduling in leaf-spine data centers
  Journal of Parallel and Distributed Computing, Vol. 148
- SmartDis: Near-Optimal Task Scheduling in Multi-edge Networks
  9 April 2021
- SEH: Size Estimate Hedging for Single-Server Queues
  19 August 2021
- Instability of LAS multiclass queueing networks
  Operations Research Letters, Vol. 49, No. 1
- Optimal multiserver scheduling with unknown job sizes in heavy traffic
  Performance Evaluation, Vol. 145
- Size-based scheduling for TCP flows: Implementation and performance evaluation
  Computer Networks, Vol. 183
- Frequency scaling in multilevel queues
  Performance Evaluation, Vol. 143
- Sequoia
  12 October 2020
- SCHEDULING IN A SINGLE-SERVER QUEUE WITH STATE-DEPENDENT SERVICE RATES
  21 May 2019 | Probability in the Engineering and Informational Sciences, Vol. 34, No. 4
- Anti-Aging Scheduling in Single-Server Queues: A Systematic and Comparative Study
- Simple Near-Optimal Scheduling for the M/G/1
  27 May 2020 | Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 4, No. 1
- Comment on "Datacenter Congestion Control: Identifying what is essential and making it practical" by Aisha Mushtaq, et al, CCR, July 2019
  23 May 2020 | ACM SIGCOMM Computer Communication Review, Vol. 50, No. 2
- To schedule or not to schedule: When no-scheduling can beat the best-known flow scheduling algorithm in datacenter networks
  Computer Networks, Vol. 172
- Toward Fast and Optimal Robotic Pick-and-Place on a Moving Conveyor
  IEEE Robotics and Automation Letters, Vol. 5, No. 2
- Heavy-Traffic Analysis of Sojourn Time Under the Foreground–Background Scheduling Policy
  Bart Kamphorst,
  Bert Zwart
  17 February 2020 | Stochastic Systems, Vol. 10, No. 1
- A Queueing Model that Works Only on the Biggest Jobs
  3 April 2020
- Simple Near-Optimal Scheduling for the M/G/1
  4 December 2019 | ACM SIGMETRICS Performance Evaluation Review, Vol. 47, No. 2
- Low-Complexity Flow Scheduling for Commodity Switches in Data Center Networks
- OnDisc: Online Latency-Sensitive Job Dispatching and Scheduling in Heterogeneous Edge-Clouds
  IEEE/ACM Transactions on Networking, Vol. 27, No. 6
- A note on single-machine scheduling to tradeoff between the number of tardy jobs and the start time of machine
  Operations Research Letters, Vol. 47, No. 6
- Datacenter Traffic Control: Understanding Techniques and Tradeoffs
  IEEE Communications Surveys & Tutorials, Vol. 20, No. 2
- Theoretical and Experimental Evaluation of the Two-Level Processor Sharing Discipline for TCP Flows
- Open Problem—M/G/k/SRPT Under Medium Load
  Isaac Grosof
  18 September 2019 | Stochastic Systems, Vol. 9, No. 3
- Open Problem—M/G/1 Scheduling with Preemption Delays
  Ziv Scully
  17 September 2019 | Stochastic Systems, Vol. 9, No. 3
- Offloading distributed applications onto smartNICs using iPipe
  19 August 2019
- Hybrid Deep Neural Network Scheduler for Job-Shop Problem Based on Convolution Two-Dimensional Transformation
  Computational Intelligence and Neuroscience, Vol. 2019
- On the Control of Fork-Join Networks
  Erhun Özkan,
  Amy R. Ward
  31 January 2019 | Mathematics of Operations Research, Vol. 44, No. 2
- Last in line
  Operations Research Letters, Vol. 47, No. 2
- SRPT for Multiserver Systems
  25 January 2019 | ACM SIGMETRICS Performance Evaluation Review, Vol. 46, No. 3
- Diffusion Limits for SRPT and LRPT Queues via EDF Approximations
  23 July 2019
- Workload adaptive flow scheduling
  4 December 2018
- SRPT for multiserver systems
  Performance Evaluation, Vol. 127-128
- Kairos
  11 October 2018
- Achievable Performance of Blind Policies in Heavy Traffic
  Nikhil Bansal,
  Bart Kamphorst,
  Bert Zwart
  8 March 2018 | Mathematics of Operations Research, Vol. 43, No. 3
- An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in Datacenters
  IEEE/ACM Transactions on Networking, Vol. 26, No. 4
- Age-optimal updates of multiple information flows
- Performance-Aware Fair Scheduling: Exploiting Demand Elasticity of Data Analytics Jobs
- Task Replication for Deadline-Constrained Vehicular Cloud Computing: Optimal Policy, Performance Analysis, and Implications on Road Traffic
  IEEE Internet of Things Journal, Vol. 5, No. 1
- Delay-Efficient Multiclass Packet Scheduler
  24 April 2018
- Control and Optimization of the SRPT Service Policy by Frequency Scaling
  15 August 2018
- On Saturation Effects in Coupled Speed Scaling
  15 August 2018
- GEODIS: towards the optimization of data locality-aware job scheduling in geo-distributed data centers
  20 July 2017 | Computing, Vol. 100, No. 1
- Efficient Data Center Flow Scheduling Without Starvation Using Expansion Ratio
  IEEE Transactions on Parallel and Distributed Systems, Vol. 28, No. 11
- Edge minimality of EDF resource sharing networks
  24 June 2017 | Mathematical Methods of Operations Research, Vol. 86, No. 2
- Energy-aware SRPT server with batch arrivals: Analysis and optimization
  Performance Evaluation, Vol. 115
- Congestion Control for Background Data Transfers With Minimal Delay Impact
  IEEE/ACM Transactions on Networking, Vol. 25, No. 5
- The impact of processing order on performance: A taxonomy of semi-FIFO policies
  Journal of Computer and System Sciences, Vol. 88
- Scheduling Jobs with Estimation Errors for Multi-server Systems
- Cluster fair queueing: Speeding up data-parallel jobs with delay guarantees
- Competitive analysis for online scheduling in software-defined optical WAN
- Online job dispatching and scheduling in edge-clouds
- A feedback control approach to dynamic speed scaling in computing systems
- Optimal control of a single server in a finite-population queueing network
  16 November 2016 | Queueing Systems, Vol. 85, No. 1-2
- A New Approach to Online Scheduling
  21 December 2016 | ACM Transactions on Algorithms, Vol. 13, No. 1
- Models and Concepts of Classical Scheduling
  19 October 2016
- Smart Grid-aware scheduling in data centres
  Computer Communications, Vol. 96
- DRASH: A Data Replication-Aware Scheduler in Geo-Distributed Data Centers
- Optimizing resource management during business process execution: A case study
- Schemes for Fast Transmission of Flows in Data Center Networks
  IEEE Communications Surveys & Tutorials, Vol. 17, No. 3
- A delay efficient multiclass packet scheduler for heterogeneous M2M uplink
- Minimality of EDF networks with resource sharing
  22 April 2016 | Mathematical Methods of Operations Research, Vol. 84, No. 2
- Large profits or fast gains: A dilemma in maximizing throughput with applications to network processors
  Journal of Network and Computer Applications, Vol. 74
- Meeting Soft Deadlines in Single- and Multi-server Systems
- Autoscaling Effects in Speed Scaling Systems
- Experimental Calibration and Validation of a Speed Scaling Simulator
- Fluid Limits for Multiple-Input Shortest Remaining Processing Time Queues
  Łukasz Kruk,
  Ewa Sokołowska
  21 April 2016 | Mathematics of Operations Research, Vol. 41, No. 3
- Whittle index approach to size-aware scheduling for time-varying channels with multiple states
  14 June 2016 | Queueing Systems, Vol. 83, No. 3-4
- Joint Optimization of Flow Latency in Routing and Scheduling for Software Defined Networks
- PERFORMANCE OF NON-COOPERATIVE ROUTING OVER PARALLEL NON-OBSERVABLE QUEUES
  19 May 2016 | Probability in the Engineering and Informational Sciences, Vol. 30, No. 3
- A Set of Successive Job Allocation Models in Distributed Computing Infrastructures
  17 October 2015 | Journal of Grid Computing, Vol. 14, No. 2
- Online Scheduling FIFO Policies with Admission and Push-Out
  12 April 2015 | Theory of Computing Systems, Vol. 58, No. 2
- A Picking Strategy for Circular Conveyor Tracking
  12 June 2015 | Journal of Intelligent & Robotic Systems, Vol. 81, No. 2
- Flow Time Minimization
  22 April 2016
- From Preemptive to Non-preemptive Scheduling Using Rejections
  20 July 2016
- Energy-Aware Server with SRPT Scheduling: Analysis and Optimization
  3 August 2016
- An Inequality for the Variance of Waiting Time under a General Queueing Discipline
  24 November 2015
- Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling
  The Annals of Applied Probability, Vol. 25, No. 6
- Hopper
  17 August 2015 | ACM SIGCOMM Computer Communication Review, Vol. 45, No. 4
- Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates
  7 October 2013 | International Journal of Systems Science, Vol. 46, No. 11
- Hopper
  17 August 2015
- User satisfaction fairness based optimal charging algorithm for multiple devices
- Approximately optimal scheduling of an M/G/1 queue with heavy tails
  3 February 2015 | Queueing Systems, Vol. 80, No. 3
- Whittle Index Approach to Size-aware Scheduling with Time-varying Channels
  15 June 2015 | ACM SIGMETRICS Performance Evaluation Review, Vol. 43, No. 1
- Whittle Index Approach to Size-aware Scheduling with Time-varying Channels
  15 June 2015
- Non-intrusive scheduling of TCP flows
- DRX-Aware Power and Delay Optimized Scheduler for Bursty Traffic Transmission
- Provably delay efficient data retrieving in storage clouds
- Revisiting symbiotic job scheduling
- MapReduce Job Scheduling Based on Remaining Job Sizes
  IEICE Transactions on Communications, Vol. E98.B, No. 1
- Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions
  3 January 2014 | Engineering Optimization, Vol. 46, No. 12
- Don't be fat: Towards efficient online flow scheduling in data center networks
- A Tight 2-Approximation for Preemptive Stochastic Scheduling
  Nicole Megow,
  Tjark Vredeveld
  30 May 2014 | Mathematics of Operations Research, Vol. 39, No. 4
- Turbocharged Speed Scaling: Analysis and Evaluation
- Improving the quality of experience with size-based and opportunistic scheduling
- Queueing-theoretic approaches for dynamic scheduling: A survey
  Surveys in Operations Research and Management Science, Vol. 19, No. 2
- Decoupled speed scaling: Analysis and evaluation
  Performance Evaluation, Vol. 73
- How to transfer flows efficiently via the Internet?
- Balancing work and size with bounded buffers
- Implementation of shortest remaining processing time based schedulers on a 32 bit serial based processing platform
- Shortest remaining processing time based schedulers for reduction of traffic congestion
- Joint optimization of overlapping phases in MapReduce
  Performance Evaluation, Vol. 70, No. 10
- Dynamic HTTP download scheduling with respect to energy consumption
- A combinatorial auctions perspective on min-sum scheduling problems
- The expected asymptotical ratio for preemptive stochastic online problem
  Theoretical Computer Science, Vol. 495
- Online Speed Scaling Based on Active Job Count to Minimize Flow Plus Energy
  27 January 2012 | Algorithmica, Vol. 65, No. 3
- Single machine batch scheduling with release times and delivery costs
  18 October 2011 | Journal of Scheduling, Vol. 16, No. 1
- Online and Semi-online Scheduling
  26 July 2013
- The Two-Machine Flow Shop
  22 August 2012
- Priorities and Scheduling in M/G/1
  28 March 2013
- Scheduling for weighted flow time and energy with rejection penalty
  Theoretical Computer Science, Vol. 470
- Non-myopic vehicle and route selection in dynamic DARP with travel time and workload objectives
  Computers & Operations Research, Vol. 39, No. 12
- A taxonomy of Semi-FIFO policies
- Is Tail-Optimal Scheduling Possible?
  Adam Wierman,
  Bert Zwart,
  9 October 2012 | Operations Research, Vol. 60, No. 5
- Optimal size-based opportunistic scheduler for wireless systems
  14 March 2012 | Queueing Systems, Vol. 72, No. 1-2
- A spike-detecting AQM to deal with elephants
  Computer Networks, Vol. 56, No. 13
- Decoupled Speed Scaling: Analysis and Evaluation
- Probabilistic alternatives for competitive analysis
  13 April 2011 | Computer Science - Research and Development, Vol. 27, No. 3
- Minimizing slowdown in heterogeneous size-aware dispatching systems
  11 June 2012 | ACM SIGMETRICS Performance Evaluation Review, Vol. 40, No. 1
- Flow-level modeling and analysis of dynamic TDD in LTE
- ASIdE: Using Autocorrelation-Based Size Estimation for Scheduling Bursty Workloads
  IEEE Transactions on Network and Service Management, Vol. 9, No. 2
- Distributed and Online Fair Resource Management in Video Surveillance Sensor Networks
  IEEE Transactions on Mobile Computing, Vol. 11, No. 5
- Single-machine scheduling with no idle time and release dates to minimize a regular criterion
  15 July 2010 | Journal of Scheduling, Vol. 15, No. 2
- Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates
  Computers & Operations Research, Vol. 39, No. 3
- Size- and state-aware dispatching problem with queue-specific job sizes
  European Journal of Operational Research, Vol. 217, No. 2
- Invariance of fluid limits for the shortest remaining processing time and shortest job first policies
  9 November 2011 | Queueing Systems, Vol. 70, No. 2
- Many Flows Asymptotics for SMART Scheduling Policies
  IEEE Transactions on Automatic Control, Vol. 57, No. 2
- FIFO Queueing Policies for Packets with Heterogeneous Processing
- M/M/1-PS queue and size-aware task assignment
  Performance Evaluation, Vol. 68, No. 11
- Using spikes to deal with elephants
- Heavy-traffic analysis of mean response time under Shortest Remaining Processing Time
  Performance Evaluation, Vol. 68, No. 10
- Resource-sharing in a single server with time-varying capacity
- Minimizing flow time in the wireless gathering problem
  15 July 2011 | ACM Transactions on Algorithms, Vol. 7, No. 3
- On the optimal trade-off between SRPT and opportunistic scheduling
  7 June 2011
- Diffusion Limits for Shortest Remaining Processing Time Queues
  H. Christian Gromoll,
  Łukasz Kruk,
  Amber L. Puha
  6 February 2011 | Stochastic Systems, Vol. 1, No. 1
- Providing performance guarantees in multipass network processors
- Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures
- Queueing Disciplines
  15 February 2011
- Single Machine Scheduling
  15 February 2011
- The M / G /1 Queue
  15 February 2011
- Size-Based Flow-Scheduling Using Spike-Detection
- Fairness and scheduling in single server queues
  Surveys in Operations Research and Management Science, Vol. 16, No. 1
- On the Analysis of Supplier-Manufacturer Information Sharing Strategies for Production Scheduling
- Discrete-time MAP/G/1/∞ system with inversive probabilistic servicing discipline
  12 January 2011 | Automation and Remote Control, Vol. 71, No. 12
- Tail-robust scheduling via limited processor sharing
  Performance Evaluation, Vol. 67, No. 11
- The average response time in a heavy-traffic srpt queue
  15 October 2010 | ACM SIGMETRICS Performance Evaluation Review, Vol. 38, No. 2
- Simulation of the Foreground-Background Queue in Parallel Systems
- Scheduling for the tail: Robustness versus optimality
- Balancing SRPT prioritization vs opportunistic gain in wireless systems with flow dynamics
- Efficient Web Requests Scheduling Considering Resources Sharing
- A new scheduling algorithm for server farms load balancing
- QTL: An efficient scheduling policy for 10Gbps network intrusion detection system
- A Flow Scheduler Architecture
- Efficient Algorithms for Average Completion Time Scheduling
- Online Cooperative Cost Sharing
- ATLAS: A scalable and high-performance scheduling algorithm for multiple memory controllers
- On the Gittins index in the M/G/1 queue
  24 September 2009 | Queueing Systems, Vol. 63, No. 1-4
- An RL-based scheduling algorithm for video traffic in high-rate wireless personal area networks
  Computer Networks, Vol. 53, No. 18
- Fluid Limits for Shortest Remaining Processing Time Queues
  Douglas G. Down,
  H. Christian Gromoll,
  Amber L. Puha,
  20 October 2009 | Mathematics of Operations Research, Vol. 34, No. 4
- State-dependent response times via fluid limits in shortest remaining processing time queues
  16 October 2009 | ACM SIGMETRICS Performance Evaluation Review, Vol. 37, No. 2
- Multi-objective scheduling for real-time data warehouses
  2 April 2009 | Computer Science - Research and Development, Vol. 24, No. 3
- SRPT applied to bandwidth-sharing networks
  13 September 2008 | Annals of Operations Research, Vol. 170, No. 1
- Optimal choice of threshold in Two Level Processor Sharing
  13 September 2008 | Annals of Operations Research, Vol. 170, No. 1
- Heavy-tailed limits for medium size jobs and comparison scheduling
  13 September 2008 | Annals of Operations Research, Vol. 170, No. 1
- Round robin scheduling of heterogeneous parallel servers in heavy traffic
  European Journal of Operational Research, Vol. 195, No. 2
- Performance Evaluation of Interactive Data Services Under Sharing and Preemptive Scheduling Disciplines
- Fifty years of scheduling: a survey of milestones
  21 December 2017 | Journal of the Operational Research Society, Vol. 60, No. sup1
- BMAP/G/1/∞ system with last come first served probabilistic priority
  16 May 2009 | Automation and Remote Control, Vol. 70, No. 5
- Power-Aware Speed Scaling in Processor Sharing Systems
- On the Impact of Heterogeneity and Back-End Scheduling in Load Balancing Designs
- Efficient fair algorithms for message communication
  Simulation Modelling Practice and Theory, Vol. 17, No. 3
- Shortest Remaining Response Time Scheduling for Improved Web Server Performance
- Assessing the efficiency of resource allocations in bandwidth-sharing networks
  Performance Evaluation, Vol. 66, No. 1
- Sojourn times in (discrete) time shared systems and their continuous time limits
  25 October 2008 | Queueing Systems, Vol. 60, No. 3-4
- Improving peer-to-peer performance through server-side scheduling
  19 December 2008 | ACM Transactions on Computer Systems, Vol. 26, No. 4
- On the twin measure and queueing systems predictability
  Performance Evaluation, Vol. 65, No. 11-12
- SRPT optimally utilizes faster machines to minimize flow time
  12 December 2008 | ACM Transactions on Algorithms, Vol. 5, No. 1
- Combining opportunistic and size-based scheduling in wireless systems
  27 October 2008
- The effect of local scheduling in load balancing designs
  31 August 2008 | ACM SIGMETRICS Performance Evaluation Review, Vol. 36, No. 2
- Recent sojourn time results for multilevel processor‐sharing scheduling disciplines
  22 July 2008 | Statistica Neerlandica, Vol. 62, No. 3
- Scheduling despite inexact job-size information
  2 June 2008 | ACM SIGMETRICS Performance Evaluation Review, Vol. 36, No. 1
- Scheduling despite inexact job-size information
  2 June 2008
- Scheduling problems in master-slave model
  1 December 2007 | Annals of Operations Research, Vol. 159, No. 1
- ASYMPTOTIC PROPERTIES OF SOJOURN TIMES IN MULTICLASS TIME-SHARED SYSTEMS
  19 March 2008 | Probability in the Engineering and Informational Sciences, Vol. 22, No. 2
- Fine-Tuning MAC-Level Protocols for Optimized Real-Time QoS
  IEEE Transactions on Industrial Informatics, Vol. 4, No. 1
- Flow Time Minimization
- Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
- Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count
- Minimizing Average Flow Time in Sensor Data Gathering
- Scheduling for performance and availability in systems with temporal dependent workloads
- On the relative value of local scheduling versus routing in parallel server systems
- Efficient resource allocation in bandwidth-sharing networks
  1 December 2007 | ACM SIGMETRICS Performance Evaluation Review, Vol. 35, No. 3
- Minimizing weighted flow time
  1 November 2007 | ACM Transactions on Algorithms, Vol. 3, No. 4
- Scheduling in polling systems
  Performance Evaluation, Vol. 64, No. 9-12
- Fair Efficiency, or Low Average Delay without Starvation
- PBS
  12 June 2007
- Adaptive and scalable comparison scheduling
  12 June 2007
- PBS
  12 June 2007 | ACM SIGMETRICS Performance Evaluation Review, Vol. 35, No. 1
- Adaptive and scalable comparison scheduling
  12 June 2007 | ACM SIGMETRICS Performance Evaluation Review, Vol. 35, No. 1
- A Network Architecture for Large-Scale Science
- Approximability of single machine scheduling with fixed jobs to minimize total completion time
  European Journal of Operational Research, Vol. 178, No. 1
- Fairness and classifications
  1 March 2007 | ACM SIGMETRICS Performance Evaluation Review, Vol. 34, No. 4
- Flow Shop Scheduling
- Impact of Size-Based Scheduling on Flow Level Performance in Wireless Downlink Data Channels
- Stability of Networks with Age-Based Scheduling
- On the effect of inexact size information in size based policies
  1 December 2006 | ACM SIGMETRICS Performance Evaluation Review, Vol. 34, No. 3
- M/G/1/MLPS compared with M/G/1/PS within service time distribution class IMRL
  15 August 2006 | Mathematical Methods of Operations Research, Vol. 64, No. 2
- A large-deviations analysis of the GI/GI/1 SRPT queue
  Queueing Systems, Vol. 54, No. 2
- A Branch and bound for 1|ri| wiCi, Scheduling Problem
- Optimal Scheduling of Heavy Tailed Traffic via Shape Parameter Estimation
- Handling load with less stress
  Queueing Systems, Vol. 54, No. 1
- Revisiting unfairness in Web server scheduling
  Computer Networks, Vol. 50, No. 13
- Multi-layered round robin routing for parallel servers
  Queueing Systems, Vol. 53, No. 4
- Minimizing sum of completion times and makespan in master-slave systems
  IEEE Transactions on Computers, Vol. 55, No. 8
- Tail asymptotics for policies favoring short jobs in a many-flows regime
  26 June 2006 | ACM SIGMETRICS Performance Evaluation Review, Vol. 34, No. 1
- Tail asymptotics for policies favoring short jobs in a many-flows regime
  26 June 2006
- The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
  7 June 2005 | Mathematical Programming, Vol. 106, No. 1
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
  Luca Becchetti,
  Stefano Leonardi,
  Alberto Marchetti-Spaccamela,
  Guido Schäfer,
  Tjark Vredeveld,
  1 February 2006 | Mathematics of Operations Research, Vol. 31, No. 1
- TCP as an Implementation of Age-Based Scheduling: Fairness and Performance
- Comparing Different Approaches to the use of DiffServ in the Internet
- Design choices for content distribution in P2P networks
  6 October 2005 | ACM SIGCOMM Computer Communication Review, Vol. 35, No. 5
- Systems with multiple servers under heavy-tailed workloads
  Performance Evaluation, Vol. 62, No. 1-4
- A review of exact solution methods for the non-preemptive multiprocessor flowshop problem
  European Journal of Operational Research, Vol. 164, No. 3
- Nearly insensitive bounds on SMART scheduling
  6 June 2005
- Classifying scheduling policies with respect to higher moments of conditional response time
  6 June 2005
- Nearly insensitive bounds on SMART scheduling
  6 June 2005 | ACM SIGMETRICS Performance Evaluation Review, Vol. 33, No. 1
- Classifying scheduling policies with respect to higher moments of conditional response time
  6 June 2005 | ACM SIGMETRICS Performance Evaluation Review, Vol. 33, No. 1
- Minimizing flow time on a constant number of machines with preemption
  Operations Research Letters, Vol. 33, No. 3
- On the average sojourn time under M/M/1/SRPT
  Operations Research Letters, Vol. 33, No. 2
- Priority Auctions and Queue Disciplines That Depend on Processing Time
  Thomas Kittsteiner,
  Benny Moldovanu,
  1 February 2005 | Management Science, Vol. 51, No. 2
- Cooperative Content Distribution: Scalability Through Self-Organization
- New On-Line Preemptive Scheduling Policies for Improving Real-Time Behavior
- Analysis and control of correlated web server queues
  Computer Communications, Vol. 27, No. 18
- Looking at the server side of peer-to-peer systems
  22 October 2004
- On-line scheduling to minimize average completion time revisited
  Operations Research Letters, Vol. 32, No. 5
- Formalizing SMART scheduling
  1 September 2004 | ACM SIGMETRICS Performance Evaluation Review, Vol. 32, No. 2
- Optimizing Pilot Planning and Training for Continental Airlines
  Gang Yu,
  Julian Pachon,
  Benjamin Thengvall,
  Darryal Chandler,
  Al Wilson,
  1 August 2004 | Interfaces, Vol. 34, No. 4
- Adaptive memory allocations in clusters to handle unexpectedly large data-intensive jobs
  IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 7
- SPT is optimally competitive for uniprocessor flow
  Information Processing Letters, Vol. 90, No. 5
- Two-level processor-sharing scheduling disciplines
  1 June 2004
- Two-level processor-sharing scheduling disciplines
  1 June 2004 | ACM SIGMETRICS Performance Evaluation Review, Vol. 32, No. 1
- Asymptotic Performance Ratio of an Online Algorithm for the Single Machine Scheduling With Release Dates
  IEEE Transactions on Automatic Control, Vol. 49, No. 5
- Enhancing Both Network and User Performance for Networks Supporting Best Effort Traffic
  IEEE/ACM Transactions on Networking, Vol. 12, No. 2
- Class Scheduling for Pilot Training
  Xiangtong Qi,
  Jonathan F. Bard,
  Gang Yu,
  1 February 2004 | Operations Research, Vol. 52, No. 1
- Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line Algorithms
- Sensitivity Analysis for Scheduling Problems
  Journal of Scheduling, Vol. 7, No. 1
- Size-based scheduling policies with inaccurate scheduling information
- Simulation evaluation of hybrid srpt scheduling policies
- Logistics scheduling: Analysis of two-stage problems
  Journal of Systems Science and Systems Engineering, Vol. 12, No. 4
- Competitive Analysis of a Better On-line Algorithm to Minimize Total Completion Time on a Single-machine
  Journal of Global Optimization, Vol. 27, No. 1
- On the average sojourn time under M/M/1/SRPT
  1 September 2003 | ACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 2
- Revisiting correlations and scheduling in Web servers
  1 September 2003 | ACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 2
- Evolutionary programming for minimizing the average flow time in the presence of non-zero ready times
  Computers & Industrial Engineering, Vol. 45, No. 2
- Analysis of LAS scheduling for job size distributions with high variance
  10 June 2003
- Fairness and efficiency in web server protocols
  10 June 2003
- Classifying scheduling policies with respect to unfairness in an M/GI/1
  10 June 2003
- Analysis of LAS scheduling for job size distributions with high variance
  10 June 2003 | ACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 1
- Fairness and efficiency in web server protocols
  10 June 2003 | ACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 1
- Classifying scheduling policies with respect to unfairness in an M/GI/1
  10 June 2003 | ACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 1
- A class of on-line scheduling algorithms to minimize total completion time
  Operations Research Letters, Vol. 31, No. 3
- Finite State and Action MDPS
- Optimization-Based Integrated Manpower Management for Airlines
- Web servers under overload: How scheduling can help
- Quantifying the properties of SRPT scheduling
- SWIFT: scheduling in web servers for fast response time
- Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms
  SSRN Electronic Journal, Vol. 31
- On the Invariance of Stationary State Probabilities of a Non-Product-Form Single-Line Queueing System
  Problems of Information Transmission, Vol. 38, No. 4
- Asymptotic convergence of scheduling policies with respect to slowdown
  Performance Evaluation, Vol. 49, No. 1-4
- Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed
  Computers & Operations Research, Vol. 29, No. 3
- Size-based adaptive bandwidth allocation: optimizing the average QoS for elastic flows
- A QoS framework for heavy-tailed traffic over the wireless Internet
- Scheduling heavy-tailed data traffic over the wireless Internet
- Analysis of M/G/1/SRPT under transient overload
  1 December 2001 | ACM SIGMETRICS Performance Evaluation Review, Vol. 29, No. 3
- Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates
  Operations Research Letters, Vol. 29, No. 3
- A flexible flowshop problem with total flow time minimization
  European Journal of Operational Research, Vol. 132, No. 3
- Analysis of SRPT scheduling
  1 June 2001
- Analysis of SRPT scheduling
  1 June 2001 | ACM SIGMETRICS Performance Evaluation Review, Vol. 29, No. 1
- SRPT Scheduling for Web Servers
  19 October 2001
- The Map/G/ /1/$\infty$ Queue with SRPT Service Discipline
  Theory of Probability & Its Applications, Vol. 45, No. 3
- Parallel Machine Scheduling to Minimize Total Completion Time with Release Dates Constraints
  IFAC Proceedings Volumes, Vol. 33, No. 17
- Sorting of items on a moving conveyor belt. Part 2: performance evaluation and optimization of pick-and-place operations
  Robotics and Computer-Integrated Manufacturing, Vol. 16, No. 2-3
- Scheduling on a Constant Number of Machines
- Minimizing total completion time subject to release dates and sequence‐dependentprocessing times
  Annals of Operations Research, Vol. 86, No. 0
- A Review of Machine Scheduling: Complexity, Algorithms and Approximability
- Online scheduling algorithms for improving performance of pick-and-place operations on a moving conveyor belt
- Scheduling Models and Algorithms for TMA Traffic Management
- Scheduling packet transmissions in a multi-hop packet switched network based on message length
- Ranking Dispatching Rules by Data Envelopment Analysis in a Job Shop Environment
  13 September 2016 | IIE Transactions, Vol. 28, No. 8
- On-Line Algorithms for a Single Machine Scheduling Problem
- On-line scheduling to maximize task completions
- Network of queues modeling in flexible manufacturing systems : a survey
  29 March 2011 | RAIRO - Operations Research, Vol. 27, No. 2
- A branch-and-bound algorithm to minimize total flow time with unequal release dates
  Naval Research Logistics, Vol. 39, No. 6
- Further applications of the optimal strategy srpt to media access protocols in local area networks
  12 September 2008 | European Transactions on Telecommunications, Vol. 3, No. 3
- A branch-and-bound algorithm to minimize total tardiness with different release dates
  Naval Research Logistics, Vol. 39, No. 2
- An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems
- Central processor scheduling using I/O behaviour models
  International Journal of Systems Science, Vol. 21, No. 10
- The steady-state appearance of the M / G /1 queue under the discipline of shortest remaining processing time
  1 July 2016 | Advances in Applied Probability, Vol. 22, No. 2
- Further results on a new combined strategy based on the SRPT-principle
  IEEE Transactions on Communications, Vol. 38, No. 5
- The performance of multiprogrammed multiprocessor scheduling algorithms
  1 April 1990 | ACM SIGMETRICS Performance Evaluation Review, Vol. 18, No. 1
- Chapter 11 Queueing networks
- Applying the SRPT Principle to Improve the Performance of the CSMA/CD Media Access Control Protocol
- Performance evaluation of a new CSMA/CD protocol based on the SRPT principle
- Limits on stationary queue length under various service disciplines
  Journal of Soviet Mathematics, Vol. 40, No. 4
- Stationary deterministic flows: II. The single-server queue
  Theoretical Computer Science, Vol. 52, No. 3
- Stochastically minimizing the number of customers in exponential queuing systems
  European Journal of Operational Research, Vol. 27, No. 1
- Evaluation of the Optimal SRPT Strategy with Overhead
  IEEE Transactions on Communications, Vol. 34, No. 4
- Process Scheduling in a Computer System
  IEEE Transactions on Computers, Vol. C-34, No. 7
- Optimal Resource Allocation for Two Processes*
  29 July 2013 | AT&T Technical Journal, Vol. 64, No. 1
- Serving process with least thinking time maximizes resource utilization
  IEEE Transactions on Automatic Control, Vol. 29, No. 11
- The serving process with least thinking time maximizes resource utilization
- On reducing time spent in M/G/1 systems
  European Journal of Operational Research, Vol. 9, No. 3
- Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime
  14 July 2016 | Journal of Applied Probability, Vol. 19, No. 01
- Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime
  14 July 2016 | Journal of Applied Probability, Vol. 19, No. 1
- Scheduling Stochastic Jobs on Parallel Machines to Minimize Makespan or Flowtime
- On n/1/F̄ dynamic deterministic problems
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 26, No. 3
- Adaptive Processor Scheduling Based On Approximating Demand Distribution
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 15, No. 2
- Multiple feedback at a single-server station
  Stochastic Processes and their Applications, Vol. 5, No. 2
- A hamiltonian approach to optimal stochastic resource allocation
  1 July 2016 | Advances in Applied Probability, Vol. 9, No. 1
- Scheduling, Queues and Dynamic Allocation Indices
- Scheduling Techniques for Operating Systems
  Computer, Vol. 9, No. 10
- Multi-queue scheduling of two tasks
  Acta Informatica, Vol. 7, No. 2
- A simulation tool for performance evaluation of the IBM 360/75
  International Journal of Computer & Information Sciences, Vol. 3, No. 1

Volume 16, Issue 3

May-June 1968

Pages 457-707

Article Information

Metrics

Information

Published Online:June 01, 1968

Cite as

Linus Schrage, (1968) Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline. Operations Research 16(3):687-690.

https://doi.org/10.1287/opre.16.3.687

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline

Volume 16, Issue 3

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News