Bus O711 Web Page

Chapter 17: Queueing Theory

0. Motivation

Lucille Ball at the chocolate factory: See what happens when the chocolates arrive faster than Lucille and her friend can wrap them; i.e., when arrival rate is faster than the service rate.

Here's another funny YouTube queue video. (Don't leave your queue!)

When there are variations in arrival and service patterns, queues will form even if the arrival rate (average number of arrivals per time) is less than the service rate (average number of service completions per time).

1. Features of Queueing Processes

Two videos of a simple queueing animation:

Stable queue: Here, the arrival rate is α = 0.45 customers per time and service rate is β = 0.50 customers per time. Since α < β, the system will eventually settle down at an average of 9 customers in the the system. The variable Q(t) keeps track of the number of customers in the system, E(t) measures the fraction of time the server is idle, and W(t) is the average waiting time of a customer.
Exploding queue: Here, α = 0.95 and β = 0.5, so the queue will grow without bound.

What do we mean by limiting (or, steady-state) probability? This Excel spreadsheet shows that the fraction of time we obtain Heads in a coin toss approaches 1/2 only after a large number of trials. Initially, the fraction is not very close to 1/2.

Professor John D. C. Little discovered Little's formula (law) L = λW. Here's an interview with him where he explains his law.

2. Importance of the Exponential Distribution in Queueing

An Excel spreadsheet demonstrating an arrival process where interarrivals are exponential with rate λ = 1. The graph shows that histogram approximates the exponential density f(t) = λ·exp(-λt) = exp(-t). There are statistical tests, (e.g., chi-square) to determine the validity of the exponential assumption. You can read my hand-written notes about this test here.

Exponential distribution calculations : This Excel file calculates the probabilities and expected value related to the exponential. It also plots the graph of the density function f(t) = α·exp(-αt). As mentioned above, there are statistical tests, (e.g., chi-square) to determine the validity of the exponential assumption. You can read my hand-written notes about this test here.

Poisson distribution calculations: This Excel file calculates and plots the Poisson distribution for any α and t.

Using Soccer Goals to Motivate the Poisson Process

We will discuss the interesting paper by S. Chu who has shown that the intergoal times in four world cup soccer games are distributed exponentially, i.e., the goal scoring process is Poisson. The four world cup competitions are 1990, 1994, 1998 and 2002.

Who is the young goalkeeper in this picture?

3. Birth-and-Death (B&D) Processes

Phone operators at Queen's Park: This Excel spreadsheet calculates the state probabilities and other related performance measures of the switchboard system.

*** Solution of Problem 17-5.13, p. 817 (Two classes) . As this is a rather challenging problem, it would be instructive to look at a brief explanation of its solution.

4. Exponential (Memoryless) Queueing Models Based on B&D Processes

(a) M/M/1 System

Two videos of a simple M/M/1 queue animation (same as in Section 1 above):

Stable queue: Here, the arrival rate is α = 0.45 customers per time and service rate is β = 0.50 customers per time. Since α < β, the system will eventually settle down at an average of 9 customers in the the system. The variable Q(t) keeps track of the number of customers in the system, E(t) measures the fraction of time the server is idle, and W(t) is the average waiting time of a customer. In the limit, of course, the average of Q(t) gives L, the average of E(t) gives ρ, and W(t) gives W.
Exploding queue: Here, α = 0.95 and β = 0.5, so the queue will grow without bound.

Innis Library with one librarian: This Excel spreadsheet calculates the state probabilities and other related performance measures of the M/M/1 library system.

(b) M/M/s System

Here is the Excel file for the library example with s = 2, i.e., the M/M/2 system.

(c) M/M/1/K System with Finite System Capacity K

Here is the Excel file for the barbershop example with s = 1 barber and K = 5 chairs, i.e., the M/M/1/5 system.

(d) M/M/s/K System with Finite System Capacity K

Here is the Excel file for the barbershop where a new barber is hired, i.e., the example with s = 2 barbers and K = 6 chairs (M/M/2/6 system). We have K = 6 chairs because the new barber needs a barber's chair, too.

(e) M/M/1/./N System with Finite Population N

Here is the Excel file for the bus repair facility with s = 1 repairman and N = 4 busses that need repairs.

(f) M/M/s/./N System with Finite Population N

Here is the Excel file for the bus repair facility with s = 2 repairmen and N = 4 busses that need repairs.

*** Solution of Problem 17-6.32, p. 821 (Dolomite Corp.) As this is a rather challenging problem, it would be instructive to look at a brief explanation of its solution.

5. M/G/1 Queue and Its Variations

Erlang distribution: Here is a link to this important (and interesting) distribution.

For calculations related to the M/G/1 queue, this Excel template can be used.

6. The Application of Queueing Theory (Optimization of Queues)

This Excel file calculates the expected total cost of service plus waiting.