A Skorokhod Map on Measure-Valued Paths with Applications to Priority Queues

Rami Atar, Anup Biswas, Haya Kaspi, Kavita Ramanan

Published 2016-04-17Version 1

The Skorokhod map on the half-line has proved to be a useful tool for studying processes with non-negativity constraints. In this work we introduce a measure-valued analog of this map that transforms each element $\zeta$ of a certain class of c\`{a}dl\`{a}g paths that take values in the space of signed measures on the half-line to a c\`{a}dl\`{a}g path that takes values in the space of non-negative measures on $[0,\infty)$ in such a way that for each $x > 0$, the path $t \mapsto \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.