-
Queueing theory studies waiting lines or queues under the assumption of known queue lengths and waiting time distribution
-
A Queue consists of jobs that arrive to the queue, possibly wait some time, take some time to be processed, and then depart from the queue.
- The queue may consist of servers that take an arriving job, process it, and when the job departs, is free to take new jobs.
-
Single queueing nodes are described using Kendall’s Notation of the form
where describes the distribution of durations between each arrival to the queue describes the service times for jobs describes the servers at the node. (optional) describes the capacity of the queue (optional) describes the size of the population of the jobs to be served (optional) describes the queueing discipline.
Fundamental Relations
-
We denote the average arrival rate as
and the average service rate as -
The average service time is denoted
-
The Utilization
is given by -
The expected total wait time is the sum of the average service time and the average wait time in the queue
-
Little’s Law states that the long term average number
of jobs (i.e., WIP) in a stationary system is equal to the long term average effective arrival rate (i.e., throughput) times the average time a customer spends in a system (i.e., cycle time) -
When the queue has infinite capacity,
because what goes in must come out -
When the queue has finite capacity,
instead denotes the rate of potential arrivals as if the system were not full. In a similar vein, is the utilization assuming no arrivals were turned away.
Queueing Systems
M/M/1
-
Both arrival and service rates are characterized with an exponential distribution resulting in the Markov property. These can be modelled with a Poisson process with means
and respectively. -
The state of the system is characterized with the number of jobs in queue, denoted
. -
The dynamics of the system is governed by the following recurrence relation of differential equations
-
In the long term , we observe that given
-
Intuitively, this means that if the number of arrivals is less than the number of departures on average, the probabilities
will converge. This only happens when
. -
The number of customers in the system follows a geometric distribution with parameter
. -
The average number of jobs is
-
Using Little’s law, the average response time is given by
-
Using Little’s law, the average time spent waiting is given by
-
The number of jobs in the queue is given by
-
M/G/1
-
The long run average probability that the server is busy is the utilization
. -
The average number of jobs in service as seen by a randomly arriving job is also given by the utilization
. -
The average remaining process time of a job in service as seen by a randomly arriving job is approximated by
G/G/1
-
Here we consider the general case of arrival and service time distributions.
-
We can approximate the mean waiting time using the Kingman Approximation.
Denote
- the coefficient of variation for arrivals - the coefficient of variation for service times This is also known as the VUT formula. Respectively, the terms are the utilization, variability and service time.
-
If we denote
as the wait time of an M/M/1 queue, and for the G/G/1 queue, we observe that the Kingman approximation can be written as -
When variability
, the queue time is greater than the M/M/1 queue. Conversely, when variability , the queue time is smaller than the M/M/1 queue -
The expected number of jobs in the system is given by the following approximation
M/M/c
-
An extension of M/M/1 except we allow for
servers. -
The expected wait time for this queue is given by the following
G/G/c
-
In a similar vein to the Kingman approximation, we have the following approximation from Whitt.
In closed form this becomes
M/M/1/b
-
A variation of the M/M/1 queue except the only valid states are
. -
The dynamics of the system is governed by the following recurrence relation of differential equations
-
In the long term , we observe that given
-
We observe the following values for throughput
Similarly for the number of jobs in total we have
G/G/1/b
-
The general idea for utilization
is to use the utilization in the non-blocking case (see G/G/1) , say and correct it to obtain . -
For
, we correct the utilization using The throughput is then obtained via substitution of
-
For
, we can compute by reversing the line which is approximately the same as the original. Using the Kingman equation with as the utilization. The corrected utilization for the reversed line is also given by
Throughput is then found using substitution of the above
-
For
, we use the approximation by Buzacott and Shanthikumar -
The values of
and for this line can be bound as follows. -
For small buffers,
will be close to but less than the maximum buffer in the system For large buffers,
approaches the same bound for the G/G/1 queue, so -
Similarly, from Little’s law,
is bound as follows
-