Home > Queuing Theory I

Page 1 |

Queuing Theory I

© 2006 Samuel L. Baker

Page 2 |

Queue factors: 1. how many queues one or more than one 2. service priority among customers first come first served is most common other possibilities: random, customers with shorter service time go first, triage and priority assignment, with or without preemption of customers already being served 3. customer behavior in queue balking -- customers don't join line that's too long reneging -- customers quit line if wait gets too long bounded queue -- waiting list can only be so long Some flow charts of queues: Single-Server Single-Stage Queue Arrivals ---> Queue ---> Service ---> Done Several Single Server Single Stage Queues in Parallel Arrivals ---> Queue ---> Service ---> Done Arrivals ---> Queue ---> Service ---> Done Arrivals ---> Queue ---> Service ---> Done Multiple Server Single Stage Queue

+)> Service ---> Done

Arrivals ---> Queue )3)> Service ---> Done

.)> Service ---> Done

Single Server Multiple Stage Queue Arrivals ---> Queue ---> Service ---> Service ---> Service ... - --> Done The Multiple Stage model is like a cafeteria, in which customers waiting to get their main dishes may prevent customers behind them from getting their salads. Single Server Queues in Series Arrivals ---> Queue ---> Service ---> Queue ---> Service ... --- > Done The Queues-in-Series model has queues between the stages of service, which the Multiple Stage model does not. This might be appropriate for a doctor��s office. Patient wait in the waiting room until seen by a nurse. Then they wait again in examining rooms until the doctor arrives.

Page 3 |

The Poisson distribution is good to use if the arrivals are all random and independent of each other. For the

Page 4 |

Here��s an explanation of the formula =EXP(-$B$3)*$B$3^A6/FACT(A6) in B6: EXP is the Excel function for raising e to a power. =EXP(-$B$3) means e , which is e , since -

-$B$3 -��t

��t is in B3. The dollar signs keep the cell reference on B3 when the formula is copied and pasted to another cell. The caret symbol ^ is for raising a number to a power. $B$3^A6 means ($B$3) , which means

A6

(��t) .x The FACT function (@FACT in Quattro Pro) calculates factorials. Here, it is calculating x!, the factorial of the x value in column A. The formula in the C column, starting with C7, gives a running total of the P of x's. Each cell is the cell above, which is the previous total, plus the cell to the left, the current P of x. When you are constructing the table of probabilities in the spreadsheet: 1. Fill in row 6 as shown. 2. In A7, type =A6+1 as shown. 3. Copy cell B6 and paste to B7. 4. In C7, type =B7+C6 as shown. That should give you row 7 complete as in the diagram above. 5. Copy A7:C7. Paste to a range starting in A8 and extending down the A column as far down as you want. (For the homework, you��ll want to go down about twenty rows.) Here are the numbers I see after I copy A7:C7 to A8:A24. As mentioned, Column B, rows 6 and below, gives us probability of x events happening, for values of x from 0 to 18. For instance, cell B14 tells us that the probability of exactly 8 arrivals in the next two hours is 0.139587. Column C is a running total of B, the probability that x or fewer events happen, for values of x from 0 to 18. Cell C14 tells us that the probability of 0 through 8 arrivals is 0.592547. As x increases from 0, the probability of exactly x events rises at first. The probability is highest at x = ��t-1 and x = ��t, which in this example is x = 7 and x = 8. For higher values of x, the probability of x diminishes, approaching 0 as x gets very large. As x increases, the probability of x or fewer events rises, approaching 1 as x gets very large. The Poisson distribution is skewed. It's not symmetrical about its mean. The probability of 7 or less arrivals (.453) is greater

Page 5 |

than the probability of 9 or more arrivals (.407 = 1-.593). The average of the distribution is 8, because of the possibility of a very large number of arrivals. This is a graph of the P of x numbers in column B. The shape is a skewed bell. The right tail is larger than the left tail. The degree of skewness depends on ��t. The larger ��t is, the more the Poisson distribution approaches the normal distribution, which has a symmetrical bell shape. The Poisson distribution is a limiting case of the binomial distribution. That means that you are making two important assumptions when you use the Poisson: 1.

Page 6 |

