Queueing systems
Queueing systems
1
Introduction
Queueing theory is the mathematical study of the operation of
stochastic systems describing processing of flows of jobs. Queues
occur when current demand for service exceeds the capacity of the
service facility.
Waiting lines Service
Arrival flows Departure flows
2
Standard setup for arrivals
I We use the terminology ‘customers’, but they could be
telephone calls, computer jobs, information packets, etc.
I Arrival times T1, T2, T3, · · · . The inter-arrival times are
τ1 = T1 − T0, τ2 = T2 − T1, τ3 = T3 − T2 . . .
I The inter-arrival times are assumed to be i.i.d.
I Alternatively, we could use a counting process Nt giving the
number of arrivals in [0, t], t ≥ 0.
3
Standard setup for service
I There is a total of m spaces for both receiving service and
waiting for it.
I If there is an idle server, service commences for an arriving
customer immediately.
I The service time S
(j)
i of the ith customer at the jth server is a
random variable.
I The service times are assumed to be independent (and also
identically distributed for each fixed j
I When a server is serving a customer, it cannot provide any
service to other customers.
I If all servers are busy, then the arriving customers join a queue
if there is enough space, otherwise, the customer is rejected.
4
Service Disciplines
This could be
I FIFO: First In – First Out (FCFS: First Come – First Served).
I Last Come – First Served (with or without pre-emption).
I Processor Sharing.
I Priority (with or without pre-emption).
I more complicated disciplines?
We will consider only FIFO in this course.
One can use such queueing systems to construct queueing networks
by forwarding customers departing from one queue to other queues.
5
Quantities of interest
Xt is the number of customers in the system at time t (including
those in service and those waiting to begin service).
waiting time: length of time a customer spends in the queue before
her/his service commences.
sojourn time: total length of time a customer spends in the system
(waiting time plus service time).
6
Kendall’s notation
This was devised by David Kendall in 1953. It takes the form
A/B/n/m where
I A describes the arrival process
I A = M (Markov) inter-arrival times are
exponentially-distributed.
I A = GI or (G ) inter-arrival times have some arbitrary
distribution.
I A = D inter-arrival times are deterministic.
7
Kendall’s notation
I B describes the service process
I B = M service times are exponentially-distributed.
I B = GI or (G ) service times have some arbitrary distribution.
I B = D service times are deterministic.
I n gives the number of servers.
I m gives the capacity of the system. When m =∞, this is
usually omitted.
Most common is M/M/1/∞ (or just M/M/1).
8
Questions
I Does a queueing system have a steady-state regime or does
the queue increase unboundedly?
I What is the steady-state queue length distribution if it exists?
I What is the steady-state waiting time distribution if it exists?
I What fraction of time is the server idle?
9
M/M/1 queue
I Arrival stream: Poisson process with intensity λ
I Service: n = 1 server, service times ∼ exp(µ)
I Infinite space for waiting: m =∞
I The state Xt gives the number of customers at time t:
I If Xt = 0 the server is idle.
I If Xt = k ≥ 1 one customer is being served and k − 1
customers are waiting in the queue.
This is a CTMC (in fact a birth and death process) with non-zero
transition rates qi ,i+1 = λ and qi+1,i = µ for all i ∈ Z+.
Exercise: draw the transition diagram for this CTMC
10
M/M/1 an interpretation
If Xt = 0, the process remains at 0 for an exp(λ) time τ+ until a
new customer arrives, so Xt+τ+ = 1.
If Xt = k > 0, the process remains at k for a time τ = min(τ+, τ−)
where
I τ+ ∼ exp(λ) is the time until the next arrival after t
I τ− ∼ exp(µ) is the time until the end of service of the
customer in service at t.
Xt+τ = k + 1 if τ+ < τ− and Xt+τ = k − 1 if τ+ > τ−.
11
M/M/1 stationary distribution
Using our results from CTMCs, we see that a stationary
distribution for (Xt)t≥0 exists if (and only if) the chain is positive
recurrent. This is equivalent to ρ ≡ λ/µ < 1, in which case, for
n ∈ Z+,
πn = (λ/µ)
nπ0.
Using the normalisation condition
∑∞
i=0 πn = 1, we see that
π0
∞∑
i=0
(λ/µ)i = 1
which tells us that
π0 = 1− ρ
and, for n ≥ 0,
πn = (1− ρ)ρn.
So the stationary distribution for the number of customers in the
system is geometric*(1− ρ). (Note that this geometric takes
values in Z+).
12
M/M/1 further questions
I What is the stationary expected number ` of customers in the
system?
I What is the stationary expected number `q of customers in
just the queue?
I What is the expected waiting time of a customer in
stationarity?
I What is the distribution of the waiting time?
We might guess that `q = `− 1. However this is not right because
the system might be empty.
13
M/M/1 waiting times in stationarity
I In the stationary regime, a tagged arriving customer will find a
random number N of customers where N ∼ (πk)k∈Z+
(PASTA). ((Careful when interpreting this statement, e.g. it’s
not true for the first customer to arrive after time t))
I If N = 0, then the customer will go straight into service.
I If N > 0, the remaining service time S1 for the customer
being served ∼ exp(µ).
I The service times S2, S3, . . . ,SN , for those in the queue are
independent exp(µ) random variables, also independent of N.
I So the waiting time for our tagged customer is W =
∑N
j=1 Sj ,
where we interpret the empty sum as equal to 0.
14
M/M/1 waiting times in stationarity
The distribution of a non-negative random variable Y is
characterized by its Laplace transform MY (−s) = E[e−sY ] for
s > 0.
We can write
Eπ[e−sW ] = Eπ[Eπ[e−sW |N]] = Eπ[Eπ[e−s
∑N
j=1 Sj |N]]
= Eπ[(Eπ[e−sS1 ])N ]
= Eπ
[(
µ
s + µ
)N]
= MN(log(µ/(s + µ)))
= (1− ρ)
∞∑
n=0
ρ
n
(
µ
s + µ
)n
=
(1− ρ)(s + µ)
s + µ− λ
= (1− ρ) + ρ
µ− λ
s + µ− λ
,
and we see that the distribution of W is a mixture of a 0-random variable and
an exponential(µ− λ) random variable. To be precise,
P(W = 0) = 1− ρ, P(W > x) = ρe−x(µ−λ), for x > 0.
15
M/M/1 waiting times in stationarity
It follows that the expected waiting time is
E[W ] =
ρ
µ− λ
.
Once we have the expected waiting time, we can calculate the
expected total time d in the system via the formula
d = E[W ] +
1
µ
=
1
µ− λ
.
16
Little’s law:
Recall that ` is the expected number of customers in the system,
while `q is the expected number of customers waiting for service
(both at stationarity).
Little’s law says that
` = λd ,
and
`q = λE[W ].
17
Sketch proof of Little’s law
Let Nt and Dt denote the number of customers who have entered
and departed from the system in [0, t] respectively. So the number
in the system at time t is Xt = Nt − Dt . Denoting the area under
the function Xs for s ≤ t by At , we calculate E[At/t] in two
different ways. First
E
[
At
t
]
= E
[
1
t
∫ t
0
Xudu
]
which approaches the average number ` in the system as t →∞.
18
Sketch proof of Little’s law
Second, we have,
At
t
=
1
t
Nt∑
n=1
Dn + o(1)
where Di is the time spent in the system by the ith customer.
Now
E
[
At
t
]
=
1
t
E[
Nt∑
n=1
Dn] + o(1)
=
1
t
λtd + o(1)
= λd + o(1)
So taking t large we have ` = λd .
19
Example
A repairperson is assigned to service a bank of machines in a shop.
Assume that failure times occur according to a Poisson process
with rate λ = 1/12 per minute and the repair rate is µ = 1/8 per
minute.
20
Example
I The traffic intensity is ρ = 2/3 < 1, so a stationary distribution exists. I For k ≥ 0, the stationary distribution is πk = (1− ρ)ρk . I The repairperson is idle with prob 1− ρ = 1/3. I The expected number of machines requiring repair is ` = ρ/(1− ρ) = 2. I The expected time that a machine spends with the repair person is d = `/λ (or 1/(µ− λ)) = 24 minutes. I The expected time waiting for repair is E[W ] = d − 1/µ = 16 minutes. I Also, e.g. P(W > 10) = ρe−(µ−λ)10 ≈ 0.44.
21
Example
I Suppose that the failure rate of machines increases (e.g. due
to aging) by 16% to λ′ = 1/10, then the new traffic intensity
is ρ′ = 4/5, and `′ = 4 with d ′ = 40 and E[W ′] = 32.
I A 16% increase in arrival rate has drastically increased the
expected number of failed machines and doubled the time
that they have to wait before getting repaired.
I We see that, when ρ is close to 1, the effect of small changes
of ρ is profound: if a queueing system has long waiting times
and lines, a rather modest increase in the service rate can
bring about a dramatic reduction in waiting times.
22
Costs example
I Suppose there is a new piece of equipment that will increase
the repair rate from µ = 1/8 to µ∗ = 1/6, that is, decrease
the expected repair time from 8 minutes to 6 minutes.
I The increase in maintenance cost for the new equipment is
cM = $6 per minute.
I The cost of lost production when a machine is out of order is
cD = $5 per minute.
I Should we purchase the new equipment?
23
Costs example solution
Without the new equipment
I The expected number of failed machines is ` = ρ/(1− ρ) = 2.
I The expected cost of lost production is `cD = $10 per minute.
I With the new equipment, ρ∗ = 0.5, and the expected cost is
`∗cD + cM = $11 per minute.
I We should buy the equipment if `∗cD + cM < `cD , so we should not buy the equipment. 24 Another costs example At a service station the rate of service is µ cars per hour, and the rate of arrivals of cars is λ per hour. The cost incurred by the service station due to delaying cars is $c1 per car per hour and the operating and service costs are $µc2 per hour. The rate of service µ is a control parameter. Determine the value of µ so that the least expected cost is achieved and find the value of the latter. 25 Another costs example solution I If there are Y cars in the service station, the cost is $c1Y + µc2 per hour. I In the stationary regime, E[Y ] = ρ/(1− ρ). I The expected total cost per hour is $c(µ) = c1ρ/(1− ρ) +µc2 I To find the minimum, we find µ such that c ′(µ) = 0 and since µ > λ, we have a solution µ0 = λ+
√
λc1/c2.
I We can check that µ0 achieves the minimum and
c(µ0) = λc2 + 2
√
λc1c2.
26
M/M/a Queue
This system has the following properties
I a ≥ 1 servers,
I a Poisson arrival process with rate λ,
I a FIFO service discipline,
I independent exp(µ) service times,
I when an arrival finds more than one idle server, it chooses one
at random,
I when k servers are working, the total service rate is kµ.
27
M/M/a Queue
The transition rates are qi ,i+1 = λ, for i ≥ 0 and
qi ,i−1 = µ×min(a, i) for i ≥ 1.
Exercise: draw the transition diagram
This is a birth-and-death process with νi = λ for i = 0, 1, 2, . . . and
µi = iµ for i = 1, 2, . . . , a and µi = aµ for i > a.
28
M/M/a ergodicity
κj ≡
ν0 · · · νj−1
µ1 · · ·µj
=
{
(λ/µ)j/j! if j ≤ a
(λ/µ)j
a!aj−a
if j > a.
We know that
∞∑
j=0
κj <∞⇐⇒
∞∑
j=a
κj <∞.
This occurs if λ < aµ, in which case
∞∑
j=0
κj =
a−1∑
k=0
λk
k!µk
+
λa
a!µa
aµ
aµ− λ
.
29
M/M/a ergodicity
So the M/M/a queue is ergodic if and only if arrival rate λ is less
than the maximum service rate aµ.
In this case, the stationary distribution is given by
πk =
{
π0(λ/µ)
k/k! if k < a
π0(λ/µ)
k/(a!ak−a) if k ≥ a,
where
π0 =
∞∑
j=0
κj
−1 .
30
M/M/a busy servers
For what proportion of time δq are all the servers busy? This is the
same as the probability that an arriving customer will have to wait
(recall the PASTA principle).
We have
δq =
∞∑
k=a
πk = π0
λa
µaa!
aµ
aµ− λ
.
The expected queue length is
`q = E[max(Xt − a, 0)] =
λ
aµ− λ
δq.
31
M/M/a busy servers
In stationarity, the expected number bs of busy servers is
Eπ[min(Xt , a)] =
λ
µ
.
Note that, provided that λ < aµ, this does not depend on a.
The expected number of customers in the system is
` = bs + `q =
λ
µ
+
λ
aµ− λ
δq
32
M/M/a waiting times
By Little’s Law, the expected waiting time is
Eπ[W ] =
`q
λ
=
δq
aµ− λ
.
(can also get the above directly from π)
The expected delay is
d = Eπ[W ] +
1
µ
=
δq
aµ− λ
+
1
µ
.
33
M/M/a Example
An insurance company has 3 claim adjusters in its branch office.
Claims against the company arrive according to a Poisson process
at an average rate of 20 per 8 hour day. The amount of time an
adjuster spends with a claimant is exponentially-distributed with
mean service time 40 minutes.
I How many hours a week can an adjuster expect to spend with
claimants?
I How much time, on average, does a claimant spend in the
branch office?
34
M/M/a example solution
I The arrival rate is λ = 20/8 = 2.5 per hour.
I The service rate is µ = 1.5 per hour.
I λ/(aµ) = 5/9 < 1, so a stationary distribution exists.
I We get Pπ(adjuster is busy) by noticing that
Eπ[number of busy adjusters] =
3∑
i=1
Eπ[1{ith adjuster is busy}]
So, by symmetry,
Eπ[number of busy adjusters] = 3Eπ[1{a given adjuster is busy}]
= 3Pπ(a given adjuster is busy).
35
M/M/a example solution
Substituting the parameter values, we calculate that each adjuster
spends 22.2 hours a week on claims and that π0 = 24/139,
δq = 125/417 and d = 0.817 hours (which corresponds to 49
minutes).
If there were only two adjusters, we could similarly calculate
I An adjuster will spend on average 33.3 hours with claimants.
I We can calculate that π0 = 1/11, δq = 25/33 and d = 2.18
hours.
We can use this information to quantify the trade-off between the
cost of an extra adjuster and the extra level of service that is
produced.
36
Single or multiple servers?
Which is better? A single fast server or several smaller ones with
the same “cumulative service rate”? Assume that the arrival
process is Poisson with rate λ, and compare:
I A single server with service rate aµ, and
I a servers with service rate µ each.
A heuristic argument tells us that
I if Xt ≥ a, both systems work with the same rate, but
I if Xt = k < a the rate for the a server queue is kµ, which is
less than the rate aµ for the single server.
So we might conclude that the single server is better. This is
“easy” to prove via the technique of coupling.
37
Single or multiple servers?
We saw that, for the M/M/a queue, the expected number in the system
is
=
λ
µ
+
λ
aµ− λ
δq
and the expected time in the system is
=
1
µ
+
1
aµ− λ
δq.
For the M/M/1 queue with service rate aµ, the expected number in the
system is
=
λ
aµ− λ
and the expected time in the system is
=
1
aµ− λ
.
38
Single or multiple servers?
With some work, we can show that δq + (aµ− λ)/µ > 1, so both
the expected number in the system and the expected time in the
system are smaller for the M/M/1 queue, which proves our
conjecture.
As an exercise, think about the waiting time, rather than the time
in the system, for each of the systems.
39
What if our queue is not Markovian??
Then we need renewal theory!
40