Site icon R-bloggers

Queueing Notation

[This article was first published on R on Thomas Roh, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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 \]
Utilization
\[\mu\]
Service Rate

\[\lambda\]

Arrival Rate
\[c\]
number of parallel servers

\[W\]

Waiting time in system
\[W_q\]
Waiting time in queue

\[L\]

Entities in system

\[L_q\]

Entities in queue
\[L = \lambda W, L_q = \lambda W_q\]

Little’s Law

\[p_0\]
Probably of zero servers being busy
\[p_n\]
Probability of n servers being busy
\[r\]
Offered Load

To leave a comment for the author, please follow the link and comment on their blog: R on Thomas Roh.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.