MGOC10 Analysis for Decision Making

Lecture 10
Chapter 11 – Waiting Line (Queuing) Models

1. Introduction

Queuing Theory – the study of waiting lines

Quantity of interest:
 What is probability having 3 customers in system?
 What is expected # customers in system?
 What is expected # customers in line?
 What is expected time customer waits in line?
 What is utilization of servers?

 Providing too much service (having lots of servers) is costly.

 Not providing enough service causes long waiting lines – also costly.
 Need to balance these costs.

2. The Basic Queuing Process

Note: # of servers = # of channels in your textbook

Customers – generated over time from a population.

 Population size can be infinite or finite.
 “Customers” can be cars arriving to be wash, planes arriving for landing, etc.
1
Inter-arrival times – between successive customers is random.
 Most common is to assume exponentially distributed random variable
 # of customers arriving in a time period is then Poisson Dist. random variable

x = # of arrivals in the time period, most common is to assume Poisson random variable,
eg. p[5 customers arriving in a 15 min time interval]
λ = mean number of arrivals per time period. eg. 45 customers / hour

Example
On average 45 customers/hr arrive to a car wash.
(a) What is probability no customers will arrive in a one minute period?

λ = 45 cars/hour = 45 cars/60min = 0.75cars/min,

(b) What is probability more than 2 cars arriving in one minute period?

P[x > 2] = 1 - P[ x ≤ 2] = 1- (P[x = 0] + p[x = 1] + p[x = 2])

= 1- ( )
=1 – (0.4724+0.3543+ 0.1329) = 0.0404

Queue size – can assume infinite or finite queue size. Most common is to assume infinite.

Queue discipline
First come first serve = FCFS
Last come first serve = LCFS
Service in random order = SIRO
General queue discipline = GD

Other considerations:
Jockey – Customers jumping /changing queues
Balk – Customers don’t want to enter system or system rejects customers (busy signal)
Renege – Customers quit after waiting too long in queue

Service times
2
 Time to complete service.
 Can be constant or random variable.
 Most common is to assume service time is exponentially distributed random variable
with mean service rate μ.

eg. μ = 5 customers/hr means if customers are always present, server can process 5
customers/hr and the time to service each customer is 1/5 hr.

 Common to assume all workers work at same speed/rate.

t = time to serve a customer, exponentially distributed random variable
μ = mean number of customers that can be served per time period

P[service time ≤ t] = 1-e-µt

Example
(a) Server can process on average 60customers/hour. What is probability that a customer will
get processed in 0.5 min or less?

μ = 60 customers/hr = 60customers/60min = 1 customer/min

(b) Server can process on average 2 customers/hr. What is the average time it takes to process a
customer?

μ = 2 customers/hr so mean time to process a customer is = 1/μ = 0.5hr/customer

Notation for specifying a queuing system: (a / b / k) : (d / e / f)

a = inter-arrival time distribution

M = exponential (Markovian)
D = constant (deterministic)
Ek = Erland or gamma
G = general distribution

b = service time distribution - M, D, Ek, G

k = # of parallel servers or channels (1,2,3…k)

d = Queue discipline – FCFS, LCFS, SIRO, GD

e = max # of customers allow in system

f = size of input population (finite/infinite)

Example
(M/M/2): (FCFS/10/∞)

This is a queuing system with exponential inter-arrival times and service times, 2 servers, first
come first serve, max 10 customers allowed in system, infinite input population size.

3
3. Little’s Formulas
Little Formulas – provides general relationships for waiting line models
Use to calculate things such as expected # of customers in system.

Wq = Expected wait time in queue

W = Expected time spent in system
L = expected number of customers in system
Lq = expected number of customers in queue

L = λW Lq = λWq

(expected wait time in system) = (expected wait time in queue) + (expected service time)

W = Wq + 1/μ

If multiply W = Wq + 1/μ by λ → λW = λWq + λ/μ gives L = Lq + λ/μ

4. Single Channel, Poisson arrival, exponential service times- (M/M/1) : (FCFS/∞/∞) model

Consider model with 1 server, want to know probability of having 4 customers in system (P4).

Queuing formulas applicable for system in steady state

 What is steady state?

