Editing Queueing theory (section)

== Single queueing nodes ==

A ''queue'' or ''queueing node'' can be thought of as nearly a [[black box]]. ''Jobs'' (also called ''customers'' or ''requests'', depending on the field) arrive to the queue, possibly wait some time, take some time being processed, and then depart from the queue.

[[File:Black box queue diagram.png|thumb|350px|center|A black box. Jobs arrive to, and depart from, the queue.]]

However, the queueing node is not quite a pure black box since some information is needed about the inside of the queueing node. The queue has one or more ''servers'' which can each be paired with an arriving job. When the job is completed and departs, that server will again be free to be paired with another arriving job.

[[File:Queueing node service digram.png|thumb|500px|center|A queueing node with 3 servers. Server '''a''' is idle, and thus an arrival is given to it to process. Server '''b''' is currently busy and will take some time before it can complete service of its job. Server '''c''' has just completed service of a job and thus will be next to receive an arriving job.]]

An analogy often used is that of the cashier at a supermarket. Customers arrive, are processed by the cashier, and depart. Each cashier processes one customer at a time, and hence this is a queueing node with only one server. A setting where a customer will leave immediately if the cashier is busy when the customer arrives, is referred to as a queue with no ''buffer'' (or no ''waiting area''). A setting with a waiting zone for up to ''n'' customers is called a queue with a buffer of size ''n''.

=== Birth-death process ===
{{See also|Survival analysis}}
The behaviour of a single queue (also called a ''queueing node'') can be described by a [[birth–death process]], which describes the arrivals and departures from the queue, along with the number of jobs currently in the system. If ''k'' denotes the number of jobs in the system (either being serviced or waiting if the queue has a buffer of waiting jobs), then an arrival increases ''k'' by 1 and a departure decreases ''k'' by 1.

The system transitions between values of ''k'' by "births" and "deaths", which occur at the arrival rates <math>\lambda_i</math> and the departure rates <math>\mu_i</math> for each job <math>i</math>. For a queue, these rates are generally considered not to vary with the number of jobs in the queue, so a single [[average]] rate of arrivals/departures per unit time is assumed. Under this assumption, this process has an arrival rate of <math>\lambda = \text{avg}(\lambda_1,\lambda_2,\dots,\lambda_k)</math> and a departure rate of <math>\mu = \text{avg}(\mu_1, \mu_2, \dots, \mu_k)</math>.

[[File:BD-proces.png|thumb|center|643x643px|A birth–death process. The values in the circles represent the state of the system, which evolves based on arrival rates ''λ<sub>i</sub>'' and departure rates ''μ<sub>i</sub>''.]]

[[File:Mm1_queue.svg|thumb|center|250px|A queue with 1 server, arrival rate ''λ'' and departure rate ''μ'']]

==== Balance equations ====

The [[steady state]] equations for the birth-and-death process, known as the [[balance equation]]s, are as follows. Here <math>P_n</math> denotes the steady state probability to be in state ''n''.

: <math>\mu_1 P_1 = \lambda_0 P_0</math>
: <math>\lambda_0 P_0 + \mu_2 P_2 = (\lambda_1 + \mu_1) P_1</math>
: <math>\lambda_{n-1} P_{n-1} + \mu_{n+1} P_{n+1} = (\lambda_n + \mu_n) P_n</math>

The first two equations imply
: <math>P_1 = \frac{\lambda_0}{\mu_1} P_0</math>
and
: <math>P_2 = \frac{\lambda_1}{\mu_2} P_1 + \frac{1}{\mu_2} (\mu_1 P_1 - \lambda_0 P_0) = \frac{\lambda_1}{\mu_2} P_1 = \frac{\lambda_1 \lambda_0}{\mu_2 \mu_1} P_0</math>.

By mathematical induction,
: <math>P_n = \frac{\lambda_{n-1} \lambda_{n-2} \cdots \lambda_0}{\mu_n \mu_{n-1} \cdots \mu_1} P_0 = P_0 \prod_{i = 0}^{n-1} \frac{\lambda_i}{\mu_{i+1}}</math>.

The condition <math>\sum_{n = 0}^{\infty} P_n = P_0 + P_0 \sum_{n=1}^\infty \prod_{i=0}^{n-1} \frac{\lambda_i}{\mu_{i+1}} = 1</math> leads to
: <math>P_0 = \frac{1}{1 + \sum_{n=1}^{\infty}\prod_{i=0}^{n-1} \frac{\lambda_i}{\mu_{i+1}} }</math>
which, together with the equation for <math>P_n</math> <math>(n\geq1)</math>, fully describes the required steady state probabilities.

