A Skorokhod map on measure-valued paths with applications to priority queues Rami Atar, Anup Biswas, Haya Kaspi, and Kavita Ramanan

Abstract

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 càdlàg paths that take values in the space of signed measures on [0,∞) to a càdlàg path that takes values in the space of nonnegative measures on [0,∞) in such a way that for each x>0, the path t↦ζ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.