A SKOROKHOD MAP ON MEASURE-VALUED PATHS WITH APPLICATIONS TO PRIORITY QUEUES

• 成果类型: Article
• 署名作者: Atar, Rami; Biswas, Anup; Kaspi, Haya; Ramanan, Kavita
• 署名单位: Technion Israel Institute of Technology; Indian Institute of Science Education & Research (IISER) Pune; Technion Israel Institute of Technology; Brown University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1309
• 发表日期: 2018
• 页码: 418-481
• 关键词: many-server queues; remaining processing time; fluid limits; sharing queue; discipline; STABILITY; networks; policies; 1st

摘要

The Skorokhod map on the half-line has proved to be a useful tool for studying processes with nonnegativity constraints. In this work, we introduce a measure-valued analog of this map that transforms each element. of a certain class of cadlag paths that take values in the space of signed measures on [0, infinity) to a cadlag path that takes values in the space of nonnegative measures on [0, infinity) in such a way that for each x > 0, the path t (bar right arrow) zeta(t) [0, x] is transformed via a Skorokhod map on the half-line, and the regulating functions for different x > 0 are coupled. We establish regularity properties of this map and show that the map provides a convenient tool for studying queueing systems in which tasks are prioritized according to a continuous parameter. Three such well-known models are the earliest-deadline-first, the shortest-job-first and the shortest-remaining-processing-time scheduling policies. For these applications, we show how the map provides a unified framework within which to form fluid model equations, prove uniqueness of solutions to these equations and establish convergence of scaled state processes to the fluid model. In particular, for these models, we obtain new convergence results in time-inhomogeneous settings, which appear to fall outside the purview of existing approaches.