Report

Readings Readings Chapter 11, Sections 1, 2, 3, 5 Waiting Line Models BA 452 Lesson B.7 Waiting Line Predictions 1 Overview Overview BA 452 Lesson B.7 Waiting Line Predictions 2 Overview Exponential Probability is a continuous probability distribution (the probability of hitting any single value is zero, like a dart hitting a single point). It models the time between independent events. Poisson Probability is a discrete probability distribution of the number of events occurring in a fixed period of time if those events occur independently, with a known average rate. Structure of a Waiting Line System has four characteristics: customer arrivals, service time, the order of service (like first-come, first-served), the number and configuration of servers in the system. Analytical Formulas for operating characteristics (average units in system, average time in the system, …) have been derived, under the queue discipline first-come, first-served, for several queuing models. M/M/1 Queuing System designates M = Markov (memoryless) arrival distribution (Poisson), M = Markov service-time distribution (exponential), and 1 service channel, under first-come, first-served. BA 452 Lesson B.7 Waiting Line Predictions 3 Exponential Probability Exponential Probability BA 452 Lesson B.7 Waiting Line Predictions 4 Exponential Probability Overview Exponential Probability is a continuous probability distribution (the probability of hitting any single value is zero, like a dart hitting a mathematical point). In general, it models the time between independent events that can happen at a constant average rate. BA 452 Lesson B.7 Waiting Line Predictions 5 Exponential Probability How many servers should be available at Malibu Yogurt? What do you need to know about Malibu Yogurt to answer? Three things: First, how long does it take to serve customers? That is a random variable. The customer may be indecisive; the yogurt machine may be slow; … . We often use an exponential distribution for service times. Second, how many customer arrivals do you expect? That is another random variable. Even regular customers may be stuck in traffic; … We often use a Poisson distribution for arrival times. Third, how valuable is your customers’ time? (Malibu attracts wealthy customers, so you want to have enough servers so customers do not have to wait long.) BA 452 Lesson B.7 Waiting Line Predictions 6 Exponential Probability The exponential is a continuous probability distribution (the probability of hitting any single value is zero, like a dart hitting a mathematical point). In general, it models the time between independent events that can happen at a constant average rate. The probability density function (pdf) of an exponential distribution is f(t) = µe-µt for variables t in the interval [0,∞). Often, t is an instant in time. f(t) can thus be the instantaneous (infinitesimal) probability that a customer takes exactly t units of time to serve. The cumulative distribution function is P(T < t ) = 1 - e-µt (that is, f(t) integrated from 0 to t) for variables t in [0,∞). P(T < t ) can thus model the probability that a customer can be served in t units of time or less. P(T < t ) = P(T < t ). BA 452 Lesson B.7 Waiting Line Predictions 7 Exponential Probability µ > 0 is the distribution’s only parameter, often called the rate parameter. A higher µ means events occur more quickly. Thus consider the probability density functions for rate parameters µ = 0.5, µ = 1.5, µ = 1.5: µ = 0.5 µ = 1.0 µ = 1.5 The expected value of the exponential distribution (the integral of tf(t)) is 1/µ. The variance (the integral of (t- 1/µ) 2f(t)) is 1/µ2. BA 452 Lesson B.7 Waiting Line Predictions 8 Exponential Probability We will assume that customers’ service times have an exponential probability distribution. Why? That is, why assume P(T < t ) = 1 - e-µt is the probability that a customer can be served in t units of time or less? One good reason is the exponential probability function has only a single parameter, and that parameter, µ, is the rate of customer service. One bad reason is the exponential attaches positive probability to even unreasonably large service times (like 2 billion years) or to small times (like 1 second). One other property, which may be a good or a bad reason to assume exponential probability (depending on the type of service) is the exponential probability distribution is memoryless. BA 452 Lesson B.7 Waiting Line Predictions 9 Exponential Probability Exponential probability is the only continuous probability distribution that is memoryless. For example, its conditional probability obeys P(T > 40 | T > 30) = P(T > 10) That is, the probability that you have to wait more than another 10 seconds before your service is completed (your Malibu yogurt is ready), given that you already had to wait 30 seconds, is no different from the initial probability that you have to wait more than 10 seconds after you first arrive for service. Is that realistic? When you hang up on a 30-minute phone transaction and decide to save time by calling back later, you believe P(T > 40 | T > 30) is greater than P(T > 10) BA 452 Lesson B.7 Waiting Line Predictions 10 Exponential Probability In the simplest waiting-line models, customers’ service time is assumed to have an exponential probability distribution. The time between the arrival of each new customer is also assumed to be an exponential variable. In particular, P(T > 40 | T > 30) = P(T > 10) means the probability that you have to wait more than another 10 minutes before a new customer comes in for service, given that you already had to wait 30 minutes, is no different from the initial probability that you have to wait more than 10 minutes before a new customer comes in for service. Is that realistic? When you close your store early because you have not had any customers for 30 minutes, and decide to start fresh tomorrow, you believe P(T > 40 | T > 30) is greater than P(T > 10) BA 452 Lesson B.7 Waiting Line Predictions 11 Poisson Probability Poisson Probability BA 452 Lesson B.7 Waiting Line Predictions 12 Poisson Probability Overview Poisson Probability is a discrete probability distribution that expresses the probability of a number of events occurring in a fixed period of time if those events occur with a known average rate, and are independent of the time since the last event. BA 452 Lesson B.7 Waiting Line Predictions 13 Poisson Probability An alternative and equivalent way to measure the time between the arrival of each new customer is to measure the probability f(k) that a number k of customers arrives within a fixed period of time. When the time between arrivals has an exponential distribution, the probabilities f(k) have a Poisson distribution. In general, the Poisson distribution is a discrete probability distribution that expresses the probability of a number of events occurring in a fixed period of time if those events occur with a known average rate, and are independent of the time since the last event. The probability mass function of a Poisson distribution has the form f(k) = k e-/k! for non-negative integers k = 0, 1, … , where k is the number of events that occur, and k! is the factorial of k (for example, 3! = 3x2x1, … .). BA 452 Lesson B.7 Waiting Line Predictions 14 Poisson Probability > 0 is the Poisson distribution’s parameter, often called its arrival rate. equals the distribution’s expected value; it equals the expected number of arrivals that occur during the given interval. A higher means arrivals can occur more quickly. Thus consider the probability mass functions for parameters = 1, = 4, = 10: =1 =4 = 10 BA 452 Lesson B.7 Waiting Line Predictions 15 Structure of a Waiting Line System Structure of a Waiting Line System BA 452 Lesson B.7 Waiting Line Predictions 16 Structure of a Waiting Line System Overview The Structure of a Waiting Line System has four characteristics: the manner in which customers arrive (the simplest case is a random variable with a Poisson distribution) the time required for service (the simplest case is a random variable with an exponential distribution) the priority determining the order of service (the most common is first come, first served; it has less waiting variance than first come, last served) the number and configuration of servers in the system. BA 452 Lesson B.7 Waiting Line Predictions 17 Structure of a Waiting Line System The order of service • Most common queue discipline is first come, first served (FCFS). • An elevator is an example of last come, first served (LCFS) queue discipline (because the last one on is the first one off). • Other disciplines assign priorities to the waiting units and then serve the unit with the highest priority first. BA 452 Lesson B.7 Waiting Line Predictions 18 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 BA 452 Lesson B.7 Waiting Line Predictions 19 Structure of a Waiting Line System A three part code A/B/k describes various queuing systems. A identifies the arrival distribution, B the service (departure) distribution, and k the number of channels for the system. Symbols used for the arrival and service processes are: M = Markov (memoryless) distributions (Poisson/exponential), D = Deterministic (constant), and G = General distribution (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. BA 452 Lesson B.7 Waiting Line Predictions 20 Structure of a Waiting Line System So, how well is Malibu Yogurt serving customers? Determine 1) 2) 3) 4) 5) 6) 7) The probability of no units in the system: P0 The average number of units in the waiting line: Lq The average number of units in the system: L The average time a unit spends in the waiting line: Wq The average time a unit spends in the system: W The probability that an arriving unit has to wait: Pw Probability of n units in the system: Pn BA 452 Lesson B.7 Waiting Line Predictions 21 Analytical Formulas Analytical Formulas BA 452 Lesson B.7 Waiting Line Predictions 22 Analytical Formulas Overview Analytical Formulas for operating characteristics (average units in system, average time in the system, …) have been derived, under the queue discipline FCFS, for several different queuing models including the following: • M/M/1 • M/M/k Analytical formulas are not available for all possible queuing systems. With no formula, insights may be gained through a simulation of the system (starting with our Lesson III.1). BA 452 Lesson B.7 Waiting Line Predictions 23 Analytical Formulas The following analytical formulas apply to an M/M/1 system in a steady state (after the initial customers have passed through) 1) The probability of no units in the system: P0 = 1-/m 2) The average number of units in the waiting line: Lq = 2/(m(m-)) 3) The average number of units in the system: L = Lq + /m 4) The average time a unit spends in the waiting line: Wq = Lq/ 5) The average time a unit spends in the system: W = 1/(m-) 6) The probability that an arriving unit has to wait: Pw = /m 7) Probability of n units in the system: Pn = (/m)nP0 BA 452 Lesson B.7 Waiting Line Predictions 24 Analytical Formulas Poisson arrival-rate distribution Exponential service-time distribution Single channel Unlimited maximum queue length Infinite calling population of potential customers Examples (which are approximations when “unlimited” and “infinite” are really just “large”): • Single-window theatre ticket sales booth • Single-scanner airport security station BA 452 Lesson B.7 Waiting Line Predictions 25 M/M/1 Queuing System M/M/1 Queuing System BA 452 Lesson B.7 Waiting Line Predictions 26 M/M/1 Queuing System Overview M/M/1 Queuing System designates M = Markov (memoryless) arrival distribution (exponential), M = Markov service-time distribution (Poisson), and 1 service channel, under first-come, first-served. BA 452 Lesson B.7 Waiting Line Predictions 27 M/M/1 Queuing System Question: 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. Assume Poisson arrival times and exponential service times. Answer the following questions using the Analytical Formulas for a M/M/1 queuing system: M/M/1: P0 = 1-/m Lq = 2/(m(m-)) L = Lq + /m Wq = Lq/ W = 1/(m-) Pw = /m Pn = (/m)nP0 BA 452 Lesson B.7 Waiting Line Predictions 28 M/M/1 Queuing System Arrival rate distribution questions: P (x=k) = (ke -)/k! What is the probability that no orders are received within a 15-minute period? Answer: 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. Hence, P (x = 0) = (50e -5)/0! = e -5 = .0067 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 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 BA 452 Lesson B.7 Waiting Line Predictions 29 M/M/1 Queuing System Service rate distribution questions: P (T < t ) = 1 - e-µt 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.), the mean service rate, µ, is µ = 1/(mean service time), or 60/2. m = 30/hr. 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). Use the exponential distribution, P (T < t ) = 1 - e-µt. Hence, P (T < 1/60) = 1 - e-30(1/60) = 1 - .6065 = .3935 = 39.35% BA 452 Lesson B.7 Waiting Line Predictions 30 M/M/1 Queuing System Service rate distribution questions: P (T < t ) = 1 - e-µt 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. 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% BA 452 Lesson B.7 Waiting Line Predictions 31 M/M/1 Queuing System M/M/1: P0 = 1-/m Lq = 2/(m(m-)) L = Lq + /m Wq = Lq/ W = 1/(m-) Pw = /m Pn = (/m)nP0 What is the average time an order must wait from the 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. Analytical Formula #5 says the average time an order waits in the system is: W = 1/(µ - ) = 1/(30 - 20) = 1/10 hour or 6 minutes BA 452 Lesson B.7 Waiting Line Predictions 32 M/M/1 Queuing System M/M/1: P0 = 1-/m Lq = 2/(m(m-)) L = Lq + /m Wq = Lq/ W = 1/(m-) Pw = /m Pnper = (/m)nP0 What is the average number of orders Joe has waiting to be processed? Answer: This is an M/M/1 queue with = 20 hour and m = 30 per hour. Analytical Formula #2 says the average number of orders waiting in the queue is: Lq = 2/[µ(µ - )] = (20)2/[(30)(30-20)] = 400/300 = 4/3 BA 452 Lesson B.7 Waiting Line Predictions 33 M/M/1 Queuing System M/M/1: P0 = 1-/m Lq = 2/(m(m-)) L = Lq + /m Wq = Lq/ W = 1/(m-) Pw = /m Pn = (/m)nP0 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 (the probability of waiting Pw). Thus, the percentage of time he is processing orders is: /m = 20/30 = 2/3 or 66.67% BA 452 Lesson B.7 Waiting Line Predictions 34 M/M/1 Queuing System BA 452 Lesson B.7 Waiting Line Predictions 35 M/M/1 Queuing System M/M/1: P0 = 1-/m Lq = 2/(m(m-)) L = Lq + /m Wq = Lq/ W = 1/(m-) Pw = /m Pn = (/m)nP0 BA 452 Lesson B.7 Waiting Line Predictions 36 BA 452 Quantitative Analysis End of Lesson B.7 BA 452 Lesson B.7 Waiting Line Predictions 37