Category: Entertainment

Presentation Description

No description available.


Presentation Transcript

Slide 1: 


Slide 2: 

2 Queuing models are everywhere. For example, airplanes “queue up” in holding patterns, waiting for a runway so they can land. Then, they line up again to take off. People line up for tickets, to buy groceries, etc. Jobs line up for machines, orders line up to be filled, and so on. A. K. Erlang (a Danish engineer) is credited with founding queuing theory by studying telephone switchboards in Copenhagen for the Danish Telephone Company. Many of the queuing results used today were developed by Erlang.

Slide 3: 

3 A queuing model is one in which you have a sequence of times (such as people) arriving at a facility for service, as shown below: Consider St. Luke’s Hospital in Philadelphia and the following three queuing models. Model 1: St. Luke’s Hematology Lab St. Luke’s treats a large number of patients on an outpatient basis (i.e., not admitted to the hospital). Outpatients plus those admitted to the 600-bed hospital produce a large flow of new patients each day.

Slide 4: 

4 Most new patients must visit the hematology laboratory as part of the diagnostic process. Each such patient has to be seen by a technician. 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 and the technician sees a new patient. We must decide how many technicians to hire.

Slide 5: 

5 WATS (Wide Area Telephone Service) is an acronym for a special flat-rate, long distance service offered by some phone companies. Model 2: Buying WATS Lines As part of its remodeling process, St. Luke’s is designing a new communications system which will include WATS lines. We must decide how many WATS lines the hospital should buy so that a minimum of busy signals will be encountered. 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.

Slide 6: 

6 The equipment includes measuring devices such as Model 3: Hiring Repairpeople St. Luke’s hires repairpeople to maintain 20 individual pieces of electronic equipment. If a piece of equipment fails and all the repairpeople are occupied, it must wait to be repaired. We must decide how many repairpeople to hire and balance their cost against the cost of having broken equipment.

Slide 7: 

7 All three of these models fit the general description of a queuing model as described below: These models will be resolved by using a combination of analytic and simulation models. To begin, let’s start with the basic queuing model.

Slide 8: 

8 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 which varies 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.

Slide 9: 

9 2. The number of people in the queue (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). 4. The waiting time in the queue (the time between entering the system and the beginning of service). Questions about this or any other queuing system center on four quantities: 1. The number of people in the system (those being served and waiting in line).

Slide 10: 

10 ASSUMPTIONS OF THE BASIC MODEL 1. Arrival Process. Each arrival will be called a “job.” The interarrival time (the time between arrivals) is not known. Therefore, the exponential probability distribution (or negative exponential distribution) will be used to describe the interarrival times for the basic model. The exponential distribution is completely specified by one parameter, l, the mean arrival rate (i.e., how many jobs arrive on the average during a specified time period).

Slide 11: 

11 Mean interarrival time is the average time between two arrivals. Thus, for the exponential distribution Thus, if l = 0.05 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 m (the mean service rate in jobs per minute).

Slide 12: 

12 mT 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. The mean or average, service time (the average time to complete a job) is Thus, if m = 0.10 3. Queue Size. There is no limit on the number of jobs that can wait in the queue (an infinite queue length).

Slide 13: 

