Queuing theory 1
Inhaltsverzeichnis
Introduction
Queuing theory is the mathematical analysis of waiting systems. Queues occur eg. in manufacturing systems, in supermarkets or in traffic systems. In addition to the analysis of these processes, it is the task of queuing theory to provide a best possible balance between processing and waiting costs.
Representation of a waiting system
A waiting system generally consists of a processing area, where incoming orders are handled, and a waiting area, where incoming orders are waiting if no service unit is available.
Following Kendall's notation, five parameters are defined :
A / B / s: (d, e)
with
A: arrival process
B: service time distribution
s: number of servers (or service channels)
d: number of places in the system (capacity of the system)
s: the queues disciplinee (e.g. random selection or First-In-First-Out)
The arrival process and the service time distribution are simulated by using probability laws.
Example
In the following, the basic model M/M/1: (∞, FIFO) will be analyzed.
M = Markov; the arrival processes are considered to be random and independent of each other. Depending on the perspective (time-/event-related), they are simulated by the poisson/exponential distribution. There is one server, and there is no restriction on the size of the queue. Serving follows the First-in-first-out principle. These parameters will be determined below:
It is considered a fixed time interval T.
λ = the average number of arrivals in T
μ = the average number of persons served in T
We are interested in the average queue length, and the average service time per person.
The starting point is a very small time range Δt in which only one person can arrive or can be served.
The probability (P) that there is no person in the queue is equal to the probability that no person is in the queue and within Δt no new person will arrive, plus the probability that a person is in the queue and will be served, but no new person will arrive.
P0 = P0 (1-λΔt) + P1 (1-λΔt) μΔt
P0 = P0 (1-λΔt) + P1μΔt - P1λΔtμΔt
P0 = P0 (1-λΔt) + P1μΔt (Δt² is insignificant)
With that, we get the probability that one person is in the system
P1 = (λ / μ) P0
This formula can be generalized to:
The sum of all probabilities is equal to 1
So we obtain: P0 = 1 - (λ / μ)
The average length of the queue (expected value) is equal to the probability that a queue with length i occurs, multiplied by i, and summed up over all i (Regarding a cube the expected value is 3.5 = 1/6 * 1 +1 / 2 + 6 * 1/6 * 3 +1 / 6 * 4 +1 / 6 +1 * 5/6 * 6):
The average resting time an element spends in the system is derived from the average length of the queue divided by the average arrivals per time unit:
= n / λ = 1 / (μ-λ)
The average waiting time is equal to the average resting time minus the average service time:
= 1 / (μ-λ) -1 / μ
Numerical example for M/M/1 (∞, FIFO) queue
In the following numerical example the queuing system of a company will be investigated. On average, 15 people visit the shop per hour (λ) and a seller can serve 20 people per hour (μ).
The average length of the queue is n = λ / (μ, λ) = 15/5 = 3
The residence time is tv = n / λ = 3/15 = 0.2 hr = 12min
The waiting time of tw = tv - 1 / μ = 0,2 - 1/20 = 0.15 h = 9min
Now a new vendor is hired. She can serve an average of only 18 people per hour.
The average queue length is now n = λ / (μ-λ) = 15/3 = 5
The residence time is tv = n / λ = 5/15 = 0.33 h = 20min
The waiting time of tw = tv - 1 / μ = 0.33 - 1/18 = 0.278 h = 16.67 min
Tutorial
If you want to dig deeper into a M/M/1-System, you can do this using tutorials of University Melbourne, which also offers the opportunity to solve their own examples. On the pages of the University of Hagen you find a Java applet for simulation of queues.
Lecture / Lecture
You can view a lecture yourself on this topic.
