Invariance of fluid limits for the Shortest Remaining Processing Time\n and Shortest Job First policies

2010/07/14 by H. Christian Gromoll, Gromoll, H. Christian, Martin Keutel +1
Business, Management and Accounting · Computer Science · Engineering · Health Professions · #60F17 #68M20 #90B22 #Advanced Queuing Theory Analysis #Advanced Wireless Network Optimization #Age of Information Optimization #FOS: Mathematics #Healthcare Operations and Scheduling Optimization #Primary 60K25 #Probability (math.PR) #secondary 60G57

paper · pdf · doi:10.48550/arxiv.1007.2469

openalex publication_date 2010/07/14 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28

Abstract

We consider a single-server queue with renewal arrivals and i.i.d. service\ntimes, in which the server employs either the preemptive Shortest Remaining\nProcessing Time (SRPT) policy, or its non-preemptive variant, Shortest Job\nFirst (SJF). We show that for given stochastic primitives (initial condition,\narrival and service processes), the model has the same fluid limit under either\npolicy. In particular, we conclude that the well-known queue length optimality\nof preemptive SRPT is also achieved, asymptotically on fluid scale, by the\nsimpler-to-implement SJF policy. We also conclude that on fluid scale, SJF and\nSRPT achieve the same performance with respect to response times of the\nlongest-waiting jobs in the system.\n

Citations

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

Related

• Fluid limits of G/G/1+G queues under the non-preemptive earliest-deadline-first discipline
• On the SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers
• Dynamic scheduling in a partially fluid, partially lossy queueing system
• Stationary analysis of the Shortest Queue First service policy
• A Fluid Limit for Processor-Sharing Queues Weighted by Functions of Remaining Amounts of Service