Summary: We study a single server queue operating under the shortest remaining processing time (SRPT) scheduling policy; that is, the server preemptively serves the job with the shortest remaining processing time first. Since one needs to keep track of the remaining processing times of all jobs in the system in order to describe the evolution, a natural state descriptor for an SRPT queue is a measure valued process in which the state of the system at a given time is the finite nonnegative Borel measure on the nonnegative real line that puts a unit atom at the remaining processing time of each job in system. In this work we are interested in studying the asymptotic behavior of the suitably scaled measure valued state descriptors for a sequence of SRPT queuing systems. H. C. Gromoll et al. [Stoch. Syst. 1, No. 1, 1–16 (2011; Zbl 1291.60187)] have studied this problem under diffusive scaling (time is scaled by \(r^2\) and the mass of the measure normalized by \(r\), where \(r\) is a scaling parameter approaching infinity). In the setting where the processing time distributions have bounded support, under suitable conditions, they show that the measure valued state descriptors converge in distribution to the process that at any given time is a single atom located at the right edge of the support of the processing time distribution with the size of the atom fluctuating randomly in time. In the setting where the processing time distributions have unbounded support, under suitable conditions, they show that the diffusion scaled measure valued state descriptors converge in distribution to the process that is identically zero. In [A. L. Puha, Ann. Appl. Probab. 25, No. 6, 3381–3404 (2015; Zbl 1328.60205)] for the setting where the processing time distributions have unbounded support and light tails, a nonstandard scaling of the queue length process is shown to give rise to a form of state space collapse that results in a nonzero limit.
In the current work we consider the case where processing time distributions have finite second moments and regularly varying tails. Results of [Zbl 1328.60205] suggest that the right scaling for the measure valued process is governed by a parameter \(c^r\) that is given as a certain inverse function related to the tails of the first moment of the processing time distribution. Using this parameter we consider a novel scaling for the measure valued process in which the time is scaled by a factor of \(r^2\), the mass is scaled by the factor \(c^r /r\) and the space (representing the remaining processing times) is scaled by the factor \(1/c^r\). We show that the scaled measure valued process converges in distribution (in the space of paths of measures). In a sharp contrast to results for bounded support and light tailed service time distributions, this time there is no state space collapse and the limiting measures are not concentrated on a single atom. Nevertheless, the description of the limit is simple and given explicitly in terms of a certain \(\mathbb{R}_+\) valued random field which is determined from a single Brownian motion. Along the way we establish convergence of suitably scaled workload and queue length processes. We also show that as the tail of the distribution of job processing times becomes lighter in an appropriate fashion, the difference between the limiting queue length process and the limiting workload process converges to zero, thereby approaching the behavior of state space collapse.