Queueing Theory
Queues are waiting lines.
Basic Structure of Queueing
Models
The Basic Queueing
Process
The
basic process assumed by most queueing models is the
following. Customers requiring service are generated over time by an input
source (arriving process). These customers enter the queueing system and join a queue. At certain times, a
member of the queue is selected for service by some rule known as the queue
discipline. The required service is then performed for the customer by
the service mechansism, after which the customer
leaves the queueing system. This process is depicted
in the figure below:
Arriving Process (Input Source; Calling
Population)
One
characteristic of the input source is its size. The size is the total number of
customers that might require service from time to time, i.e., the total number
of distinct potential customers. This population from which arrivals come is
referred to as the calling population.
Poisson Process
Relationship between interarrival times
and arrival times:
Let
Xk be the k^{th}
interarrival time and S_{k}
be the k^{th} arrival time.
X1
= S1
X1+X2
= S2
X1+X2+
+Xk = S_{k}
If
{X1, X2, X3
} is a sequence of i.i.d.
random variables from exponential (λ) and { S1, S2, S3
S_{k}
} is
a sequence of arrival times (followed the relationship listed above), then we
have S_{k} ~ Gamma [k ,λ] and this can be proved by The Uniqueness of Moment
Generating Function.
N (t) = number of arrivals before time t
(or during the time interval (0 , t))
P
[N (t) = K] = [e ^{ }^{λ}^{t}^{
}(λt)^{
K]}^{ }/K!
K = 0, 1, 2
number of arrivals
λ : the mean arrival rate
Example:
λ = 10 customers / hour
t
= 1 hour
P
[N (1) =3] = [e ^{}^{10*1}(10*1)^{ 3}_{] }/3!
Poisson Process
Two
ways to define a poisson process
1. P [N (t) = K] = [e ^{ }^{λ}^{t}^{
}(λt)^{
K] }/K!
2. The sequence of interarrival times {X1, X2
}
is a sequence of i.i.d. RVs from exponential (λ)
Density
functions of exponential distributions (below):
X ~ exponential (λ)
Its probability density function (pdf) f (x)
f(x)
= {λe ^{ }^{λ}^{x}^{
},
x > 0
0
, o/w
Queue
Discipline

FIFO ( First  In  First  Out)

LIFO ( Last In First Out) example:

SRO (Service in Random Order)

SST (Shortest Service Time)

EDD (Earliest Due Date First)

VIP
Queue
Capacity
The
maximum length of the waiting line
Example:
barber shop
Example: Consider a typical hospital emergency room.
Labels
for Queuing Models
To
identify which probability distribution is being assumed for service times (and
for interarrival times), a queueing model for a
basic queueing system conventionally is labeled as
follows:
Distribution
of interarrival times / Distribution of service times / S / K
S
= the number of servers.
K
= the capacity of the system
EXAMPLE:
M
/ M / 1 / K
M: Arrival process is Poisson process (interarrival
times are exponentially distributed).
M:
Service Process, service times are exponentially distributed.
1:
Number of Server = 1.
K:
Capacity. Drop this if the capacity is
infinity or we dont care.
M
= Exponential distribution (Markovian)
D
= Degenerate distribution (constant times)
Ek = Erlang distribution (shape parameter = k)
There
even are queueing models that permit choosing any
probability distribution for the interarrival times or for the service times.
The symbols used in these cases are
GI = General independent interarrivaltime
distribution (any arbitrary distribution allowed).
G=
General servicetime distribution (any arbitrary distribution allowed).
The Role of the Exponential Distribution
X ~ exponential (λ)
Its probability density function (pdf) f (x)
f(x)
= {λe ^{ }^{λ}^{x}^{
},
x > 0
0
, o/w
Property 1: f_{X}(x) is a
strictly decreasing function of x.
Property 2: Lack of
memory.
Property 3: The Minimum
of several independent exponential random variables has an exponential
distribution.
Property 4: Relationship
to Poisson distribution.
Property 5: For all
positive values of t, P{T≤ t + ∆t
│T > t} ≈ α∆t.
Property 6: Unaffected
by aggregation or disaggregation.
The BirthAndDeath Process
Assumption
1.
Given N(t) = n,
the current probability distribution of the remaining time until the next
arrival (birth) is exponential with parameter λ _{n}( n=0, 1, 2,
3,
.).
Assumption
2.
Given N(t) = n,
the current probability distribution of the remaining time until the next
service completion (death) is exponential with parameter μ _{n}(
n=0, 1, 2, 3,
.).
Assumption
3.
The random variable of assumption 1 (the
remaining time until the next arrival) and the random variable of assumption 2
(the remaining time until the next service completion) are independent.
Because the above assumptions, the
birthanddeath process is a special type of continuous time Markov Chain. Queueing models that can be represented by a continuous time markov chain are far more tractable analytically than any
other.
Measures of Performance
L: Average number of customers in the system
W: Average waiting time in the system
L_{Q}: Average number of customers in Queue
W_{Q}: Average waiting time in Queue
λ is the mean arriving rate
μ is the mean service rate
If λ > μ, then, the waiting line keeps
building up, the system is not stable.
In our discussion, we focus
on the case that λ < μ, the queuing system is stable.
Define Pn = the steady state (of a stable queuing system) probability
of having n customers in the system.
State of the queuing system: the number of customers in the system
W = W_{Q }+ 1/ μ
Little Formula
L = λ * W
Given a pair of times (t_{1 },t_{2} ), t_{2 }> t_{1}
Time t_{1 }(the time
that the tagged customer enters the system),
Time t_{2 }(the time that the tagged customer leaves the system)_{}
The customers in the system
at time t_{2 }are those customers joined the system during the waiting
time (W = t_{2 } t_{1}) of the tagged customer.
Time = t_{1 }Time
= t_{2}
_{ }
The M / M /1 Queueing Model:
Rate in = Rate out Principle
The equations expressing this
principal are called Balance Equations.
(State 0) μP _{1} = λP_{0 }ΰ P _{1 }= (λ/μ) P_{0}
(State 1) λP _{0 }+ μP _{2 }= (λ+μ) P _{1 } ΰ P _{2 }= (λ/μ)^{2} P_{0 }
(State 2) λP _{1 }+ μP _{3 }= (λ+μ) P _{2 } ΰ P _{3 }= (λ/μ)^{3} P_{0 }
(State 3) λP _{2 }+ μP _{4 }= (λ+μ) P _{3 } ΰ P _{4 }= (λ/μ)^{4} P_{0 }
_{ }
Derivation details:
1. We know: P _{1 }= (λ/μ) P_{0}
λP _{0 }+ μP _{2 } = (λ+μ) P _{1 } = (λ+μ) (λ/μ) P_{0}
_{ }μP _{2 } =
(λ^{2 }/μ) P_{0 }+λP
_{0 }λP
_{0 }
P
_{2 }= (λ/μ)^{2} P_{0 }
P _{n }= (λ/μ)^{n} P_{0 }
2.
P _{N }= (λ/μ)
P_{0 }+ P_{1}
+ P_{2 }+ P_{3 }+
= 1
P_{0 }+δP_{0}
+δ^{2}P_{0 }+δ^{3}P_{0 }+
= 1
P_{0 }*
(1+δ+δ^{2}_{ }+δ^{3}+
) = 1
S. (Geometric Series)
[S = 1+δ+δ^{2}_{
}+δ^{3}+
δs
=δ+δ^{2}_{ }+δ^{3}+δ^{4}
Cancel common factors
]
(1 δ)* S = 1
S = 1/ (1δ)
ΰ
3.
L = 0 * P_{0}
+ 1 * P_{1 } (1 *δP_{0})
+ 2 * P_{2} (2 *δ^{2}P_{0
})
+ 3 * P_{3 } (3 *δ^{3}P_{0}
)
+ 4 * P_{4 } (4 *δ^{4}P_{0}
)
.
.
. .
. .
L =δP_{0 }+ 2
*δ^{2}P_{0 }+ 3 *δ^{3}P_{0} + 4
*δ^{4}P_{0 }+
δL = δ^{2}P_{0 }+ 2
*δ^{3}P_{0} + 3 *δ^{4}P_{0 }+
(1δ) L =δP_{0 }+δ^{2}P_{0}
+δ^{3}P_{0 }+
=δP_{0 }(1+δ+δ^{2}_{
}+δ^{3}+
)
S= 1 / (1δ)
=δP_{0 }/ (1δ)
L =δ_{ }/ (1δ) ={(λ/μ) / [1 (λ/μ)]} * (μ/μ)
= λ / (μλ)
Comment : (λ/μ) = δ
Some other books, define (λ/μ) =
ρ
In a stable queueing
system, (λ/μ) = ρ < 1
4.
Now we want to find W
Use the Little Formula
L = λ * W ΰ W = L /λ
W= 1 / (μλ)
_{}
5. The relationship between Wq
& W.
W = Wq
+ 1 mean service time (This is true for all
queueing models!)
W = Wq
+ 1/μ
Wq = W  1/μ = 1/(μλ)  1/μ = (μμ+ λ)
/[μ *(μλ)]
=
λ /[μ *(μλ)] = (λ/μ) / (μλ) = δ /
(μλ)
6.
Lq = λ * Wq ΰ Little Formula
=λ * {λ /[μ *(μλ)]}
=λ^{2 }/ [μ *(μλ)]
Review Exercises for Measures of Performance
Example: MonandPop's Grocery
Store has a small adjacent parking lot with three parking spaces reserved for
the store's customers. During store hours, when the lot is not full, cars enter
the lot and use one of the spaces at a mean rate of two per hour. When the lot
is full, arriving cars leave and do not return. For n=0, 1, 2, 3, the
probability Pn that exactly n spaces currently are
being used is
a. Describe how this parking lot
can be interpreted as being a queueing system. In
particular, identify the customers and the servers. What is the service being
provided? What constitutes a service time? What is the queue capacity?
b. Determine the basic measures
of performance  L, Lq, W, Wq
 for this queueing system.(Hint: You can use the
given probabilities to determine the average number of parking spaces that are
being used.)
c. Use the results from part b to
determine the average length of time that a car remains in a parking space.
Example: Midtown Bank always has
two tellers on duty. Customers arrive to receive service from a teller at a
mean rate of 40 one hour. A teller requires an average of two minutes to serve
a customer. When both tellers are busy, an arriving customer joins a single
line to wait for service. Experience has shown that customers wait in line an
average of one minute before service begins.
a. Describe why this is a queueing
system.
b. Determine the basic measures of performance  Wq, W, L, and Lq  for this queueing system. (Hint: we don't know the probability
distributions of inter arrival times and service times for this queueing system, so you will need to use the relationships
between these measures of performance to help answer the question.)
Example: Newell and
Jeff are the two barbers in a barber shop they own and operate. They provide
two chairs for customers who are waiting to begin a haircut, so the number of
customers in the shop varies between 0 and 4. For n = 0, 1, 2, 3, 4, the
probability Pn that exactly n customers are in the
shop is
a. Use the formula L= 0*
b. For each of the possible
values of the number of customers in the queueing
system, specify how many customers are in the queue. For each of the possible numbers
in the queue, multiply by its probability, and then add these products to
calculate Lq. How would you describe the meaning of Lq to Newell and Jeff?
c. Given that an average of four
customers per hour arrive and stay to receive a haircut, determine W and Wq. Describe these two quantities in terms meaningful to
Newell and Jeff?
d. Given that Newell and Jeff are
equally fast in giving haircuts, what is the average duration of a haircut?
Example:
Explain why the utilization
factor ρ
for the server in a singleserver queueing
system must equal 1  Po, where
Example:
The Friendly Neighbour Grocery Store has a single
checkout stand with a fulltime cashier. Customers arrive randomly at the stand
at a mean rate of 30 per hour. The servicetime distribution is exponential,
with a mean of 1.5 minutes. This situation has resulted in occasional long
lines and complaints from customers. Therefore, because there is no room for a
second checkout stand, the manager is considering the alternative of hiring
another person to help the cashier by bagging the groceries. This help would
reduce the expected time required to process a customer to 1 minute, but the
distribution still would be exponential.
The manager would like to have the percentage of
time that there are more than two customers at the checkout stand down below 25
percent. She also would like to have no more than 5 percent of the customers
needing to wait at least five minutes before beginning service, or at least
seven minutes before finishing service.
a. Use the formulas for the M/M/I model to
calculate L, W, Wq, Lq,
b. Use the Excel template for this model to check
your answers in part a. Also, find the probability that the waiting time before
beginning service exceed five minutes, and the probability that the waiting
time before finishing service exceeds seven minutes.
c. Repeat part a. for the alternative being
considered by the manager.
d. Repeat part b. for this alternative.
e. Which approach should the manager use to
satisfy her criteria as closely as possible?
Example:
Suppose a queueing
system fitting the M/M/I model has W=120 minutes and L=8 customers. Use these
facts (and the formula for W) to find λand μ. Then find the various
other measures of performance for this queueing
system.
Example:
The
The Federal Aviation Administration has a number
of criteria regarding the safe level of congestion of airplanes waiting to
land. These criteria depend on a number of factors regarding the airport
involved, such as the number of runways available for landing. For Centerville,
the criteria are (1) the average number of airplanes waiting to receive
clearance to land should not exceed one, (2) 95 percent of the time, the actual
number of airplanes waiting to receive clearance to land should not exceed
four, (3) for 99 percent of the airplanes , the amount of time spent circling
the airport
On Poisson Arrival See Time Averages (PASTA)
7. P[W ≤ t] = 1 _{}
Use PASTA & Conditional
Probability:
8. P[Wq
≤ t] = 1 ρ_{}
Formulas for the M / M /1 Queueing
Model:
1. P _{N }= (λ/μ)
2.
3. L =δ_{ }/ (1δ) =λ /
(μλ)
4. W = L /λ
5. Wq = λ /[μ
*(μλ)] = (λ/μ) / (μλ) =δ / (μλ)
6. Lq =λ^{2 }/ [μ *(μλ)]
7. P[W ≤ t] = 1 _{}
8. P[Wq ≤ t] = 1 ρ_{}
Other Queueing Models:
1. The M/M/1/K Model
2. The M/M/s/K Model
3. The M/G/1 Model
4. The M/D/s Model
5. The M/Ek/s Model
The Application of Queueing
Theory