Stability of skill-based queues with deterministic waiting time thresholds

Abstract

We consider skill-based queues where service is First--Come--First--Served, but some compatibility lines are only available once a customer's waiting time exceeds a threshold. For this model, we establish necessary and sufficient stability conditions. We find that the thresholds do not affect stability; an intuitive result that has not been proved in the literature up to this point. While necessity follows from a coupling argument, the sufficiency proof is more challenging. It follows by formulating the First--in--Line waiting time process as a Piecewise Deterministic Markov Process (PDMP) and constructing a Lyapunov function that accounts for the threshold structure. We show that this Lyapunov function satisfies the boundary condition of the PDMP framework, and that its generator has negative drift when waiting times are large. Finally, we show that bounded waiting-time sets are petite, so that the Foster--Lyapunov criterion applies.