We use the Poisson distribution to model how often people come to the drug store to buy a prescription. We can see how much inventory the pharmacists will need under different assumptions about the size of purchases and how often they happen. Best for the pharmacist, as far as inventory need is concerned, would be if the purchases were on a strict schedule. If the pharmacist knows when every customer is going to appear and what the customer will buy, little or no inventory is required. The pharmacist could arrange to have the drugs delivered just before the patient comes in to buy them. If the patients�� purchases are randomly timed, however, inventory is required. How much inventory? The store does not want to turn away customers, so it wants enough inventory to make running out unlikely. No level of inventory is enough to be 100% sure of never running out, but the more inventory a store has, the less likely it is to run out. There is a cost to inventory, however. Goods on the shelf have to be bought. Inventory is capital. The more inventory a store keeps, the higher is the store��s cost of operating. We will assume for this example that the pharmacist will settle for a 95% probability of having enough stock on hand to satisfy the customers. In other words, the pharmacist will tolerate a 5% chance of running out on any given day. To simplify the numbers as much as possible, suppose that a pharmacy's customers switch from buying one bottle of pills per month to buying three bottles at once, but only once every three months. Suppose that the pharmacy has enough customers so that it sells an average of three bottles per day, both before and after the policy change. We also assume that the pharmacy gets one shipment per day. Every night, after closing, the store places an order. The shipment arrives the next morning, before the store opens. Here is the Poisson model for three 1-bottle sales per day. Lambda is 3, expected bottles sold per day. The time period t is 1, for 1 day. A B C D 1 Lambda x P of x P of <=x 2 3 0 0.049787 0.049787 3 t 1 0.149361 0.199148 4 1 2 0.224042 0.423190 5 Lambda*t 3 0.224042 0.647232 6 3 4 0.168031 0.815263 7 5 0.100819 0.916082 8 6 0.050409 0.966491 Look down the running total of the probabilities in column D and find the first number that is bigger than 0.95. That number, 0.966491, is in the row where x is 6, so 0.966491 is the probability that 6 or fewer customers will arrive. This means that the pharmacist needs to start the day with 6 bottles in inventory to make the probability of running out less than 5%. Now let��s model one sale per day, with three bottles in each sale. We still expect to sell three bottles per day, but now the sales are in three-bottle lumps. Lambda is now 1, because the expected rate of sales is 1 three-bottle order per day.

Page 7 |

In the table below, x is the number of sales events. x is not the number of bottles in the table below, as it was in the table above, because each sale is a sale of three bottles. A B C D 1 Lambda x P of x P of <=x 2 1 0 0.367879 0.367879 0 bottles 3 t 1 0.367879 0.735759 3 bottles 4 1 2 0.183940 0.919699 6 bottles 5 Lambda*t 3 0.061313 0.981012 9 bottles 6 1 Look down the running total of the probabilities in column D and find the first number that is bigger than 0.95. This time, it is 0.981012, in the row for x=3. The pharmacist has to be prepared for three sales events, if he or she wants at least a 95% chance of not running out. Three sales means nine bottles. The pharmacist needs to start the day with 9 bottles in inventory to make the probability of running out less than 5%. Lumpy sales increases the inventory required from six bottles to nine. That adds capital cost, cutting into the profit that the pharmacist makes selling to Medicaid patients. That is why the pharmacists were unhappy with the change.

-1

This result may surprise you. Many people expect the answer to be ½. The actual probability is greater than ½ because the exponential distribution is skewed, as the Poisson is. Another exponential distribution calculation example: Suppose �� is 4. The probability that the next arrival will come in the next 0.25 and 0.5 hours is calculated by subtracting the probability that the next arrival will come sooner than 0.25 hours from the probability that the next arrival will come sooner than 0.5 hours.

Page 8 |

( 1 - e ) - ( 1 - e ) =

-4��0.5 -4��0.25

.8646647 - .6321206 = .2325442 The mean of the exponential distribution is 1/��. If we expect 4 events per hour, then the expected interval between events is ¼ of an hour. This does make intuitive sense. Your turn:

Page 9 |

Page 10 |

Steady state formulas for a single-server single-stage queue with Poisson distribution arrivals, exponential distribution service times, first-come first-served queue discipline, drawing on an infinite population (so the future arrival rate does not depend on the past arrival rate). The probability of any given number of customers being in the system (waiting or being served): L is the average number of customers in the system, waiting in queue or being served:

q

L is the average number of customers waiting in the queue: W is the average time customers spend in system, waiting plus being served:

q

W is the average time a customer spends in waiting in queue before service starts: Some interpretation: These formulas imply that you can tell how busy the server is just by watching the length of the line.

q

That's because L can be calculated from ��, the server utilization factor, the proportion of the time that the

q

server is busy. For example, if you see that there two people in line, on average, then L = 2 = �� /(1-��).

2

Solve that for �� , and you get �� = 0.732..., so the server is busy almost three-fourths of the time. Be careful about trying this is practice, though, especially if your impression of the length of the line is from your

q

casual observation. When you look, the line is more likely to be shorter than L than it is to be longer than

q

L . That��s because the distribution is skewed. Every so often, the line will get very long, and that��s what

q

brings the average length up to L .

q

