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 inter-arrival times and arrival times:

Let Xk be the kth inter-arrival time and Sk be the kth arrival time.

X1 = S1

X1+X2 = S2

X1+X2++Xk = Sk

If {X1, X2, X3 } is a sequence of i.i.d. random variables from exponential (λ) and { S1, S2, S3  Sk } is a sequence of arrival times (followed the relationship listed above), then we have Sk ~ 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 inter-arrival 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.

1. Describe why it is a queueing system.
2. What is the queue in this case? Describe how you would expect the queue discipline to operate.
3. Would you expect random arrivals?
4. What are service times in this context? Would you expect much variability in the service times?

Labels for Queuing Models

To identify which probability distribution is being assumed for service times (and for inter-arrival times), a queueing model for a basic queueing system conventionally is labeled as follows:

Distribution of inter-arrival 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 (inter-arrival 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 dont 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 inter-arrival times or for the service times. The symbols used in these cases are

GI = General independent interarrival-time distribution (any arbitrary distribution allowed).

G= General service-time 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: fX(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 Birth-And-Death 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 birth-and-death 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

LQ: Average number of customers in Queue

WQ: 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 = WQ + 1/ μ

Little Formula

L = λ * W

Given a pair of times (t1 ,t2 ), t2 > t1

Time t1 (the time that the tagged customer enters the system),

Time t2 (the time that the tagged customer leaves the system)

The customers in the system at time t2 are those customers joined the system during the waiting time (W = t2 - t1) of the tagged customer.

Time = t1                                                                                                                                                             Time = t2

The M / M /1 Queueing Model:

Rate in = Rate out Principle

The equations expressing this principal are called Balance Equations.

(State 0)  μP 1  = λP0   ΰ  P 1  = (λ/μ) P0

(State 1)  λP 0  + μP 2  =  (λ+μ) P 1  ΰ  P 2  =  (λ/μ)2 P0

(State 2)  λP 1  + μP 3  =  (λ+μ) P 2  ΰ  P 3  =  (λ/μ)3 P0

(State 3)  λP 2  + μP 4  =  (λ+μ) P 3  ΰ  P 4  =  (λ/μ)4 P0

Derivation details:

1. We know:        P 1  = (λ/μ) P0

λP 0  + μP 2  = (λ+μ) P 1  =  (λ+μ) (λ/μ) P0

μP 2  =  2 /μ) P0 +λP 0  -λP 0

P 2  =  (λ/μ)2 P0

P n  =  (λ/μ)n P0

2.

P N  =  (λ/μ)N P0 = δn P0  Where δ = λ/μ  < 1

P0 + P1 + P2 + P3 +  = 1

P0 +δP02P0 3P0 +  = 1

P0 * (1+δ+δ2 3+ ) = 1

S. (Geometric Series)

[S = 1+δ+δ2 3+

δs =δ+δ2 34  Cancel common factors]

(1 -δ)* S = 1

S = 1/ (1-δ)

ΰ Po *  [1/ (1-δ)] = 1

Po = 1-δ

3.

L = 0 * P0

+ 1 * P1   (1 *δP0)

+ 2 * P2   (2 *δ2P0 )

+ 3 * P3   (3 *δ3P0 )

+ 4 * P4   (4 *δ4P0 )

.         .

.         .

.         .

L =δP0 + 2 *δ2P0 + 3 *δ3P0 + 4 *δ4P0 +

δL =      δ2P0 + 2 *δ3P0 + 3 *δ4P0 +

(1-δ) L =δP0 2P03P0 +

=δP0 (1+δ+δ2 3+ )

S= 1 / (1-δ)

=δP0 / (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: Mon-and-Pop'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 Po = 0.2, P1=0.3, P2=0.3, P3=0.2.

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 Po=1/16, P1 = 4/16, P2 = 6/16, P3 = 4/16, P4 = 1/16.

a. Use the formula L= 0*Po + 1*P1 + 2*P2 + 3*P3 + 4*P4 to calculate L. How would you describe the meaning of L to Newell and Jeff?

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 single-server queueing system must equal 1 - Po, where Po is the probability of having 0 customers in the system.

Example:

The Friendly Neighbour Grocery Store has a single checkout stand with a full-time cashier. Customers arrive randomly at the stand at a mean rate of 30 per hour. The service-time 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, Po, P1, and P2 for the current mode of operation. What is the probability of having more than two customers at the checkout stand?

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 Centerville International Airport has two runways, one used exclusively for takeoffs and the other exclusively for landings. Airplanes arrive randomly in the Centerville air space to request landing instructions at a mean rate of 10 per hour. The time required for an airplane to land after receiving clearance to land has an exponential distribution with a mean of three minutes, and this process must be completed before giving clearance to land to another airplane. Airplanes awaiting clearance must circle the airport.

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  =  (λ/μ)N P0

2. Po = 1-δ

3. L =δ / (1-δ) =λ / (μ-λ)

4. W = L /λ

5. Wq = λ /[μ *(μ-λ)] = (λ/μ) / (μ-λ) =δ / (μ-λ)

6. Lq2 / [μ *(μ-λ)]

7. P[Wt] = 1 

8. P[Wqt] = 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