o Bank opens door in morning (0 customers), mad rush of customers come in, after
a while things settle. Transient State → Steady State

n = state of system = # of customers in system

Pn = steady state probability of having n customers in system

Condition for Steady State (service rate faster than arrive rate): λ/µ < 1

Probability of 0 customers in system:

Probability of n # of customers in system is: for n=0,1,2….

Expected # customers in queue:

 Other parameters can be obtained via Little’s Formula.

4
 From Lq = λWq can get Wq

From W = Wq + 1/μ can get W

From L = λW can get L

The prob. arriving unit has to wait for service = Pw = 1- P0 = λ/µ

Example 1
An average of 10 cars/hr arrive at car wash center. Average service time for each car is 4mins.
Assume exponential for inter-arrival and service times, FCFS, infinite queue and an infinite
population size.
(a) What is the probability that car wash center is idle?

(b) What is average # of cars waiting in line for car wash?

(c) What is average amount of time car spends in the car wash center?

6. Multi-server with Poisson arrival, exponential distribution - (M/M/k) : (FCFS/∞/∞)

5
k =number of servers.
Steady state can be reached if

Probability there are no customers in system =

Probability there are n customers in system =

Expected # of customers in queue =

 Other parameters can be obtained via Little’s Formula

From Lq = λWq can get Wq

From W = Wq + 1/μ can get W

From L = λW can get L

The prob. arriving unit has to wait for service =
Example 2
An average of 80 parts/hr arrive at a manufacturing line with 2 identical machine for processing.
Average service time for each part is 1.2mins. Assume exponential for inter-arrival and service
times, FCFS, infinite queue and an infinite population size.
(a) Can steady state be reached? What is the expected number of parts in the system?

6
(b) What is the fraction of time machine 1 is idle? Machine 2 idle? At least one machine is idle?

7. Economic Analysis of Waiting Lines

 Is it better to have individual waiting lines or a single “mega-cash” counter?

7
  Can compare performance measures: L, Lq, W, Wq
 Can compare costs (operating + parts/workers waiting for service + space needed + etc.)

Example 3
An average of 24 customers/hr arrive at a small Driver Licensing Office (Poisson distribution)
waiting to renew their driver’s license, update their vehicle registration sticker, etc. At present,
there are 3 clerks. Customers wait in a single line for the first available clerk. The average time
for a clerk to service a customer is 4min (exponentially dist). Clerks earn $12/hr, and the
government assesses a waiting time cost of $20 for each hour that a customer waits in line.

(a) When a customer finally reaches the clerk, what is the probability it will take 25 seconds or
more to complete service?

(b) The Manager feels that if there are more than 10 customers arriving in a 15min time period,
then the Office would have problems with space. What is the chance that the Office will run
into this problem?

(b) What is the expected cost per hour to operate the office?

8
(c) What is the probability you will not have to wait in line when you come to this office?

(d) The government is considering replacing one of the clerk with an Automatic Service Machine
(ASM). Management estimates of the 24 customers/hr that arrive, 20% of them will use the
ASM. Customers form a separate line at the ASM and assume that customers are not
permitted to changes lines. An ASM takes an average of 8 min (exponential dist) to service
each customer. It costs $5/hr to operate the ASM. Should the government install the ASM?

9
7. Derivation of Po and Lq for (M/M/1) : (FCFS/∞/∞) model – For Reference Only

State Diagram

Balance Equations to determine P0

 For any state of the system n=0,1,2,3… enter rate = leaving rate in steady state.
 This principal allow us to express balance equations for each state n and solve for Pn

State enter = leave

0 P1μ = P0λ
1 λP0 + μP2 = (λ+μ)P1
2 λP1 + μP3 = (λ+μ)P2
…
n-1 λPn-2 + μPn = (λ+μ)Pn-1
n λPn-1 + μPn+1 = (λ+μ)Pn

Rewrite equations in terms of P0

State enter = leave
0 P1 = (λ/μ)P0
1 P2 = (λ/μ)2P0
2 P3 = (λ/μ)3P0
…
n-1 Pn = (λ/μ)nP0

Total probability = 1: →

For steady state (λ/μ) < 1, we get

Expected # customers in queue= Lq = 0P0 + 0P1 + 1P2 + 2P3 + …

10