14 KiB
| created_at | title | url | author | points | story_text | comment_text | num_comments | story_id | story_title | story_url | parent_id | created_at_i | _tags | objectID | year | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2015-06-03T14:41:11.000Z | What happens when you add a new teller? (2008) | http://www.johndcook.com/blog/2008/10/21/what-happens-when-you-add-a-new-teller/ | isp | 78 | 36 | 1433342471 |
|
9652882 | 2008 |
Adding a new teller | queuing theory example
(832) 422-8646
What happens when you add a new teller?
Posted on 21 October 2008 by John
Suppose a small bank has only one teller. Customers take an average of 10 minutes to serve and they arrive at the rate of 5.8 per hour. What will the expected waiting time be? What happens if you add another teller?
We assume customer arrivals and customer service times are random (details later). With only one teller, customers will have to wait nearly five hours on average before they are served. But if you add a second teller, the average waiting time is not just cut in half; it goes down to about 3 minutes. The waiting time is reduced by a factor of 93.
Why was the wait so long with one teller? There’s not much slack in the system. Customers are arriving every 10.3 minutes on average and are taking 10 minutes to serve on average. If customer arrivals were exactly evenly spaced and each took exactly 10 minutes to serve, there would be no problem. Each customer would be served before the next arrived. No waiting.
The service and arrival times have to be very close to their average values to avoid a line, but that’s not likely. On average there will be a long line, 28 people. But with a second teller, it’s not likely that even two people will arrive before one of the tellers is free.
Here are the technical footnotes. This problem is a typical example from queuing theory. Customer arrivals are modeled as a Poisson process with λ = 5.8/hour. Customer service times are assumed to be exponential with mean 10 minutes. (The Poisson and exponential distribution assumptions are common in queuing theory. They simplify the calculations, but they’re also realistic for many situations.) The waiting times given above assume the model has approached its steady state. That is, the bank has been open long enough for the line to reach a sort of equilibrium.
Queuing theory is fun because it is often possible to come up with surprising but useful results with simple equations. For example, for a single server queue, the expected waiting time is λ/(μ(μ – λ)) where λ the the arrival rate and μ is the service rate. In our example, λ = 5.8 per hour and μ = 6 per hour. Some applications require more complicated models that do not yield such simple results, but even then the simplest model may be a useful first approximation.
Related post: Server utilization: Joel on queuing
For daily posts on probability, follow @ProbFact on Twitter.
Categories : Math
Tags : Queuing theory
Bookmark the permalink
Post navigation
Previous PostData synthesis
Next PostFreeing Vista diskspace
9 thoughts on “What happens when you add a new teller?”
- John Venier
Wow, that’s amazing! I never would have guessed, but when you put it in terms of slack it makes sense.
This example is dramatic because the lone teller is already near saturation (arrival rate ~= service rate) and the queue is growing unbounded. So naturally, adding
another teller will halve the utilization of each and reduce the queue size significantly.
I used PDQ-R to check your calculations. See below, although the formatting might die in this little Reply box. The original waiting line has 28 people in steady state and indeed the residence time is 5 hrs. In the 2nd scenario, a customer only waits about 30% of the time and their mean waiting time is about 3 mins (0.0508 Hours), as you stated.
A more interesting question is, what happens if we now double the traffic rate into the bank with 2 tellers? See PDQ report 3. Even though the tellers will return to being as busy as the original lone teller, the waiting time is only 2.3757 Hours;
half that in scenario 1. Dual tellers really win!
The great feature of 2 tellers or a dual-core processor, is that the customer (or thread) at the head of the waiting line gets serviced by the next available teller.
The benefit over a single teller is due to the variation about the mean service period S. With an exp service time dsn, the variance is the same magnitude as the mean. So, if one customer is opening a new bank account (long service period), other customers (with shorter transactions) can be serviced in parallel by the other teller.
New question: What happens if a 3rd teller is added? 🙂
`
****** PDQ Model Results *******
1. Single teller model.
Node Sched Resource Workload Class Demand
---- ----- -------- -------- ----- ------
1 MSQ teller deposit TRANS 0.1667
****** RESOURCE Performance *******
Metric Resource Work Value Unit
------ -------- ---- ----- ----
Throughput teller deposit 5.8000 Cust/Hour
Utilization teller deposit 96.6667 Percent
Queue length teller deposit 29.0000 Cust
Waiting line teller deposit 28.0333 Cust
Waiting time teller deposit 4.8333 Hour
Residence time teller deposit 5.0000 Hour
2. Add another teller.
Node Sched Resource Workload Class Demand
---- ----- -------- -------- ----- ------
2 MSQ teller deposit TRANS 0.1667
****** RESOURCE Performance *******
Metric Resource Work Value Unit
------ -------- ---- ----- ----
Throughput teller deposit 5.8000 Cust/Hour
Utilization teller deposit 48.3333 Percent
Queue length teller deposit 1.2613 Cust
Waiting line teller deposit 0.2947 Cust
Waiting time teller deposit 0.0508 Hour
Residence time teller deposit 0.2175 Hour
3. Double the customer traffic as well.
Node Sched Resource Workload Class Demand
---- ----- -------- -------- ----- ------
2 MSQ teller deposit TRANS 0.1667
****** RESOURCE Performance *******
Metric Resource Work Value Unit
------ -------- ---- ----- ----
Throughput teller deposit 11.6000 Cust/Hour
Utilization teller deposit 96.6667 Percent
Queue length teller deposit 29.4915 Cust
Waiting line teller deposit 27.5582 Cust
Waiting time teller deposit 2.3757 Hour
Residence time teller deposit 2.5424 Hour
`
I see that you discuss R elsewhere in your blog, so here is the PDQ-R (Pretty Damn Quick in R) code for the above Bank model.
`
PDQ v5.0
Created by NJG on Monday, May 4, 2009
library(pdq)
arrival_rate=5.8 * 2 # cust/hr
service_time=10.0/60 # 10 minutes
Init("M/M/m Blog Example")
#define the workflow
CreateOpen("deposit", arrival_rate)
SetWUnit("Cust")
SetTUnit("Hour")
#define an m-server queue (here m = 2)
CreateMultiNode(2,"teller", CEN, FCFS)
#define the service demand on the server
SetDemand("teller", "deposit", service_time)
Solve(CANON)
Report()
`
- David Anderson
I’m totally on board with Exponential arrivals, but wouldn’t M/G/1 but a more accurate representation of a bank queue? Service times are probably much closer to Normal than Exponential. I know M/M/1 is nice and clean, but probably not that accurate. And the long tail of exponential service times is what creates lots of the backlog and excess waiting times.
- R.S.S.
Queuing Theory is fun. Thank your U.S. Navy for a lot of work in the area.
- mikemikemikemikemike
You state that each customer takes 10 minutes to service. You then state that a customer comes every 10.3 minutes. How the hell is there a 5 hour wait, and why are there 28 people in line?
Customer 1 shows up, takes 10 minutes, leaves
.3 minutes lapse while teller 1 takes a bump of coke
Customer 2 shows up…
Am I confused?
- John
You are correct, if customers arrive regularly on the schedule in your example. The problem is that people arrive randomly. In the best case scenario, there’s never a line, though that’s extremely unlikely. It’s far more likely that the line will grow over time until it reaches an equilibrium around 5 hours.
-
Pingback: A little simplicity goes a long way
-
Pingback: Server Utilization: Joel On Queuing
Leave a Reply Cancel reply
Your email address will not be published. Required fields are marked *
Comment
Notify me of followup comments via e-mail
Name *
Email *
Website
Search for:
John D. Cook, PhD
Latest Posts
- Fibonacci / Binomial coefficient identity
- Painless project management
- New animation feature for exponential sums
- Quantifying normal approximation accuracy
- Ordinary Potential Polynomials
Categories
CategoriesSelect CategoryBusinessClinical trialsComputingCreativityGraphicsMachine learningMathMusicPowerShellPythonScienceSoftware developmentStatisticsTypographyUncategorized
| ----- |
| 
| Subscribe via email |
| 
| Subscribe via RSS |
| 
| Monthly newsletter |
John D. Cook
© All rights reserved.
Search for: