Operations Research seminar

Operations Research seminar

Analysis and optimisation of polling systems with Markovian server routing

Jan-Pieter Dorsman, Universiteit Leiden


Polling systems are queueing systems that consist of a number of queues, attended by a single server. These systems find their origin in a wealth of real-life applications, such as manufacturing environments, computer-communication systems and traffic systems.

Many studies on polling systems assume that the server visits the queues in a cyclic order. This, however, may in some cases not be a realistic assumption, as the queue to be visited next is determined by an external random environment. As such, we study the generalised case where the order in which the server visits the queues is governed by a Markov chain: after a visit to queue i, the server visits queue j with probability p_{i,j}.

These polling systems with so-called Markovian server routing are much harder to analyse than cyclic polling systems, since the queue length processes do not satisfy a certain branching property. Nevertheless, in this talk, we discuss several new results for the analysis of these generalised systems, such as heavy-traffic asymptotics for the stationary queue length distributions. Using these results, several optimisation problems can be addressed.

This talk is based on joint work with Sem Borst, Onno Boxma, Rob van der Mei and Maria Vlasiou.