Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-22T20:33:32.118Z Has data issue: false hasContentIssue false
  • English
  • Français

The shortest queue problem

Published online by Cambridge University Press:  14 July 2016

Shlomo Halfin
Shlomo Halfin*
Affiliation:
Bell Communications Research
*
∗ Postal address: Bell Communications Research, Room 2L-379, Morris Research and Engineering Center, Morristown, NJ 07960, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

A Poisson stream of customers arrives at a service center which consists of two single-server queues in parallel. The service times of the customers are exponentially distributed, and both servers serve at the same rate. Arriving customers join the shortest of the two queues, with ties broken in any plausible manner. No jockeying between the queues is allowed. Employing linear programming techniques, we calculate bounds for the probability distribution of the number of customers in the system, and its expected value in equilibrium. The bounds are asymptotically tight in heavy traffic.

Keywords

QUEUES IN PARALLELBOUNDSLINEAR PROGRAMMING
Type
Research Papers
Information
Journal of Applied Probability , Volume 22 , Issue 4 , December 1985 , pp. 865 - 878
Copyright
Copyright © Applied Probability Trust 1985 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Conolly, B. W. (1984) The autostrada queueing problem. J. Appl. Prob. 21, 394–403.CrossRefGoogle Scholar
Flatto, L. and Mckean, H. P. (1977) Two queues in parallel. Comm. Pure. Appl. Math. 30, 255–263.Google Scholar
Haight, F. A. (1958) Two queues in parallel. Biometrika 45, 401–410.Google Scholar
Kingman, J. F. C. (1961) Two similar queues in parallel. Ann. Math. Statist. 32, 1314–1323.CrossRefGoogle Scholar
Smith, D. R. and Whitt, W. (1981) Resource sharing for efficiency in traffic systems. Bell System Tech. J. 60, 39–55.Google Scholar
Wolff, R. W. (1977) An upper bound for multi-channel queues. J. Appl. Prob. 14, 884–888.Google Scholar