Queueing Notation
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 \]\[\lambda\]
\[W\]
\[L\]
\[L_q\]
Little’s Law
\[p_0\]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.