Table of Contents Chapter 14 (Queueing Models) Elements of a Queueing Model (Section 14.1) Some Examples of Queueing Systems (Section 14.2) Measures of Performance for Queueing Systems (Section 14.3) A Case Study: The Dupit Corp. Problem (Section 14.4) Some Single-Server Queueing Models (Section 14.5) Some Multiple-Server Queueing Models (Section 14.6) Priority Queueing Models (Section 14.7) Some Insights about Designing Queueing Systems (Section 14.8) Economic Analysis of the Number of Servers to Provide (Section 14.9) 14.214.13 14.1414.16 14.1714.20 14.2114.23 14.2414.33 14.3414.42 14.4314.50 14.5114.53 14.5414.57 Queueing Models (UW Lecture) 14.5814.76 These slides are based upon a lecture from the MBA elective course Modeling with Spreadsheets at the University of Washington (as taught by one of the authors). Queueing Applications (UW Lecture) 14.7714.90 These slides are based upon a lecture from the MBA elective course Modeling with Spreadsheets at the University of Washington (as taught by one of the authors). McGraw-Hill/Irwin 14.1 The McGraw-Hill Companies, Inc., 2003 A Basic Queueing System Served Customers Queueing System Queue Customers CCCCCCC C C C C S
S S S Service facility Served Customers McGraw-Hill/Irwin 14.2 The McGraw-Hill Companies, Inc., 2003 Herr Cutters Barber Shop Herr Cutter is a German barber who runs a one-man barber shop. Herr Cutter opens his shop at 8:00 A.M. The table shows his queueing system in action over a typical morning. Customer Time of Arrival Haicut Begins Duration of Haircut Haircut Ends 1 8:03 8:03 17 minutes 8:20 2 8:15
8:20 21 minutes 8:41 3 8:25 8:41 19 minutes 9:00 4 8:30 9:00 15 minutes 9:15 5 9:05 9:15 20 minutes 9:35 6 9:43 McGraw-Hill/Irwin 14.3 The McGraw-Hill Companies, Inc., 2003 Arrivals The time between consecutive arrivals to a queueing system are called the
interarrival times. The expected number of arrivals per unit time is referred to as the mean arrival rate. The symbol used for the mean arrival rate is = Mean arrival rate for customers coming to the queueing system where is the Greek letter lambda. The mean of the probability distribution of interarrival times is 1 / = Expected interarrival time Most queueing models assume that the form of the probability distribution of interarrival times is an exponential distribution. McGraw-Hill/Irwin 14.4 The McGraw-Hill Companies, Inc., 2003 Evolution of the Number of Customers 4 Number of Customers in the System 3 2 1 0 McGraw-Hill/Irwin 20 40 60 Time (in minutes) 14.5 80
100 The McGraw-Hill Companies, Inc., 2003 The Exponential Distribution for Interarrival Times 0 McGraw-Hill/Irwin Mean Time 14.6 The McGraw-Hill Companies, Inc., 2003 Properties of the Exponential Distribution There is a high likelihood of small interarrival times, but a small chance of a very large interarrival time. This is characteristic of interarrival times in practice. For most queueing systems, the servers have no control over when customers will arrive. Customers generally arrive randomly. Having random arrivals means that interarrival times are completely unpredictable, in the sense that the chance of an arrival in the next minute is always just the same. The only probability distribution with this property of random arrivals is the exponential distribution. The fact that the probability of an arrival in the next minute is completely uninfluenced by when the last arrival occurred is called the lack-of-memory property. McGraw-Hill/Irwin 14.7 The McGraw-Hill Companies, Inc., 2003 The Queue
The number of customers in the queue (or queue size) is the number of customers waiting for service to begin. The number of customers in the system is the number in the queue plus the number currently being served. The queue capacity is the maximum number of customers that can be held in the queue. An infinite queue is one in which, for all practical purposes, an unlimited number of customers can be held there. When the capacity is small enough that it needs to be taken into account, then the queue is called a finite queue. The queue discipline refers to the order in which members of the queue are selected to begin service. The most common is first-come, first-served (FCFS). Other possibilities include random selection, some priority procedure, or even lastcome, first-served. McGraw-Hill/Irwin 14.8 The McGraw-Hill Companies, Inc., 2003 Service When a customer enters service, the elapsed time from the beginning to the end of the service is referred to as the service time. Basic queueing models assume that the service time has a particular probability distribution. The symbol used for the mean of the service time distribution is 1 / = Expected service time where is the Greek letter mu.
The interpretation of itself is the mean service rate. = Expected service completions per unit time for a single busy server McGraw-Hill/Irwin 14.9 The McGraw-Hill Companies, Inc., 2003 Some Service-Time Distributions Exponential Distribution The most popular choice. Much easier to analyze than any other. Although it provides a good fit for interarrival times, this is much less true for service times. Provides a better fit when the service provided is random than if it involves a fixed set of tasks. Standard deviation: = Mean Constant Service Times A better fit for systems that involve a fixed set of tasks. Standard deviation: = 0. Erlang Distribution Fills the middle ground between the exponential distribution and constant. Has a shape parameter, k that determines the standard deviation. In particular, = mean / (k) McGraw-Hill/Irwin 14.10 The McGraw-Hill Companies, Inc., 2003 Standard Deviation and Mean for Distributions McGraw-Hill/Irwin Distribution Standard Deviation Exponential mean Degenerate (constant) 0
Erlang, any k (1 / k) (Mean) Erlang, k = 2 (1 / 2) (Mean) Erlang, k = 4 (1 / 2) (Mean) Erlang, k = 8 (1 / 22) (Mean) Erlang, k = 16 (1 / 4) (Mean) 14.11 The McGraw-Hill Companies, Inc., 2003 Labels for Queueing Models To identify which probability distribution is being assumed for service times (and for interarrival times), a queueing model conventionally is labeled as follows: Distribution of service times // Number of Servers Distribution of interarrival times The symbols used for the possible distributions are M = Exponential distribution (Markovian) D = Degenerate distribution (constant times) Ek = Erlang distribution (shape parameter = k) GI = General independent interarrival-time distribution (any distribution) G = General service-time distribution (any arbitrary distribution) McGraw-Hill/Irwin 14.12 The McGraw-Hill Companies, Inc., 2003 Summary of Usual Model Assumptions 1. Interarrival times are independent and identically distributed according to a specified probability distribution. 2. All arriving customers enter the queueing system and remain there until service has been completed. 3. The queueing system has a single infinite queue, so that the queue will hold an unlimited number of customers (for all practical purposes). 4. The queue discipline is first-come, first-served. 5. The queueing system has a specified number of servers, where each server is capable of serving any of the customers.
6. Each customer is served individually by any one of the servers. 7. Service times are independent and identically distributed according to a specified probability distribution. McGraw-Hill/Irwin 14.13 The McGraw-Hill Companies, Inc., 2003 Examples of Commercial Service Systems That Are Queueing Systems Type of System Customers Server(s) Barber shop People Barber Bank teller services People Teller ATM machine service People ATM machine Checkout at a store People Checkout clerk Plumbing services Clogged pipes Plumber Ticket window at a movie theater People Cashier Check-in counter at an airport
People Airline agent Brokerage service People Stock broker Gas station Cars Pump Call center for ordering goods People Telephone agent Call center for technical assistance People Technical representative Travel agency People Travel agent Automobile repair shop Car owners Mechanic Vending services People Vending machine Dental services People Dentist Roofing Services Roofs
Roofer McGraw-Hill/Irwin 14.14 The McGraw-Hill Companies, Inc., 2003 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 services Employees Programmer Mainframe computer Employees Computer First-aid center Employees Nurse Faxing services 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 operators Clerk McGraw-Hill/Irwin 14.15 The McGraw-Hill Companies, Inc., 2003 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 Runway Airplanes 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
McGraw-Hill/Irwin 14.16 The McGraw-Hill Companies, Inc., 2003 Choosing a Measure of Performance Managers who oversee queueing systems are mainly concerned with two measures of performance: When customers are internal to the organization, the first measure tends to be more important. How many customers typically are waiting in the queueing system? How long do these customers typically have to wait? Having such customers wait causes lost productivity. Commercial service systems tend to place greater importance on the second measure. Outside customers are typically more concerned with how long they have to wait than with how many customers are there. McGraw-Hill/Irwin 14.17 The McGraw-Hill Companies, Inc., 2003 Defining the Measures of Performance L = Expected number of customers in the system, including those being served (the symbol L comes from Line Length). Lq = Expected number of customers in the queue, which excludes customers being served. W = Expected waiting time in the system (including service time) for an individual customer (the symbol W comes from Waiting time).
Wq = Expected waiting time in the queue (excludes service time) for an individual customer. These definitions assume that the queueing system is in a steady-state condition. McGraw-Hill/Irwin 14.18 The McGraw-Hill Companies, Inc., 2003 Relationship between L, W, Lq, and Wq Since 1/ is the expected service time W = Wq + 1/ Littles formula states that L = W and Lq = Wq Combining the above relationships leads to L = Lq + McGraw-Hill/Irwin 14.19 The McGraw-Hill Companies, Inc., 2003 Using Probabilities as Measures of Performance In addition to knowing what happens on the average, we may also be interested in worst-case scenarios. What will be the maximum number of customers in the system? (Exceeded no more than, say, 5% of the time.) What will be the maximum waiting time of customers in the system? (Exceeded no more than, say, 5% of the time.) Statistics that are helpful to answer these types of questions are available for some queueing systems: Pn = Steady-state probability of having exactly n customers in the system. P(W t) = Probability the time spent in the system will be no more than t. P(Wq t) = Probability the wait time will be no more than t.
Examples of common goals: No more than three customers 95% of the time: P0 + P1 + P2 + P3 0.95 No more than 5% of customers wait more than 2 hours: P(W 2 hours) 0.95 McGraw-Hill/Irwin 14.20 The McGraw-Hill Companies, Inc., 2003 The Dupit Corp. Problem The Dupit Corporation is a longtime leader in the office photocopier marketplace. Dupits service division is responsible for providing support to the customers by promptly repairing the machines when needed. This is done by the companys service technical representatives, or tech reps. Current policy: Each tech reps territory is assigned enough machines so that the tech rep will be active repairing machines (or traveling to the site) 75% of the time. A repair call averages 2 hours, so this corresponds to 3 repair calls per day. Machines average 50 workdays between repairs, so assign 150 machines per rep. Proposed New Service Standard: The average waiting time before a tech rep begins the trip to the customer site should not exceed two hours. McGraw-Hill/Irwin 14.21 The McGraw-Hill Companies, Inc., 2003 Alternative Approaches to the Problem Approach Suggested by John Phixitt: Modify the current policy by decreasing the percentage of time that tech reps are expected to be repairing machines. Approach Suggested by the Vice President for Engineering: Provide new equipment to tech reps that would reduce the time required for repairs.
Approach Suggested by the Chief Financial Officer: Replace the current one-person tech rep territories by larger territories served by multiple tech reps. Approach Suggested by the Vice President for Marketing: Give owners of the new printer-copier priority for receiving repairs over the companys other customers. McGraw-Hill/Irwin 14.22 The McGraw-Hill Companies, Inc., 2003 The Queueing System for Each Tech Rep The customers: The machines needing repair. Customer arrivals: The calls to the tech rep requesting repairs. The queue: The machines waiting for repair to begin at their sites. The server: The tech rep. Service time: The total time the tech rep is tied up with a machine, either traveling to the machine site or repairing the machine. (Thus, a machine is viewed as leaving the queue and entering service when the tech rep begins the trip to the machine site.) McGraw-Hill/Irwin 14.23 The McGraw-Hill Companies, Inc., 2003 Notation for Single-Server Queueing Models = Mean arrival rate for customers = Expected number of arrivals per unit time 1/ = expected interarrival time
= Mean service rate (for a continuously busy server) = Expected number of service completions per unit time = expected service time = the utilization factor = the average fraction of time that a server is busy serving customers = McGraw-Hill/Irwin 14.24 The McGraw-Hill Companies, Inc., 2003 The M/M/1 Model Assumptions 1. Interarrival times have an exponential distribution with a mean of 1/. 2. Service times have an exponential distribution with a mean of 1/. 3. The queueing system has one server. The expected number of customers in the system is L = 1 = The expected waiting time in the system is W = (1 / )L = 1 / ( ) The expected waiting time in the queue is Wq = W 1/ = / [( )] The expected number of customers in the queue is Lq = Wq = 2 / [( )] = 2 / (1 ) McGraw-Hill/Irwin 14.25 The McGraw-Hill Companies, Inc., 2003 The M/M/1 Model
The probability of having exactly n customers in the system is Pn = (1 )n Thus, P0 = 1 P1 = (1 ) P2 = (1 )2 : : The probability that the waiting time in the system exceeds t is P(W > t) = e(1)t for t 0 The probability that the waiting time in the queue exceeds t is P(Wq > t) = e(1)t for t 0 McGraw-Hill/Irwin 14.26 The McGraw-Hill Companies, Inc., 2003 M/M/1 Queueing Model for the Dupits Current Policy B 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 s= Pr(W > t) = when t =
Prob(W q > t) = McGraw-Hill/Irwin when t = C Data 3 4 1 D (mean arrival rate) (mean service rate) (# servers) 0.368 1 0.276 1 14.27 E G L= Lq = H Results 3 2.25 W= Wq = 1 0.75 0.75 n 0 1 2 3 4 5 6 7 8 9
10 Pn 0.25 0.1875 0.1406 0.1055 0.0791 0.0593 0.0445 0.0334 0.0250 0.0188 0.0141 The McGraw-Hill Companies, Inc., 2003 John Phixitts Approach (Reduce Machines/Rep) The proposed new service standard is that the average waiting time before service begins be two hours (i.e., Wq 1/4 day). John Phixitts suggested approach is to lower the tech reps utilization factor sufficiently to meet the new service requirement. Lower = / , until Wq 1/4 day, where = (Number of machines assigned to tech rep) / 50. McGraw-Hill/Irwin 14.28 The McGraw-Hill Companies, Inc., 2003 M/M/1 Model for John Phixitts Suggested Approach (Reduce Machines/Rep) B 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 20 21 22 23 s= Pr(W > t) = when t = Prob(Wq > t) = when t = McGraw-Hill/Irwin C Data 2 4 1 D E (mean arrival rate) (mean service rate) (# servers) 0.135 1 0.068 1 14.29 G L= Lq = H Results 1 0.5 W= Wq = 0.5 0.25 0.5
n 0 1 2 3 4 5 6 7 8 9 10 Pn 0.5 0.25 0.1250 0.0625 0.0313 0.0156 0.0078 0.0039 0.0020 0.0010 0.0005 The McGraw-Hill Companies, Inc., 2003 The M/G/1 Model Assumptions 1. Interarrival times have an exponential distribution with a mean of 1/. 2. Service times can have any probability distribution. You only need the mean (1/) and standard deviation (). 3. The queueing system has one server. The probability of zero customers in the system is P0 = 1 The expected number of customers in the queue is Lq = 22 + 2] / [2(1 )] The expected number of customers in the system is L = Lq + The expected waiting time in the queue is Wq = Lq /
The expected waiting time in the system is W = Wq + 1/ McGraw-Hill/Irwin 14.30 The McGraw-Hill Companies, Inc., 2003 The Values of and Lq for the M/G/1 Model with Various Service-Time Distributions Distribution Mean Model Lq Exponential 1/ 1/ M/M/1 2 / (1 ) Degenerate (constant) 1/ 0 M/D/1 (1/2) [2 / (1 )] Erlang, with shape parameter k 1/ (1/k) (1/) M/Ek/1 (k+1)/(2k) [2 / (1 )] McGraw-Hill/Irwin
14.31 The McGraw-Hill Companies, Inc., 2003 VP for Engineering Approach (New Equipment) The proposed new service standard is that the average waiting time before service begins be two hours (i.e., Wq 1/4 day). The Vice President for Engineering has suggested providing tech reps with new state-of-the-art equipment that would reduce the time required for the longer repairs. After gathering more information, they estimate the new equipment would have the following effect on the service-time distribution: Decrease the mean from 1/4 day to 1/5 day. Decrease the standard deviation from 1/4 day to 1/10 day. McGraw-Hill/Irwin 14.32 The McGraw-Hill Companies, Inc., 2003 M/G/1 Model for the VP of Engineering Approach (New Equipment) B 3 4 5 6 7 8 9 10 11 12 s= McGraw-Hill/Irwin C Data 3 0.2 0.1
1 D (mean arrival rate) (expected service time) (standard deviation) (# servers) E F L= Lq = G Results 1.163 0.563 W= Wq = 0.388 0.188 P0 = 14.33 0.6 0.4 The McGraw-Hill Companies, Inc., 2003 The M/M/s Model Assumptions 1. Interarrival times have an exponential distribution with a mean of 1/. 2. Service times have an exponential distribution with a mean of 1/ 3. Any number of servers (denoted by s). With multiple servers, the formula for the utilization factor becomes = / s but still represents that average fraction of time that individual servers are busy. McGraw-Hill/Irwin 14.34 The McGraw-Hill Companies, Inc., 2003
Values of L for the M/M/s Model for Various Values of s Steady-state expected number of customers in the queueing system 100 10 s = 25 s = 20 s = 15 s = 10 s=7 s=5 s=4 s=3 0.5 s=2 s=1 0.2 0.1 McGraw-Hill/Irwin 0 0.1 0.3 14.35 0.5 0.7 Utilization factor 0.9 1.0 s The McGraw-Hill Companies, Inc., 2003 CFO Suggested Approach (Combine Into Teams) The proposed new service standard is that the average waiting time before service begins be two hours (i.e., Wq 1/4 day). The Chief Financial Officer has suggested combining the current one-person tech rep territories into larger territories that would be served jointly by multiple tech reps.
A territory with two tech reps: Number of machines = 300 Mean arrival rate = = 6 Mean service rate = = 4 Number of servers = s = 2 Utilization factor = = /s = 0.75 McGraw-Hill/Irwin (versus 150 before) (versus = 3 before) (as before) (versus s = 1 before) (as before) 14.36 The McGraw-Hill Companies, Inc., 2003 M/M/s Model for the CFOs Suggested Approach (Combine Into Teams of Two) B 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 s=
Pr(W > t) = when t = Prob(Wq > t) = McGraw-Hill/Irwin when t = C Data 6 4 2 D (mean arrival rate) (mean service rate) (# servers) 0.169 1 0.087 1 14.37 E G L= Lq = H Results 3.4286 1.9286 W= Wq = 0.5714 0.3214 0.75 n 0 1 2 3 4 5 6 7
8 9 10 Pn 0.1429 0.2143 0.1607 0.1205 0.0904 0.0678 0.0509 0.0381 0.0286 0.0215 0.0161 The McGraw-Hill Companies, Inc., 2003 CFO Suggested Approach (Teams of Three) The Chief Financial Officer has suggested combining the current one-person tech rep territories into larger territories that would be served jointly by multiple tech reps. A territory with three tech reps: Number of machines = 450 Mean arrival rate = = 9 Mean service rate = = 4 Number of servers = s = 3 Utilization factor = = /s = 0.75 McGraw-Hill/Irwin (versus 150 before) (versus = 3 before) (as before) (versus s = 1 before) (as before) 14.38 The McGraw-Hill Companies, Inc., 2003 M/M/s Model for the CFOs Suggested Approach (Combine Into Teams of Three) B
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 s= Pr(W > t) = when t = Prob(W q > t) = McGraw-Hill/Irwin when t = C Data 9 4 3 D (mean arrival rate) (mean service rate) (# servers) 0.090 1 0.028 1 14.39 E G L= Lq =
H Results 3.9533 1.7033 W= Wq = 0.4393 0.1893 0.75 n 0 1 2 3 4 5 6 7 8 9 10 Pn 0.0748 0.1682 0.1893 0.1419 0.1065 0.0798 0.0599 0.0449 0.0337 0.0253 0.0189 The McGraw-Hill Companies, Inc., 2003 Comparison of Wq with Territories of Different Sizes Number of Tech Reps Number of Machines
s Wq 1 150 3 4 1 0.75 0.75 workday (6 hours) 2 300 6 4 2 0.75 0.321 workday (2.57 hours) 3 450 9 4 3 0.75 0.189 workday (1.51 hours) McGraw-Hill/Irwin 14.40 The McGraw-Hill Companies, Inc., 2003 Values of L for the M/D/s Model for Various Values of s Steady-state expected number of customers in the queueing system
100 s = 25 10 s = 20 s = 15 s = 10 s=7 s=5 1.0 s=4 s=3 s=2 s=1 0.1 McGraw-Hill/Irwin 0 0.1 0.3 0.5 0.7 Utilization factor 14.41 0.9 1.0 s The McGraw-Hill Companies, Inc., 2003 Values of L for the M/Ek/2 Model for Various Values of k Steady-state expected number of customers in the queueing system 100 k=1 10 k=2 k=8 1.0 0.1
McGraw-Hill/Irwin 0 0.2 0.4 14.42 0.6 0.8 Utilization factor 1.0 s The McGraw-Hill Companies, Inc., 2003 Priority Queueing Models General Assumptions: There are two or more categories of customers. Each category is assigned to a priority class. Customers in priority class 1 are given priority over customers in priority class 2. Priority class 2 has priority over priority class 3, etc. After deferring to higher priority customers, the customers within each priority class are served on a first-come-fist-served basis. Two types of priorities Nonpreemptive priorities: Once a server has begun serving a customer, the service must be completed (even if a higher priority customer arrives). However, once service is completed, priorities are applied to select the next one to begin service. Preemptive priorities: The lowest priority customer being served is preempted (ejected back into the queue) whenever a higher priority customer enters the queueing system. McGraw-Hill/Irwin 14.43 The McGraw-Hill Companies, Inc., 2003 Preemptive Priorities Queueing Model Additional Assumptions 1. Preemptive priorities are used as previously described. 2. For priority class i (i = 1, 2, , n), the interarrival times of the customers in that class have an exponential distribution with a mean of 1/i. 3. All service times have an exponential distribution with a mean of 1/, regardless of
the priority class involved. 4. The queueing system has a single server. The utilization factor for the server is = (1 + 2 + + n) / McGraw-Hill/Irwin 14.44 The McGraw-Hill Companies, Inc., 2003 Nonpreemptive Priorities Queueing Model Additional Assumptions 1. Nonpreemptive priorities are used as previously described. 2. For priority class i (i = 1, 2, , n), the interarrival times of the customers in that class have an exponential distribution with a mean of 1/i. 3. All service times have an exponential distribution with a mean of 1/, regardless of the priority class involved. 4. The queueing system can have any number of servers. The utilization factor for the servers is = (1 + 2 + + n) / s McGraw-Hill/Irwin 14.45 The McGraw-Hill Companies, Inc., 2003 VP of Marketing Approach (Priority for New Copiers) The proposed new service standard is that the average waiting time before service begins be two hours (i.e., Wq 1/4 day). The Vice President of Marketing has proposed giving the printer-copiers priority over other machines for receiving service. The rationale for this proposal is that the printer-copier performs so many vital functions that its owners cannot tolerate being without it as long as other machines. The mean arrival rates for the two classes of copiers are
1 = 1 customer (printer-copier) per workday (now) 2 = 2 customers (other machines) per workday (now) The proportion of printer-copiers is expected to increase, so in a couple years 1 = 1.5 customers (printer-copiers) per workday (later) 2 = 1.5 customers (other machines) per workday (later) McGraw-Hill/Irwin 14.46 The McGraw-Hill Companies, Inc., 2003 Nonpreemptive Priorities Model for VP of Marketings Approach (Current Arrival Rates) B 3 4 5 6 7 8 n= s= D E F G (# of priority classes) (mean service rate) (# servers) Results 9
10 11 12 13 14 15 16 17 C Data 2 4 1 Priority Class 1 Priority Class 2 Priority Class 3 Priority Class 4 Priority Class 5 McGraw-Hill/Irwin i L Lq W Wq 1 2 1 1 1 0.5 2.5 #DIV/0! #DIV/0! 1.75 0.25 2 #DIV/0! #DIV/0! 1.5 0.5 1.25
#DIV/0! #DIV/0! 1.75 0.25 1 #DIV/0! #DIV/0! 1.5 3 0.75 14.47 The McGraw-Hill Companies, Inc., 2003 Nonpreemptive Priorities Model for VP of Marketings Approach (Future Arrival Rates) B 3 4 5 6 7 8 n= s= D E F G (# of priority classes) (mean service rate) (# servers) Results 9 10 11 12 13 14 15 16 17 C Data
2 4 1 Priority Class 1 Priority Class 2 Priority Class 3 Priority Class 4 Priority Class 5 McGraw-Hill/Irwin i L Lq W Wq 1.5 1.5 1 1 1 0.825 2.175 #DIV/0! #DIV/0! 1.75 0.45 1.8 #DIV/0! #DIV/0! 1.5 0.55 1.45 #DIV/0! #DIV/0! 1.75 0.3 1.2 #DIV/0! #DIV/0! 1.5 3
0.75 14.48 The McGraw-Hill Companies, Inc., 2003 Expected Waiting Times with Nonpreemptive Priorities Wq for Printer Copiers Wq for Other Machines s When 1 2 1 Now 1 2 4 0.75 0.25 workday (2 hrs.) 1 workday (8 hrs.) 1 Later 1.5 1.5 4 0.75 0.3 workday (2.4 hrs.) 1.2 workday (9.6 hrs.)
2 Now 2 4 4 0.75 0.107 workday (0.86 hr.) 0.439 workday (3.43 hrs.) 2 Later 3 3 4 0.75 0.129 workday (1.03 hrs.) 0.514 workday (4.11 hrs.) 3 Now 3 6 4 0.75 0.063 workday (0.50 hr.) 0.252 workday (2.02 hrs.) 3 Later 4.5 4.5
4 0.75 0.076 workday (0.61 hr.) 0.303 workday (2.42 hrs.) McGraw-Hill/Irwin 14.49 The McGraw-Hill Companies, Inc., 2003 The Four Approaches Under Considerations Proposer Proposal Additional Cost John Phixitt Maintain one-person territories, but reduce number of machines assigned to each from 150 to 100 $300 million per year VP for Engineering Keep current one-person territories, but provide new state-of-the-art equipment to the tech-reps One-time cost of $500 million Chief Financial Officer Change to three-person territories None, except disadvantages of larger territories VP for Marketing Change to two-person territories with priority given to the printercopiers for repairs None, except disadvantages of larger territories Decision: Adopt fourth proposal (except for sparsely populated areas where
second proposal should be adopted). McGraw-Hill/Irwin 14.50 The McGraw-Hill Companies, Inc., 2003 Some Insights About Designing Queueing Systems 1. When designing a single-server queueing system, beware that giving a relatively high utilization factor (workload) to the server provides surprisingly poor performance for the system. 2. Decreasing the variability of service times (without any change in the mean) improves the performance of a queueing system substantially. 3. Multiple-server queueing systems can perform satisfactorily with somewhat higher utilization factors than can single-server queueing systems. For example, pooling servers by combining separate single-server queueing systems into one multiple-server queueing system greatly improves the measures of performance. 4. Applying priorities when selecting customers to begin service can greatly improve the measures of performance for high-priority customers. McGraw-Hill/Irwin 14.51 The McGraw-Hill Companies, Inc., 2003 Effect of High-Utilization Factors (Insight 1) B 3 4 5 A B C C Data 0.5 1 D E G (mean arrival rate) (mean service rate) D
H Results L= Lq = 1 0.5 E 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 0 0.01 0 0.25 0 0.5 0 0.6 0 0.7 0 0.75 0 0.8 0 0.85 0 0.9 0 0.95 0 0.99 0 0.999 Lq 0.5 0.0001 0.0833 0.5 0.9 1.6333 2.25
3.2 4.8167 8.1 18.05 98.01 998.001 McGraw-Hill/Irwin Average Line Length (L) 9 Data Table Demonstrating the Effect of 10 Increasing on Lq and L for M/M/1 L 1 0.0101 0.3333 1 1.5 2.3333 3 4 5.6667 9 19 99 999 100 80 60 40 20 0 0 0.2 0.4 0.6 0.8 System Utilization (r) 14.52 The McGraw-Hill Companies, Inc., 2003 1 Effect of Decreasing (Insight 2) A B
C D E F G H 1 Template for the M/G/1 Queueing Model 2 3 Data Results 4 0.5 (mean arrival rate) L= 0.8125 Lq = 5 1 (expected service time) 0.3125 6 0.5 (standard deviation) 7 s= 1 (# servers) W= 1.625 Wq = 8 0.625 9 10 0.5 11 P0 = 12 0.5 13 14 Data Table Demonstrating the Effect of Decreasing s on Lq for M/G/1 15 16 17 18 19
20 21 22 23 McGraw-Hill/Irwin Body of Table Shows L q Values 0.3125 0.5 0.75 0.9 0.99 1 0.500 2.250 8.100 98.010 0.5 0.313 1.406 5.063 61.256 14.53 0 0.250 1.125 4.050 49.005 The McGraw-Hill Companies, Inc., 2003 Economic Analysis of the Number of Servers to Provide In many cases, the consequences of making customers wait can be expressed as a waiting cost. The manager is interested in minimizing the total cost. TC = Expected total cost per unit time SC = Expected service cost per unit time WC = Expected waiting cost per unit time The objective is then to choose the number of servers so as to Minimize TC = SC + WC When each server costs the same (Cs = cost of server per unit time), SC = Cs s
When the waiting cost is proportional to the amount of waiting (Cw = waiting cost per unit time for each customer), WC = Cw L McGraw-Hill/Irwin 14.54 The McGraw-Hill Companies, Inc., 2003 Acme Machine Shop The Acme Machine Shop has a tool crib for storing tool required by shop mechanics. Two clerks run the tool crib. The estimates of the mean arrival rate and the mean service rate (per server) are = 120 customers per hour = 80 customers per hour The total cost to the company of each tool crib clerk is $20/hour, so Cs = $20. While mechanics are busy, their value to Acme is $48/hour, so Cw = $48. Choose s so as to Minimize TC = $20s + $48L. McGraw-Hill/Irwin 14.55 The McGraw-Hill Companies, Inc., 2003 Excel Template for Choosing the Number of Servers B C Data 120 80 3
3 4 5 6 s= 7 8 Pr(W > t) = 0.02581732 9 when t = 0.05 10 Prob(Wq > t) = 0.00058707 11 12 when t = 0.05 13 14 Economic Analysis: 15 Cs = $20.00 16 Cw = $48.00 17 18 Cost of Service $60.00 19 Cost of Waiting $83.37 20 Total Cost $143.37 McGraw-Hill/Irwin D E (mean arrival rate) (mean service rate) (# servers) F L= Lq = G Results 1.736842105
0.236842105 W= Wq = 0.014473684 0.001973684 0.5 (cost / server / unit time) (waiting cost / unit time) 14.56 n 0 1 2 3 4 5 6 7 Pn 0.210526316 0.315789474 0.236842105 0.118421053 0.059210526 0.029605263 0.014802632 0.007401316 The McGraw-Hill Companies, Inc., 2003 Comparing Expected Cost vs. Number of Clerks H I J K L M N 1 Data Table for Expected Total Cost of Alternatives 2 3
Cost of Cost of Total 4 s r L Service Waiting Cost 5 0.50 1.74 $60.00 $83.37 $143.37 6 1 1.50 #N/A $20.00 #N/A #N/A 7 2 0.75 3.43 $40.00 $164.57 $204.57 8 3 0.50 1.74 $60.00 $83.37 $143.37 9 4 0.38 1.54 $80.00 $74.15 $154.15 10 5 0.30 1.51 $100.00 $72.41 $172.41 Cost ($/hour) $250 Cost of Service $200 $150 Cost of Waiting $100
Total Cost $50 $0 0 1 2 3 4 5 Number of Servers (s) McGraw-Hill/Irwin 14.57 The McGraw-Hill Companies, Inc., 2003 Where is There Waiting? Service Facility Fast-food restaurants Post office Grocery store Bank Disneyland Highway traffic Manufacturing Equipment awaiting repair
Phone or computer network Product orders McGraw-Hill/Irwin 14.58 The McGraw-Hill Companies, Inc., 2003 Why is There Waiting? Example #1: McDonalds 50 customers arrive per hour Service rate is 60 customers per hour Example #2: Doctors Office Arrivals are scheduled to arrive every 20 minutes. The doctor spends an average of 18 minutes with each patient. McGraw-Hill/Irwin 14.59 The McGraw-Hill Companies, Inc., 2003 System Characteristics Number of servers Arrival and service pattern rate of arrivals and service distribution of arrivals and service Maximum size of the queue Queue disciplince FCFS? Priority system? Population size
Infinite or finite? McGraw-Hill/Irwin 14.60 The McGraw-Hill Companies, Inc., 2003 Measures of System Performance Average number of customers waiting in the system in the queue Average time customers wait in the system in the queue Which measure is the most important? McGraw-Hill/Irwin 14.61 The McGraw-Hill Companies, Inc., 2003 Number of Servers Single Server ... Customers Service Center Multiple Servers ... ... ... Customers ... Customers Service Centers
McGraw-Hill/Irwin 14.62 Service Centers The McGraw-Hill Companies, Inc., 2003 Arrival Pattern A Poisson distribution is usually assumed. A good approximation of random arrivals. Lack-of-memory property: Probability of an arrival in the next instant is constant, regardless of the past. Relative Frequency .18 .16 .14 .12 .10 .08 .06 .04 .02 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Customers per time unit
McGraw-Hill/Irwin 14.63 The McGraw-Hill Companies, Inc., 2003 Service Pattern Either an exponential distribution is assumed, Implies that the service is usually short, but occasionally long If service time is exponential then service rate is Poisson Lack-of-memory property: The probability that a service ends in the next instant is constant (regardless of how long its already gone). Decent approximation if the jobs to be done are random. Not a good approximation if the jobs to be done are always the same. Relative Frequency (%) Service Time Or any distribution Only single-server model is easily solved. McGraw-Hill/Irwin 14.64 The McGraw-Hill Companies, Inc., 2003 Maximum Size of Queue Most queueing models assume an infinite queue length is possible. ... If the queue length is limited, a finite queue model can be used. McGraw-Hill/Irwin 14.65 The McGraw-Hill Companies, Inc., 2003 Queue Discipline Most queueing systems assume customers are served first-come first-served. .. .
Customers Service Center If certain customers are given priority, a priority queueing model can be used. Nonpreemptive: Finish customer in service before taking a new one. Preemptive: If priority customer arrives, any regular customer in service is preempted (put back in the queue). ... Regular Customers McGraw-Hill/Irwin Priority Customers 14.66 Service Center The McGraw-Hill Companies, Inc., 2003 Population Source Most queueing models assume an infinite population source. ... Customer Source System If the number of potential customers is small, a finite source model can be used. Number in system affects arrival rate (fewer potential arrivals when more in system) Okay to assume infinite if N > 20. ... Customer Source McGraw-Hill/Irwin System 14.67
The McGraw-Hill Companies, Inc., 2003 Models 1. 2. 3. 4. 5. 6. Single server, exponential service time (M/M/1) Single server, general service time (M/G/1) Multiple servers, exponential service time (M/M/s) Finite queue (M/M/s/K) Priority queue (nonpreemptive and preemptive) Finite calling population A Taxonomy / / (and an optional fourth element / ) Arrival Distribution Service Distribution Number of Servers Maximum in Queue where M = Exponential (Markovian) D = deterministic (constant) G = general distribution McGraw-Hill/Irwin 14.68 The McGraw-Hill Companies, Inc., 2003 Notation Parameters: = customer arrival rate = service rate (1/ = average service time) s = number of servers Performance Measures Lq L Wq W
Pn = average number of customers in the queue = average number of customers in the system = average waiting time in the queue = average waiting time (including service) = probability of having n customers in the system = system utilization McGraw-Hill/Irwin 14.69 The McGraw-Hill Companies, Inc., 2003 Model 1 (M/M/1) Customers arrive to a small-town post office at an average rate of 10 per hour (Poisson distribution). There is only one postal employee on duty and he can serve customers in an average of 5 minutes (exponential distribution). A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 B C D E G H
I Template for the M/M/s Queueing Model s= Data 10 12 1 Results (mean arrival rate) (mean service rate) (# servers) Pr(W > t) = 0.13533528 when t = 1 L= Lq = 5 4.166666667 W= Wq = 0.5 0.416666667 Prob(W q > t) = McGraw-Hill/Irwin when t = 0.1127794 1 n 0 1 2 3 4 5 6 7 8 9 10
14.70 minutes 30 25 0.833333333 Pn 0.166666667 0.138888889 0.115740741 0.096450617 0.080375514 0.066979595 0.055816329 0.046513608 0.03876134 0.032301117 0.026917597 The McGraw-Hill Companies, Inc., 2003 Model 2 (M/D/1) ABC Car Wash is an automated car wash. Each customer deposits four quarters in a coin slot, drives the car into the auto-washer, and waits while the car is automatically washed. Cars arrive at an average rate of 20 cars per hour (Poisson). The service time is exactly 2 minutes. A 1 2 3 4 5 6 7 8 9 10 11 12 B C D E F G H
Template for the M/G/1 Queueing Model McGraw-Hill/Irwin Data 20 0.03333333 0 s= 1 (mean arrival rate) (expected service time) (standard deviation) (# servers) L= Lq = Results 1.333 0.667 W= Wq = 0.067 0.033 minutes 4 2 0.666666667 P0 = 14.71 0.333333333 The McGraw-Hill Companies, Inc., 2003 Model 3 A grocery store has three registers open. Customers arrive to check out at an average of 1 per minute (Poisson). The service time averages 2 minutes (exponential). A 1 2 3 4 5 6
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 B C D E G H Template for the M/M/s Queueing Model McGraw-Hill/Irwin s= Data 1 0.5 3 (mean arrival rate) (mean service rate) (# servers) Pr(W > t) = 0.74131525 when t = 1 L= Lq = Results 2.888888889
0.888888889 W= Wq = 2.888888889 0.888888889 Prob(Wq > t) = 0.26956918 when t = 1 n 0 1 2 3 4 5 6 7 8 9 10 14.72 0.666666667 Pn 0.111111111 0.222222222 0.222222222 0.148148148 0.098765432 0.065843621 0.043895748 0.029263832 0.019509221 0.013006147 0.008670765 The McGraw-Hill Companies, Inc., 2003 Model 4 A call center that handles the tech support for a software manufacturer currently has 10 telephone lines, with three people fielding the calls. Customers call at an average rate of 40 per hour (Poisson). A customer can be served in an average of four minutes (exponential). A 1 2 3 4 5 6
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 B C D E F G Template for M/M/s Finite Queue Model McGraw-Hill/Irwin s= K= Data 40 15 3 10 (mean arrival rate) (mean service rate) (# servers) (max customers) Results L = 4.5577194 Lq = 2.0413889 W= 0.1208 Wq = 0.0540838
0.8888889 n 0 1 2 3 4 5 6 7 8 9 10 14.73 Pn 0.0406825 0.1084866 0.1446488 0.1285767 0.1142904 0.1015915 0.0903035 0.0802698 0.071351 0.0634231 0.0563761 The McGraw-Hill Companies, Inc., 2003 Model 5a (Nonpreemptive Priority Queue) Consider a small-town hospital emergency room (ER) that has just one doctor on duty. When patients arrive, they are classified as either critical or non-critical. When the doctor is finished treating a patient, she takes the next critical patient. If there are no critical patients, then she takes the next non-critical patient. The ER doctor spends an average of 10 minutes (exponential) treating each patient before they are either released or admitted to the hospital. An average of 1 critical patient and 3 non-critical patients arrive each hour (Poisson). A 1 2 3 4 5 6 7 8 B C D E
F G H Wq Wq (minutes) Template for M/M/s Nonpreemptive Priorities Queueing Model 1 0 0 0 0 9 0 10 11 12 13 14 15 16 17 0 0 0 0 0 0 0 0 n= s= Data 2 6 1 (# of priority classes) (mean service rate) (# servers) Results i Priority
Priority Priority Priority Priority McGraw-Hill/Irwin Class 1 Class 2 Class 3 Class 4 Class 5 1 3 1 1 1 L Lq W 0.3 0.133333333 0.3 0.133333333 1.7 1.2 0.566666667 0.4 2.166666667 2 2.166666667 2 #DIV/0! #DIV/0! #DIV/0! #DIV/0! #DIV/0! #DIV/0! #DIV/0! #DIV/0! 8 24 4 0.666666667 14.74 The McGraw-Hill Companies, Inc., 2003
Model 5b (Preemptive Priority Queue) Reconsider the same small-town hospital emergency room (ER). Now suppose they change their policy so that if a critical patient arrives while a non-critical patient is being treated, the doctor stops treating the non-critical patient, and immediately starts treating the critical patient. Only when there are no critical patients to be treated does the doctor start treating non-critical patients. A 1 2 3 4 5 6 7 8 B C D E F G H Template for M/M/1 Preemptive Priorities Queueing Model n= s= McGraw-Hill/Irwin (# of priority classes) (mean service rate) (# servers) Results i 9 10 11 12 13 14 15 16 Data 2
6 1 Priority Priority Priority Priority Priority Class 1 1 Class 2 3 Class 3 1 Class 4 1 Class 5 1 4 0.666666667 L Lq W Wq Wq (minutes) 0.2 1.8 3 #DIV/0! #DIV/0! 0.033333333 1.3 2.833333333 #DIV/0! #DIV/0! 0.2 0.6 3 #DIV/0! #DIV/0! 0.033333333 0.433333333 2.833333333 #DIV/0! #DIV/0!
2 26 14.75 The McGraw-Hill Companies, Inc., 2003 Model 6 (Finite Calling Population) Consider a PC-Board assembly facility. There are six automated component insertion machines. Unfortunately, they are very prone to break down. Each operating machine breaks down every eight hours or so (exponential distribution). Because these machines are so prone to break down, a full-time repairperson is kept on staff just to repair these machines. Each repair takes an average of one hour (exponential distribution). On average, how many machines are operating at a time? A B C D E F G 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 McGraw-Hill/Irwin Template for M/M/s Finite Calling Population Model s= N= Data
0.75 1 1 6 (max arrival rate) (mean service rate) (# servers) (size of population) L= Lq = Results 1.118015082 0.507766967 W= Wq = 1.832066425 0.832066425 0.75 -bar = 0.610248115 0 1 2 3 4 5 6 7 8 9 10 n 0 1 2 3 4 5 6 7 8 9 14.76 Pn 0.389751885 0.292313914 0.182696196
0.091348098 0.034255537 0.008563884 0.001070486 0 0 0 The McGraw-Hill Companies, Inc., 2003 Application of Queueing Models We can use the results from queueing models to make the following types of decisions: How many servers to employ. How large should the waiting space be. Whether to use a single fast server or a number of slower servers. Whether to have a general purpose server or faster specific servers. McGraw-Hill/Irwin 14.77 The McGraw-Hill Companies, Inc., 2003 Total Cost The goal is to minimize total cost = cost of servers + cost of waiting Cost Total Cost Cost of Service Capacity Cost of customers waiting Optimum Service Capacity McGraw-Hill/Irwin 14.78 The McGraw-Hill Companies, Inc., 2003 Example #1: How Many Servers? The MIS department of a high tech company handles employee requests for assistance when computer questions arise. Employees requiring assistance phone the MIS department with their questions (but may have to wait on hold if all of the tech support staff are busy). The MIS department receives an average of 40 requests for assistance per hour (Poisson). The average question can be answered in 3 minutes (exponential). The MIS staff is paid an average of $15 per hour. The average employee earns $25 per hour.
Question: What is the optimal size of the MIS tech support staff? McGraw-Hill/Irwin 14.79 The McGraw-Hill Companies, Inc., 2003 Example #1: How Many Servers A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 B C D E F G Template for Economic Analysis of M/M/s Queueing Model
s= Data 40 20 4 (mean arrival rate) (mean service rate) (# servers) Pr(W > t) = 0.4083219 when t = 0.05 L= Lq = Results 2.173913043 0.173913043 W= Wq = 0.054347826 0.004347826 0.5 Prob(Wq > t) = 0.02353657 when t = 0.05 1 2 Economic Analysis: 2 Cs = $15.00 1 Cw = $25.00 0 0 Cost of Service $60.00 0 Cost of Waiting $54.35 0 Total Cost $114.35 0 0 0
0 0 0 0 0 0 0 0 0 McGraw-Hill/Irwin (cost / server / unit time) (waiting cost / unit time) 14.80 n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Pn 0.130434783 0.260869565 0.260869565 0.173913043 0.086956522 0.043478261 0.02173913 0.010869565 0.005434783 0.002717391 0.001358696 0.000679348 0.000339674 0.000169837 8.49185E-05 4.24592E-05
2.12296E-05 1.06148E-05 5.3074E-06 2.6537E-06 The McGraw-Hill Companies, Inc., 2003 A Data Table for Example #1: How Many Servers? I 1 2 3 4 5 6 7 8 J K L M N Cost of Service $60.00 $45.00 $60.00 $75.00 $90.00 Cost of Waiting $54.35 $72.22 $54.35 $51.00 $50.23 Total Cost $114.35 $117.22 $114.35 $126.00 $140.23 Data Table for Example #1 s 3 4 5 6
Lq 0.174 0.889 0.174 0.040 0.009 McGraw-Hill/Irwin Wq (min) 0.261 1.333 0.261 0.060 0.014 14.81 The McGraw-Hill Companies, Inc., 2003 Example #2: How Many Servers? A McDonalds franchise is trying to decide how many registers to have open during their busiest time, the lunch hour. Customers arrive during the lunch hour at a rate of 98 customers per hour (Poisson distribution). Each service takes an average of 3 minutes (exponential distribution). Question #1: If management would not like the average customer to wait longer than five minutes in line, how many registers should they open? Question #2: If management would like no more than 5% of customers to wait more than 5 minutes, how many registers should they open? McGraw-Hill/Irwin 14.82 The McGraw-Hill Companies, Inc., 2003 Example #2: How Many Servers? A 1 2 3 4 5 6 7
8 9 10 11 12 B C D E G H I Template for the M/M/s Queueing Model s= Data 98 20 6 (mean arrival rate) (mean service rate) (# servers) Pr(W > t) = 0.34895764 when t = 0.08333333 minutes 5 Prob(W q > t) = 0.08826736 when t = 0.08333333 minutes 5 L= Lq = W= Wq = K 1 2 3
4 5 6 7 8 9 McGraw-Hill/Irwin n L Results 7.359291808 2.459291808 0.075094814 0.025094814 minutes 4.51 1.51 0.816666667 Pn M Data Table for Example #2 s 5 6 7 8 9 Wq (min) 1.5057 28.510 1.506 0.430 0.148 0.053 14.83 Pr(Wq > 5 min) 0.08827 0.80443 0.08827 0.00908 0.00087 0.00008 The McGraw-Hill Companies, Inc., 2003
Example #3: How Much Waiting Space? A photo development shop operates a drive-through lane where customers can drop off film to be developed and pick up developed photos. Customers arrive at an average rate of 40 per hour (Poisson). Each service takes an average of 1 minute (exponential). They are remodeling the parking area and drive-through lane. They would like the drive-through lane to hold all of the customers at least 95% of the time. Question: How many cars must the drive-through lane be able to hold? McGraw-Hill/Irwin 14.84 The McGraw-Hill Companies, Inc., 2003 Example #3: How Much Waiting Space? A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 B C
D E G H I Template for the M/M/s Queueing Model s= Data 40 60 1 Results (mean arrival rate) (mean service rate) (# servers) Pr(W > t) = 2.0612E-09 when t = 1 Prob(W q > t) = 1.3741E-09 when t = 1 McGraw-Hill/Irwin 14.85 L= Lq = 2 1.333333333 W= Wq = 0.05 0.033333333 0.666666667 n 0 1
2 3 4 5 6 7 8 9 10 0.333333333 0.222222222 0.148148148 0.098765432 0.065843621 0.043895748 0.029263832 0.019509221 0.013006147 0.008670765 0.00578051 Pn cumulative 0.3333 0.5556 0.7037 0.8025 0.8683 0.9122 0.9415 0.9610 0.9740 0.9827 0.9884 The McGraw-Hill Companies, Inc., 2003 Example #4: One Fast Server or Many Slow Servers A McDonalds is considering changing the way that they serve customers. Customers arrive at an average rate of 50 per hour. Current System: For most of the day (all but their lunch hour), they have three registers open. Each cashier takes the customers order, collects the money, and then gets the burgers and pours the drinks. This takes an average of 3 minutes per customer (exponential distribution).
Proposed System: They are considering having just one cash register. While one person takes the order and collects the money, another will pour the drinks, and another will get the burgers (like Wendys). The three together think they can serve a customer in an average of 1 minute. Question: Should they switch to the proposed system? McGraw-Hill/Irwin 14.86 The McGraw-Hill Companies, Inc., 2003 3 Slow Servers (McDonalds) B 3 4 5 6 7 8 9 10 s= C Data 50 20 3 D E (mean arrival rate) (mean service rate) (# servers) G L= Lq = W= Wq = Pr(W > t) = 0.46194225 when t = 0.1 H
Results 6.011235955 3.511235955 0.120224719 0.070224719 I minutes 7.21 4.21 0.833333333 1 Fast Server (Wendys) B 3 4 5 6 7 8 9 10 s= Pr(W > t) = when t = McGraw-Hill/Irwin C Data 50 60 1 D E (mean arrival rate) (mean service rate) (# servers) 4.54E-05 1 G H Results L=
Lq = 5 4.166666667 W= Wq = 0.1 0.083333333 14.87 I minutes 6 5 0.833333333 The McGraw-Hill Companies, Inc., 2003 Example #5: General or Specific Servers A small bank in a mall has two tellers. The bank handles two kinds of customers: merchant customers and regular customers. Each arrive at an average rate of 20 customers per hour (for a total arrival rate of 40 customers per hour). Current System (Specific Servers): Currently one teller handles only merchant customers and one teller handles only regular customers. The service time for both tellers averages 2 minutes (exponential). Proposed System (General Servers): The bank manager is considering changing the setup to allow each teller to handle both merchant customers and regular customers. Since the tellers would have to handle both types of jobs, their efficiency would decrease to a mean service time of 2.2 minutes. Question: Should they switch to the proposed system? McGraw-Hill/Irwin 14.88 The McGraw-Hill Companies, Inc., 2003
Current (Specific Servers) B 3 4 5 6 7 8 9 10 s= Pr(W > t) = when t = C Data 20 30 1 D E (mean arrival rate) (mean service rate) (# servers) 4.54E-05 1 G H Results L= Lq = 2 1.333333333 W= Wq = 0.1 0.066666667 I total in bank
4 2.667 minutes 6 4 0.666666667 Proposed (General Servers) B 3 4 5 6 7 8 9 10 s= C Data 40 27.27 2 D E (mean arrival rate) (mean service rate) (# servers) Pr(W > t) = 6.4082E-07 when t = 1 McGraw-Hill/Irwin G L= Lq = H Results 3.173076923 1.706410256 W= Wq = 0.079326923
0.042660256 14.89 I total in bank 3.173 1.706 minutes 4.760 2.560 0.733333333 The McGraw-Hill Companies, Inc., 2003 LL Bean LL Beans mail order business Mail order phone lines open 24 hours per day, 365 days per year 78,000 calls per week (average) Seasonal variations as well as variability during each day How LL Bean estimates the number of servers needed Each of the weeks 168 hours in a week is modeled separately as a period to be staffed Each hour modeled as an M/M/s queue Arrival rates and service rates estimated from historical data Service standard: no more than 15% of calls wait more than 20 seconds Full-time, part-time, and temporary workers scheduled to meet service standard McGraw-Hill/Irwin 14.90 The McGraw-Hill Companies, Inc., 2003
Other Hazards Biological Hazards Seafood Toxins Ciguatera toxin
FOOD ADDITIVES Use of unapproved additives, or the use of approved additives in amounts exceeding those allowed by food additive regulations could result in foodborne illness, including allergic reactions. For example, many adverse reactions have occurred because of the indiscriminate...