Waiting in line with polynomials

Edwards & Chelst: Algebraic

Modeling Chapter 8

Queuing Analysis
Chapter 13 Taylor (IMS)

Queuing Models 09/02/202 1

4
 Alternatives to Improve Service

After reviewing the results, Dave was deeply troubled. The USPS has a standard
that the average waiting time should be less than 10 minutes. Currently, the
average wait in queue was more than double this standard. He is considering three
options to improve service.

A. A 40-hour retraining program designed to improve the efficiency of the postal

worker. Typically, participants can reduce their average service time by 1
minute after completing the program. That will cost the postal service $2,500.

B. A redesign of the workplace and the addition of some specialty equipment will
reduce the average service time by 1.5 minutes. The cost of these changes is
estimated to be $5,000.

C. Merge two offices

Queuing Models 09/02/2 2

024
 Option B Impact
For Option A, the average service time is reduced from 6 minutes to 5 minutes.

For Option B the average service is reduced from 6 minutes to 4.5 minutes.
The average service rate is now 13.3 customers per hour.

What is the new value of ρ? ­

Calculate the values of Lq and Wq and complete Table.

Consider the cost and the impact on waiting. Which option would you
recommend and why?
Added
Option λ μ ρ Lq Wq
Cost
Current 0 8 10 0.8 3.2 24 min.
0.66
A - Training $2500 8 12 1.33 10 min.
7
B- 13. 6.75
$5000 8 0.6 0.9
Equipment 3 min.
Queuing Models 09/02/2 3
024
 Merge Two Offices – Two servers

Dave decided to consider a broader view of the services provided in the region. There
is another small post office in Macon Township, a ten-minute drive from Britton. It
services approximately the same number of people. It too provides only limited hours
on Saturdays. He is considering recommending that on Saturdays the Macon office
close and that worker from Macon Township join the worker at the Britton office. This
will save the post office an estimated $45 per Saturday in reduced utility and cleanup
expenses. There will be no labor savings as the worker will simply work in a different
location but the same number of hours.

As a result, there will now be two servers in the Britton office. For simplicity’s sake,
we will assume that all of the customers who would otherwise use the Macon office on
Saturday will make the short drive to Britton instead. Thus, the arrival rate will double
to 16 customers per hour at the merged branch in Britton. For the individual post
office, the average utilization was 0.8. The formula for average utilization for the
merged post offices is adjusted to recognize the fact that there are now two clerks who
service twice as many customers per hour.
Queuing Models 09/02/2 4
024
 Merger - Higher Order Polynomials

=λ/sμ
2
One Server Lq  / (1   )
( )2 =
𝜆
𝜇 𝜆2
=
𝜆2
1−
𝜆 [ 𝜇 2 − 𝜆 𝜇] 𝜇 [ 𝜇 − 𝜆]
𝜇

3
2
Two Servers Lq  / (1   )

Queuing Models 09/02/2 5

024
Basic Single-Server Queuing Formulas
Numbers in Queue: customers, jobs

Probability that no customers are in the queuing

system:
( )
𝑃0= 1 −
𝜆
𝜇
Probability that n customers are in the
system:

() ( )( )
𝑛 𝑛
𝜆 𝜆 𝜆
𝑃 𝑛= ⋅ 𝑃 0= 1−
𝜇 𝜇 𝜇
Average number of customers in 𝜆
𝐿=
system: 𝜇− 𝜆

Lq    2

Average number of customer in the waiting line:      

Queuing Models
 Performance of Two-Server Facility

λ = 2×8 = 16 per hour and μ = 10 per hour

ρ = λ/2μ  fraction of time each server busy = 0.8
Two Servers 3 2
𝐿𝑞=𝜌 /(1 − 𝜌 )
Lq = 0.83/(1-0.82) Lq = 0.512/(0.36)
=1.4
Wq = Lq / = 1.4/16 = 5.3
minutes
Option Added Cost λ μ ρ Lq Wq

Current 0 8 10 0.8 3.2 24 min.

A - Training $2500 8 12 0.667 1.33 10 min.

B - Equipment $5000 8 13.3 0.6 0.9 6.75 min.

Lq multiply by 2 to obtain total queue in both offices

Option A 2(1.33) = 2.67 Option B 2(0.9) = 1.8

Queuing Models 09/02/2 7

024
Performance of Two-Server
Facility
Impact on Macon Customers

Macon customers (half the total) experience this

wait time but drive 10 minutes to get there.
What is their total time to go to PO (and return
home)?

Would you recommend the merger?

Queuing Models 09/02/2 8

024
8.3 TSA Airport Security Screening

• Four or five servers

• Approximation – complex
formula
• S= number of servers
𝜌 √
2( 𝑠 +1 )
𝐿𝑞=
1−𝜌

Queuing Models 09/02/2 9

024
The Transportation Security Agency (TSA) is concerned about long back-ups in the security
screening area at Charlene York International Airport (CYA). The area has 7 x-ray screening
devices. TSA can vary the number of staff to operate these devices up to a maximum of
seven. In the morning, the number of screeners can be adjusted every hour. Any unneeded
screeners are assigned other tasks.

As customers go through the screening area, they move through a series of security screening
steps. First, their boarding pass and id are checked. Then, they wait to join one of the
screening lines. There they wait to approach a long counter where they begin unloading their
personal items into bins to be passed through an x-ray detection device. As their personal
items are screened, they pass through a metal detection device. The primary backlog is
created by the bins passing through the x-ray equipment. Each bin is looked at carefully.
There is significant variability as the number of bins and contents vary from customer to
customer. On occasion people have to be specially checked or pass through the metal detector
a second time.

