Queuing Models

Statistics : Poisson Distribution - Introduction : ExamSolutions
[http://www.youtube.com/watch?v=bqsfcCSqpBs&feature=related How You Can Use the Poisson Distribution to Solve Problems - and Do It In

### Abstract

Coordination and scheduling problems abound in all areas of social life. One subclass of these involves situations where access to a resource is necessarily sequential. This can be as mundane as getting in line for the bathroom or scheduling deliveries at the loading dock at the Salvation Army to designing appointment management procedures so as to maximize the benefit delivered by a free clinic.

### Example One

How many toll booths should be open on the Bay Bridge (go back to the era before EZPass)? First of all, let's diagram the situtation:

Let's brainstorm for a moment about what some of the parameters and variables in this system might be.

1. Time. We expect to come up with a dynamic model. We'll be interested in how things unfold over time.
2. The rate at which cars arrive at the bridge
3. The rate at which cars get through the toll booths and onto the bridge
4. The number of toll booths.
5. How long it takes to get each vehicle through the toll booth.

STOP AND THINK. Why not just throw lots of toll booths at the problem? The more the better? Answer: it costs money. We know that there is a much heavier flow of traffic at some times of the day compared to others.

STOP AND THINK. Try to describe the pattern of arrivals at the the toll crossing. Is it random? Random with "a pattern"?

STOP AND THINK. What do we anticipate will be the outputs of a model of this situation?

What are the inputs?

### Example Two

Consider the passport control in San Francisco airport. Suppose that on average it takes 30 seconds to check and stamp the passport of U.S. citizens. Further, suppose that each day approximately 1200 U.S. citizens arrive. This is less than a single immigration officer on each shift can handle (the limit would be 24 hours x 2/minute x 60 minutes/hour = 2880 per day. The problem is 300 of them come in on a flight that lands at 6 p.m. and 300 at 7p.m. So, we begin by assuming, though, that only one immigration officer is on duty.

If all the passengers except these two groups are spread evenly throughout the day, how many arrive per hour on average?

The "rest of the passengers" = 1200 - 300 -300 = 600. If they arrive throughout the day that's 600/24 = 25 per hour.

1. Let’s assume that no one is on line when the 6:00 flight arrives. How many passengers get through immigration before the 7:00 flight lands?
1. It takes 30 seconds per passenger. Three hundred passengers will take 150 minutes — 2.5 hours. In the 60 minutes before the 7:00 p.m. flight lands 120 of them can be processed.
2. Not worrying about the “other” passengers (the one’s arriving throughout the day) how many passengers will there be to serve when the 7:00 p.m. flight lands?
1. From the 6 p.m. flight we'll still have 180 to process.
3. How long will it take to process this group?
1. At 30 seconds each, we'll need another 90 minutes to work through this group.
4. Now how many of the “other” passengers will have arrived while all of this was going on and about how much longer will they add to the time it takes to reduce the lines to zero?
1. Since 25 "other" passengers arrive each hour there will be an extra 25 in line before the people from the 7 p.m. flight get in line. These folks delay things an additional 12.5 minutes. During the 90+12.5 minutes before the first 7 p.m. passenger is processed, another 25x102.5/600=43 additional "other" passengers.
5. What would happen if we added a second immigration officer at 6 p.m.?
6. Together the two officers could process 4 people per minute or 240 total. Still a back up at 7 p.m.
7. What about three officers working at 6:00?
• They could process 6 people per minute and so could do all 300 arrivals (plus the 25 "others") and have the lanes cleared by the time the 7 p.m. flight arrived.
8. Forgetting for the moment about the passengers arriving on other flights, calculate the average wait for passengers on the 6 and 7 pm flights with 1 and with 2 and with 3 immigration officers.

OK. Let's first look at the 300 arriving at 6 p.m. with one officer. Obviously, the first person doesn't wait at all. And then all the rest of the people in line have to wait for all the people in front of them to be processed. The second person waits 30 seconds, the third 60 seconds, and so on. The 300th passenger waits 299*30seconds or about 150 minutes. We could just add all these up and then divide by the 300 people.

There's got to be an easier way.

The 1^st^ passenger waits 0, the 300^th^ passenger waits 299*30 seconds. Together they wait 299*30 seconds. The 2^nd^ passenger waits 30 seconds and the next to last passenger waits 298 x 30 seconds. Together they wait 30 + 298 x 30 = 299 x 30 which is exactly what the first and last wait when we added them together. We can keep doing this until we have 150 pairs of passengers and each pair will wait, in total, 299 x 30 seconds. Thus, the total wait of the entire line is

150 x 299 x 30 seconds = 1,345,500 seconds = 22,425 minutes = 373.5 hours.

If we divide this total among all the people doing the waiting we get 1 hour 14 minutes and 45 seconds (1.245 hours).

Is there a more general expression for this average wait?

Yes, we can simply average the least wait and the most when we have everyone in a nice linear line like this. So, if there are two officers they can handle 4 passengers per minute and the 300th passenger should be processed within 150 minutes. The last passengers will wait 149*30 seconds so the average of her wait and the first passenger (and thus of all the others) will be 37.25 minutes.

And with three officers we expect the 300th passenger to be processed at minute 50. The average wait will be 99*30/2 = 24.75 minutes.

STOP AND THINK. What other variables might we care about? If it's an airport, for example, we might want to know what the maximum length of the line will be (so there is space). And we'll want to know how much time our servers would sit idle during slack periods.

### Theory

In the more general case, new clients arrive randomly, but at known rates that vary over time. On a freeway, for example, cars enter the road at random, but at an average rate during Monday morning rush hour that is relatively constant from week to week. Or the arrival of clients at a legal aid office is random but they come at a known average number on different days of the week. After a client comes through the door we have no way to predict when the next one will come, but we can usually say that if we wait an hour a particular number will come (we just can't say when).

The general name for a process that happens like this is Poisson process after a French mathematician who first wrote about them in the early 1800s.

When a situation is modeled as a Poisson process have a parameter called ''lambda'' that describes the average number of arrivals expected in a given period of time. In our dialysis clinic, for example, we may know that, on average, between 9 a.m. and 10 a.m. 12 clients arrive. Sometimes more, sometimes less. Sometimes they all come at the same time, sometimes they are more spread out.

### How to Read the Poisson Distribution

Here's what the distribution looks like for different values of Lambda. The x-axis is k, the number of arrivals in a given time period. The y-axis is probability. Look first at the violet points — for lambda = 4 (which means, on average, we expect 4 arrivals in the given time period).

Starting from the left, we see that there is a very tiny chance that there will be zero arrivals and about a 7 or 8% chance of there being 1 arrival in the time period. Then there is about a 15% chance of 2, a 20% chance of 3 or 4, a 15% chance of 5 and so on.

This distribution is skewed out to the right because with a low average number (here 4) there's only so much room for events to the left of the average but there's lots of room for rare events (even the probability of having 15 arrive is not zero (though it's really really small)).

Now look at the curve for Lamdba=10. It's practically a "bell curve" around the mean of 10. There appears to be about a 10-12% chance of 9, a little more of 10 and about that same level for 11. Thus, we have something like a 30-40% chance of seeing 9-11 arrivals when the average is ten, but there's still a reasonable chance (5% or so) of getting 4, 5, 15, or 16 arrivals.

'''Cumulative Distribution'''

Often we are interested in not the probability of a given number of arrivals but the accumulated probability of a given number or less. To chart this we start over at the left on the above chart and add up the probabilities. Thus, for Lambda=4 it looks like we have p(k=0) = 0.02 and p(k=1) = 0.07. Thus, the probability of 1 or fewer arrivals is 0.07+0.02=0.09. And what about k=2? Here the probability is about 0.15. Thus, the chance of 0, 1 or 2 arrivals is 0.24. And so on. Eventually, when we are over at k=10, we've used up most of the probability — the chances that we have 10 or fewer arrivals (when the average expected is 4) is almost 100 percent (in other words, there's very little chance of it being more than 10). This cumulative probability ends up looking like an S curve. It picks up slowly at first but then gets really steep around the numbers where the Poisson curve is highest and then starts to slow down and plateau as it nears 100%.

### Examples

Customers/clients arriving at a bank (or hair salon or homeless shelter or employment agency).
Deliveries arriving at a warehouse.

### Problems

In our last lab we looked at an army that was recruiting a fixed number of new members during each time period. We represented this in a table like this:

 Period(t) Trainees[[BR]]Ready[[BR]]To Go Reenlistments S1(t) S2(t) S3(t) S4(t) Total in Army(t) 0 0 0 500 100 100 100 800 1 150 50 200 500 100 100 900 2 150 50 200 200 500 100 1000 3 150 50 200 200 200 500 1100 4 150 250 400 200 200 200 1000 5 150 100 250 400 200 200 1050 6 150 100 250 250 400 200 1100

To convert this into a queuing model we need to do two things. First we play around with the arrival of new recruits. Second we add some service that takes clients out of the system.

### References

http://maths.paisley.ac.uk/jemg/Queuing%20Models.htm

[[File(Gilbert-Troitzsch-queuing-model-Slides.pdf)]]
[[File(Evans Newark.pdf)]]