13 4. Queue Discipline. Jobs are served on a first-come, first-serve basis (i.e., 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.

Slide 14: 

14 CHARACTERISTICS OF THE BASIC MODEL The values of the parameters l and m (together with the assumptions) are all that is needed to calculate several important operating characteristics of the basic model. NOTE: these formulas hold only if l < m.

Slide 15: 

15 Consider a specific example where l = 0.25 and m = 0.10. Thus, on the average, a job arrives every 1/l = 1 / 0.25 = 4 minutes. Similarly, the time it takes to complete a job, on average, is 1/m = 1 / 0.10 = 10 minutes. In this case, since l > m, the service operation will get further behind (the queue will grow longer) as time goes by. Now, return to the Xerox model, in which l < m. Spreadsheets are ideal for crunching the numerical results from such formulas.

Slide 16: 

16 The following Excel spreadsheet was originally developed by Professor David Ashley. It already has the formulas entered. Here is the introductory page.

Slide 17: 

17 Plugging the numerical values from the Xerox model, l = 0.05 and m = 0.10 into the appropriate cells of the MMs worksheet yields the following results:

Slide 18: 

18 Steady-State Result Let’s interpret the results. L is the expected number of people in the system after the queue has reached steady-state. Steady-state means that the probability that you will observe a certain number of people in the system does not depend on the time at which you count them.

Slide 19: 

19 Thus, in a steady-state, 1. The system is empty with probability ½ 2. On average, there is 0.5 person in the queue 3. On average, an arrival must wait 10 min. before starting to use the machine. 4. On average, an arrival will spend 20 minutes in the system.

Slide 20: 

20 Using the Results These results hold for the basic model and the particular values for the parameters (l = 0.05 and m = 0.10 ). Suppose, for example, management makes the following calculations: Since l = 0.05, on the average 5/100 of a job arrives each minute. During each 8-hour day there are 8 x 60 = 480 minutes. Thus, during each day there is on the average a total of (0.05)(480) = 24 arrivals. (24 arrivals/day)(20 minutes/arrival) = 480 minutes or 8 hours We know that on the average each person spends 20 minutes in the system (W = 20). Thus, the total time spent at the facility is:

Slide 21: 

21 If management feels that 8 hours is too long to spend at the facility, then the following 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. In any case, management must balance the cost of providing service against the cost of waiting.

Slide 22: 

22 A TAXONOMY OF QUEUING MODELS There are many possible queuing models. Therefore, to facilitate communication among those working on queuing models, D. G. Kendall proposed a taxonomy based on the following notation: A/B/s 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.

Slide 23: 

23 M = exponential distribution D = deterministic number G = any (a general) distribution of service times GI = any (a general) distribution of arrival times The following conventions are in general use: For example, the Xerox model is an M/M/1 model (i.e., a single-server queue with exponential inter-arrival and service times).

Slide 24: 

24 It can be proven that in a steady-state queuing process L = lW In the Xerox model, L = 0.05 x 20 = 1.0 Consider the diagram below: In scene 1 our hero arrives and joins the queue. This equation is often called Little’s flow equation.

Slide 25: 

25 In scene 2 he has just completed service. Assume the system is in steady-state. Since in this case the average number of people in the system is independent of time, let’s 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. Therefore, if W is his waiting time and people arrive at a rate of l, we would expect L to equal lW.

Slide 26: 

26 Note that Little’s flow equation applies to any steady-state queuing process and is thus applicable to a wide variety of models. The proof used to establish Little’s flow equation also shows that Lq = lWq In the Xerox model, Lq = 0.05 x 10 = 0.5 It is essential that l represent the rate at which arrivals join the queue. Consider, for example, a queue with an upper limit on the number of items that can wait in the queue (called a finite queue).

Slide 27: 

27 In such a system, a person can call, find the system full (receive a busy signal) and be sent away (hang up). For example, a modern phone system holds only a certain number of calls (say, 10) in a queue until they are answered by the next available service representative. This person does not join the queue. This is called a balk. Similarly, a customer may tire of waiting in line (or being on hold) and leave without being served. Here, the person joined the queue, became impatient and left without completing the transaction. This is called reneging.

Slide 28: 

28 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 found that Putting the general result in symbols yields For the Xerox model: This general result holds for any queuing model in which a steady-state occurs.

Slide 29: 

29 Now we can easily compute the four operating characteristics L, Lq, W, Wq: First calculate L: From Little’s flow equation we know that L = lW Thus, after computing L, we can now compute W: W = L/l Knowing W, we can now compute Wq: Lq = lWq And knowing Wq, we can now compute Lq:

Slide 30: 

30 The exponential distribution 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 necessary to know the service time distribution, only the mean service time, 1/m, and its variance, s2.

Slide 31: 

31 The operating characteristics for this model are: As s2 increases, L, Lq, W, Wq all increase. This means that the consistency of a server may be as important as the speed of the server.

Slide 32: 

32 For example, 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. With the “MG1” and “MMs” worksheets, we can easily determine which secretary will give shorter average turnaround times on documents.

Slide 33: 

33 Since Secretary 1 types every document in exactly 15 minutes, s2 = 0. In addition, l = 3 per hour (or 0.05 per minute) and m = 1/15 per minute.

Slide 34: 

34 For Secretary 2, enter the parameters s = 14, l = 0.05, and m = 1/14 per minute. Even though Secretary 2 is “faster,” her average turnaround times are longer because of the high variability of her service times.

Slide 35: 

35 Previously, the stated goal was to attack the three St. Luke’s Hospital models with queuing models. Consider the blood-testing model (Model 1): Each patient joins a common queue and, on arriving at the head of the line, enters the first available examining room.

Slide 36: 

36 This type of system must not be confused with a system in which a queue forms in front of each server, as in a typical grocery store. Now, assume This implies that a new patient arrives every 5 minutes on average since Mean interarrival = 1/l = 1/0.20 = 5

Slide 37: 

37 This implies that the mean service time is 8 minutes since Mean service time for an individual server = 1/m = 1/0.125 = 8 Note that if there were only one server, the queue would grow without limit because l > m (0.20 > 0.125). However, for a multiserver queue, a steady-state will exist as long as l < sm, where s is the number of servers. For example, if there are 2 servers, a steady-state will be achieved because 0.20 < (2*0.125).

Slide 38: 

38 The Key Equations We want to find the values L, Lq,W, and Wq. However, since this is a multiserver queue, we must use different formulas. For this model, the probability that the system is empty is: The expected number of people in the queue is:

Slide 39: 

39 Assume now that we have decided to hire two technicians. We can input the parameters s = 2, l = 0.20, and m = 0.125 into the MMs worksheet to obtain the results.

Slide 40: 

40 Here are the results when a third technician is added (s = 3). Note that the expected waiting time has been reduced from 22.22 minutes to 9.56 minutes.

Slide 41: 

41 When a fourth technician is added (s = 4), the expected waiting time has been reduced slightly more.

Slide 42: 

42 Adding additional servers may decrease the waiting time, however, you have to consider not only how much extra you will pay for the additional servers but also if those additional servers will be busy most of the time. The previous results show that as more servers are added, the percentage of idle time for the technicians increases, which could lead to boredom and sloppy work.

Slide 43: 

43 The cost of hiring additional technicians is fairly clear. Now, let’s determine the cost of waiting. The cost to the patient is irrelevant to the decision, except as it affects the patient’s willingness to use the hospital. Besides the possible effect on demand, the hematology lab could cost the hospital money if it reduced the output of the hospital.

Slide 44: 

44 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) Let’s start by calculating the total cost of hiring 2 servers for an 8-hour day.