Queuing Models 09/02/202 10

4
Screening Time : 45 seconds
Determine Minimum number of servers <1

Calculate total workload (person hours)

(Arrivals * Avg. Service seconds)/3600
6-7 am  315 * 45 /3600 =3.94 person Hours s=4

Customer
Arrivals Number of Screeners
Total
Minimu
Interval Total workload
m
(hrs.)
6-7 am 315 3.94 4 3.94/4 = 0.984
7-8 am 375 4.69 5 4.69/5 = 0.938
8-9 am 470 5.88 6 5.88/6 = 0.980
9-10 am 500 6.25 7 6.25/7 = 0.893
Queuing Models 09/02/202 11
4
His staff has collected data on the total number of arrivals in hour intervals from 6
am until 10 am. After that time, there was a significant decrease in the number of
arrivals until late in the afternoon. They found, for example, between 6 am and 7
am on average 315 customers arrive daily. The average service time per customer
is 45 seconds. The total screening workload per hour is 315 multiplied by 45
seconds.
Total Workload per hour = 315*45 seconds = 14,175 seconds.
This number was then divided by the number 3600 seconds in an hour,.
The total workload per hour 14175/3600 = 3.94 hours of work.
need for at least four screeners between 6 am and 7 am.
=======================================================
between 7 am and 8 am on average 375 customers arrive daily.
Average service time per customer is the same 45 seconds.
Total screening workload per hour is 16,875 seconds or 4.69 hours.

Queuing Models 09/02/202 12

4
Multi-server Formula and
Approximation

Queuing Models 09/02/202 13

4
 Dr. Queue found the formula for Lq with 4 servers in
Modeling Random Processes by James J. Solberg.

32  5
Lq 
3  6   3 2  4  3  8  4
She applied formula to first time period, 6 am to 7 am.  = (0.984)
32(0.984) 5
Lq 
 3
3  6(0.984)  3(0.984) 2  4 0.984   8(0.984) 4

Lq
59.3
Wq   0.188 hours or 11.3 minutes
  315

Queuing Models 09/02/202 14

4
 All Performance Measures

Average Screening Service Time = 45 seconds

Minimum Minimum Plus 1
Interv Arrival Screene  Screene 
Lq Wq Lq Wq
al s rs rs
6-7 0.98 59. 11. 0.78 2.
315 4 5 0.4
am 4 3 3 8 1

Queuing Models 09/02/202 15

4
Approximation 4 & 5 servers

2 ( c 1)

Lq 
1 

(0.984) 2 ( 41)
Lq  59.4
1  (0.984)

(0.788) 2( 51)
Lq  2.1
1  (0.788)

Queuing Models 09/02/202 16

4
Compare Formula and Approximation
less than 0.2% different from exact value.

Average Screening Service Time = 45 seconds

Minimum Minimum Plus 1
Screene  Screener 
Interval Lq Wq Lq Wq
rs s
6-7 0.98 59. 2.
4 11.3 5 0.788 0.4
am 4 3 1
0.98 59. 2.
Approx. 4 11.3 5 0.788 0.4
4 4 1

Queuing Models 09/02/202 17

4
Steady State Probabilities -- Pn

 State
n  number of people in the
system including in service

Queuing Models 09/02/2 18

024
Steady State
Probabilities

 State
 number of people in the
system
 P0 = no one in the system

 Pw  arriving customer will have to

wait  ALL Servers are busy
2server system – Will Wait if state
n≥ 2
 Pw = 1 – P0 – P1Queuing Models 09/02/2
024
19
 Queuing Formulas (2 of 3)

1
P0  probability no customers in system
 n c  1 1    n
 1     c 
c

       
 n 0 n !     c !     c    
n
1 
Pn    P0 for n  c
c ! c n c 
n
1  
Pn    P0 for n  c probability of n customers in system
n 
c

  
L  P 

 average customers in system
2 0
c  1! c     
L
W  average time customers spends in the system


Queuing Models
λ = 2×8 = 16 per hour and μ = 10 per hour
λ/μ = 16/10 = 1.6

Denominator (1 + (1/1!) ×1.6 + ½!

×(2.56)[(2×10)/[(2×10)-16}]
1+1.6 +(1/2) ×2.56×20/4 = 1 + 1.6 +6.4 = 9
P0 = 1/9= .11

Queuing Models 09/02/2 21

024
 Queuing Formulas (3 of 3)


Lq L  average number of customers in the queue

1 Lq
Wq W   average time customers is in the queue
 
c
1    c
Pw    P0 probability customer must wait for service
c !    c  

½(1.6)2 (2*10/(20-16) = .5×2.56×5×0.11 =

0.64×1.1 =0.704

Queuing Models
 Biggs Department Store Example
(1 of 2)

 = 10,  = 4, c = 3
1
P0 
 1  10  0 1  10 1 1  10  2  1  10  3 3(4)
           
 0!  4  1!  4  2!  4   3!  4  3(4)  10
.045probability of no customers
3
 10 
(10)(4)  
 4  10
L (.045) 
(3  1)!  3(4)  10 
2
4
6 customers on average in service department
6
W  0.60 hour average customer time in the service department
10

Queuing Models
 Biggs Department Store Example
(2 of 2)

10
Lq 6 
4
3.5 customers on the average waiting to be served
3.5
Wq 
10
0.35 hour average waiting time in line per customer
3
1  10  3(4)
Pw    (.045)
3!  4  3(4)  10
.703 probability customer must wait for service

Queuing Models