Queueing Theory Essentials: Models, Kendall Notation, and Key Metrics

1 Queueing Theory Models

Queueing theory describes the phenomenon where people, objects, or information must wait for a service.

Physical queues, such as waiting to buy tickets or cars waiting at a gas station.

Virtual queues, such as telephone call signals waiting for a switch or computer jobs waiting for processing.

For convenience, we refer to all entities that wait as customers and all entities that provide service as servers .

Queueing theory studies the stochastic behavior of queueing systems under different conditions of arrival and service time randomness, aiming to build mathematical models that support optimal design and operation decisions.

2 Mathematical Model of a Queueing System

Every queueing system consists of three basic components: the input process, the queue discipline, and the service discipline.

2.1 Input Process

The input process describes the source of customers and the pattern of their arrivals. It is typically characterized by:

Whether the number of potential customers is finite or infinite.

Whether arrivals occur singly or in batches.

Whether arrivals are independent (the arrival of one customer does not affect others) or correlated.

Whether the inter‑arrival time distribution is deterministic or random.

Whether the process is stationary (distribution parameters do not change over time) or non‑stationary.

In the following discussion we assume arrivals are independent and the input process is stationary.

2.2 Service Facility and Service Rules

The service facility is described by the number of service stations, their arrangement, and the mode of service:

Number of service stations : there may be one or many.

Configuration : single‑queue‑single‑server, single‑queue‑multiple‑servers, multiple‑queues‑multiple‑servers, series of servers, or hybrid forms.

Service mode : serving customers individually or in batches; this article considers only individual service.

Service time : like the input process, service time can be deterministic or random; when random, its distribution (often exponential) must be known.

At least one of the inter‑arrival time or service time is assumed to be random.

We denote the number of servers by c . When c = 1 the system is a single‑server queue; otherwise it is a multi‑server queue.

The service time for a customer is a random variable with a known probability distribution, commonly the exponential distribution.

2.3 Queue and Service Discipline

Queueing rules are generally classified as waiting, loss, or mixed disciplines.

Waiting discipline : a customer joins the queue if all servers are busy. Service is then provided according to one of the following rules: First‑Come‑First‑Served (FCFS) Last‑Come‑First‑Served (FCLS) Random Service (SIRO) Priority Service (PR)

Loss discipline (also called immediate or balking): a customer leaves the system immediately when all servers are occupied and never returns.

Mixed discipline : a combination of waiting and loss, typically limiting the queue length or waiting time. The three common variants are: Finite queue capacity. Maximum waiting time; customers abandon the system after this time. Maximum total time in system (waiting time plus service time).

3 Symbolic Representation of Queueing Models: Kendall Notation

The general Kendall notation is expressed as A / S / c / K / N / D , where:

A : distribution type of inter‑arrival times.

S : distribution type of service times.

c : number of servers.

K : system capacity.

N : number of sources (potential customers).

D : service discipline (e.g., FCFS, FCLS).

For example, M/M/1/∞/∞/FCFS denotes a system with exponential inter‑arrival and service times, a single server, unlimited capacity, unlimited sources, and first‑come‑first‑served discipline.

Often the last three components are omitted, yielding the three‑parameter notation A/S/c . For instance, M/M/2 represents a system with exponential arrivals and services and two servers.

4 Main Performance Indicators of Queueing Systems

Studying queueing problems aims to evaluate system efficiency, service quality, and to determine optimal parameters. Key performance metrics include:

Number of customers in system (L) : the expected total number of customers (both waiting and being served). The expected number of waiting customers is denoted L_q . Larger values indicate lower service efficiency.

Busy period : the continuous time during which a server remains occupied, from the arrival of a customer to the moment the server becomes idle again. It reflects server workload; the complementary idle period represents the time a server stays free.

Server utilization (the proportion of time servers are busy) and customer loss rate (the proportion of customers who never receive service) are also important indicators.

Reference

ThomsonRen GitHub: https://github.com/ThomsonRen/mathmodels