Videos

Diffusion Limits for Shortest Remaining Processing Time Queues under Nonstandard Spatial Scaling

Presenter
June 26, 2015
Keywords:
  • Diffusion-limited aggregation
Abstract
In a shortest remaining processing time (SRPT) queue, the job that requires the least amount of processing time is preemptively served first. One effect of this is that the queue length is small in comparison to the total amount of work in the system (measured in units of processing time). In the case of service time distributions with unbounded support, the queue length is minimized so well that the sequence of queue length processes associated with a sequence of SRPT queues, rescaled with standard functional central limit theorem scaling and satisfying standard heavy traffic conditions, converges in distribution to the process that is identically equal to zero. This happens despite the fact that under this same regime the rescaled workload processes converge to a non-degenerate reflected Brownian motion. In particular, the queue length process is of smaller order magnitude than the workload process. In the case of processing time distributions that satisfy a rapid variation condition, we implement an alternative, unconventional scaling that leads to a non-trivial limit for the queue length process. This result quantifies this order of magnitude difference between queue length and workload processes. We illustrate this result for Weibull processing time distributions.