Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T15:23:45.729Z Has data issue: false hasContentIssue false
  • English
  • Français

The interchangeability of tandem queues with heterogeneous customers and dependent service times

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Richard R. Weber
Richard R. Weber*
Affiliation:
University of Cambridge
*
∗Postal address: University Engineering Department, Management Studies Group, Mill Lane, Cambridge CB2 1RX, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider m queueing stations in tandem, with infinite buffers between stations, all initially empty, and an arbitrary arrival process at the first station. The service time of customer j at station i is geometrically distributed with parameter pi, but this is conditioned on the fact that the sum of the m service times for customer j is cj. Service times of distinct customers are independent. We show that for any arrival process to the first station the departure process from the last station is statistically unaltered by interchanging any of the pi's. This remains true for two stations in tandem even if there is only a buffer of finite size between them. The well-known interchangeability of ·/M/1 queues is a special case of this result. Other special cases provide interesting new results.

Keywords

OUTPUT PROCESSES

MSC classification

Primary: 60K25: Queueing theory
Secondary: 90B22: Queues and service
Type
Research Article
Information
Advances in Applied Probability , Volume 24 , Issue 3 , September 1992 , pp. 727 - 737
Copyright
Copyright © Applied Probability Trust 1992 

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.)

Footnotes

This research has been supported in part by NSF Grant DDM-8914863.

References

Anantharam, V. (1987) Probabilistic proof of interchangeability of /M/1 queues in series. QUESTA 2, 387–392.Google Scholar
Avi-Itzhak, B. and Yadin, M. (1965) A sequence of two servers with no intermediate queue. Management Sci. 11, 553–564.Google Scholar
Chao, X. and Pinedo, M. (1990a) On reversibility of tandem queues with blocking. In preparation.Google Scholar
Chao, X. and Pinedo, M. (1990b) Batch arrivals to tandem queues without an intermediate buffer. Stoch. Models 6, 735–749.Google Scholar
Chao, X., Pinedo, M. and Sigman, K. (1989) On the interchangeability and stochastic ordering of exponential queues in tandem with blocking. Prob. Eng. Inf. Sci. 3, 223–236.Google Scholar
Ding, J. and Greenberg, B. S. (1991) Bowl shapes are better with buffers—sometimes. Prob. Eng. Inf. Sci. 5, 159–169.CrossRefGoogle Scholar
Friedman, H. D. (1965) Reduction methods for tandem queueing systems. Operat. Res. 13, 121–131.Google Scholar
Greenberg, B. S. and Wolff, R. W. (1988) Optimal order of servers for tandem queues in light traffic. Management Sci. 34, 500–508.Google Scholar
Kijima, M. and Makimoto, N. (1990) On interchangeability for exponential single-server queues in tandem. J. Appl. Prob. 27, 690–695.Google Scholar
Lehtonen, T. (1986) On the ordering of tandem queues with exponential servers. J. Appl. Prob. 23, 115–129.CrossRefGoogle Scholar
Pinedo, M. (1982) On the optimal order of stations in tandem queues. In Applied Probability—Computer Science: The Interface , ed. Disney, R. L. and Ott, T. J., pp. 307–326, Birkhauser, Boston, MA.Google Scholar
Tembe, S. V. and Wolff, R. W. (1974) The optimal order of service in tandem queues. Operat. Res. 30, 148–162.Google Scholar
Tsoucas, P. and Walrand, J. (1987) On the interchangeability and stochastic ordering of ·/M/1 queues in tandem. Adv. Appl. Prob. 16, 515–520.Google Scholar
Weber, R. R. (1979) The interchangeability of tandem ·/M/1 queues in series. J. Appl. Prob. 16, 690–695.Google Scholar
Weber, R. R. and Weiss, G. (1991) The cafeteria process—tandem queues with dependent 0–1 service times and the bowl shape phenomenon. Submitted.Google Scholar