Waiting Line Analysis

Chapter 6. Waiting Line Analysis The Little’s Law represents the steady state relationship between Throughput, Flow Time and Inventory in form of RT=I. Using this formula, and also the using the unit load of each resource pool, Tp. And capacity of each resource pool (c/Tp), we can compute utilizations. Using utilization (U) of each resource pool, and c the number of resource units in each resource pool we can compute the number of low units in each resource pool. Summation of the member of flow units in each resource pool provide us with the total number of flow units in all resource poos, i.e., in the process. That is what we refer to it as Ip (number of flow units in the processes). If we add Tp of all the resource pools, we then get the theoretical flow time (ThFt), by using the Little Law R(ThFT) = Ip, we can find Ip in a different way. If the Ips obtained through the two procedures are not equal, we have made a mistake, either in computing ThFT or in not including c. However, a process does not contain the process alone, usually, a waiting line exists in front of each process (even is capacity is larger or much larger than demand Rp>>R), Why? A Simple Process R Waiting Line Process R 1 1. The Application to Waiting Lines: In earlier chapters, we were introduced to formulas like: I. • II. • Flow time 𝑇𝑇 = 𝑇𝑇𝑖𝑖 + 𝑇𝑇𝑝𝑝 Explains that flow time (𝑇𝑇) is equal to buffer time (𝑇𝑇𝑖𝑖 ) + processing time (𝑇𝑇𝑝𝑝 ) Inventory 𝐼𝐼 = 𝐼𝐼𝑖𝑖 + 𝐼𝐼𝑝𝑝 Explains that Inventory (𝐼𝐼) is equal to the number of flow units in the buffer (𝐼𝐼𝑖𝑖 ) + the total number of flow units in all processors (𝐼𝐼𝑝𝑝 ) III. • 𝐼𝐼𝑖𝑖 = 𝑅𝑅 𝑥𝑥 𝑇𝑇𝑖𝑖 Explains that the number of flow units in the buffer (𝐼𝐼𝑖𝑖 ) is equal to throughput (𝑅𝑅 x buffer time (𝑇𝑇𝑖𝑖 ) IV. 𝐼𝐼𝑝𝑝 = 𝑅𝑅 𝑥𝑥 𝑇𝑇𝑝𝑝 • Explains that the total number of flow units in all processors (𝐼𝐼𝑝𝑝 ) is equal to throughput x processing time (𝑇𝑇𝑝𝑝 ) 2 Hence we can conclude that: 𝑹𝑹 = 𝑰𝑰𝒑𝒑 𝑰𝑰 𝑰𝑰𝒊𝒊 = = 𝑻𝑻 𝑻𝑻𝒊𝒊 𝑻𝑻𝒑𝒑 We also have to take into consideration the formulas that we learn in Capacity such as: I. • II. • III. • 𝑼𝑼 = 𝑹𝑹/𝑹𝑹𝒑𝒑 Explains that utilization is equal to throughput (𝑅𝑅) divided capacity (𝑅𝑅𝑝𝑝 ) 𝑹𝑹𝒑𝒑 = 𝒄𝒄/𝑻𝑻𝒑𝒑 Explains that Capacity (𝑅𝑅𝑝𝑝 ) is equal to the number of processors (𝑐𝑐) divided by processing time (𝑇𝑇𝑝𝑝 ) 𝑹𝑹 = 𝑰𝑰𝒑𝒑 /𝑻𝑻𝒑𝒑 Explains that throughput (𝑅𝑅) is equal to the total number of flow units in all processors (𝐼𝐼𝑝𝑝 ) divided by processing time (𝑇𝑇𝑝𝑝 ) Hence we conclude that: 𝑼𝑼 = 𝑰𝑰𝒑𝒑 𝑰𝑰𝒑𝒑 𝑹𝑹 𝒄𝒄 = � �� � = 𝑹𝑹𝒑𝒑 𝑻𝑻𝒑𝒑 𝑻𝑻𝒑𝒑 𝒄𝒄 B. Characteristics of Waiting Lines 𝑼𝑼 = 𝑰𝑰𝒑𝒑 𝒄𝒄 1. Variability in arrival time and service time leads to a) Idleness of resources b) Waiting time of flow units 3 As utilization goes up, the number of people in the buffer goes up. The other one is variability; If every four minutes, exactly every four minutes, one customer arrives, and it takes exactly three minutes for that flow unit to pass the processor, then we never observe the waiting line. In this case, utilization is one hundred percent, that is the maximum possible utilization, but there is absolutely no variability, neither in inter-arrival time nor flow time, then we never see flow units in the buffer. 2. We are interested in two measures a) Average waiting time of flow units in the waiting line and in the system (Waiting line + Processor). b) Average number of flow units waiting in the waiting line (to be then processed). C. Operational Performance Measures As explained earlier, if we know 𝑅𝑅, and we know 𝑇𝑇𝑝𝑝 , we can easily computer 𝐼𝐼𝑝𝑝 . Therefore all we need to compute is 𝑇𝑇𝑖𝑖 𝑎𝑎𝑎𝑎𝑎𝑎 𝐼𝐼𝑖𝑖 . And if we know one of them because we know throughput (𝑅𝑅), then we can computer the other one. I. Flow time II. Inventory 𝑇𝑇 = 𝑇𝑇𝑖𝑖 + 𝑇𝑇𝑝𝑝 𝐼𝐼 = 𝐼𝐼𝑖𝑖 + 𝐼𝐼𝑝𝑝 We have an approximation formula for Ii and we have exact formula for some specific cases of waiting line. D. Utilization – Variability - Delay Curve The graph below explains the relationship between utilization and variability. As utilization increases, the waiting time increases and as variability increases, the waiting time increases and vice versa. 4 1. Utilization and Variability: A. Our two measures of effectiveness (average number of flow units waiting and their average waiting time) are driven by 1. Utilization: The higher the utilization the longer the waiting line/time. 2. Variability: The higher the variability, the longer the waiting line/time. B. High utilization 𝑈𝑈 = 𝑅𝑅/𝑅𝑅𝑝𝑝 or low safety capacity 𝑅𝑅𝑅𝑅 = 𝑅𝑅𝑝𝑝 − 𝑅𝑅, due to 1. High inflow rate 𝑹𝑹 5 2. Low processing rate 𝑹𝑹𝒑𝒑 = 𝒄𝒄/𝑻𝑻𝒑𝒑 , which may be due to small-scale c and/or slow speed 1/𝑇𝑇𝑝𝑝 2. Drivers of Process Performance: Variability in the inter arrival time and processing time is measured using standard deviation (or Variance). Higher standard deviation (or Variance) means greater variability. The formula for variance is: 𝑉𝑉(𝑋𝑋) = 𝐸𝐸[(𝑋𝑋 − 𝜇𝜇𝑥𝑥 )2 Standard deviation is computed by taking the square root of variance. The formula for standard deviation is: 𝜎𝜎𝑋𝑋 = �𝑉𝑉(𝑥𝑥) = �𝐸𝐸[(𝑋𝑋 − 𝜇𝜇𝑥𝑥 )2 ] Standard deviation is not enough to understand the extent of variability. Does a standard deviation of 20 for an average of 80 represents more variability or a standard deviation of 150 for an average of 1000? Coefficient of Variation: The ratios of the standard deviation of inter arrival time (or processing time) to the mean (average). We refer to coefficient of variation of inter-arrival time as 𝐶𝐶𝑎𝑎 , and coefficient of variation of processing time as 𝐶𝐶𝑝𝑝 , capital 𝐶𝐶. The number of servers we show it by small 𝑐𝑐, coefficient of variation, we show it by capital 𝐶𝐶. Capital 𝐶𝐶 small 𝑎𝑎 for coefficient of variation of interarrival time, and capital 𝐶𝐶 small 𝑝𝑝 for coefficient of variation of processing time. 𝑪𝑪𝒂𝒂= 𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄 𝒐𝒐𝒐𝒐 𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗 𝒇𝒇𝒇𝒇𝒇𝒇 𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊 𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕 𝑪𝑪𝒑𝒑= 𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄 𝒐𝒐𝒐𝒐 𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗𝒗 𝒇𝒇𝒇𝒇𝒇𝒇 𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑 𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕 3. The Queue Length Approximation Formula: The approximation formula is used for the number of flow units in the buffer. Ii, the number of flow units in the buffer is equal to utilization to the power of two times one plus the number of servers divided by one minus the utilization and we refer to it as utilization affect or u-part. Utilization affect is multiplied by variability affect. And that is squared coefficient of variability of inter-arrival time plus square of coefficient of variability of processing time divided by two. And we refer to it as variability affect or vpart. 𝐼𝐼𝑖𝑖 = 𝑈𝑈 �2(𝑐𝑐+1) 𝐶𝐶𝐶𝐶2 + 𝐶𝐶𝐶𝐶2 x 1 − 𝑈𝑈 2 6 And we have to keep in mind that: • • • 𝑅𝑅 𝑈𝑈 = 𝑅𝑅 , 𝑤𝑤ℎ𝑒𝑒𝑒𝑒𝑒𝑒 𝑅𝑅𝑝𝑝 = 𝑐𝑐/𝑇𝑇𝑝𝑝 𝑝𝑝 𝐶𝐶𝑎𝑎 and 𝐶𝐶𝑝𝑝 are the Coefficients of Variation Standard Deviation/Mean of the inter-arrival or processing times (assumed independent) 4. Factors affecting Queue Length: A. Utilization effect; the queue length increases rapidly as 𝑈𝑈 approaches 1. 𝐼𝐼𝑖𝑖 = 𝑈𝑈 �2(𝑐𝑐+1) 1 − 𝑈𝑈 B. Variability effect; the queue length increases as the variability in inter arrival and processing times increases. 𝐶𝐶𝐶𝐶2 + 𝐶𝐶𝐶𝐶2 2 C. While the capacity is not fully utilized, if there is variability in arrival or in processing times, queues will build up and customers will have to wait. E. Coefficient of Variations for Alternative Distributions: • • • • 𝑇𝑇𝑝𝑝 : average processing time: 𝑅𝑅𝑝𝑝 = 𝑐𝑐/𝑇𝑇𝑝𝑝 𝑇𝑇𝑎𝑎 : average inter arrival time: 𝑅𝑅𝑎𝑎 = 1/𝑇𝑇𝑎𝑎 𝑆𝑆𝑝𝑝 : standard deviation of the processing time 𝑆𝑆𝑎𝑎 : standard deviation of the inter arrival time If processing time does not have a specific distribution such as exponential, Poisson, or constant, and if its average is 𝑇𝑇𝑝𝑝 , and its standard deviation is 𝑆𝑆𝑝𝑝 , then its coefficient of variation, is 𝑆𝑆 𝑝𝑝 divided by 𝑝𝑝 . 7 The same is for inter-arrival time. If inter-arrival time is a general distribution, and by general distribution we mean it is not Poisson, not exponential, and it is not constant, and it has an average of 𝑇𝑇𝑎𝑎 and standard deviation of 𝑆𝑆𝑎𝑎 , then for inter-arrival time, coefficient of variation is 𝑆𝑆𝑎𝑎 divided by 𝑇𝑇. This is explained by the table below: Inter arrival time or Processing Time distribution Mean arrival time or Processing Time Standard deviation ofInter arrival time or Processing Time Coefficient of Variation of Inter arrival time or Processing Time General (G) Poisson (M) Exponential (M) Constant (D) 𝑇𝑇𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑇𝑇𝑎𝑎 ) 𝑇𝑇𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑇𝑇𝑎𝑎 ) 𝑇𝑇𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑇𝑇𝑎𝑎 ) 𝑇𝑇𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑇𝑇𝑎𝑎 ) 1 1 0 𝑆𝑆𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑇𝑇𝑎𝑎 ) 𝑆𝑆𝑝𝑝 /𝑇𝑇𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑆𝑆𝑎𝑎 /𝑇𝑇𝑎𝑎 ) 𝑇𝑇𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑇𝑇𝑎𝑎 ) 𝑇𝑇𝑝𝑝 (𝑜𝑜𝑜𝑜 𝑇𝑇𝑎𝑎 ) 0 Therefore exponential distribution shows the time between two events and Poisson distribution shows the number of events over a specific time period. Example 1: A sample of 10 observations on inter arrival times in minutes are: 10, 10, 2, 10, 1, 3, 7, 9, 2, 6 minutes. 𝑇𝑇𝑎𝑎 = average of sample = 6 minutes Systems and Operations Management Study Guide, Ardavan Asef-Vaziri 8 1 1 𝑅𝑅𝑎𝑎 = 𝑇𝑇 = 6 arrivals per minute 𝑎𝑎 𝑆𝑆𝑎𝑎 = standard deviation, found through the use of excel: 3.94 𝐶𝐶𝑎𝑎 = 𝑆𝑆𝑎𝑎 /𝑇𝑇𝑎𝑎 = 3.94/6 = 0.66 Example 1b: A sample of 10 observations on inter arrival times in minutes are: 7, 1, 7, 2, 8, 7, 4, 8, 5, 1 minutes. 𝑇𝑇𝑝𝑝 = average of sample = 5 minutes 1 1 𝑅𝑅𝑝𝑝 = 𝑇𝑇 = 5 arrivals per minute 𝑝𝑝 𝑆𝑆𝑝𝑝 = standard deviation, found through the use of excel: 2.83 𝐶𝐶𝑝𝑝 = 𝑆𝑆𝑝𝑝 /𝑇𝑇𝑝𝑝 = 2.83 /5 = 0.57 Using examples 1 and 1b, we are able to figure out how many people are in the waiting line and what is the safety capacity with the use of the queue length approximation formula. We can also compute what is the waiting time in the line and system. (Example 1c) Example 1c: 1 𝑅𝑅𝑎𝑎 = 6 per minute or 10 per hour. 1 𝑅𝑅𝑝𝑝 = 5 per minute or 12 per hour. 𝑅𝑅𝑎𝑎 < 𝑅𝑅𝑝𝑝 . Since 𝑅𝑅𝑎𝑎 = 𝑅𝑅, 𝑈𝑈 = 𝑅𝑅/𝑅𝑅𝑝𝑝 = (1/6)/(1/5) = 0.83 𝐶𝐶𝑎𝑎 = 0.66 and 𝐶𝐶𝑝𝑝 = 0.57 By using the queue length approximation formula, we have the following: 9 0.83�2(1+1) 0.662 + 0.572 𝐼𝐼𝑖𝑖 = x 1 − 0.83 2 𝐼𝐼𝑖𝑖 = 1.56 passengers waiting in line. To compute safety capacity, we use 𝑅𝑅𝑅𝑅 = 𝑅𝑅𝑝𝑝 − 𝑅𝑅. 𝑅𝑅𝑅𝑅 = (1/5) – (1/6) = 1/30 passengers per minute or (60)(1/30) = 2 passenger per hour. We want to compute what is the waiting time for each person in the waiting line. The Little’s law states that I = RT, therefore 𝑅𝑅𝑇𝑇𝑖𝑖 = 𝐼𝐼𝑖𝑖 . We can conclude that 𝑇𝑇𝑖𝑖 = 𝐼𝐼𝑖𝑖 /𝑅𝑅. 𝑇𝑇𝑖𝑖 =1.56/(1/6) = 9.4 minutes The approximate waiting time in the line is 9.4 minutes. We can also calculate the waiting time in the whole system. 𝑇𝑇 = 𝑇𝑇𝑖𝑖 + 𝑇𝑇𝑝𝑝 Because we know that 𝑇𝑇𝑝𝑝 is 5 minute, the waiting time in the whole system is 14.4 minutes (5 + 9.4). Using Little’s Law (I = RT) we are able to calculate the total number of people in the system. 1 𝐼𝐼 = 𝑅𝑅𝑅𝑅 = �6� (14.4) = 2.4 people We know that there are 1.56 people in the buffer. To calculate the total number of people in the processor, we add 1.56 to .83, the arrivals per minute to get 2.39. Now let us suppose we have two servers instead of one, are we able to calculate the new waiting line and time? The following examples show how two servers change the waiting line and waiting time. 10 Example 1c-a: 1 𝑅𝑅𝑎𝑎 = 6 per minute or 10 per hour. 2 𝑅𝑅𝑝𝑝 = 5 per minute or 24 per hour. 𝑅𝑅𝑎𝑎 < 𝑅𝑅𝑝𝑝 . Since 𝑅𝑅𝑎𝑎 = 𝑅𝑅, 𝑈𝑈 = 𝑅𝑅/𝑅𝑅𝑝𝑝 = (1/6)/(2/5) = (5/12) = 0.417 𝐶𝐶𝑎𝑎 = 0.66 and 𝐶𝐶𝑝𝑝 = 0.57 By using the queue length approximation formula, we have the following: 0.417�2(2+1) 0.662 + 0.572 𝐼𝐼𝑖𝑖 = x 1 − 0.417 2 𝐼𝐼𝑖𝑖 = 0.076 passengers waiting in line. To compute safety capacity, we use 𝑅𝑅𝑅𝑅 = 𝑅𝑅𝑝𝑝 − 𝑅𝑅. 𝑅𝑅𝑅𝑅 = (2/5) – (1/6) = 7/30 passengers per minute or (60)(7/30) = 14 passenger per hour. We want to compute what is the waiting time for each person in the waiting line. The Little’s law states that I = RT, therefore 𝑅𝑅𝑇𝑇𝑖𝑖 = 𝐼𝐼𝑖𝑖 . We can conclude that 𝑇𝑇𝑖𝑖 = 𝐼𝐼𝑖𝑖 /𝑅𝑅. 𝑇𝑇𝑖𝑖 =0.076/(1/6) = 0.46 minutes The approximate waiting time in the line is 9.4 minutes. We can also calculate the waiting time in the whole system. 𝑇𝑇 = 𝑇𝑇𝑖𝑖 + 𝑇𝑇𝑝𝑝 Because we know that 𝑇𝑇𝑝𝑝 is 5 minute, the waiting time in the whole system is 5.46 minutes (5 + 0.46). 11 Using Little’s Law (I = RT) we are able to calculate the total number of people in the system. 1 𝐼𝐼 = 𝑅𝑅𝑅𝑅 = �6� (5.46) = 0.91 people We know that there are 0.076 people in the buffer. To calculate the total number of people in the processor, we add 0.076 to 0.417, the arrivals per minute to get 0.91. Example 2: A call center has 11 operators. The arrival rate of calls is 200 calls per hour. Each of the operators can serve 20 customers per hour. Assume inter-arrival time and processing time follow Poisson and Exponential, respectively. What is the average waiting time (time before a customer’s call is answered?) By using the queue length approximation formula, we have the following: 0.91�2(11+1) 12 + 12 x 𝐼𝐼𝑖𝑖 = 1 − 0.91 2 Therefore: 𝐼𝐼𝑖𝑖 = 6.89 𝐼𝐼 = 𝑅𝑅𝑅𝑅 = 200(𝑇𝑇𝑖𝑖 ) = 6.89 𝑇𝑇𝑖𝑖 = 2.1 minutes Example 2a: The average waiting time before a call is answered is 2.1 minutes. Now let us suppose the service time is constant. Will the waiting time be more or less than 2.1 minutes? 0.91�2(11+1) 12 + 02 𝐼𝐼𝑖𝑖 = x 1 − 0.91 2 12 Therefore: 𝐼𝐼𝑖𝑖 = 3.45 𝐼𝐼 = 𝑅𝑅𝑅𝑅 = 200(𝑇𝑇𝑖𝑖 ) = 3.45 𝑇𝑇𝑖𝑖 = 1.03 minutes Example 3: Vons contains 7 checkout stands. The arrival rate of customers is 175 per hour. Each of the checkout stands can serve 15 customers per hour. What is the average waiting time (time before a customer gets to the cashier?) By using the queue length approximation formula, we have the following: 0.92�2(7+1) 12 + 12 𝐼𝐼𝑖𝑖 = x 1 − 0.92 2 𝐼𝐼𝑖𝑖 = 8.95 minutes Example 4: A small room has been assigned on a University campus, for honor students to have a quiet place to study by themselves. Since the room is so small, the only other use for it would be storage. The room is open 16 hours every day. Only one student can use the room at a time. The dean wants to know if the room is being fully utilized by students, or of the room should be changed to a storage space. The best SOM professor at the University was assigned to solve this problem. In his research, he found that students arrive at the room at a rate of 3 per hour following Poisson distribution. The students stay in the room an average of 15 minutes and deviation of 5 minutes. a. What percentage of time is the room idle (rounded)? (3 ∗ 15) =1− = 25% 60 b. What is the utilization rate of the room? (3 ∗ 15) = = 75% 60 c. What is the average number of students in the waiting line? 0.75 2 (1+1) Ii = = 2.25 (1 − 0.75) d. How much time, on average, does a student spend in the waiting line? 13 𝐼𝐼 = 𝑅𝑅𝑅𝑅 = 3𝑇𝑇 = 2.25 𝑇𝑇 = .75 ℎ𝑟𝑟𝑟𝑟 = 45 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 Example 5: Yogurtland has one cashier. Every 5 minutes, a new customer comes in. It takes the cashier about 5 minutes to weigh the yogurt and ring up each customer. Yogurtland has been losing customers to the new frozen yogurt shop next door. In order to stop this, Yogurtland has implemented a new policy to pay customers waiting in line. The customer will get paid 1 dollar per minute of waiting time. A SOM professor has been recruited from a nearby university to analyze the cost of the new pay while you wait policy. Preliminary studies the SOM professor did, indicated that there are an average of .5 people waiting in line. Assume that arrivals follow Poisson and service time follows exponential distribution. a. What is the capacity of the cashier per hour? It takes a cashier 5 minutes per customer, therefore, 60 minutes / 5 minutes per customer = 12 customers. b. What proportion of the time is the cashier busy? 𝑅𝑅 𝑈𝑈 = 𝑅𝑅 = 6/12 = 50% 𝑝𝑝 c. On average, how long does a customer wait in line? .05 * 60 minutes = 3 minutes d. What is the hourly cost of the new policy? The hourly cost of the new policy is 1 * 60 = $60. Because there are .5 customers in the line at all ties, .5 * 60 = $30. e. What is the most Yogurtland would be willing to pay for another cashier? Answer = $30. Another cashier would increase Rp to 24 customers per hour. If Rp is 24 per hour, there would be no waiting line because there are only 12 customer per hour. Yogurtland would only be willing to pay the amount that would be saved by having a new cashier. 14