Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T03:04:16.506Z Has data issue: false hasContentIssue false
  • English
  • Français

User-Optimal State-Dependent Routeing in Parallel Tandem Queues with Loss

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  14 July 2016

Scott Spicer  and
Ilze Ziedins
Scott Spicer*
Affiliation:
The University of Auckland
Ilze Ziedins*
Affiliation:
The University of Auckland
*
∗ Postal address: Department of Statistics, The University of Auckland, Private Bag 92019, Auckland, New Zealand.
∗ Postal address: Department of Statistics, The University of Auckland, Private Bag 92019, Auckland, New Zealand.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a system of parallel, finite tandem queues with loss. Each tandem queue consists of two single-server queues in series, with capacities C1 and C2 and exponential service times with rates μ1 and μ2 for the first and second queues, respectively. Customers that arrive at a queue that is full are lost. Customers arriving at the system can choose which tandem queue to enter. We show that, for customers choosing a queue to maximise the probability of their reaching the destination (or minimise their individual loss probability), it will sometimes be optimal to choose queues with more customers already present and/or with greater residual service requirements (where preceding customers are further from their final destination).

Keywords

Parallel queuestandem queuesloss probabilityrouteinguser optimality

MSC classification

Primary: 90B15: Network models, stochastic
Secondary: 60K25: Queueing theory
Type
Short Communications
Information
Journal of Applied Probability , Volume 43 , Issue 1 , March 2006 , pp. 274 - 281
Copyright
© Applied Probability Trust 2006 

References

Avi-Itzhak, B. and Levy, H. (2001). Buffer requirements and server ordering in a tandem queue with correlated service times. Math. Operat. Res. 26, 358–374.Google Scholar
Bell, C. E. and Stidham, S. (1983). Individual versus social optimization in the allocation of customers to alternative servers. Manag. Sci. 29, 831–839.CrossRefGoogle Scholar
Bertsekas, D. and Gallager, R. (1992). Data Networks, 2nd edn. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Calvert, B., Solomon, W. and Ziedins, I. (1997). Braess's paradox in a queueing network with state-dependent routing. J. Appl. Prob. 34, 134–154.Google Scholar
Cheng, D. W. and Yao, D. D. (1993). Tandem queues with general blocking: a unified model and comparison results. J. Discrete Event Dyn. Systems Theory Appl. 2, 207–234.Google Scholar
Cohen, J. E. and Kelly, F. P. (1990). A paradox of congestion in a queueing network. J. Appl. Prob. 27, 730–734.Google Scholar
Ephremides, A., Varaiya, P. and Walrand, J. (1980). A simple dynamic routing problem. IEEE Trans. Automatic Control 25, 690–693.Google Scholar
Hordijk, A. and Koole, G. (1990). On the optimality of the generalized shortest queue policy. Prob. Eng. Inf. Sci. 4, 477–487.CrossRefGoogle Scholar
Hordijk, A. and Koole, G. (1992). On the shortest queue policy for the tandem parallel queue. Prob. Eng. Inf. Sci. 6, 63–79.Google Scholar
Hordijk, A. and Koole, G. (1992). On the assignment of customers to parallel queues. Prob. Eng. Inf. Sci. 6, 495–511.Google Scholar
Kelly, F. P. (1979). Reversibility and Stochastic Networks. John Wiley, Chichester.Google Scholar
Koole, G., Sparaggis, P. D. and Towsley, D. (1999). Minimizing response times and queue lengths in systems of parallel queues. J. Appl. Prob. 36, 1185–1193.CrossRefGoogle Scholar
Kumar, P. R. and Walrand, J. (1985). Individually optimal routing in parallel servers. J. Appl. Prob. 22, 989–995.CrossRefGoogle Scholar
Martin, J. B. (2002). Large tandem queueing networks with blocking. Queueing Systems 41, 45–72.Google Scholar
Norris, J. R. (1997). Markov Chains. Cambridge University Press.CrossRefGoogle Scholar
Towsley, D., Sparaggis, P. D. and Cassandras, C. G. (1992). Optimal routing and buffer allocation for a class of finite capacity queueing systems. IEEE Trans. Automatic Control 37, 1446–1451.Google Scholar
Walrand, J. (1988). An Introduction to Queueing Networks. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Weber, R. R. (1978). On the optimal assignment of customers to parallel servers. J. Appl. Prob. 15, 406–413.CrossRefGoogle Scholar
Whitt, W. (1986). Deciding which queue to Join: some counterexamples. Operat. Res. 34, 55–62.Google Scholar
Winston, W. (1977). Optimality of the shortest line discipline. J. Appl. Prob. 14, 181–189.Google Scholar