4 minutes

# Queueing Notation

Queueing theory has some commonly accepted shorthand to describe characteristics of queuing models. Although across books and peer reviewed articles you will see slight variations, this post outlines commonly accepted terms for reference.

# Kendall’s Notation

Kendall’s notation was proposed as a standard for describing queueing models.
You may see some queueing models that omit the last two elements. The *Y* and
*Z* typically default to infinite and FCFS. The table below illustrates the
standard:

`$$A/B/X/Y/Z$$`

Notation | Description | Characteristic |
---|---|---|

A | Interarrival Distribution | Markovian, Deterministic, General |

B | Service Time Distribution | Markovian, Deterministic, General |

X | Parallel Servers | positive integer, infinity |

Y | Max Queue Size | non-negative integer, infinity |

Z | Queue Discipline | FCFS, LCFS, Random, Priority, General Discipline |

## Interarrival Distribution

The rate at which entities arrive to a queueing system to be processed. E.g. customers arrive every 5 minutes or 12 customers arriver per hour.

## Service Time Distribution

The rate at which entities are processed by a server in a queueing system. E.g. Customers are serviced in 5 minutes or 12 customers are serviced per hour.

### Distribution Classifications

#### Markovian Distributions

Markovian distributions, though few meet this classification, are
a very important in many queueing models and theory. They have one important
property that is memorylessness.
For distributions that are memoryless, the current sample from the distribution is
not dependent on the prior sample. In queueing context, an entity’s current
processing time is independent on how much longer it will take to process. Markovian distributions are the
exponential,
geometric, and
poisson.
The exponential and poisson are the most commonly used and are closely
related. The shorthand
notation is *M*.

```
library(ggplot2)
library(trstyles)
x <- data.frame(x = 0:5)
rate <- 1:5
rateGroups <- factor(1:5)
e <- ggplot(x, aes(x = x)) +
labs(y = 'density', title = 'Exponential PDF') +
theme_tr()
for (i in 1:5) {
e <- e +
stat_function(fun = dexp,
aes_(color = rateGroups[i]),
args = list(rate = rate[i]),
size = 1)
}
e +
scale_color_tr(name = "Rate",
breaks = rateGroups)
```

#### Deterministic Distributions

Deterministic means that the rate is always the same. It is a constant. The shorthand notation is *D*.

#### General Distributions

General probability distributions refer to when you make no assumptions
on the shape and form. It can be any probability distribution. The shorthand
notation is *G*. Below are some common distributions:

```
library(fitur)
library(actuar)
set.seed(438)
x <- rweibull(10000, shape = 5, scale = 1)
dists <- c('gamma', 'lnorm', 'weibull', 'gamma', 'llogis')
fits <- lapply(dists, fit_univariate, x = x)
plot_density(x, fits, nbins = 30) +
scale_color_tr(name = 'Distribution') +
theme_tr()
```

## Parallel Servers

The number of workers, servers, machines, etc. available to process entities. An infinite server queue will have no waiting times since there is always server capacity. Values include:

`$$1,\:2,\:...,\:\infty$$`

## Maximum Queue Size

The number of entities that are allowed to wait in the queue when all servers are busy. Entities that arrive when the queue is full leave the queueing system. Values include:

`$$0,\:1,\:...,\:\infty$$`

## Queue Discipline

The queue discipline refers to how entities are assigned to servers.

- First Come First Serve (FCFS)
- Entities are prioritized by earliest arrival time
- Customers waiting to checkout at a grocery store

- Last Come First Serve (LCFS)
- Entities are prioritized by latest arrival time
- A worker answering emails from the top of the inbox

- Random
- All entities have equal probability of being selected
- Customers waiting to be served at a bar

- Priority
- Entities have some characteristics that would prioritize them over other entities even if the other entities have been waiting longer.
- Patients in an emergency department with assigned acuity

# Mathematical Queueing Notation

$$\rho $$

`$$\mu$$`

`$$\lambda$$`

`$$c$$`

`$$W$$`

`$$W_q$$`

`$$L$$`

`$$L_q$$`

`$$L = \lambda W, L_q = \lambda W_q$$`

`$$p_0$$`

`$$p_n$$`

`$$r$$`