=== Kendall's notation ===
{{Main|Kendall's notation}}
Single queueing nodes are usually described using Kendall's notation in the form A/S/''c'' where ''A'' describes the distribution of durations between each arrival to the queue, ''S'' the distribution of service times for jobs, and ''c'' the number of servers at the node.<ref name="tijms">Tijms, H.C, ''Algorithmic Analysis of Queues'', Chapter 9 in  A First Course in Stochastic Models, Wiley, Chichester, 2003</ref><ref>{{Cite journal | last1 = Kendall | first1 = D. G. | author-link1 = David George Kendall| title = Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain | doi = 10.1214/aoms/1177728975 | jstor = 2236285| journal = The Annals of Mathematical Statistics | volume = 24 | issue = 3 | pages = 338–354 | year = 1953| doi-access = free }}</ref> For an example of the notation, the [[M/M/1 queue]] is a simple model where a single server serves jobs that arrive according to a [[Poisson process]] (where inter-arrival durations are [[exponentially distributed]]) and have exponentially distributed service times (the M denotes a [[Markov process]]). In an [[M/G/1 queue]], the G stands for "general" and indicates an arbitrary [[probability distribution]] for service times.

=== Example analysis of an M/M/1 queue ===

Consider a queue with one server and the following characteristics:
* ''<math>\lambda</math>'': the arrival rate (the reciprocal of the expected time between each customer arriving, e.g. 10 customers per second)
* ''<math>\mu</math>'': the reciprocal of the mean service time (the expected number of consecutive service completions per the same unit time, e.g. per 30 seconds)
* ''n'': the parameter characterizing the number of customers in the system
* <math>P_n</math>: the probability of there being ''n'' customers in the system in steady state

Further, let <math>E_n</math> represent the number of times the system enters state ''n'', and <math>L_n</math> represent the number of times the system leaves state ''n''. Then <math>\left\vert E_n - L_n \right\vert \in \{0, 1\}</math> for all ''n''. That is, the number of times the system leaves a state differs by at most 1 from the number of times it enters that state, since it will either return into that state at some time in the future (<math>E_n = L_n</math>) or not (<math>\left\vert E_n - L_n \right\vert = 1</math>).

When the system arrives at a steady state, the arrival rate should be equal to the departure rate.

Thus the balance equations
: <math>\mu P_1 = \lambda P_0</math>
: <math>\lambda P_0 + \mu P_2 = (\lambda + \mu) P_1</math>
: <math>\lambda P_{n-1} + \mu P_{n+1} = (\lambda + \mu) P_n</math>
imply
: <math>P_n = \frac{\lambda}{\mu} P_{n-1},\ n=1,2,\ldots</math>
The fact that <math>P_0 + P_1 + \cdots = 1</math> leads to the [[geometric distribution]] formula
: <math>P_n = (1 - \rho) \rho^n</math>
where <math>\rho = \frac{\lambda}{\mu} < 1</math>.

=== Simple two-equation queue ===

A common basic queueing system is attributed to [[Agner Krarup Erlang|Erlang]] and is a modification of [[Little's Law]]. Given an arrival rate ''λ'', a dropout rate ''σ'', and a departure rate ''μ'', length of the queue ''L'' is defined as:

: <math>L = \frac{\lambda - \sigma}{\mu}</math>.

Assuming an exponential distribution for the rates, the waiting time ''W'' can be defined as the proportion of arrivals that are served. This is equal to the exponential survival rate of those who do not drop out over the waiting period, giving:

: <math>\frac{\mu}{\lambda} = e^{-W{\mu}}</math>

The second equation is commonly rewritten as:

: <math>W = \frac{1}{\mu} \mathrm{ln}\frac{\lambda}{\mu}</math>

The two-stage one-box model is common in [[epidemiology]].<ref>{{Cite journal|last=Hernández-Suarez|first=Carlos|date=2010|title=An application of queuing theory to SIS and SEIS epidemic models|journal=Math. Biosci.|volume=7|issue=4|pages=809–823|doi=10.3934/mbe.2010.7.809|pmid=21077709|doi-access=free}}</ref>