Bulk queue

Last updated

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]

Contents

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

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

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 constraints, can be modelled as a Markov decision process. [13]

Bulk arrival

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

Waiting Time Distribution

The waiting time distribution of bulk Poisson arrival is presented in. [14]

Related Research Articles

Queueing theory Mathematical study of waiting lines, or queues

Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service.

In queueing theory, a discipline within the mathematical theory of probability, Little's result, theorem, lemma, law, or formula is a theorem by John Little which states that the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system. Expressed algebraically the law is

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has a product-form solution. It was the first significant development in the theory of networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research, including ideas used in the development of the Internet. The networks were first identified by James R. Jackson and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’

In queueing theory, a discipline within the mathematical theory of probability, a G-network is an open network of G-queues first introduced by Erol Gelenbe as a model for queueing systems with specific control functions, such as traffic re-routing or traffic destruction, as well as a model for neural networks. A G-queue is a network of queues with several types of novel and useful customers:

In actuarial science and applied probability ruin theory uses mathematical models to describe an insurer's vulnerability to insolvency/ruin. In such models key quantities of interest are the probability of ruin, distribution of surplus immediately prior to ruin and deficit at time of ruin.

In queueing theory, a discipline within the mathematical theory of probability, Burke's theorem is a theorem asserting that, for the M/M/1 queue, M/M/c queue or M/M/∞ queue in the steady state with arrivals a Poisson process with rate parameter λ:

  1. The departure process is a Poisson process with rate parameter λ.
  2. At time t the number of customers in the queue is independent of the departure process prior to time t.

In probability theory, a product-form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a product of the metric across the different components. Using capital Pi notation a product-form solution has algebraic form

In queueing theory, a discipline within the mathematical theory of probability, the arrival theorem states that "upon arrival at a station, a job observes the system as if in steady state at an arbitrary instant for the system without that job."

In queueing theory, a discipline within the mathematical theory of probability, quasireversibility is a property of some queues. The concept was first identified by Richard R. Muntz and further developed by Frank Kelly. Quasireversibility differs from reversibility in that a stronger condition is imposed on arrival rates and a weaker condition is applied on probability fluxes. For example, an M/M/1 queue with state-dependent arrival rates and state-dependent service times is reversible, but not quasireversible.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are c servers and job service times are exponentially distributed. It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian, service times have a General distribution and there is a single server. The model name is written in Kendall's notation, and is an extension of the M/M/1 queue, where service times must be exponentially distributed. The classic application of the M/G/1 queue is to model performance of a fixed head hard disk.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/k queue is a queue model where arrivals are Markovian, service times have a General distribution and there are k servers. The model name is written in Kendall's notation, and is an extension of the M/M/c queue, where service times must be exponentially distributed and of the M/G/1 queue with a single server. Most performance metrics for this queueing system are not known and remain an open problem.

In queueing theory, a discipline within the mathematical theory of probability, a heavy traffic approximation is the matching of a queueing model with a diffusion process under some limiting conditions on the model's parameters. The first such result was published by John Kingman who showed that when the utilisation parameter of an M/M/1 queue is near 1 a scaled version of the queue length process can be accurately approximated by a reflected Brownian motion.

Design of robust and reliable networks and network services relies on an understanding of the traffic characteristics of the network. Throughout history, different models of network traffic have been developed and used for evaluating existing and proposed networks and services.

In queueing theory, a discipline within the mathematical theory of probability, Ross's conjecture gives a lower bound for the average waiting-time experienced by a customer when arrivals to the queue do not follow the simplest model for random arrivals. It was proposed by Sheldon M. Ross in 1978 and proved in 1981 by Tomasz Rolski. Equality can be obtained in the bound; and the bound does not hold for finite buffer queues.

In queueing theory, a discipline within the mathematical theory of probability, a D/M/1 queue represents the queue length in a system having a single server, where arrivals occur at fixed regular intervals and job service requirements are random with an exponential distribution. The model name is written in Kendall's notation. Agner Krarup Erlang first published a solution to the stationary distribution of a D/M/1 and D/M/k queue, the model with k servers, in 1917 and 1920.

In probability theory, the Markov–Krein theorem gives the best upper and lower bounds on the expected values of certain functions of a random variable where only the first moments of the random variable are known. The result is named after Andrey Markov and Mark Krein.

The Borel distribution is a discrete probability distribution, arising in contexts including branching processes and queueing theory. It is named after the French mathematician Émile Borel.

Polling system

In queueing theory, a discipline within the mathematical theory of probability, a polling system or polling model is a system where a single server visits a set of queues in some order. The model has applications in computer networks and telecommunications, manufacturing and road traffic management. The term polling system was coined at least as early as 1968 and the earliest study of such a system in 1957 where a single repairman servicing machines in the British cotton industry was modelled.

Stochastic scheduling concerns scheduling problems involving random attributes, such as random processing times, random due dates, random weights, and stochastic machine breakdowns. Major applications arise in manufacturing systems, computer systems, communication systems, logistics and transportation, machine learning, etc.

References

  1. 1 2 Chiamsiri, Singha; Leonard, Michael S. (1981). "A Diffusion Approximation for Bulk Queues". Management Science . 27 (10): 1188–1199. doi:10.1287/mnsc.27.10.1188. JSTOR   2631086.
  2. ↑ Özden, Eda (2012). Discrete Time Analysis of Consolidated Transport Processes. KIT Scientific Publishing. p. 14. ISBN   978-3866448018.
  3. ↑ Chaudhry, M. L.; Templeton, James G. C. (1983). A first course in bulk queues. Wiley. ISBN   978-0471862604.
  4. 1 2 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. doi:10.1287/mnsc.44.5.684. JSTOR   2634473.
  5. 1 2 3 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. doi:10.1287/mnsc.24.13.1362. JSTOR   2630642.
  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.
  8. ↑ Marcel F. Neuts (1967). "A General Class of Bulk Queues with Poisson Input" (PDF). The Annals of Mathematical Statistics. 38 (3): 759–770. doi:10.1214/aoms/1177698869. JSTOR   2238992.
  9. ↑ Henderson, W.; Taylor, P. G. (1990). "Product form in networks of queues with batch arrivals and batch services". Queueing Systems . 6: 71–87. doi:10.1007/BF02411466.
  10. ↑ Iglehart, Donald L.; Ward, Whitt (1970). "Multiple Channel Queues in Heavy Traffic. II: Sequences, Networks, and Batches" (PDF). Advances in Applied Probability. 2 (2): 355–369. doi:10.1017/s0001867800037435. JSTOR   1426324 . Retrieved 30 Nov 2012.
  11. ↑ Harrison, P. G.; Hayden, R. A.; Knottenbelt, W. (2013). "Product-forms in batch networks: Approximation and asymptotics" (PDF). Performance Evaluation . 70 (10): 822. CiteSeerX   10.1.1.352.5769 . doi:10.1016/j.peva.2013.08.011. Archived from the original (PDF) on 2016-03-03. Retrieved 2015-09-04.
  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.
  13. ↑ Deb, Rajat K.; Serfozo, Richard F. (1973). "Optimal Control of Batch Service Queues". Advances in Applied Probability. 5 (2): 340–361. doi:10.2307/1426040. JSTOR   1426040.
  14. ↑ Medhi, Jyotiprasad (1975). "Waiting Time Distribution in a Poisson Queue with a General Bulk Service Rule". Management Science. 21 (7): 777–782. doi:10.1287/mnsc.21.7.777. JSTOR   2629773.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.