Fluid Limits for Shortest Remaining Processing Time Queues
Fluid Limits for Shortest Remaining Processing Time Queues
复制标题
最短剩余处理时间队列的流体限制
DOI：
10.1287/moor.1090.0409
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Amber L. Puha
中科院分区：
文献类型：
--
作者：
D. Down;Christian H. Gromoll;Amber L. Puha
我们考虑一个带有续签到达和身份证明的单服务台排队。服务器使用最短剩余处理时间策略的服务时间。为了描述该队列的演变，我们使用一个度量值流程来跟踪所有缓冲作业的剩余服务时间。我们提出了该系统的流体模型(或形式大数定律近似)，并在较温和的假设下证明了流体模型解的存在唯一性。此外，我们还证明了一个标度极限定理，证明了流体模型是随机模型的一阶近似。流体模型的状态描述符是一个度量值函数，其动力学由结合标准工作负载方程的某些不等式来控制。具体地说，这些动力学决定了状态描述符支持的左边缘(下确界)的演变，这产生了关于响应时间的结论。我们将这一左边缘的演化描述为初始条件、到达率和服务时间分布的逆泛函。这种表征揭示了左边缘的增长率取决于服务时间分布的方式。通过考虑不同的例子，作者表明，速度可以从对数到多项式变化。
We consider a single-server queue with renewal arrivals and i.i.d. service times in which the server uses the shortest remaining processing time policy. To describe the evolution of this queue, we use a measure-valued process that keeps track of the residual service times of all buffered jobs. We propose a fluid model (or formal law of large numbers approximation) for this system and, under mild assumptions, prove the existence and uniqueness of fluid model solutions. Furthermore, we prove a scaling limit theorem that justifies the fluid model as a first-order approximation of the stochastic model. The state descriptor of the fluid model is a measure-valued function whose dynamics are governed by certain inequalities in conjunction with the standard workload equation. In particular, these dynamics determine the evolution of the left edge (infimum) of the state descriptor's support, which yields conclusions about response times. We characterize the evolution of this left edge as an inverse functional of the initial condition, arrival rate, and service time distribution. This characterization reveals the manner in which the growth rate of the left edge depends on the service time distribution. By considering varying examples, the authors show that the rate can vary from logarithmic to polynomial.