We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Dynamics of the non-homogeneous supermarket model.

MacPhee, I.M. and Menshikov, M.V. and Vachkovskaia, M. (2012) 'Dynamics of the non-homogeneous supermarket model.', Stochastic models., 28 (4). pp. 533-556.


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.

Item Type:Article
Full text:(NA) Not Applicable
Download PDF (arXiv version)
Publisher Web site:
Publisher statement:This is an Accepted Manuscript of an article published by Taylor & Francis Group in Stochastic Models on 06/11/2012, available online at:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:November 2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar