Queuing Theory

Waiting Line Models ? ? ? ? ? ? ? ? The Structure of a Waiting Line System Queuing Systems Queuing System Input Characteristics Queuing System Operating Characteristics Analytical Formulas Single-Channel Waiting Line Model with Poisson Arrivals and Exponential Service Times Multiple-Channel Waiting Line Model with Poisson Arrivals and Exponential Service Times Economic Analysis of Waiting Lines Slide 1 Structure of a Waiting Line System ? ? Queuing theory is the study of waiting lines. Four characteristics of a queuing system are: †¢the manner in which customers arrive †¢the time required for service the priority determining the order of service †¢the number and configuration of servers in the system. Slide 2 Structure of a Waiting Line System ? ? Distribution of Arrivals †¢Generally, the arrival of customers into the system is a random event. †¢Frequently the arrival pattern is modeled as a Poisson process. Distribution of Service Times †¢Service time i s also usually a random variable. †¢A distribution commonly used to describe service time is the exponential distribution. Slide 3 Structure of a Waiting Line System ? Queue Discipline †¢Most common queue discipline is first come, first served (FCFS). An elevator is an example of last come, first served (LCFS) queue discipline. †¢Other disciplines assign priorities to the waiting units and then serve the unit with the highest priority first. Slide 4 Structure of a Waiting Line System ? Single Service Channel Customer arrives ? Waiting line Multiple Service Channels System S1 Customer leaves System S1 Customer arrives Waiting line S2 Customer leaves S3 Slide 5 Examples of Internal Service Systems That Are Queueing Systems Type of System Customers Server(s) Secretarial services Employees Secretary Copying services Employees Copy machine Computer programming servicesEmployees Programmer Mainframe computer Employees Computer First-aid center Employees Nurse Faxing service s Employees Fax machine Materials-handling system Loads Materials-handling unit Maintenance system Machines Repair crew Inspection station Items Inspector Production system Jobs Machine Semiautomatic machines Machines Operator Tool crib Machine Clerk Slide 6 Examples of Transportation Service Systems That Are Queueing Systems Type of System Customers Server(s) Highway tollbooth Cars Cashier Truck loading dock Trucks Loading crew Port unloading area Ships Unloading crew Airplanes waiting to take off Airplanes RunwayAirplanes waiting to land Airplanes Runway Airline service People Airplane Taxicab service People Taxicab Elevator service People Elevator Fire department Fires Fire truck Parking lot Cars Parking space Ambulance service People Ambulance Slide 7 Queuing Systems ? ? ? ? A three part code of the form A/B/k is used to describe various queuing systems. A identifies the arrival distribution, B the service (departure) distribution and k the number of channels for the system. Sym bols used for the arrival and service processes are: M – Markov distributions (Poisson/exponential), D – Deterministic (constant) and G – General istribution (with a known mean and variance). For example, M/M/k refers to a system in which arrivals occur according to a Poisson distribution, service times follow an exponential distribution and there are k servers working at identical service rates. Slide 8 Queuing System Input Characteristics = 1/? =  µ= 1/ µ = = the average arrival rate the average time between arrivals the average service rate for each server the average service time the standard deviation of the service time Slide 9 Queuing System Operating Characteristics P0 = Pn = Pw = Lq = probability the service facility is idle robability of n units in the system probability an arriving unit must wait for service average number of units in the queue awaiting service L = average number of units in the system Wq = average time a unit spends in the queu e awaiting service W = average time a unit spends in the system Slide 10 Analytical Formulas ? ? For nearly all queuing systems, there is a relationship between the average time a unit spends in the system or queue and the average number of units in the system or queue. These relationships, known as Little's flow equations are: L = ? W and Lq = ? Wq Slide 11 Analytical Formulas ? ?When the queue discipline is FCFS, analytical formulas have been derived for several different queuing models including the following: †¢M/M/1 †¢M/M/k †¢M/G/1 †¢M/G/k with blocked customers cleared †¢M/M/1 with a finite calling population Analytical formulas are not available for all possible queuing systems. In this event, insights may be gained through a simulation of the system. Slide 12 M/M/1 Queuing System ? ? ? ? ? ? Single channel Poisson arrival-rate distribution Exponential service-time distribution Unlimited maximum queue length Infinite calling population Examples: †¢Single-window theatre ticket sales booth Single-scanner airport security station Slide 13 Notation for Single-Server Queueing Models ? ? = Mean arrival rate for customers = Expected number of arrivals per unit time 1/? = expected interarrival time ? m = Mean service rate (for a continuously busy server) = Expected number of service completions per unit time 1/m = expected service time ? r = the utilization factor = the average fraction of time that a server is busy serving customers = /? m Slide 14 ? Assumptions 1. Interarrival times have an exponential distribution with a mean of 1/?. 2. Service times have an exponential distribution with a ean of 1/m. 3. The queueing system has one server. †¢ The expected number of customers in the system is L = r? /? (1 –? r) = /? (m? – ? )? †¢ The expected waiting time in the system is W = (1 / ? )L = 1 / (m – ? ) †¢ The expected waiting time in the queue is Wq = W – 1/m = ? / [m(m – ? )] â⠂¬ ¢ The expected number of customers in the queue is Lq = ? Wq = ? 2 / [m(m – ? )] = r2 / (1 – r) Slide 15 ? The probability of having exactly n customers in the system is Pn = (1 – r)rn Thus, P0 = 1 – r P1 = (1 – r)r P2 = (1 – r)r2 : : ? The probability that the waiting time in the system exceeds t is P(W ; t) = e–m(1–r)t for t ? ? The probability that the waiting time in the queue exceeds t is P(Wq ; t) = re–m(1–r)t for t ? 0 Slide 16 Problem: ? Consider the situation where the mean arrival rate is one customer every 4 minutes and the mean service time is 2. 5 minutes. Calculate the following †¢Average no. of customer in the system †¢Average queue length †¢Average time a customer spends in the system †¢Average time a customer waits before being served. Slide 17 Problem: ? ? ? Arrivals at a telephone booth are considered to be Poisson, with an average time of 10 minutes between one arrival an d the next. The length of a phone call is ssumed to be exponentially distributed with mean 3 minutes. What is the probability that a person arriving at the booth will have to wait? The telephone department will install a second booth when convinced that an arrival would expect to have to wait at least three minutes for the phone. By how much must the flow of arrivals be increased in order to justify a second booth? Slide 18 Example: SJJT, Inc. (A) ? M/M/1 Queuing System Joe Ferris is a stock trader on the floor of the New York Stock Exchange for the firm of Smith, Jones, Johnson, and Thomas, Inc. Stock transactions arrive at a mean rate of 20 per hour.Each order received by Joe requires an average of two minutes to process. Orders arrive at a mean rate of 20 per hour or one order every 3 minutes. Therefore, in a 15 minute interval the average number of orders arriving will be ? = 15/3 = 5. Slide 19 Example: SJJT, Inc. (A) ? Arrival Rate Distribution Question What is the probability that no orders are received within a 15-minute period? Answer P (x = 0) = (50e -5)/0! = e -5 = .0067 Slide 20 Example: SJJT, Inc. (A) ? Arrival Rate Distribution Question What is the probability that exactly 3 orders are received within a 15-minute period? Answer P (x = 3) = (53e -5)/3! 125(. 0067)/6 = . 1396 Slide 21 Example: SJJT, Inc. (A) ? Arrival Rate Distribution Question What is the probability that more than 6 orders arrive within a 15-minute period? Answer P (x ; 6) = 1 – P (x = 0) – P (x = 1) – P (x = 2) – P (x = 3) – P (x = 4) – P (x = 5) – P (x = 6) = 1 – . 762 = . 238 Slide 22 Example: SJJT, Inc. (A) ? Service Rate Distribution Question What is the mean service rate per hour? Answer Since Joe Ferris can process an order in an average time of 2 minutes (= 2/60 hr. ), then the mean service rate,  µ, is  µ = 1/(mean service time), or 60/2. m = 30/hr. Slide 23 Example: SJJT, Inc. (A) ?Service Time Distribution Ques tion What percentage of the orders will take less than one minute to process? Answer Since the units are expressed in hours, P (T ; 1 minute) = P (T ; 1/60 hour). Using the exponential distribution, P (T ; t ) = 1 – e- µt. Hence, P (T ; 1/60) = 1 – e-30(1/60) = 1 – . 6065 = . 3935 = 39. 35% Slide 24 Example: SJJT, Inc. (A) ? Service Time Distribution Question What percentage of the orders will be processed in exactly 3 minutes? Answer Since the exponential distribution is a continuous distribution, the probability a service time exactly equals any specific value is 0 . Slide 25Example: SJJT, Inc. (A) ? Service Time Distribution Question What percentage of the orders will require more than 3 minutes to process? Answer The percentage of orders requiring more than 3 minutes to process is: P (T ; 3/60) = e-30(3/60) = e -1. 5 = . 2231 = 22. 31% Slide 26 Example: SJJT, Inc. (A) ? Average Time in the System Question What is the average time an order must wait from th e time Joe receives the order until it is finished being processed (i. e. its turnaround time)? Answer This is an M/M/1 queue with ? = 20 per hour and m = 30 per hour. The average time an order waits in the system is: W = 1/( µ – ? ) 1/(30 – 20) = 1/10 hour or 6 minutes Slide 27 Example: SJJT, Inc. (A) ? Average Length of Queue Question What is the average number of orders Joe has waiting to be processed? Answer Average number of orders waiting in the queue is: Lq = ? 2/[ µ( µ – ? )] = (20)2/[(30)(30-20)] = 400/300 = 4/3 Slide 28 Example: SJJT, Inc. (A) ? Utilization Factor Question What percentage of the time is Joe processing orders? Answer The percentage of time Joe is processing orders is equivalent to the utilization factor, ? /m. Thus, the percentage of time he is processing orders is: ?/m = 20/30 = 2/3 or 66. 67% Slide 29 Example: SJJT, Inc. A) Solution ? 1 2 3 4 5 6 7 8 9 A B C D E F Poisson Arrival Rate Exponential Service Rate Operating Character istics Probability of no orders in system Average number of orders waiting Average number of orders in system Average time an order waits Average time an order is in system Probability an order must wait G ? m H 20 30 Po Lg L Wq W Pw 0. 333 1. 333 2. 000 0. 067 0. 100 0. 667 Slide 30 M/M/k Queuing System ? ? ? ? ? ? Multiple channels (with one central waiting line) Poisson arrival-rate distribution Exponential service-time distribution Unlimited maximum queue length Infinite calling population Examples: Four-teller transaction counter in bank †¢Two-clerk returns counter in retail store Slide 31 1 ? P? n ? m ? P0 , for (n ? k) ? n! ? ? n ? ? m ? P0 , for (n ? k) ? ? ? 1 n k ? 1 1 km ? ? ? ? n! ? m ? ? k! ? m ? km ? ? ? ? ? 1 ? k! k n ? k P? 0 P w ? n ? k ? 1 ? n ? 0 ? n 1 ? ? P(n ? k ) ? ?m? ? k! ? ? k km P0 , km ? ? k ?m ? ? m ? ? ? ? ? ? L? P0 ? 2 m (k ? 1)! (km ? ? ) W? L ? , Lq ? ,r ? km Lq ? 1 ? L? , Wq ? W ? ? m m ? Slide 32 General Operating Characteristics Little' s F low Equations : L (or W ? ) ? Lq (or Wq ? ) ? L ? ?W L q ? ?Wq W ? Wq ? 1 m Slide 33 Problem: ? ? ? ? ? ? ? ?A Tax consulting firm has four service stations (counters) in its office to receive people who have problems and complaints about their income, wealth and sales taxes. Arrivals average 80 persons in an 8 hour service day. Each tax advisor spends irregular amount of time servicing the arrivals which have been found to have an exponential distribution. The average service time is 20 minutes. Calculate the average no. of customers in the system, average no. of customers waiting to be serviced, average time a customer spend in the system, average waiting time for a customer in queue. Calculate how many hours each week does a tax advisor spend erforming his job? What is the probability that a customer has to wait before he gets service? What is the expected no. of idle tax advisors at any specified time? Slide 34 Example: SJJT, Inc. (B) ? M/M/2 Queuing System Smith, Jones, Joh nson, and Thomas, Inc. has begun a major advertising campaign which it believes will increase its business 50%. To handle the increased volume, the company has hired an additional floor trader, Fred Hanson, who works at the same speed as Joe Ferris. Note that the new arrival rate of orders, ? , is 50% higher than that of problem (A). Thus, ? = 1. 5(20) = 30 per hour. Slide 35Example: SJJT, Inc. (B) ? Sufficient Service Rate Question Why will Joe Ferris alone not be able to handle the increase in orders? Answer Since Joe Ferris processes orders at a mean rate of  µ = 30 per hour, then ? =  µ = 30 and the utilization factor is 1. This implies the queue of orders will grow infinitely large. Hence, Joe alone cannot handle this increase in demand. Slide 36 Example: SJJT, Inc. (B) ? Probability of n Units in System Question What is the probability that neither Joe nor Fred will be working on an order at any point in time? Slide 37 Example: SJJT, Inc. (B) ? Probability of n Units in Sy stem (continued)Answer Given that ? = 30,  µ = 30, k = 2 and (? / µ) = 1, the probability that neither Joe nor Fred will be working is: 1 P0 ? k ? 1 ( ? / m )n (? / m ) k km ? ( ) ? n! k! km ? ? n? 0 = 1/[(1 + (1/1! )(30/30)1] + [(1/2! )(1)2][2(30)/(2(30)-30)] = 1/(1 + 1 + 1) = 1/3 = .333 Slide 38 Example: SJJT, Inc. (B) ? Average Time in System Question What is the average turnaround time for an order with both Joe and Fred working? Slide 39 Example: SJJT, Inc. (B) ? Average Time in System (continued) Answer The average turnaround time is the average waiting time in the system, W. Lq = ? µ(? / µ)k (k-1)! (k µ – ? )2 P0 = (30)(30)(30/30)2 (1! ((2)(30)-30))2 (1/3) = 1/3 L = Lq + (? / µ) = 1/3 + (30/30) = 4/3 W = L/ (4/3)/30 = 4/90 hr. = 2. 67 min. Slide 40 Example: SJJT, Inc. (B) ? Average Length of Queue Question What is the average number of orders waiting to be filled with both Joe and Fred working? Answer The average number of orders waiting to be filled is Lq. This was calculated earlier as 1/3 . Slide 41 Example: SJJT, Inc. (B) ? Formula Spreadsheet 1 2 3 4 5 6 7 8 9 10 A B C D E F Number of Channels Mean Arrival Rate (Poisson) Mean Service Rate (Exponential ) Operating Characteristics Probability of no orders in system Average number of orders waitingAverage number of orders in system Average time (hrs) an order waits Average time (hrs) an order is in system Probability an order must wait G k ? m H 2 30 30 Po =Po(H1,H2,H3) Lg ## L =H6+H2/H3 Wq =H6/H2 W =H8+1/H3 Pw =H2/H3 Slide 42 Example: SJJT, Inc. (B) ? Spreadsheet Solution 1 2 3 4 5 6 7 8 9 10 A B C D E F Number of Channels Mean Arrival Rate (Poisson) Mean Service Rate (Exponential ) Operating Characteristics Probability of no orders in system Average number of orders waiting Average number of orders in system Average time (hrs) an order waits Average time (hrs) an order is in system Probability an order must waitG k ? m H 2 30 30 Po Lg L Wq W Pw 0. 333 0. 333 1. 333 0. 011 0. 044 1 . 000 Slide 43 Example: SJJT, Inc. (C) ? Economic Analysis of Queuing Systems The advertising campaign of Smith, Jones, Johnson and Thomas, Inc. (see problems (A) and (B)) was so successful that business actually doubled. The mean rate of stock orders arriving at the exchange is now 40 per hour and the company must decide how many floor traders to employ. Each floor trader hired can process an order in an average time of 2 minutes. Slide 44 Example: SJJT, Inc. (C) ? Economic Analysis of Queuing Systems Based on a number of factors the brokerage firm as determined the average waiting cost per minute for an order to be $. 50. Floor traders hired will earn $20 per hour in wages and benefits. Using this information compare the total hourly cost of hiring 2 traders with that of hiring 3 traders. Slide 45 Example: SJJT, Inc. (C) ? Economic Analysis of Waiting Lines Total Hourly Cost = (Total salary cost per hour) + (Total hourly cost for orders in the system) = ($20 per trader per hour) x (Number of traders) + ($30 waiting cost per hour) x (Average number of orders in the system) = 20k + 30L. Thus, L must be determined for k = 2 traders and for k = 3 traders with ? = 40/hr. nd m = 30/hr. (since the average service time is 2 minutes (1/30 hr. ). Slide 46 Example: SJJT, Inc. (C) ? Cost of Two Servers P0 ? 1 k ? 1 (? ? n? 0 / m )n ( ? / m ) k km ? ( ) n! k! km ? ? P0 = 1 / [1+(1/1! )(40/30)]+[(1/2! )(40/30)2(60/(60-40))] = 1 / [1 + (4/3) + (8/3)] = 1/5 Slide 47 Example: SJJT, Inc. (C) ? Cost of Two Servers (continued) Thus, Lq = ? µ(? / µ)k (k-1)! (k µ -? )2 P0 = (40)(30)(40/30)2 1! (60-40)2 (1/5) = 16/15 L = Lq + (? / µ) = 16/15 + 4/3 = 12/5 Total Cost = (20)(2) + 30(12/5) = $112. 00 per hour Slide 48 Example: SJJT, Inc. (C) ? Cost of Three Servers P0 ? 1 k ? 1 (? ? n? 0 / m )n ( ? / m ) k km ( ) n! k! km ? ? P0 = 1/[[1+(1/1! )(40/30)+(1/2! )(40/30)2]+ [(1/3! )(40/30)3(90/(90-40))] ] = 1 / [1 + 4/3 + 8/9 + 32/45] = 15/59 Slide 49 Example: SJJT, Inc. (C) ? Cost of Three Servers (continued) (30)(40)(40/30)3 Hence, Lq = (15/59) = 128/885 = . 1446 (2! )(3(30)-40)2 Thus, L = 128/885 + 40/30 = 1308/885 (= 1. 4780) Total Cost = (20)(3) + 30(1308/885) = $104. 35 per hour Slide 50 Example: SJJT, Inc. (C) ? System Cost Comparison 2 Traders 3 Traders Wage Cost/Hr $40. 00 60. 00 Waiting Cost/Hr $82. 00 44. 35 Total Cost/Hr $112. 00 104. 35 Thus, the cost of having 3 traders is less than that of 2 traders. Slide 51