Slide 45: 

45 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 8 is the number of hours each server works waiting cost = (CW)(L2)(8) where L2 is the number of people in the queue when there are two servers. To calculate the total cost of using 4 servers for a 6-hour day, take (Cs)(4)(6) + (CW)(L4)(6) or [(Cs)(4) + (CW)(L4)]6

Slide 46: 

46 The Total Cost per Hour We now define TC(s) = total cost per hour of using s servers = (Cs)(s) + (CW)(Ls) The goal is to find the value of s that will minimize the sum of these two costs. Note that as s, the number of servers, increases, the waiting cost will decrease and the server cost will increase. Unfortunately, it is not possible to derive a formula that gives the optimal value of s. However, consider the following worksheet…

Slide 47: 

47 In this worksheet, specify Cs = $50/server/hour and Cw = $100/customer/hour. The results show that 3 servers minimizes the Total Cost.

Slide 48: 

48 Next, create a data table to determine the sensitivity of this decision to the “fuzzy” cost, CW ($0 to $180).

Slide 49: 

49 Excel automatically fills in the table as shown below.

Slide 50: 

50 These results can be graphed to look for patterns and trends. You can see that 2 servers is optimal for CW = 0, while 3 servers is optimal from CW = $20 up to $180. For values of CW > $200, 4 servers is optimal.

Slide 51: 

51 The role of the exponential distribution in analytical queuing models is useful in understanding the use of queuing models. Most analytic results for queuing situations involve the exponential distribution either as the distribution of interarrival times or service times or both. The following three properties help to identify the set of circumstances in which it is reasonable to assume that an exponential distribution will occur.

Slide 52: 

52 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. This situation arises when (a) there are many individuals who could potentially arrive at the system (b) each person decides to arrive independently of the other individuals (c) each individual selects his or her time of arrival completely at random

Slide 53: 

53 2. Small service times: With an exponential distribution, small values of the service time are common (as shown below). This graph shows the probability that the service time S is less than or equal to t if the mean service time is 10.

Slide 54: 

54 The graph showed that more than 63% of the service times were smaller than the average service time (10). Compare this to the normal distribution where only 50% of the service times are smaller than the average. The practical implication is that an exponential distribution can best be used to model the distribution of service times in a system in which a large proportion of “jobs” take a very short time and only a few “jobs” run for a long time.

Slide 55: 

55 3. Relation to the Poisson distribution: While introducing the basic model, a relationship between the exponential and Poisson distributions was noted. In particular, if the time between arrivals has an exponential distribution with parameter l, then in a specified period of time (say, T) the number of arrivals will have a Poisson distribution with parameter lT. Then, if X is the number of arrivals during the time T, the probability that X equals a specific number (say, n) is given by the equation For any nonnegative integer value of n.

Slide 56: 

56 The relationship between the exponential and the Poisson distributions plays an important role in the theoretical development of queuing theory. It also has an important practical implication. By comparing the number of jobs that arrive for service during a specific period of time with the number that the Poisson distribution suggests, the manager is able to see if his or her choices of a model and parameter values for the arrival process are reasonable.

Slide 57: 

57 In addition to the arrival distribution, service distribution and number of servers, the queue discipline must also be specified to define a queuing system. So far, we have always assumed that arrivals were served on a first-come, first-serve basis (often called FIFO, for “first-in, first-out”). However, this may not always be the case. For example, in an elevator, the last person in is often the first out (LIFO). Adding the possibility of selecting a good queue discipline makes the queuing models more complicated. These models are referred to as scheduling models.

authorStream Live Help