Overview
In general, customers arrive at one or more servers and wait in a queue until they get served. We assume that for any server at most one customer is being served. The number of customers in the system = the number of customers (if any) waiting in the queue plus the number of customers (if any) being served (in any of the servers). Customers are serviced in the order in which they arrive (FIFO = first in, first out).
Figure 1 – Queueing model with one server
Assumptions
We will assume that the arrivals follow an exponential distribution, i.e. they adhere to a Poisson process. That the arrivals follow a Poisson process is a reasonable reflection of reality. Whether or not the same is true for servicing depends on the situation. The assumption is reasonable if the server provides a range of services that take different times to deliver. The assumption is not reasonable, for example, if the server(s) tends to perform the same service for all customers and the time to deliver is similar.
Unless stated otherwise, we will assume that the queue can hold as many customers as necessary (infinite queue).
Notation
We will use the following notation:
λ = mean arrival rate = reciprocal of the mean inter-arrival time
μ = mean service rate = reciprocal of the service time
s = # of servers
ρ = λ/(sμ) = utilization = probability that at least one server is busy (i.e. the proportion of the time that some server is busy); thus, it follows that 1 – ρ = the proportion of the time that all the servers are idle.
τ = λ/μ: equals ρ in the single server case where s = 1
l = random variable = # of customers in the system
lq = random variable = # if customers in the queue
L = mean number of customers in the system = E[l]
Lq = mean number of customers in the queue = E[lq]
w = random variable = time in the system
wq = random variable = time in the queue
W = mean waiting time in the system = E[w]
Wq = mean waiting time in the queue = E[wq]
pn = probability that there are n customers in the system = P(l = n)
Pn = probability that there are at least n customers in the system = P(l ≥ n)
Properties
Property 1
Note that, although these are sums of an infinite number of elements, both sums converge to a real number.
Property 2 (Little’s Law)
Property 3
Steady-state
Based on certain assumptions, it turns out that a queueing model enters into a steady state. This means that what happens next only depends on the current state and not on past states. E.g. in a queueing model with exponential arrivals and exponential servicing by one service (i.e. an M/M/1 model), a steady state is reached provided λ < μ (i.e. ρ < 1).
The values of L, Lq, W, Wq, pn, Pn, etc. described above are based on the steady-state.
Queueing Models
Click on any of the following to learn more about each of the supported queueing models
- M/M/1 queue: exponential arrivals and service time, 1 server
- M/M/s queue: exponential arrivals and service time, multiple servers
- M/M/1/K queue: M/M/1 with a finite queue of size K
- M/M/s/K queue: M/M/s with a finite queue of size K
- M/M/1/N queue: M/M/1 with a finite # of customers equal to N
- M/M/s/N queue: M/M/s with a finite # of customers equal to N
- M/M/1 with non-preemptive priority queueing
- M/M/s with non-preemptive priority queueing
- M/M/1 with non-preemptive priority queueing with variable service means
- M/M/1 with preemptive priority queueing
- M/M/s with preemptive priority queueing
- M/D/1 queue: exponential arrivals, constant (deterministic) service time, 1 server
- M/G/1 queue: exponential arrivals, general service time, 1 server
- M/G/∞ queue: exponential arrivals, general service time, infinite # of servers
- Single-server queueing simulation
- Event-driven simulation
- Multi-server queueing simulation
References
Ross, S. M. (2014) Introduction to probability models, 11th Ed. Academic Press
https://ebin.pub/introduction-to-probability-models-11nbsped-0124079482-9780124079489.html
Leong, T-Y. (2007) Simpler spreadsheet simulation of multi-server queues. INFORMS Transactions on Education 7(2):172-177.
https://ink.library.smu.edu.sg/sis_research/215/
Sztrik, J. (2021) Basic queueing theory
https://irh.inf.unideb.hu/~jsztrik/education/16/SOR_Main_Angol.pdf
Shores, T. S. (2017) Queueing theory basics and models
No longer available online