Fluid Limits for Multiple-Input Shortest Remaining Processing Time Queues

• 成果类型: Article
• 署名作者: Kruk, Lukasz; Sokolowska, Ewa
• 署名单位: Maria Curie-Sklodowska University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0768
• 发表日期: 2016
• 页码: 1055-1092
• 关键词: state-space collapse; m/g/1; discipline; optimality; STABILITY; SYSTEM; PROOF

摘要

A single queueing station serving K input streams with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served by the Shortest Remaining Processing Time policy. In the case of a tie, the first-in, first-out policy is utilized. We analyze a fluid model for the evolution of a measure-valued state descriptor of this system, with particular emphasis on its limiting behavior in the critical case as time gets large. We also prove a fluid limit theorem justifying our fluid model as the first-order approximation of the queueing system under consideration. Along the way, we establish fluid limits for the corresponding state-dependent response times.