Skip to main content

Research Repository

Advanced Search

Dynamics of the non-homogeneous supermarket model

MacPhee, I.M.; Menshikov, M.V.; Vachkovskaia, M.


I.M. MacPhee

M. Vachkovskaia


We consider the long term behavior of a Markov chain ξ(t) on ℤ N based on the N station supermarket model with general neighborhoods, arrival rates and service rates. Different routing policies for the model give different Markov chains. We show that for a broad class of local routing policies, join the least weighted queue (JLW), the N one-dimensional components ξ i (t) can be partitioned into disjoint clusters C k . Within each cluster C k the speed of each component ξ j converges to a constant V k and under certain conditions ξ is recurrent in shape on each cluster. To establish these results we have assembled methods from two distinct areas of mathematics, semi-martingale techniques used for showing stability of Markov chains together with the theory of optimal flows in networks. As corollaries to our main result we obtain the stability classification of the supermarket model under any JLW policy and can explicitly compute the C k and V k for any instance of the model and specific JLW policy.


MacPhee, I., Menshikov, M., & Vachkovskaia, M. (2012). Dynamics of the non-homogeneous supermarket model. Stochastic Models, 28(4), 533-556.

Journal Article Type Article
Publication Date Nov 6, 2012
Deposit Date May 13, 2014
Publicly Available Date Jul 18, 2014
Journal Stochastic Models
Print ISSN 1532-6349
Electronic ISSN 1532-4214
Publisher Taylor and Francis
Peer Reviewed Peer Reviewed
Volume 28
Issue 4
Pages 533-556


You might also like

Downloadable Citations