Notice that L is L-��, not L-1. When there is someone being served, the number of people in the system is

Page 11 |

one plus the number in the queue, but the average number of people in line is L-��, which is more than L-1. This allows for those times when no one is being served or waiting. If that��s hard to grasp, think of it the

q q

other way around: L is L + ��, not L + 1, because when no one is in the system, the number of people in the system and the number of people waiting are both 0. The probability of no one in the system is 1 - ��. So, 1 - �� of the time, the system and the queue are the same (zero) and �� of the time, the system has one more person it in (the person being served) than the number of people waiting. On average the number of people in the system is �� more than the number of people waiting.

2

Probability (2 or fewer in system) = P(0) + P(1) + P(2) = 0.7037 Probability (3 or more in system) = 1 - ( Probability(2 or fewer in the system) = 1 - 0.7037 = 0.2963 If you have just two chairs, then almost 30% of the time there will be someone standing. Calculating line length and waiting times:

Page 12 |

L, the average number of customers waiting or being served = ��/(1-��) = 2 persons.

q

L , the average number of customers waiting in the queue = L-�� = 1.333 persons. W, the average time in system, = 1/(��-��) = 0.2 person-hours/order.

q

W , the average time in queue, = ��W = 0.1333 person-hours/order.

Method 1 Formula

When the formula is written out this way, with the units, you can see how the units multiply out. Person-hours/order times orders/hour times dollars/person-hour = dollars/hour Method 2: (First thought of by a student, not me.) On average, you have L aides in the pharmacy. Here L = 2 persons. They cost you their pay rate, $8 per person-hour, while they are there. Your hourly cost is L �� pay rate = 2 persons �� 8 $/person-hour = 16 $/hour.

Method 2 Formula

The units in this formula multiply out properly if you treat the hyphen in person-hour as multiplication (which it is) rather than subtraction. Now that we have figured out that we are losing an average of $16 per hour thanks to aides waiting, we can evaluate proposals to save some of that time. Suppose automated dispensing equipment could cut service time in half, but it costs $7 per hour to own and operate. Would it be worth buying? To find the answer double ��, recalculate W (if using Method 1) or L (if using Method 2), and then redo the

Page 13 |

hourly cost calculation. Then see if the cost savings is bigger than the hourly cost of the machine. Here is how: �� was 15; it will be 30 if we buy the new equipment. Method 1: W = 1/(��-��) = 1/(30-10)=1/20=0.05 W��8 = 0.05��10��8=4 Method 2 L = ��/(��-��) = 10/(30-10)=10/20 =0.5 L8 = 0.5��8 = 4 Hourly costs fall to $4 from $16. We save $12, so we come out ahead by $5 per hour if we pay $7 per hour for the equipment. Your turn again:

- ~The Marquee~
- Administrative Manual for Implementation of the Post Construction Storm Water Ordinance
- Presentation title: Frutiger 55 Roman, 14 pt.,, two lines maximum with 1.04 Line Spacing (17 points)
- The Science of Everyday Negotiations
- The Architecture and Evolution of CPU-GPU Systems for General Purpose Computing Manish Arora Computer Science and Engineering University of
- 1 How To: Outlining a Research Paper Note for students: This document was prepared by Dr Amy Stuart for a class in which she req
- Lab Assignment 3 (Skeleton Draft)
- Korogard® R400-Series Recess Mounted Corner Guards
- THE HONOURS PROGRAM
- EERA Proposal form
- WRITING THE GRIEVANCE ARBITRATION BRIEF
- News Coverage of the Enlargement of the European Union and Public Opinion:
- JUDICIOUS DISCIPLINE
- HONG KONG BAPTIST UNIVERSITY
- Teachers�� Code of Ethics and Practice
- KEMIKAALIN YMPÄRISTÖRISKIN ARVIOINTI
- aasmus - dychawica oskrzelowa, astma
- 10 - Cyberspace Law materials - Copyright
- Customer Service Avenues for VAWA, T and U Related Filings:
- A PROGRAMMER'S GUIDE TO THE MACH USER ENVIRONMENT Linda R. Walmer Mary R. Thompson
- Louis Database of Accessible Materials for People Who Are Blind or

- Army
- ideological and political work
- modernization
- Teaching Assistance Network System
- WWW
- ASP
- Organ transplantation
- The patients
- The offers
- Ethical basis
- Personality identification
- performance measurement
- Telecom carrier
- the Balance Scorecard
- IT Scorecard
- Porous media
- Permittivity
- Porosity
- Fractal
- Lens design
- Local features

All Rights Reserved Powered by Free Document Search and Download

Copyright © 2011This site does not host pdf,doc,ppt,xls,rtf,txt files all document are the property of their respective owners. complaint#nuokui.com