U.S. Copyright Law (title 17 of U.S. code) governs the reproduction and redistribution of copyrighted material. Downloading this document for the purpose of redistribution is prohibited. Chapter 15 QUEUING CHAPTER OUTLINE 15.1 Introduction 15.2 The Basic Model 15.3 A Taxonomy of Queuing Models 15.4 Little's Flow Equation and Related Results 15.5 The M/G/1 Queue 15.6 Model 1: An M/M/s Queue (Hematology Lab) 15.7 Economic Analysis of Queuing Systems 15.8 Model 2: A Finite Queue (WATS Lines) 15.9 Model 3: The Repairperson Model 15.10 Transient Versus Steady-State Results: Order Promising 15.11 The Role of the Exponential Distribution 15.12 Queue Discipline 15.13 Notes on Implementation 15.14 Summary KEY TERMS SELF-REVIEW EXERCISES PROBLEMS CASE 1: HOW MANY OPERATORS? REFERENCES CD15-2 C D C H A P T E R S APPLICATION OUTLINE Shortening the New York City Police Department's Arrest-to-Arraignment Time In 1988, New York City (NYC)'s arrestees were in custody waiting to be arraigned for an average of 44 hours, occasionally for more than 72 hours. Moreover, they were held in crowded, noisy conditions that were emotionally stressful, unhealthy, and often physically dangerous. In March 1990, the New York Times ran a front-page story on a woman who spent 45 hours in pre-arraignment detention in the Bronx with the headline \"Trapped in the Terror of New York's Holding Pens.\" Arrestees were being denied a speedy court appearance and the lengthy delays greatly diminished the efficiency of the justice system. That same year, the NY Supreme Court ruled that the city was to attempt to arraign within 24 hours or release the prisoner. Under these circumstances, NYC undertook the single most ambitious management science project to date in its history with the goal of reducing the arrest-to-arraignment (ATA) time. There were basically four different boroughs (Manhattan, Bronx, Brooklyn, and Queens), each with its own idiosyncratic ways of doing things. The basic process included the following basic steps, which comprise a large queuing system: arrest by an officer of NYPD; taken to precinct where prisoner is searched, fingerprinted, and detained while an arrest report is completed; taken to central booking where fingerprints are faxed to state capital for identification and report of criminal history, the arresting officer fills out more paperwork including the sworn complaint with the assistant district attorney, and the arrestee is lodged to await arraignment. In 1988, in these four boroughs alone, over 325,000 arrests were made for which the defendants could be detained awaiting arraignment (i.e., more serious crimes). Unlike many other jurisdictions in the United States, in NYC felonies predominate, many of them involving violence or illicit drugs. Thus, an arrestee might find himself in the same holding cell with violent repeat offenders or defendants in drug episodes. 15.1 INTRODUCTION The project team mounted an extensive two-year effort. While the lengthy delays in ATA time were the key factor to study, the high costs associated with the current ATA process were an additional item of study. One of the contributors to these high costs was that arresting officers were spending an average of more than 8 hours from the time they departed central booking until they swore out the complaint. Much of this time was overtime and the task itself only required 30 minutes! They were waiting in line for 71\\2 hours! The whole process was modeled as a series of stages. Some of the stages were modeled as single-server queues, others as multiple-server queues, and some were even more complex. The statistical distributions and their corresponding parameters for each stage had to be determined. The overall model could then look at various different what-if scenarios involving combinations of workloads and arrest processing policies. The model generated several types of output including average overall ATA time and average times for completing individual stages of the process. The cost of each of the scenarios could also be generated by a companion spreadsheet model. NYC could then choose between several different alternatives, each with its own cost and performance measure. In May 1990, Mayor David Dinkins released the findings of this project at a press conference with his strong endorsement of its recommended changes. The model saved the city over $10 million per year in police overtime costs alone. The city has reduced the average ATA time delay from 44 hours to about 24 hours citywide. Arrestees gain the right to a speedier trial and are no longer \"warehoused\" under horrible conditions for longer than absolutely necessary. The city has also greatly reduced its costs for prisoner supervision and transportation by about $11 million per year. One final recommendation was the elimination of a single arraignment courtroom. This resulted in additional savings of $9.5 million for the city and state. (See Larson et al.) Queuing models are everywhere. This fact is obvious even to the most casual observer. Airplanes \"queue up\" in holding patterns, waiting for a runway so they can land, and then they line up again to take off. People line up for tickets, to buy groceries, and, if they happen to live in England, for almost everything else. Jobs line up for machines, orders line up to be filled, and so on. As you can probably tell, queue is the British term for any type of line for waiting. The Danish engineer A. K. Erlang is credited with founding queuing theory by studying telephone switchboards in Copenhagen for the Danish Telephone Company. He developed many of the queuing results used today. One of the greatest uses of queuing theory in the United States is for analyzing automobile traffic flowstudying how many lanes to have, how to regulate the traffic lights, and so forthin order to maximize the flow of traffic. C H A P T E R FIGURE 15.1 Arrivals General Queuing Models 00000 1 5 Queuing CD15-3 Service facility Monte Jackson might not subscribe to the notion that all of life is a queue, but as administrative director of St. Luke's Hospital in Philadelphia, he must deal with a number of situations that can be described as queuing models. Briefly, a queuing model is one in which you have a sequence of items (such as people) arriving at a facility for service, as shown in Figure 15.1. At this moment, Monte is concerned about three particular \"queuing models.\" Model 1: St. Luke's Hematology Lab St. Luke's treats a large number of patients on an outpatient basis; that is, there are many patients who come to the hospital to see the staff doctors for diagnosis and treatment but who are not admitted to the hospital. Outpatients plus those admitted to the 600-bed hospital produce a large flow of new patients each day. Most new patients must visit the hematology laboratory as part of the diagnostic process. Each such patient has to be seen by a technician. The system works like this: After seeing a doctor, the patient arrives at the laboratory and checks in with a clerk. Patients are assigned on a first-come, first-served basis to test rooms as they become available. The technician assigned to that room performs the tests ordered by the doctor. When the testing is complete, the patient goes on to the next step in the process (perhaps X-ray), and the technician sees a new patient. Monte must decide how many technicians to hire. Superficially, at least, the trade-off is obvious. More technicians means more expense for the hospital, but quicker service for the patients. Model 2: Buying WATS Lines As part of its remodeling process, St. Luke's is designing a new communications system. Monte must decide how many WATS lines the hospital should buy. WATS (Wide Area Telephone Service) is an acronym for a special flat-rate, long-distance service offered by some phone companies. When all the phone lines allocated to WATS are in use, the person dialing out will get a busy signal, indicating that the call can't be completed. Monte knows that when people pick up the phone, they want to get through without having to try several times. How many lines he needs to achieve that result at a reasonable cost is not so clear. Model 3: Hiring Repairpeople St. Luke's hires repairpeople to maintain 20 individual pieces of electronic equipment. The equipment includes measuring devices such as the electrocardiogram machine, small dedicated computers like the one used for lung analysis, and equipment such as the CAT scanner. If a piece of equipment fails and all the repairpeople are occupied, it must wait to be repaired. Monte must decide how many repairpeople to hire. He must balance their cost against the cost of having broken equipment. As Table 15.1 indicates, all three of these models fit the general description of a queuing model. Monte will resolve these models by using a combination of analytic and simulation models. However, before we reach the level of sophistication required to deal with Monte's specific models, it is necessary for us to spend some time with the basic queuing model. In the process we will learn some terminology, and we will see the type of analytic results that are available. Table 15.1 Some Queuing Models PROBLEM ARRIVALS SERVICE FACILITY 1 2 3 Patients Telephone Calls Broken Equipment Technicians Switchboard Repairpeople CD15-4 C D 15.2 THE BASIC MODEL C H A P T E R S Consider the Xerox machine located in the fourth-floor secretarial service suite. Assume that users arrive at the machine and form a single line. Each arrival in turn uses the machine to perform a specific task. These tasks vary from obtaining a copy of a 1-page letter to producing 100 copies of a 25-page report. This system is called a single-server (or single-channel) queue. Questions about this or any other queuing system center on four quantities: 1. The number of people in the system: the number of people currently being served, as well as those waiting for service. 2. The number of people in the queue: the number of people waiting for service. 3. The waiting time in the system: the interval between when an individual enters the system and when he or she leaves the system. Note that this interval includes the service time. 4. The waiting time in the queue: the time between entering the system and the beginning of service. ASSUMPTIONS OF THE BASIC MODEL 1. Arrival Process. Each arrival will be called a \"job.\" Since the time between arrivals (the interarrival time) is not known with certainty, we will need to specify a probability distribution for it. In the basic model a particular distribution, called the exponential distribution (sometimes called the negative exponential distribution), is used. This distribution plays a central role in many queuing models. It provides a reasonable representation of the arrival process in a number of situations, and its so-called lack of memory property makes it possible to obtain analytic results. The exponential distribution is not symmetric, a fact that bothers people who think that an \"average\" must have as many values above the mean as below it. For example, if customers arrive, on the average, every 5 minutes according to an exponential distribution, then approximately 2\\3 of them will have interarrival times less than 5 minutes, and only about 1\\3 of them longer than 5 minutes (but some of those may be very long and thus \"skew\" the average). The exponential distribution describes many services (bank tellers, postal clerks). About 2\\3 of the service times will be below the mean time (a lot of short, quick transactions) and 1\\3 of the service times will be above the mean (someone with the cash receipts from his or her business, or a person mailing a package overseas). The words Poisson input are also used to describe the arrival process when the time between arrivals has an exponential distribution. This is because of the relationship between the exponential distribution and the Poisson distribution. In particular, if the interarrival time has an exponential distribution, the number of arrivals in a specified length of time (say, three hours) has a Poisson distribution. The exponential distribution and its relationship to the Poisson is discussed in some detail in Section 15.11. At this point, it is only necessary to understand that the exponential distribution is completely specified by one parameter. This parameter, called \u0002, is the mean arrival rate; that is, how many jobs arrive (on the average) during a specific period of time. In a moment we will consider an example in which \u0002 = 0.05 jobs per minute. This implies that on the average 5\\100 of a job arrives every minute. It is probably more natural to think in terms of a longer time interval. An equivalent statement is that on the average one job arrives every 20 minutes. Using more technical terms, we say that the mean interarrival time is 20 minutes. Mean interarrival time is the average time between two arrivals. Thus, for the exponential distribution average time between jobs = mean interarrival time = Thus, if \u0002 = 0.05, mean interarrival time = 1 1 = 20 = \u0002 0.05 1 \u0002 (15.1) C H A P T E R 1 5 Queuing CD15-5 2. Service Process. In the basic model, the time that it takes to complete a job (the service time) is also treated with the exponential distribution. The parameter for this exponential distribution is called \u0003. It represents the mean service rate in jobs per minute. In other words, \u0003T is the number of jobs that would be served (on the average) during a period of T minutes if the machine were busy during that time. In the upcoming example we will assume that \u0003 = 0.10. This implies that on the average 0.10 of a job is completed each minute. An equivalent statement is that on the average one job is completed every 10 minutes. The mean, or average, service time (the average time to complete a job) is 1/\u0003. When \u0003, the mean service rate, is 0.10, the average service time is 10 since 1/\u0003 = 1/0.10 = 10. 3. Queue Size. There is no limit on the number of jobs that can wait in the queue. The queue is said to be infinite. 4. Queue Discipline. Jobs are served on a first-come, first-served basis; that is, in the same order as they arrive at the queue. 5. Time Horizon. The system operates as described continuously over an infinite horizon. 6. Source Population. There is an infinite population available to arrive. Consider these assumptions in the context of the Xerox model. Suppose that the average arrival time between jobs is 20 minutes. As we have seen, the fact that the interarrival time has an exponential distribution means that 1/\u0002 = 20, and thus \u0002 = 0.05, or that the jobs arrive at the rate of 0.05 job per minute. Similarly, if the average time to complete a job is 10 minutes, we know that 1/\u0003 = 10, and thus \u0003 = 0.10, or that jobs are completed at the rate of 0.10 job per minute when the machine is operating. CHARACTERISTICS OF THE BASIC MODEL The values of these two parameters (together with the assumptions) are all that is needed to calculate several important operating characteristics of the basic model. The necessary formulas are presented in Table 15.2 WARNING! The formulas in Table 15.2 hold only if \u0002 < \u0003. If this condition does not hold (i.e., if \u0002 \u0003), the number of people in the queue will grow without limit. Consider, for example, a specific case where \u0002 = 0.25 and \u0003 = 0.10. Remember that 1/\u0002 is the average interarrival time. Thus, since 1/\u0002 = 1/0.25 = 4, on the average a job arrives every 4 minutes. Similarly, 1/\u0003 is the average time it takes to complete a job. Since 1/\u0003 = 1/0.10 = 10, on the average it takes 10 minutes to complete a job. It seems clear that in this case the service operation will get further behind (the queue will grow longer) as time goes by. Now return to the Xerox model, in which \u0002 < \u0003 and the formulas in Table 15.2 hold. Spreadsheets are ideal for crunching the numerical results from such formulas. We will use Table 15.2 Operating Characteristics for the Basic Model CHARACTERISTIC SYMBOL FORMULA Utilization \u0002/\u0003 Expected Number in System L Expected Number in Queue Lq Expected Waiting Time (Includes Service Time) W Expected Time in Queue Wq Probability that the System is Empty P0 \u0002 \u0003-\u0002 \u00022 \u0003(\u0003 - \u0002) 1 \u0003-\u0002 \u0002 \u0003(\u0003 - \u0002) 1 - \u0002/\u0003 CD15-6 C D C H A P T E R S FIGURE 15.2 Introductory Page of Queuing Workbook an Excel spreadsheet (Q.XLS) that was originally developed by Professor David Ashley and that already has these formulas entered. When you first open the spreadsheet you see the introductory page as shown in Figure 15.2 (note that there are four different worksheets [MMs, MG1, finiteQ, finitePopulation] to be used as indicated by the tabs at the bottom of the spreadsheet). Plugging the numerical values from the Xerox model, \u0002 = 0.05 and \u0003 = 0.10, into the appropriate cells (E2 and E3) of the appropriate worksheet (\"MMs\" in this example) yields the results presented in Figure 15.3. We also have to tell it that we have only one server (i.e., one copy machine) and that our time unit is minutes. Steady-State Results These numbers require some interpretation. L, for example, is the expected number of people in the system (those being served plus those waiting) after the queue has reached steady state. In this sentence, steady state means that the probability that you will observe a certain number of people (say, 2) in the system does not depend on the time at which you count them. If a steady state has been achieved, the probability that there are two people using and/or waiting for the Xerox machine should be the same at 2:30 P.M. and at 4:00 P.M. The other characteristics presented in Figure 15.3 have a similar interpretation. Thus, in a steady state, (1) the system is empty with a probability of one-half (cell F7 shows that FIGURE 15.3 Evaluating the Operating Characteristics of the Basic Model C H A P T E R 1 5 Queuing CD15-7 P0 = 0.5); (2) on the average there is 0.5 person in the queue (cell F8 shows that Lq = 0.5); (3) on the average an arrival must wait 10 minutes before starting to use the machine (cell F10 shows that Wq = 10); and (4) on the average an arrival will spend 20 minutes in the system (cell F11 shows that W = 20). Remember that these values are averages and, as such, may have the same characteristics as the exponential distribution (2\\3 of observations below mean, 1\\3 above). Thus, 2\\3 of the customers will spend less than 10 minutes in line, while 1\\3 will spend more than 10 minutes in line. Using the Results These results hold for the basic model and the particular values for the parameters (\u0002 = 0.05 and \u0003 = 0.10). They provide information that is useful to management in analyzing this service facility. Suppose, for example, that management makes the following calculations: Since \u0002 = 0.05, on the average 5\\100 of a job arrives each minute. During each 8-hour day there are 8 60 = 480 minutes. Thus, during each day there is on the average a total of (0.05)(480) = 24 arrivals. From the calculations in Figure 15.3 we know that on the average each person spends 20 minutes in the system (W = 20). Thus, a total of (24 arrivals per day) (20 minutes per arrival) = 480 minutes, or 8 hours, is spent at this facility. Management might well feel that this is too long. A variety of steps might be taken: 1. A new machine might be purchased with a smaller mean service time. 2. Another machine might be purchased and both machines used to satisfy the demand. This would change the system to a two-server queue. 3. Some personnel might be sent to a different and less busy copying facility. This would change the arrival process. Management might select one of these alternatives, or perhaps some other option. But in any case, management must balance the cost of providing service against the cost of waiting. The results in Figure 15.3 and similar results for other systems would be a central part of the analysis. These ideas will be developed in more detail in the context of Monte Jackson's models. 15.3 A TAXONOMY OF QUEUING MODELS There are many possible queuing models. For example, if the interarrival time in the basic model had been given a different distribution (not the exponential) we would have had a different model, in the sense that the previous formulas for L, Lq, and so on, would no longer hold. To facilitate communication among those working on queuing models, D. G. Kendall proposed a taxonomy based on the following notation: A/B/s where A = arrival distribution B = service distribution s = number of servers Different letters are used to designate certain distributions. Placed in the A or the B position, they indicate the arrival or the service distribution, respectively. The following conventions are in general use: M = exponential distribution D = deterministic number G = any (a general) distribution of service times GI = any (a general) distribution of arrival times We can see, for example, that the Xerox model is an M/M/1 model; that is, a singleserver queue with exponential interarrival and service times. CD15-8 C D C H A P T E R S APPLICATION CAPSULE Merging Traffic: A Queuing Simulation Helps Eliminate a Costly Bottleneck The Westinghouse Hanford Company in Richland, Washington, is a secured work facility: All vehicles and passengers are checked at a guard station before being allowed onto the premises. This security checkpoint created enormous traffic backups during shift changes, when the volume of entering vehicles was greatest. The result was a severe hazard for the workforce and a major loss of productivity for the company as personnel were detained in long lines. An in-house engineering group was therefore asked to study the problem and make recommendations for changes. The study group found that each workday morning an average of 7 buses and 283 cars and vans arrived at the plant. Upon approaching the entrance gate, the vehicles formed one line to pass through the checkpoint, which was normally manned by two guards during rush periods. The line extended past the available queue space (which could accommodate only 40 cars) and spilled out onto the adjacent highway, causing a major safety problem. Because of the long line, drivers of other vehicles often elected to continue down the highway to a second gate. This option meant additional time and distance for the employees, as well as an unknown wait at the other gate. The standard analytical queuing model predicted correctlythat because the service rate at the checkpoint was equal to the arrival rate, the queue would continue to grow without limit as long as cars kept arriving. This, however, 15.4 LITTLE'S FLOW EQUATION AND RELATED RESULTS merely confirmed what had already been observed. A simulation was therefore developed. The model was run to reproduce the current situation and then to try out alternatives. The first alternative scenario increased the number of guards to three while keeping the single lane of traffic. This approach reduced the maximum queue length from 45.5 to 28, but increased costs. The second scenario had vehicles forming two lines, with a security guard assigned to each line. When a bus arrived, it was routed around the two vehicle lines and serviced immediately by one guard while the other guard temporarily worked both lines. This solution produced a maximum queue length of 14 vehicles and a waiting time of only about 15 minutes, compared to over 30 minutes for the existing configuration. The second scenario appeared to be a good solution involving no additional cost. When it was implemented on a trial basis, the queue length was indeed drastically reduced. The biggest surprise was that the number of vehicles using the gate rose from 285 to 345. Obviously vehicles that had been regularly bypassing the main gate had started using it again. Thanks to the shorter queues, the new system easily handled the increased traffic load. (See Landauer and Becker.) It can be proven that in a steady-state queuing process L = \u0002W (15.2) This result states that L, the expected number of people in the system, equals \u0002, the arrival rate, times W, the expected waiting time. To perform a quick numerical check, see if the numbers derived for the Xerox model (Figure 15.3) satisfy (15.2). The calculation is shown in (15.3). L = 1.0 = 0.05 20 = \u0002W (15.3) To understand the intuitive foundation for this result, consider the diagram in Figure 15.4. In Scene 1 our hero arrives and joins the queue. In Scene 2 he has just completed ser- FIGURE 15.4 Little's Flow Equation Our hero arrives Scene 1: He completes service Scene 2: Arrived during the time our hero waited and was served C H A P T E R 1 5 Queuing CD15-9 vice. Assume the system is in steady state. Since in this case the average number of people in the system is independent of time, let us measure this quantity when our hero completes being served. At this time, the number of people in the system is precisely the total number who arrived after he did (i.e., the individuals who arrived during his waiting time). Therefore, if W is his waiting time and people arrive at a rate of \u0002, we would expect L, the average number in the system, to equal \u0002W. Equation (15.2) is often called Little's flow equation. Note that it applies to any steadystate queuing process and is thus applicable to a wide variety of models. The proof used to establish (15.2) also shows that Lq = \u0002Wq (15.4) A numerical check for the Xerox model shows that Lq = 0.5 = 0.05 10 = \u0002Wq which again agrees with the result in Figure 15.3. One must take some care in applying this result in more complicated cases. It is essential that \u0002 represents the rate at which arrivals join the queue. This may be different from the rate at which people actually \"arrive.\" Consider, for example, a queue with an upper limit on the number of items that can wait in the queue (called a finite queue). A modern phone system that will hold a certain number of calls (say, 10) in a queue until a service representative becomes available provides a good example of such a queue. In such a system a person who calls and finds the system full simply receives a busy signalin other words, is sent away. He or she does not join the queue. This is called a balk. Thus, if \u0002 = 0.25 (the arrival rate) and the mean time between calls is 4 minutes, this is not the rate at which people join. Thus, the relationship L = 0.25W will not hold for this system. Similarly, a customer may tire of waiting in line (or being on hold) and leave without being served. This is called reneging. Here again, L = 0.25W will not hold for this system. Another important general result depends on the observation that expected waiting time = expected waiting time in queue + expected service time For the basic model we have already made use of the fact that 1 expected service time = \u0003 Putting the general result in symbols yields 1 W = Wq + \u0003 For the Xerox model we have W = 20 = 10 + 1 1 = Wq + \u0003 0.10 (15.5) Not only does this hold for the basic model, but the general result (equation [15.5]) holds for any queuing model in which a steady state occurs. Equations (15.2), (15.4), and (15.5) make it possible to compute the four operating characteristics L, Lq, W, and Wq once one of them is known. To illustrate this fact, let us start the Xerox model all over again. We begin as last time using the second formula in Table 15.2 to calculate L: L= 0.05 \u0002 = =1 \u0003 - \u0002 0.10 - 0.05 Now rather than using the other formulas in Table 15.2 that are specifically for the basic model, we will use the two general results that we have just presented. First, from Little's flow equation (15.2) we know that L = \u0002W CD15-10 C D C H A P T E R S Thus, knowing L = 1 and \u0002 = 0.05, we obtain W = L/\u0002 = 20. Then, turning to (15.5), we see that 1 W = Wq + \u0003 1 1 Wq = W - \u0003 = 20 - = 10 0.10 Finally, (15.4) shows that Lq = \u0002Wq = 0.05 10 = 0.5 This alternative method of obtaining numerical results will turn out to be most useful when analyzing more complicated systems than the basic model. 15.5 THE M/G/1 QUEUE While the exponential distribution accurately describes the arrival process in many situations, it may not fit the service process very well. Fortunately, there is a generalization of the basic model that permits the distribution of the service time to be arbitrary. It is not even necessary to know the service time distribution, only its mean, 1/\u0003, and its variance, \u00042. The operating characteristics for the generalized model are given in Table 15.3. Note that we have made use of the results of Section 15.4 in obtaining all the operating characteristics except for Lq. As a check on the validity of these formulas, suppose that the arbitrary service time distribution is exponential. The variance of an exponential distribution is (1/\u0003)2 if the mean is 1/\u0003. Therefore, Lq = \u00022(1/\u0003)2 + (\u0002/\u0003)2 \u00022 = 2(1 - \u0002/\u0003) \u0003(\u0003 - \u0002) which is the same result as in the basic model. As \u00042 increases, L, Lq, W, and Wq all increase. This means that the consistency of a server may be as important as the speed of the server. Suppose you must hire a secretary, and you have to select one of two candidates. Secretary 1 is very consistent, typing any document in exactly 15 minutes. Secretary 2 is somewhat faster, with an average of 14 minutes per document, but with times varying according to the exponential distribution. The average workload in the office is three documents per hour, with interarrival times varying according to the exponential distribution. Which secretary will give you shorter average turnaround times on documents? This can be easily solved with the \"MG1\" and \"MMs\" worksheets of SECRETRY.XLS shown in Figures 15.5 and 15.6. Since Secretary 1 types every document in exactly 15 minutes, \u00042 is equal to 0. The values of the other parameters are \u0002 = 3 per hour (or 0.05 per minute) and \u0003 = 1\\15 per minute. These values are entered in the input parameters section of the \"MMs\" spreadsheet (cells E3:E6), which automatically incorporates the appropriate values into the \"MG1\" worksheet. The results are shown in Figure 15.5. Table 15.3 Operating Characteristics for the Generalized Model SYMBOL FORMULA Utilization CHARACTERISTIC \u0002/\u0003 Expected Number in System L \u0002 Lq + \u0003 Expected Number in Queue Lq Expected Waiting Time W Expected Time in Queue Wq Probability that the System is Empty P0 \u00022\u00042 + (\u0002/\u0003)2 2(1 - \u0002/\u0003) 1 Wq + \u0003 Lq \u0002 1 - \u0002/\u0003 C H A P T E R 1 5 Queuing CD15-11 FIGURE 15.5 Turnaround Time for Secretary 1 FIGURE 15.6 Turnaround Time for Secretary 2 We could also verify this manually by using the formulas shown in Table 15.3: Lq = (0.05)2(0) + [0.05/(1\\15)]2 2[1 - 0.05/(1\\15)] = 9\\8 Wq = (9\\8)/0.05 = 45\\2 = 22.5 minutes W = 45\\2 + 15 = 37.5 minutes average turnaround time Again, using the spreadsheet model for Secretary 2, we enter the parameters as \u0002 = 0.05, \u0003 = 1\\14 per minute, and \u0004 = 14 minutes. The results are shown in Figure 15.6. We could also use either the basic model (Table 15.2) or the generalized model (Table 15.3) to verify the spreadsheet answer for Secretary 2. Using the generalized model we get Lq = (0.05)2(14)2 + [0.05/(1\\14)]2 2[1 - 0.05/(1\\14)] = 49\\30 = 1.633 minutes Wq = (49\\30)/0.05 = 98\\3 = 32.67 minutes W = 98\\3 + 14 = 46.67 minutes average turnaround time Even though Secretary 2 is \"faster,\" her average turnaround times are longer because of the high variability of her service times. CD15-12 C D C H A P T E R S 15.6 MODEL 1: AN M/M/s QUEUE (HEMATOLOGY LAB) Recall that as we started this chapter, our stated goal was to attack three particular models at St. Luke's Hospital with queuing models. In the preceding sections we have laid the groundwork for this process. We have introduced, defined, and illustrated the characteristics of the systems that we will consider (e.g., expected number in queue, expected waiting time, etc.) as well as developed a spreadsheet that can automatically calculate such characteristics. We have also made some general results such as Little's flow equation available for use in future analysis. We are now in a position to turn our attention to Monte Jackson's models. The system described in Model 1 of Section 15.1, the blood-testing model, is illustrated in Figure 15.7. Note that each patient joins a common queue and, on arriving at the head of the line, enters the first examining room that becomes available. This type of system must not be confused with a system in which a queue forms in front of each server, as in the typical grocery store. Assume that the interarrival time is given by an exponential distribution with parameter \u0002 = 0.20 per minute. This implies that a new patient arrives every 5 minutes on the average, since mean interarrival = 1 1 = =5 \u0002 0.20 Also, assume that each server is identical and that each service time is given by an exponential distribution with parameter \u0003 = 0.125 per minute. This implies that the mean service time is 8 minutes, since 1 mean service time for an individual server = \u0003 = 1 =8 0.125 Note that if there were only one server, the queue would grow without limit, since \u0002 > \u0003(0.20 > 0.125). For a multiserver queue, however, a steady state will exist as long as \u0002 < s\u0003, where s is the number of servers. For example, if we have two servers, we will achieve a steady state because 0.20 < 0.25 (= 2 * 0.125). The Key Equations As before, we want to find values L, Lq, W, and Wq. However, since this is a multiserver queue (not a single-sever queue as in the Xerox model), we must use different formulas. To evaluate these formulas it is convenient to start with the expression for P0, the probability that the system is empty. For this model P0 = s -1 (\u0002/\u0003)n n=0 n! \u0004 1 (\u0002/\u0003)s 1 + s! 1 - (\u0002/s\u0003) \u0005 \u0006 (15.6) and Lq, the expected number of people in the queue, is expressed as (\u0002/\u0003) \u0002(s - 1)!(s - \u0002/\u0003) \u0003 s+1 Lq = P0 FIGURE 15.7 Arrivals Server 1 Multiserver Queue 000 Server 2 Server n 2 (15.7) C H A P T E R 1 5 Queuing CD15-13 FIGURE 15.8 Results for Hematology Lab with 2 Servers Equations (15.6) and (15.7) and the general results in (15.2), (15.4), and (15.5) make it possible to calculate values for Wq, W, and L for any specified parameter values (\u0003 and \u0002) and any number of servers (value of s). Again, these new formulas are already entered in the \"MMs\" worksheet of our queuing template in our workbook (HEMATLGY.XLS). Example Calculations Assume, for example, that Monte decided to hire two technicians. Then, since s = 2, \u0002 = 0.20, and \u0003 = 0.125, we can put these values into the \"MMs\" worksheet of HEMATLGY.XLS and get the following results shown in Figure 15.8. We see that the utilization (\u0002/s\u0003) = 0.8 (cell F6) and the probability that the system is empty is 0.11 (cell F7). These two values can be used in equation (15.7) to find Lq = 2.84 (cell F8). That is, the expected number of people in the queue is somewhat less than 3. Using equation (15.4), Lq = \u0002Wq, we see that, on the average, a patient waits for 14.22 minutes (cell F10) before entering an examining room. Lastly, the template uses the general observation that expected waiting time = expected waiting time in queue + expected service time to calculate that the expected waiting time (W) = 22.22 minutes (cell F11). On the average, then, a patient spends 22.10 minutes in the hematology area, waiting for a technician and having tests. Monte now wants to check what happens if he adds a third or fourth technician (server). These results are shown in Figures 15.9 and 15.10 respectively. FIGURE 15.9 Results for Hematology Lab with 3 Servers CD15-14 C D C H A P T E R S FIGURE 15.10 Results for Hematology Lab with 4 Servers There is a dramatic shortening of waiting time (Wq) with a third server (down to 1.57 minutes), but at the cost of having an extra server. Adding a fourth server doesn't make such a dramatic difference, as it reduces waiting time in the queue to 0.30 minutes. Another factor to take into account is how busy the servers would be in each scenario. We see in Figures 15.8 to 15.10 that the utilization drops from 80% to 53.3% to 40%. The more servers added, the higher the percentage of idle time for the technicians, which could lead to boredom and sloppy work. These calculations provide lots of information to help Monte make his decision. With one technician, since \u0002 > \u0003, the system is unstable and the queue will steadily grow. This could be considered irresponsible. With two technicians, the average waiting time in the queue is less than 15 minutes. By current hospital standards, this is a small and acceptable value. Obviously by adding more servers, Monte can reduce the average waiting time but at significant expense to St. Luke's. If, in some cases the queue gets uncomfortably long with two servers (remember that Wq is an expected value, and the actual time in the queue will vary), the supervisors of the hematology laboratory can temporarily move one of the blood analysts to a technician's position. Monte thus feels comfortable with the idea of hiring two full-time technicians without performing a detailed cost analysis. We note that this example model is identical to the models that are faced by fast-food franchise managers: how many people to put on a shift to keep the average customer wait below a certain value. McDonalds reportedly figures it will lose a customer if the total wait is more than five minutes. 15.7 ECONOMIC ANALYSIS OF QUEUING SYSTEMS Monte selected the number of lab technicians to hire by looking at the operating characteristics and using his judgment. This is not an unusual approach in queuing models and is especially common in the not-for-profit sector. Monte realizes that he is balancing the cost of hiring more technicians against the costs he incurs by forcing the patients to wait. The cost of hiring additional technicians is fairly clear. The waiting cost is not. Monte first notes that the cost to the patient is irrelevant to his decision, except as it affects the patient's willingness to use the hospital. It really does not matter who is waitinga consultant who charges $250 per hour for his services or an unemployed person with no opportunity costunless the waiting time persuades the patient to use another health facility. This observation explains why certain monopolies like government agencies and utilities can be so casual about your waiting time. There is no place else to go! Besides the possible effect on demand, the hematology lab could cost the hospital money if it reduced the output of the hospital. Suppose, for example, that the outpatient C H A P T E R 1 5 Queuing CD15-15 clinics could process 50 new patients each day, but that the hematology lab could handle only 10 patients. (This is clearly an extreme example to establish a point.) In this case, the hospital would be wasting a valuable resource, the doctors and other staff in the clinics, because of a bottleneck in the hematology lab. However, having stated this, it still is not easy to assess an explicit cost of a patient waiting. Cost Parameters If you are willing and able to estimate certain costs, you can build expected cost models of queuing systems. Consider, for example, the hematology lab model (in general terms any multiserver queue with exponential interarrival and service times), and suppose the manager is willing to specify two costs: Cs = cost per hour of having a server available Cw = cost per hour of having a person wait in the system (a very \"fuzzy\" or qualitative cost) With these it is possible to calculate the total costs associated with the decision to use any particular number of servers. Let us start by calculating the total cost of hiring 2 servers for an 8-hour day. There are two components: server cost = (Cs)(2)(8) where Cs is the cost per hour for one server, 2 is the number of servers, and 8 is the number of hours each server works, and waiting cost = (Cw)(L2)(8) where L2 is the number of people in the queue when there are 2 servers. This second calculation may not be as obvious, but the rationale is the same as for the server cost. If there are, on the average, L2 people waiting when the system has 2 servers, then L2 times 8 is the average number of waiting \"hours\" per day. Hence, (Cw)(L2)(8) is the average waiting cost for the 8-hour day. If we wanted to calculate the total cost of using 4 servers for a 6-hour day, we would take (Cs)(4)(6) + (Cw)(L4)(6) or [(Cs)(4) + (Cw)(L4)]6 The term in square brackets, [(Cs)(4) + (Cw)(L4)], then, is the total cost per hour of using 4 servers. The Total Cost per Hour We now define TC(s) = total cost per hour of using s servers and we see that TC(s) = (Cs)(s) + (Cw)(Ls) Our goal is to choose s, the number of servers, to minimize this function. We can see that as s increases, the waiting cost will decrease and the server cost will increase. The idea is to find that value of s that minimizes the sum of these two costs. Figure 15.11 shows the worksheet Monte created called \"Econ. Analysis\" in his HEMATLGY.XLS workbook to determine the optimal value of s. Unfortunately it is not possible to derive a formula that gives the optimal value of s. (This is in contrast to the EOQ model, where we can find the optimal order quantity, Q*, with the equation Q* = \u00072DC0 /Ch, as in Chapter 7.) In this example, let's put a relatively large cost on waiting and see if the decision changes from Monte's original decision of choosing two servers. We establish Cs = $50/server/hour and Cw = $100/customer/hour (see cells B1 and B2), and then we can calculate the server cost and waiting cost for 2, 3, and 4 servers. We'll assume we want to com- CD15-16 C D C H A P T E R S FIGURE 15.11 Economic Analysis for Hematology Lab with 2, 3, or 4 Servers Cell Formula Copy To C6 D6 E6 \u0005$B$1*A6*$E$1 \u0005$B$2*B6*$E$1 \u0005SUM(C6:D6) C7:C8 D7:D8 E7:E8 pare the cost over an 8-hour shift (cell E1), and we must enter in cells B6:B8 the values for L (expected number in system) for each value of s we want to explore (obtained from Figures 15.8 to 15.10). We can see that 3 servers minimizes the Total Cost at $2,730 (cell E7). Next Monte creates a data table to determine the sensitivity of this decision to the \"fuzzy\" cost, Cw . He decides he wants to explore values for Cw from 0 to $180. The steps for Monte to do this in his spreadsheet are: 1. Enter the initial value of 0 in cell A11. 2. Click back on cell A11, then choose Edit, Fill, and then \"Series.\" 3. Click on \"Series in Columns,\" enter a step value of 20 and a terminal value of 180. Click on OK. 4. Enter the formulas for the quantities we want to track (total cost with 2 servers, total cost with 3 servers, total cost with 4 servers) in cells B10:D10. These formulas are =E6, =E7, and =E8, respectively. 5. Highlight the range A10:D20, and click on Data, then \"Table.\" 6. Enter the Column Input Cell as B2. Click on OK. 7. Excel automatically fills in the table as shown in cells A10:D20 of Figure 15.11. Finally, Monte wants to graph the results of this sensitivity analysis to look for patterns and trends. To do this, he highlighted the range A11:D20, clicked on the Chart Wizard, and then followed the steps to generate the graph shown in Figure 15.12. We can see that 2 servers is optimal for Cw = 0, while 3 servers is optimal from Cw = $20 up to $180. It does look as though 4 servers will become the optimal decision for values of Cw $200. Let us complete our examination of the hematology lab model with these observations: We have seen how to find values for L, Lq, W, and Wq. These values were then used to select the appropriate number of technicians (servers). This decision might be made on intuitive grounds or on the basis of an explicit economic analysis. Sensitivity analysis is also important to perform, especially on harder-to-quantify parameters like Cw. We now move on to Monte's second model. C H A P T E R 1 5 Queuing CD15-17 FIGURE 15.12 Graph of Sensitivity Analysis on Cost of Waiting for Hematology Lab 15.8 MODEL 2: A FINITE QUEUE (WATS LINES) Do not be misled by the title of this section. It is devoted to Model 2, Monte's attempt to select the appropriate number of WATS lines for St. Luke's. Fortunately, in this case he can expect help from the telephone company. It has a great deal of expertise in such matters, since queuing models have found extensive use in the field of telephone traffic engineering. The problem of how many lines are needed by a switchboard was typically attacked by using the M/G/s model, \"with blocked customers cleared.\" You already know that this model is a multichannel queue with s servers (s lines), exponential interarrival times for the calls, and a general distribution for the service time, which in this case is the length of each call. The phrase \"blocked customers cleared\" is queuing jargon. It means that when an arrival finds all of the servers occupied (all of the lines busy), he or she does not get in a queue but simply leaves. This phrase clearly describes the behavior of the traditional telephone switchboard. More sophisticated systems now provide for queuing of a finite number of customers, in some cases even providing the lucky customer the opportunity to enjoy a Muzak version of Elton John's \"Can You Feel the Love Tonight?\" or the \"Macarena.\" Probability of j Busy Servers The problem of selecting the appropriate number of lines (servers) is attacked by computing the steady-state probability that exactly j lines will be busy. This, in turn, will be used to calculate the steady-state probability that all s lines are busy. Clearly, if you have s lines and they are all busy, the next caller will not be able to place a call. The steady-state probability that there are exactly j busy servers given that s lines (servers) are available is given by the expression Pj = (\u0002/\u0003)j/j ! s \u0004 (15.8) (\u0002/\u0003)k/k! k=0 where \u0002 = arrival rate (the rate at which calls arrive) 1 \u0003 = mean service time (the average length of a conversation) s = number of servers (lines) The expression is called the truncated Poisson distribution or the Erlang loss distribution. It is noteworthy that although we are considering a general service-time distribution, the value Pj defined by (15.8) depends only on the mean of this distribution. Consider a system in which \u0002 = 1 (calls arrive at the rate of 1 per minute) and 1/\u0003 = 10 (the average length of a conversation is 10 minutes). Here \u0002/\u0003 = 10. Suppose that we have CD15-18 C D C H A P T E R S five lines in the system (s = 5) and want to find the steady-state probability that exactly two are busy (j = 2). From (15.8) we see that P2 = (\u0002/\u0003)2/2! 5 \u0004 (\u0002/\u0003)k/k! k=0 = 1+ 101/1 + 102/(2 1) + 103/(3 (10)2/(2 1) 2 1) + 104/(4 3 2 1) + 105/(5 4 3 2 1) = 50 1 + 10 + 50 + 166.67 + 416.67 + 833.33 = 50 = 0.034 1477.67 In other words, on the average, two lines would be busy 3.4% of the time. An alternative way of obtaining Pj that is easy to implement in a spreadsheet (because of its sequential formulation) is as follows: Pi = Pi-1(\u0002/\u0003)/i So, for example once we know P2, we can calculate P3 as: P3 = P2(10)/3 = (0.034)(10)/3 = 0.1133 Likewise, P4 is found as P4 = P3(10)/4 = (0.1133)(10)/4 = 0.2833 Each successive Pi-1 is multiplied by (\u0002/\u0003) and divided by i to achieve the new Pi . The more interesting question is: \"What is the probability that all of the lines are busy?\" since in this case a potential caller would not be able to place a call on the WATS lines. To find the answer to this question, we simply set j = s (in our example s = 5) and we obtain P5 = P4(10)/5 = (0.2833)(10)/5 = 0.564 or on the average the system is totally occupied 56.4% of the time. Again, it is easy enough to implement all these formulas in a spreadsheet. The probability that the system is totally occupied (all servers are busy) is calculated in a new worksheet called \"finiteQ\" in the workbook WATS.XLS. We can see that the probability that a customer balks with 5 servers is much more easily calculated in a spreadsheet, as shown in Figure 15.13. Of course, we get the same value (0.564 in cell F13). We can then build a data table to determine this value for several different values of s. Figure 15.14 shows such a data table that Monte built for examining the possibility of between 0 and 10 phone lines. The steps for Monte to do this in the spreadsheet are: 1. Enter the initial value of 0 in cell A23. 2. Click back on cell A23, then choose Edit, Fill, and then \"Series.\" 3. Click on \"Series in Columns,\" enter a step value of 1 and a terminal value of 10. Click on OK. C H A P T E R 1 5 Queuing CD15-19 FIGURE 15.13 Finite Queue Spreadsheet Calculation of Probability that Customer Balks FIGURE 15.14 Data Table for Probability that Customer Balks for Different Values of s 4. Enter the formulas for the quantity we want to track (probability that a customer balks) in cell C22. The formula is =F13. 5. Highlight the range B22: C33, and click on Data, then \"Table.\" 6. Enter the Column Input Cell as E4. Click on OK. Excel automatically fills in the table as shown in Figure 15.14. Next we can create column D that calculates the marginal improvement in this probability as we add servers. This is also shown in Figure 15.14. Here it is clear that the marginal effect of adding more servers decreases. For example, adding a second line when there was one in service decreases the probability of the system being busy by 0.089, whereas adding the tenth line when there were already nine in service decreases this probability by 0.059. Average Number of Busy Servers Another interesting and useful quantity in the design of phone installations is the average number of busy lines. This quantity is called the carried load in queuing jargon. If we define N as the average number of busy servers, then \u0005\u0006 \u0002 N = \u0003 [1 - Prob. That a Customer Will Balk] (15.9) Assume now that in Monte's model with WATS lines for St. Luke's, \u0002 = 1 and 1/\u0003 = 10. Thus, if he purchases 10 lines, we see in Figure 15.14 that the probability that all 10 are busy =0.215 (cell C33). It follows from (15.9) that N = 10(1 - 0.215) = 7.85 CD15-20 C D C H A P T E R S In other words, the entire system will be busy with probability 0.215 or about one fifth of the time and, on the average, almost 8 lines will be busy. After N has been calculated, the server utilization can be calculated by dividing N by s (the number of servers). Thus, for the situation at St. Luke's, the server utilization is 7.85/10 = 78.5%, which means that each server (on average) is busy 78.5% of the time and idle 21.5% of the time. Monte feels that ten lines is a reasonable compromise. There does not seem to be a great deal of excess capacity, but, on the other hand, the probability of finding the system busy is in a region (70% to 80%) that he feels is appropriate for the hospital. If he is uncomfortable with this solution, based on a subjective balancing of the number of lines and the probability of finding the system busy, and is willing to specify a cost for each time a caller finds the system busy, he can select the number of lines to minimize the expected cost per hour. He would proceed in the same manner as in the M/M/s system of Sections 15.6 and 15.7. 15.9 MODEL 3: THE REPAIRPERSON MODEL In this model Monte must decide how many repairpersons to hire to maintain 20 pieces of electronic equipment. Repairpersons deal with machines on a first-come (perhaps firstfailed is more accurate), first-served basis. A single repairperson treats each broken machine. You can thus think of the failed machines as forming a queue in front of multiple servers (the repairpersons). This is another M/M/s model, but it differs in a fundamental way from the M/M/s system (the blood-testing model) considered in Section 15.6. In this model there is a limited number of items (20) that can join the queue, whereas in the hematology lab model an unlimited number could potentially join the queue. A queuing model, like the repairperson model, in which only a finite number of \"people\" are eligible to join the queue is said to have a finite calling population. Models with an unlimited number of possible participants are said to have an infinite calling population. Consider the model with 20 machines and 2 repairpersons. Assume that when a machine is running, the time between breakdowns has an exponential distribution with parameter \u0002 = 0.25 per hour; that is, the average time between breakdowns is 1/\u0002 = 4 hours. Similarly, assume that the time it takes to repair a machine has an exponential distribution and that the mean repair time is 0.50 hour (i.e., 1/\u0003 = 0.50). This model is an M/M/2 model with a maximum of 18 items in the queue (20 including the 2 in service) and a finite calling population. In this case the general equations for the steady-state probability that there are n jobs in the system is a function of \u0002, \u0003, s (the number of repairpersons), and N (the number of machines). In particular, Pn = N! (\u0002/\u0003)nP0 for 0 n s n!(N - n)! Pn = N! (\u0002/\u0003)nP0 for s < n N (N - n)!s!sn-s (15.10) We also know that N \u0004 Pn = 1 n=0 (15.11) We thus have N + 1 linear equations (N from equation [15.10] and 1 from equation [15.11]) in the N + 1 variables of interest (P0, P1, . . . . , Pn). This makes it possible (if painful) to calculate values of Pn for any particular model. One can see that each model becomes a bit more complex than the previous one, and that the formulas of Pn become more complex. There are, however, no simple expressions (even by these standards) for the expected number of jobs (broken machines) in the system or for waiting. If the values for Pn are C H A P T E R 1 5 Queuing CD15-21 FIGURE 15.15 Finite Population Spreadsheet for the Repairperson Model computed, then it is (truly) a simple task to find a numerical value for the expected number in the system. You must just calculate N expected number in system = L = \u0004 nPn n=0 If God had intended humans to perform this kind of calculation by hand, He would not have let spreadsheets be invented. Figure 15.15 shows the setup of the \"finite Population\" worksheet in the REPAIR.XLS workbook that can be used to compute values of Pn , the expected number in the system, and the expected number waiting, for a variety of different systems. As shown, the user enters the typical system parameters (\u0002, \u0003, and s) in the \"MMs\" worksheet, then clicks on the new worksheet \"finitePopulation\" and adds the size of the finite population (cell E5), and the spreadsheet does the rest. In this case, \"the rest\" consists of numerically evaluating the equations for Pn and using the results to find the expected number in the system. There is one \"trick\" with this kind of model, when you enter the value for the arrival rate (\u0002) in the \"MMs\" worksheet, you actually need to enter N*\u0002, or the entire population's arrival rate. As you see in Figure 15.15, for this system, Lq, the average number of machines waiting for service, is 3.348 (cell F8) and W, the expected time in the system, is 1.405 hours (cell F11). The utilization is high at 92.5% and we see from the histogram that there's a 3.3% chance that the system is empty, an increasing probability of there being one machine (8.3%), and the probabilities keep growing for increasing numbers of machines until it reaches a maximum at four and five machines (they're tied at 11.8%). Then the probabilities decline for machines beyond five. 15.10 TRANSIENT VERSUS STEADY-STATE RESULTS: ORDER PROMISING It is not always the case that we are interested in steady-state results, or that an analytical model is available to predict the behavior of the queuing system of interest. In this section we will consider a situation in which we are interested in the transient behavior of the system and must use simulation to obtain the desired answers. Manufacturing processes can be viewed as complex queuing systems. Probably the most frequently used management science tool in manufacturing is queuing systems simulation. Larry Lujack, a production planner at SONOROLA and a recent graduate of the University of Chicago's Graduate Business School, is wondering if what he learned about queuing models in his last semester of school could help him decide when to promise a new customer order. The order is for 20 units of an item that requires sequential processing at 2 CD15-22 C D C H A P T E R S work stations. The average time to process a unit at each work station is 4 hours. Each work station is available for 8 hours every working day. By considering when the last of the 20 units will be completed, Larry initially estimates that it will take 10.5 days to process the order. The last unit must wait at Work Station 1 for the first 19 units to be completed, then it must be processed at Work Station 1 and then at Work Station 2. Assuming that it does not have to wait when it gets to Work Station 2, Larry calculates as follows: (19 units 4 hours/unit + 4 hours + 4 hours) 8 hours/day = 10.5 days However, this analysis is somewhat simplistic. It ignores the variability of the processing times and the possibility of queuing at Work Station 2. Larry feels that the exponential distribution is an appropriate distribution for processing times because the 4-hour figure was arrived at by averaging many processing times that were less than 4 hours with a few processing times that were significantly longer than 4 hours (see Section 15.11). These few long processing times were due to equipment failures at a work station while processing a unit. Next Larry checks to see whether the assumptions of the basic queuing model are met. The output from Work Station 1 are the arrivals to Work Station 2, and the time between arrivals is exponential because the processing time at Work Station 1 is exponential. The service time at Work Station 2 is exponential because it is the same as the processing time. The units are processed on a first-come, first-served basis at Work Station 2, and there is sufficient buffer capacity between the work stations so that the queue size is for all practical purposes infinite. However, the assumption of an infinite time horizon is not met. Larry is interested only in the behavior of the system until \"customer\" 20 ends its processing. Larry decides to apply the basic model anyway and use it as an approximation. He approximates the time it takes to process 20 units as follows. First, he estimates that the last unit in the batch of 20 will leave Work Station 1 after 20 4 = 80 hours. Then this unit will wait in the queue in front of Work Station 2. Finally, it will complete processing at Work Station 2, at which time all 20 units will have been completed. The total time that the last unit spends at Work Station 2 is W. Thus, Larry's estimate is 20 4 + W. In the basic model, W is given by the formula 1/(\u0003 - \u0002). Larry now realizes his dilemma: \u0003 and \u0002 are equal (1 unit per 4 hours) and the formula is valid only when \u0003 is greater than \u0002. Larry decides to set up a spreadsheet (ORDER.XLS) to stimulate the flow of the 20 units through the 2 work stations. His spreadsheet is shown in Figure 15.16. Larry assumes that raw material is always available at Work Station 1 (WS1) so that the next unit at Work Station 1 can start as soon as the current unit is finished. This means that for Work Station 1 the start time of a unit is the stop time of the previous unit. For example, the formula in cell B8 of the spreadsheet is =C7. The start time of a unit at Work Station 2 is either the stop time of that unit on Work Station 1 or the stop time of the previous unit on Work Station 2, whichever is larger. So, for example, the formula in cell D8 is =MAX(C8,E7). The stop time of a unit is just the start time plus the processing time. The finish time in days is shown in cell F2 and is calculated by dividing the stop time at Work Station 2 of the last unit by the number of hours/day (8 in cell F1). The spreadsheet calculates this time to be 10.5 days if every unit takes exactly 4 hours at every work station. To analyze the impact of processing time variability, Larry replaces the constant processing time of 4 at WS1 in his spreadsheet with the appropriate random distribution (in Crystal Ball, he chooses the exponential distribution from the gallery; in @RISK, he enters =RiskExpon($B$1) ), which samples from an exponential distribution with a mean of 4. This makes the finish time a random variable. Larry would like to know the 99th percentile of this random variable (the number that 99% of the time the random variable will be less than or equal to). He could then promise the order in that number of days and be 99% sure that it would actually be completed on time. C H A P T E R 1 5 Queuing CD15-23 FIGURE 15.16 Order Promising Spreadsheet Cell Formula Copy To C7 D7 E7 B8 D8 F2 \u0005$B$1 + B7 \u0005C7 \u0005D7+$B$2 \u0005C7 \u0005MAX(C8, E7) \u0005E26/F1 C8:C26 E8:E26 B9:B26 D9:D26 Using Crystal Ball or @RISK, it is a simple matter to find any percentile of any random variable in the spreadsheet. Figure 15.17 shows the 99th percentile for cell F2 (the finish time in days) based on 1000 iterations (1000 sets of 40 random processing times20 for Work Station 1, 20 for Work Station 2). First, note that the expected finish time (\"Mean\" for cell F2 in Figure 15.17) is 15.52 days, 2 days longer than Larry's initial calculation. The extra FIGURE 15.17 Statistical Output for Order Completion Model CD15-24 C D C H A P T E R S FIGURE 15.18 Histogram of Finish Times for Order Completion Model 2 days is the average queuing delay caused by the variability of the processing times. If Larry wants to be 99% sure of having the order completed by the time he promises, he should set the due date to be 18.28 days (\"Target #1(Value)=\" in Figure 15.17) after the material becomes available at Work Station 1. The queuing that takes place at Work Station 2 has increased the lead time (time from the start of the order to its completion) by nearly 8 days (18.28 less 10.5) over what it would be if there were no variability in the processing times. Figure 15.18 shows the histogram of the finish time, and we can see that the time can vary from 6.5 days up to 21 days. Even though the basic model was not applicable in this case, it helped Larry to think about the model and to understand this answer from his spreadsheet simulation. Problem 15-29 explores a slightly different situation in which the basic model can be used to estimate the average finish time and the 99th percentile. 15.11 THE ROLE OF THE EXPONENTIAL DISTRIBUTION There is an enormous body of literature concerning queuing systems, and it is virtually impossible for a manager to be aware of all the results. There are, however, some general considerations that are useful in helping a manager think about the use of queuing models. One such consideration is the role of the exponential distribution in analytic queuing models. There are essentially no analytic results for queuing situations that do not involve the exponential distribution either as the distribution of interarrival times or service times or both. This fact makes it important for a manager to recognize the set of circumstances in which it is reasonable to assume that an exponential distribution will occur. The following three properties of the exponential distribution help to identify it: 1. Lack of memory: In an arrival process this property implies that the probability that an arrival will occur in the next few minutes is not influenced by when the last arrival occurred; that is, the system has no memory of what has just happened. This situation arises when (1) there are many individuals who could potentially arrive at the system, (2) each person decides to arrive independently of the other individuals, and (3) each individual selects his or her time of arrival completely at random. It is easy to see why the assumption of exponential arrivals fits the telephone system so well. C H A P T E R FIGURE 15.19 1 5 Queuing CD15-25 Prob S \u0006 t 1.0 A High Probability of Short Service Times 0.632 t 10 2. 3. 20 30 Small service times: With an exponential distribution, small values of the service time are common. This can be seen in Figure 15.19. This figure shows the graph of the probability that the service time S is less than or equal to t (Prob {S t}) if the mean service time is 10; that is \u0003 = 0.1 and 1/\u0003 = 10. Note that the graph rises rapidly and then slowly approaches the value 1.0. This indicates a high probability of having a short service time.