Abstract
We consider the optimal order of servers in a tandem queueing system withm stages, an unlimited supply of customers in front of the first stage, and a service buffer of size 1 but no intermediate storage buffers between the first and second stages. Service times depend on the servers but not the customers, and the blocking mechanism at the first two stages is manufacturing blocking. Using a new characterization of reversed hazard rate order, we show that if the service times for two servers are comparable in the reversed hazard rate sense, then the departure process is stochastically earlier if the slower server is first and the faster server is second than if the reverse is true. This strengthens earlier results that considered individual departure times marginally. We show similar results for the last two stages and for other blocking mechanisms. We also show that although individual departure times for a system with servers in a given order are stochastically identical to those when the order of servers is reversed, this reversibility property does not hold for the entire departure process.
Similar content being viewed by others
References
A. Avi-Itzhak, A sequence of service stations with arbitrary input and regular service times, Manag. Sci. 11 (1975) 565–573.
J. Buzacott and J.G. Shanthikumar,Stochastic Models of Manufacturing Systems (Prentice Hall, Englewood Cliffs, NJ, 1992).
X. Chao, M. Pinedo and K. Sigman, On the interchangeability and stochastic ordering of exponential queues in tandem with blocking, Prob. Eng. Inf. Sci. 3 (1989) 223–236.
D.W. Cheng, Line reversibility of tandem queues with general blocking, Manag. Sci., 41 (1995) 864–873.
D.W. Cheng and D. Yao, Tandem queues with general blocking: a unified model and comparison results, J. Discr. Event Dyn. Syst: Th. and Appl. 2 (1993) 207–234.
D.W. Cheng and Y. Zhu, Optimal order of servers in a tandem queue with general blocking, Queueing Systems 14 (1993) 427–437.
E.S. Dattatreya, Tandem queueing systems with blocking, Ph.D. Dissertation, Industrial Engineering and Operations Research, University of California, Berkeley (1978).
J. Ding and B.S. Greenberg, Bowl shapes are better with buffers ��� sometimes, Prob. Eng. Inf. Sci. 5 (1991) 159–169.
J. Ding and B.S. Greenberg, Optimal order for servers in series with no queue capacity, Prob. Eng. Inf. Sci. 5 (1991) 449–462.
H.D. Friedman, Reduction methods for tandem queueing systems, Oper. Res. 13 (1965) 121–131.
E. Frostig, On the optimal assignment of servers in a two stations tandem queue with no intermediate waiting room, Oper. Res. Lett. 13 (1993) 13–18.
C.-C. Huang and G. Weiss, On the optimal order ofM machines in tandem, Oper. Res. Lett. 9 (1990) 299–303.
M. Kijima and N. Makimoto, On the interchangeability for exponential single-server queues in tandem, J. Appl. Prob. 27 (1990) 459–464.
P. Ku and S. Niu, On Johnson's two-machine flow shop with random processing times, Oper. Res. 34 (1986) 130–136.
E.J. Muth, The reversibility property of production lines, Manag. Sci. 25 (1979) 152–158.
R. Righter, Scheduling, in:Stochastic Orderings and Their Application, eds. M. Shaked and J.G. Shanthikumar (Academic Press, New York, 1994).
H. Sakasegawa and T. Kawashima, On the equivalence of three types of blocking in non-Markovian tandem queues, Queueing Systems 16 (1994) 301–310.
M. Shaked and J.G. Shanthikumar,Stochastic Orderings and Their Application (Academic Press, New York, 1994).
J.G. Shanthikumar, G. Yamazaki and H. Sakasegawa, Characterization of optimal order of servers in a tandem queue with blocking, Oper. Res. Lett. 10 (1991) 17–22.
T. Suzuki and T. Kawashima, Reduction methods for tandem queueing systems, J. Oper. Res. Japan 17 (1974) 133–144.
S.V. Tembe and R.W. Wolff, The optimal order of service in tandem queues, Oper. Res. 24 (1974) 824–832.
R.R. Weber, The interchangeability of · /M/1 queues in series, J. Appl. Prob. 16 (1979) 690–695.
R.R. Weber and G. Weiss, The cafeteria process — Tandem queues with 0–1 dependent service times and the bowl shape phenomenon, Oper. Res. 42 (1994) 895–912.
G. Yamazaki, The interchangeability of the sojourn and delay times in aGI/M/1→/M/1(0) queue, J. Oper. Res. Japan 24 (1981) 229–236.
G. Yamazaki and Ito, Optimal order problem for two servers in tandem, Preprint (1993).
G. Yamazaki and H. Sakasegawa, Properties of duality in tandem queueing systems, Ann. Inst. Stat. Math. 27 (1975) 201–212.
G. Yamazaki, H. Sakasegawa and J.G. Shanthikumar, On optimal arrangement of stations in a tandem queueing system with blocking, Manag. Sci. 38 (1992) 137–153.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Cheng, D.W., Righter, R. On the order of tandem queues. Queueing Syst 21, 143–160 (1995). https://doi.org/10.1007/BF01158578
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01158578