Bulk queue

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In queueing theory, a discipline within the mathematical theory of probability, a bulk queue[1] (sometimes batch queue[2]) is a general queueing model where jobs arrive in and/or are served in groups of random size.[3]:vii Batch arrivals have been used to describe large deliveries[4] and batch services to model a hospital out-patient department holding a clinic once a week,[5] a transport link with fixed capacity[6][7] and an elevator.[8]

Networks of such queues are known to have a product form stationary distribution under certain conditions.[9] Under heavy traffic conditions a bulk queue is known to behave like a reflected Brownian motion.[10][11]

Kendall's notation[edit]

In Kendall's notation for single queueing nodes, the random variable denoting bulk arrivals or service is denoted with a superscript, for example MX/MY/1 denotes an M/M/1 queue where the arrivals are in batches determined by the random variable X and the services in bulk determined by the random variable Y. In a similar way, the GI/G/1 queue is extended to GIX/GY/1.[1]

Bulk service[edit]

Customers arrive at random instants according to a Poisson process and form a single queue, from the front of which batches of customers (typically with a fixed maximum size[12]) are served at a rate with independent distribution.[5] The equilibrium distribution, mean and variance of queue length are known for this model.[5]

The optimal maximum size of batch, subject to operating cost contraints, can be modelled as a Markov decision process.[13]

Bulk arrival[edit]

Optimal service-provision procedures to minimize long run expected cost have been published.[4]

References[edit]

  1. ^ a b Chiamsiri, Singha; Leonard, Michael S. (1981). "A Diffusion Approximation for Bulk Queues". Management Science 27 (10): 1188–1199. JSTOR 2631086.  edit
  2. ^ Özden, Eda. Discrete Time Analysis of Consolidated Transport Processes. KIT Scientific Publishing. p. 14. ISBN 3866448015. 
  3. ^ Chaudhry, M. L.; Templeton, James G. C. (1983). A first course in bulk queues. Wiley. ISBN 0471862606. 
  4. ^ a b Berg, Menachem; van der Duyn Schouten, Frank; Jansen, Jorg (1998). "Optimal Batch Provisioning to Customers Subject to a Delay-Limit". Management Science 44 (5): 684–697. JSTOR 2634473.  edit
  5. ^ a b c Bailey, Norman T. J. (1954). "On Queueing Processes with Bulk Service". Journal of the Royal Statistical Society, Series B 61 (1): 80–87. JSTOR 2984011. 
  6. ^ Deb, Rajat K. (1978). "Optimal Dispatching of a Finite Capacity Shuttle". Management Science 24 (13): 1362–1372. JSTOR 2630642.  edit
  7. ^ Glazer, A.; Hassin, R. (1987). "Equilibrium Arrivals in Queues with Bulk Service at Scheduled Times". Transportation Science 21 (4): 273–278. doi:10.1287/trsc.21.4.273. JSTOR 25768286.  edit
  8. ^ Marcel F. Neuts (1967). "A General Class of Bulk Queues with Poisson Input". The Annals of Mathematical Statistics 38 (3): 759–770. doi:10.1214/aoms/1177698869. JSTOR 2238992.  edit
  9. ^ Henderson, W.; Taylor, P. G. (1990). "Product form in networks of queues with batch arrivals and batch services". Queueing Systems 6: 71. doi:10.1007/BF02411466.  edit
  10. ^ Iglehart, Donald L.; Ward, Whitt (1970). "Multiple Channel Queues in Heavy Traffic. II: Sequences, Networks, and Batches". Advances in Applied Probability (Applied Probability Trust) 2 (2): 355–369. JSTOR 1426324. Retrieved 30 Nov 2012.  edit
  11. ^ Harrison, P. G.; Hayden, R. A.; Knottenbelt, W. (2013). "Product-forms in batch networks: Approximation and asymptotics". Performance Evaluation 70 (10): 822. doi:10.1016/j.peva.2013.08.011.  edit
  12. ^ Downton, F. (1955). "Waiting Time in Bulk Service Queues". Journal of the Royal Statistical Society, Series B (Royal Statistical Society) 17 (2): 256–261. JSTOR 2983959.  edit
  13. ^ Deb, Rajat K.; Serfozo, Richard F. (1973). "Optimal Control of Batch Service Queues". Advances in Applied Probability 5 (2): 340–361. JSTOR 1426040.  edit