Abstract
In this paper, we consider a general state-dependent finite-buffer bulk queue in which the rates and batch sizes of arrivals and services are allowed to depend on the number of customers in queue and service batch sizes. Such queueing systems have rich applications in manufacturing, service operations, computer and telecommunication systems. Interesting examples include batch oven processes in the aircraft and semiconductor industry; serving of passengers by elevators, shuttle buses, and ferries; and congestion control mechanisms to regulate transmission rates in packet-switched communication networks. We develop a unifying method to study the performance of this general class of finite-buffer state-dependent bulk queueing systems. For this purpose, we use semi-regenerative analysis to develop a numerically stable method for calculating the limiting probability distribution of the queue length process. Based on the limiting probabilities, we present various performance measures for evaluating admission control and batch service policies, such as the loss probability for an arriving group of customers and for individual customers within a group. We demonstrate our method by means of numerical examples.
Article PDF
Similar content being viewed by others
References
Aalto S (2000) Optimal control of batch service queues with finite service capacity and linear holding costs. Math Methods Oper Res 51(2): 263–285
Asmussen S (2003) Applied probability and queues. Springer, New York
Bagchi TP, Templeton JGC (1973) A note on the M X/G Y/1, K bulk queueing system. J Appl Probab 10(4): 901–906
Bekker R (2004) Finite buffer queues with workload-dependent service and arrival rates. PhD thesis, Eindhoven University of Technology, The Netherlands
Bekker R, Borst SC, Boxma OJ, Kella O (2004) Queues with workload-dependent arrival and service rates. Queueing Syst 46(3–4): 537–556
Burke PJ (1975) Delays in single-server queues with batch inputs. Oper Res 23(4): 830–833
Çinlar E (1975) Introduction to stochastic processes. Prentice-Hall, Englewood Cliffs
Chang SH, Choi DW, Kim TS (2004) Performance analysis of a finite-buffer bulk-arrival bulk-service queue with variable server capacity. Stoch Anal Appl 22(5): 1151–1173
Chaudry M, Templeton JGC (1983) A first course in bulk queues. Wiley, New York
Courtois PJ, Georges J (1971) On a single server finite queuing model with state-dependent arrival and service processes. Oper Res 19(2): 424–435
Deb RK (1978) Optimal dispatching of a finite capacity shuttle. Manag Sci 24(13): 1362–1372
Deb RK, Serfozo RF (1973) Optimal control of batch service queues. Adv Appl Probab 5(2): 340–361
Dshalalow JH (1997) Queueing systems with state dependent parameters. In: Dshalalow J (ed) Frontiers in queueing: models and applications in science and engineering. CRC Press, Boca Raton, pp 61–116
Dudin AN, Shaban AA, Klimenok VI (2005) Analysis of a queue in the BMAP/G/1/N system. Int J Simul Syst Sci Technol 6(1–2): 13–23
Fowler JW, Hogg GL, Phillips DT (1992) Control of multiproduct bulk service diffusion/oxidation processes. IIE Trans 24(4): 84–96
Germs R, Van Foreest ND (2010) Loss probabilities for the M X/G Y/1/K + B bulk queue. Probab Eng Inf Sci 24(4): 457–471
Gupta UC, Rao TSSS (1998) On the analysis of single server finite queue with state dependent arrival and service processes: M(n)/G(n)/1/K. OR Spectr 20(2): 83–89
Hochbaum DS, Landy D (1997) Scheduling semiconductor burn-in operations to minimize total flowtime. Oper Res 45(6): 874–885
Hodes B, Schoonhoven B, Swart R (1992) On line planning van ovens. Tech. rep., University of Twente, Enschede, The Netherlands
Hopp W, Spearman M (2008) Factory physics. McGraw-Hill, New York
MacGregor Smith J, Cruz FRB (2005) The buffer allocation problem for general finite buffer queueing networks. IIE Trans 37(4): 343–365
Medhi J (2003) Stochastic models in queueing theory. Academic Press, San Diego
Neuts MF (1977) Algorithmic methods in probability theory. North-Holland, Amsterdam
Nobel RD (1989) Practical approximations for finite-buffer queueing models with batch arrivals. Eur J Oper Res 38(1): 44–55
Schellhaas H (1983) Computation of the state dependent probabilities in M/G/1 queues with state dependent input and state dependent service. OR Spectr 5(4): 223–228
Takagi H (1993) Queueing analysis: finite systems. North-Holland, Amsterdam
Tijms HC, Van Hoorn MH (1981) Algorithms for the state probabilities and waiting times in single server queueing systems with random and quasirandom input and phase-type service times. OR Spectr 2(3): 145–152
Uzsoy R, Lee CY, Martin-Vega LA (1994) A review of production planning and scheduling models in the semiconductor industry, part ii: shop-floor control. IIE Trans 26(5): 44–55
Van der Zee DJ, Van Harten A, Schuur P (2001) On-line scheduling of multi-server batch operations. IIE Trans 33(7): 569–586
Weiss HJ (1979) The computation of optimal control limits for a queue with batch services. Manag Sci 25(4): 320–328
Acknowledgments
The authors like to thank J. Riezebos and J. Slomp for helpful discussions, and the (anonymous) referees for providing valuable suggestions to improve the paper.
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Germs, R., van Foreest, N. Analysis of finite-buffer state-dependent bulk queues. OR Spectrum 35, 563–583 (2013). https://doi.org/10.1007/s00291-012-0282-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-012-0282-7