Abstract
In this paper, we propose a fully polynomial-time randomized approximation scheme (FPRAS) for a closed Jackson network. Our algorithm is based on the Markov chain Monte Carlo (MCMC) method. Thus our scheme returns an approximate solution, for which the size of the error satisfies a given bound. To our knowledge, this algorithm is the first polynomial time MCMC algorithm for closed Jackson networks with multiple servers. We propose two new ergodic Markov chains, both of which have a unique stationary distribution that is the product form solution for closed Jackson networks. One of them is for an approximate sampler, and we show that it mixes rapidly. The other is for a perfect sampler based on the monotone coupling from the past (CFTP) algorithm proposed by Propp and Wilson, and we show that it has a monotone update function.
Similar content being viewed by others
References
Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. In D. Dold & B. Eckmann (Eds.), Springer lecture notes in mathematics : Vol. 986. Séminarie de probabilitiés XVII 1981/1982 (pp. 243–297). New York: Springer.
Baskett, F., Chandy, K. M., Muntz, R. R., & Palacious, F. G. (1975). Open, closed and mixed networks of queues with different classes of customers. Journal of ACM, 22, 248–260.
Bubley, R. (2001). Randomized algorithms: approximation, generation, and counting. New York: Springer.
Bubley, R., & Dyer, M. (1997). Path coupling: a technique for proving rapid mixing in Markov chains. In Proceedings of the 38th annual symposium on foundations of computer science (FOCS 1997) (pp. 223–231).
Buzacott, J., & Yao, D. (1986). On queueing network models of flexible manufacturing systems. Queueing Systems, 1, 5–27.
Buzen, J. P. (1973). Computational algorithms for closed queueing networks with exponential servers. Communications of the ACM, 16, 527–531.
Cao, X. (1989). Realization probability and throughput sensitivity in a closed Jackson network. Journal of Applied Probability, 26, 615–624.
Chao, X., Miyazawa, M., & Pinedo, M. (1999). Queueing networks, customers, signals and product form solutions. New York: Wiley.
Chen, W., & O’Cinneide, C. A. (1998). Towards a polynomial-time randomized algorithm for closed product-form networks. ACM Transactions on Modeling and Computer Simulation, 8, 227–253.
Dyer, M., & Greenhill, C. (2000). Polynomial-time counting and sampling of two-rowed contingency tables. Theoretical Computer Sciences, 246, 265–278.
Fill, J. (1998). An interruptible algorithm for perfect sampling via Markov chains. The Annals of Applied Probability, 8, 131–162.
Fill, J., Machida, M., Murdoch, D., & Rosenthal, J. (2000). Extension of Fill’s perfect rejection sampling algorithm to general chains. Random Structures and Algorithms, 17, 290–316.
Gelenbe, E., & Pujolle, G. (1998). Introduction to queueing networks (2nd ed.). New York: Wiley.
Gordon, W. J., & Newell, G. F. (1967). Closed queueing systems with exponential servers. Operations Research, 15(2), 254–265.
Häggström, O. (2002). London mathematical society, student texts : Vol. 52. Finite Markov chains and algorithmic application. Cambridge: Cambridge University Press.
Jackson, J. R. (1957). Networks of waiting lines. The Journal of Operations Research Society of America, 5, 518–521.
Jackson, J. R. (1963). Jobshop-like queueing systems. Management Science, 10(1), 131–142.
Jerrum, M. (2003). Lectures in mathematics. Counting, sampling and integrating: algorithms and complexity. Basel: Birkhauser.
Jerrum, M., & Sinclair, A. (1996). The Markov chain Monte Carlo method: an approach to approximate counting and integration. In D. Hochbaum (Ed.), Approximation algorithm for NP-hard problems (pp. 482–520). Boston: PWS.
Kelly, F. (1991). Loss networks. Annals of Applied Probability, 1, 319–378.
Kijima, S., & Matsui, T. (2004). Approximate counting scheme for m×n contingency tables. IEICE Transactions on Information and Systems D, E87, 308–314.
Kijima, S., & Matsui, T. (2005a). Polynomial-time randomized approximation and perfect sampler for closed Jackson networks with single servers (METR 2005-12, Mathematical Engineering Technical Reports). University of Tokyo. Available from http://www.keisu.t.u-tokyo.ac.jp/Research/techrep.0.html.
Kijima, S., & Matsui, T. (2005b). Approximate/perfect samplers for closed Jackson networks. In Proceedings of the 2005 winter simulation conference (pp. 862–868).
Kijima, S., & Matsui, T. (2006). Polynomial time perfect sampling algorithm for two-rowed contingency tables. Random Structures Algorithms, 29(2), 243–256.
Kryvinska, N. (2004). Intelligent network analysis by closed queuing models. Telecommunication Systems, 27, 85–98.
Malyshev, V., & Yakovlev, A. (1996). Condensation in large closed Jackson networks. The Annals of Applied Probability, 6, 92–115.
Matsui, T., Motoki, M., & Kamatani, N. (2003). Polynomial time approximate sampler for discretized Dirichlet distribution. In Lecture notes in computer science : Vol. 2906. 14th international symposium on algorithms and computation (ISAAC 2003) (pp. 676–685). Berlin: Springer.
Matsui, T., Motoki, M., Kamatani, N., & Kijima, S. (2006). Polynomial time approximate/perfect samplers for discretized Dirichlet distribution (METR 2006-09, Mathematical Engineering Technical Reports). University of Tokyo. Available from http://www.keisu.t.u-tokyo.ac.jp/Research/techrep.0.html.
Mitzenmacher, M., & Upfal, E. (2005). Probability and computing, randomized algorithms and probabilistic analysis. Cambridge: Cambridge University Press.
Mohamed, A., Lipsky, L., & Ammar, R. (2005). Modeling parallel and distributed systems with finite workloads. Performance Evaluation, 60, 303–325.
Ozawa, T. (2004). Perfect simulation of a closed Jackson network. The operations research society of Japan queueing symposium. Hikone, Japan.
Propp, J., & Wilson, D. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms, 9, 223–252.
Reiser, M., & Lavenberg, S. (1980). Mean value analysis for closed multi-chain Queueing networks. Journal of ACM, 27, 313–322.
Ross, K. W., & Wang, J. (1993). Asymptotically optimal importance sampling for product-form queuing networks. ACM Transactions on Modeling and Computer Simulation, 3, 244–268.
Stuck, B., & Arthurs, E. (1984). Computer and communications network performance analysis primer. Eglewood Cliffs: Prentice Hall.
Wilson, D. (2000). How to couple from the past using a read-once source of randomness. Random Structures Algorithms, 16, 85–113.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kijima, S., Matsui, T. Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers. Ann Oper Res 162, 35–55 (2008). https://doi.org/10.1007/s10479-008-0317-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0317-2