PLACE ll RETURN BOX to man this chockom 1mm your mood. TO AVOID FINES Mum on or baton data duo. DATE DUE DATE DUE DATE DUE MSU chn mum WM Opponunuy Inflation WW1 USE OF QUEUING THEORY IN DETERMINING OPTIMAL SUPER MARKET CHECK-OUT FACILITIES By 0 2W“ \ John Y‘.‘ Lu A THESIS Submitted to the School for Advanced Graduate Studies of Michigan State University of Agriculture and Applied Science in.partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Agricultural Economics 1959 4 [57(2) a/fi/w ACKNOWLEDGMENTS The author wishes to acknowledge his indebtedness to the following individuals who have directly or indirectly helped the author in the preparation of this thesis. The financial assistance given to the author during his stay at Michigan State University by Dr. Lawrence L. Roger and the facilities accorded to him by the Department of Agricultural Economics are greatly appreciated. Dr. Robert L. Gustafson has given much valuable guidance to the author in formulating the problem. Many of his ideas appear in the following pages, especially in Chapter IV. He has also read the manu— script and his comments have resulted in an improved presentation of the materials contained here. Thanks are due to Mr. Mike Wood who suggested this problem to the author and contributed much useful information, and also to Mr. Tom McDermott for enabling the author to obtain data in connection with the check-out operation of a super market. The author also had the benefit of comments by Drs. K. J. Arnold, W. A. Cromarty, and L. V. Manderscheid when the project was first being set up. Bill Grosswhite and Peter Hildebrand have read parts of the manu- script and offered a number of useful suggestions concerning its style. The mathematical exposition in Appendix B has been considerably im- proved as a result of coments by Willard Sparks. Needless to say, any error remaining in the thesis is the author's sole responsibility. The author cannot fully express here the great debt he owes to his many teachers, but he cannot refrain from singling out Dr. Clifford Hildreth to whom he owes his interest in econometrics. During the en- tire course of the author's graduate study, Dr. Hildreth has been most generous in giving encouragement and inspiration to the author. The author's heartfelt appreciation goes to M.W.L. for the invalu- able role she played in helping the author to complete his graduate work. USE OF QUEUING THEORY IN DETERMINING OPTIMAL SUPER MARKET CHECK-OUT FACILITIES By 23W? 0/0 John Y. Lu AN ABSTRACT Submitted to the School for Advanced Graduate Studies of Michigan State'University of Agriculture and Applied Science in partial fulfillment of the requirements for the degree of DOCTOR.OF PHILOSOPHY Department of Agricultural Economics Year 1959 Approved ABSTRACT The check-out service provided by a super market appears to have all the necessary features that make up a typical queuing prdblem. There are customers who demand service; as each customer reaches a service channel, he receives a service. After a certain service time, he leaves. If the service channel is not immediately available to him, he joins a queue. In most cases, the management has little control over the arrivals of customers to the service area either in quantity or in time; it can, however, expand or contract facilities to meet a certain prespecified optimum criterion. The problem involves a balanc- ing of the cost incurred by providing a certain amount of check-out facilities for a given period of time against the cost of losing customers in the future because of inferior service standards. Recent developments in queuing theory provide the basis for system- atically and quantitatively analyzing such a problem. The procedure is to first estimate, for given incoming traffic pattern and service practice, the prObability distribution of the check-out system's being in each of all the possible states which are specified by the number of customers present in the system. Next, the cost associated with the system in each state is calculated. ‘When the cost as well as the prob- ability of the system being in each state is known, the expected cost per unit time of operating the check-out service under given conditions can be calculated. This process is repeated until the conditions which ‘would result in the minimum expected cost are found. \ iv The formal model used to estimate the state probability distribu- tion is characterized as follows: Input - the number of customers arriving per unit of time is a Poisson variate. Service mechanism - the time required to serve a customer at a counter follows one of two different negative exponential distributions depending on whether or not a package boy is assisting a checker. Queuediscipline - "first come, first served." This procedure was applied to data obtained at one of the large super markets in the Detroit area. The week was subdivided into five periods. The state probability distribution was estimated for each period and the quantities of interest such as the expected length of queue and the probability of more than a certain number of customers in a queue were calculated. Based on these quantities, expected costs were obtained and the service facilities which would generate the minimum expected cost were found. Sensitivity of the choice of optimim service facilities to changes in estimated average arrival rate and average service rate was examined and was found not to be serious. The assumptions of Poisson inputs and exponential service times were tested. The number of customers arriving at the check-out area per unit of time follows closely a Poisson dis- tribution. The negative exponential distribution did not appear to give the best fit to observations on service time. The assumption that service times are distributed by a gamma mnction was found to be more plausible. An alternative procedure based on the Monte Carlo method was proposed to take account of this fact. V TABLE OF CONTENTS GiAPTER Page I mmmcrIONOOOOOOOOOOOOOOOOO. 00000000000 ~O 00000000000000000 1 What is a Qieuing Problem?..... ......................... 1 Objectives of this Studyu..... .......................... 5 II QIHJDIG MODEL TO BE USED IN THIS STUDY.. ......... ...... 7 A Simplified Representation of the Check-out Operation at aSuper Maiket................... ................ 7 Probability Distributions of Customer Arrivals and semice TmOOOOOOOOOOOOOOOOO000...... ..... .000000000 9 Eupected Values of Various Quantities of Practical Interest in the Problem Under Study........ .......... 10 Study of Volume of Daily Sales at One Detroit Super Wket Umer smdyOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO'O 13 Review of Literature............... ..................... 15 III SOME STATISTICAL ANAIJSEB OF CUSTOMER ARRIVALS AND SERVICE m.....OOCCOOOCOOOOCOCCOOOOOOOOOOOOOOOOOOOOOOOOOOOOO. 21 The Goodness-ofhfit Test................... ............ 22 Statistical Properties of Average Durations of Service TWSOOOOOO ..... GCO‘OOOOCOOOOOOOOOOOOOOO...O... 00000 30 Confidence Interval.............. ....... . ............... 32 IV OPTIMAL RULES FOR CHECK-‘OUT OPERATION ...................... 36 A Criterionof Optimality......... ...................... 37 mnerfl Math“ Of somtionOOOOOOOOOOOOOOOUOOCO OOOOOOOOOO 37 Some Specific Solutions.................... ............ ’40 Optimal Check-out Rules for the Super Market in Detroit. 142 V SUMMARY OF RESULTS AND SUGGESTICNS FOR FURTHER STUDY ....... S7 HWTURE CITE.......C.....C.OOOO00......O... ......... O ......... 66 APPDIDIX A - STATE PROBABILITY DISTRIBUTION......‘................ 68 AHMED]! B -- THE DISTRIBUTION FUNCTION OF ESTIMATED AVERAGE SEVIE TMOOOOIOOOOOOOO ...... O OOOOOOOOOOOOOOOOO 78 vi LIST OF TABLES TABLE 5 Page I Customer Arrival Goodness-of-Fit. . . . . . . . . . . ................. 28 II Confidence Limits of Average Service Time . . . . . ..... . ........ 35 III Estimates of Average Arrival Rates and Average Service Rates, and Their Confidence Intervals. 35 IV Optimum «Check-Out Rules for Monday, Tuesday, and Wednesday, X‘0.91-0.0000000070000000000000.00000000 ...... 000000000000 ’49 v Optimum Check-Out Rules for mursday,i= 1..............53.. 50 VI Optimum Check-Out Rules for, Friday, before 6 P.M., X = 1.85. 51 VII Optinum (heck-Out Rules for Friday, after 6 P.M., X = 2.55.. 52 VIII Optimum Check-Out Rules for Saturday, x a 2.1m ...... 53 IX Optinum (heck-Out Rules for Different Average Arrival Rates, and Different Criteria of Optimality....................... . 55 X Effect of Variation in Estimates of), and p on Optinum ChBCk‘Ollt mil-680000oooooooooo’ooooooococoon-00000000... ....... 56 vii LIST OF FIGURES FIGURE 8. 9. 10. Total Variable Cost of Operating a Queuing Process .......... Daily Sales Volume at One Super Market in Detroit, Jan. 5- Febo 21, 19590000000000.0000...so... ooooooooooo o oooooooooooo Actual Frequency Distribution of Customer Arrivals .......... Theoretical Frequency Distribution of Customer Arrivals ..... Comparison of Actual and Theoretical Oistomer Arrivals on Monday, Tuesday and Wednesday.. ......... ...... . ............. Comparison of Actual and Theoretical Customer Arrivals on TIMI‘Sdayoosossoooosoooo..o.......o............o............'. Comparison of Actual and Theoretical Oistomer Arrivals for Friday, before 6 P.M........................................ Comparison of Actual and Theoretical Distomer Arrivals for bid”, after 6POM000000000000000000 000000 00000000000000000 Comparison of Actual and Theoretical Oistomer Arrivals for saturdWO00.00.0000.00.000.000.000000000000 0000000000000 000. Diagramatic Determination of the Penalty Coefficient d ...... viii Page 2 ll; 23 23 25 25 26 26 27 1L6 CHAPTER I INTRODUCTION Shopping at a super market is a familiar experience for the general public. Every shopper is, to some extent, interested in super market operations whether he is an operations research analyst or not because it requires little technical training to understand the operations. As he goes through aisles, pushing a cart, selecting his purchases, and finally ending up at the check-out stand, he cannot help but wonder if there is a way of improving at least some phases of the operations. In this study, the author is thinking along the same line as this super market customer except in a more direct manner. The main concern of the study is how to provide a.high grade check-out service in the most economical manner. What is a Qleuing Problem? 1 There are many operational problems involving flow of customers in which the following two types of condition are observed: 1) Units that require service must wait for service because there is a shortage of service facilities. 2) The servicing facilities must remain unused, not only because of the lack of customers in quantity, but also because of the nature of the time spacing between customer arrivals. 1In queuing theory, the term customer is not restricted to a person. It can mean an aircraft waiting to land at an airport or an automobile waiting to pass through a toll gate. Either of these conditions results in the formulation of a waiting line. In the first instance it would be a queue of input units, and in the latter the units in a waiting line consist of service facilities. The shortage and surplus of service facilities are usually brought about by inability of a system to decide in advance a right amount of service facilities to provide to.its customers; this inability, in turn, is explained by the random elements which influence demand for service both in time and quantit . Under these conditions, a so-called queuing problem arises. The problem is to change the behavior of the arriving units, or the service facilities or both in.order that the queuing process may be operated in as efficient and economic a manner as possible. This can be illustrated for the case where a queue consists of input units. Total variable costs (TVC) of operating a system that involves a queuing process are made up of operating cest ROG) and waiting time cost (WTC). Figure 1 Total Variable cast of Operating a Queuing Process Variable Coat c ‘ WTCl ‘ we, Amount of facilities Here waiting time cost is defined as the cost of losing a potential customer because of insufficient service facilities. Operating cost may be assumed to increase approximately in.proportion to the amount of facilities provided. On the other hand waiting time cost (for units being serviced) probably decreases at a decreasing rate as more service facilities are added to the system. It should be noted that waiting time cost is a joint function of service facilities and the behavior of arriving units. For each change in the behavior of arriving units, a new waiting time cost function and a corresponding total variable cost function can be drawn as they are indicated by dotted curves in the above Fig. 1. There are at least three ways of minimizing the total variable costs. 1) For a given amount of facilities, find what behavior of arriv— ing units will give a minimum variable cost. In Fig. 1, aa' is the minimum total variable cost. 2) Find what is a right amount of service facilities which corres- ponds to the minimum point of the total variable cost curve for a given behavior of arriving units. 3) By varying the two variables (behavior of arriving units and service facilities), the minimum point along the lowest total variable cost curve can be found. In order to quantitatively solve a problem of this type, the tools of prdbability theory can be used to provide convenient methods of determining the relatiOns between the flow of arriving units, amount of service facilities, and grade of service. With this knowledge the optimum grade of service can be determined in a lOgical manner; the amount of service facilities required at any time of day as well as the flow of customers to be permitted to the system can be specified in advance. The probability theory can be applied in two different ways in solving a queuing problem. They are usually referred to as the mathe- matical and simulated sampling approaches. The mathematical or analytical approach begins with specifications of probability distributions regarding customer arrivals and service times. Based on these specifications, relationships that describe the queuing process are derived by writing down statements about the prOb- ability of there being a given number of customers in waiting line under various conditions. These relationships can be solved for such quantir ties of interest as average number of customers in the system, expected length of waiting lines, etc. ‘When costs arising from waiting time and operation of service facilities are known, one can analytically arrive at the conditions under which a minimum cost is attainable. Solution of the problem by the mathematical approach has a neat appearance. However, sometimes it is difficult to specify explicitly arrival and service distributions. Even if they can be represented in terms of probability distributions, frequently a researcher is not able to arrive at mathematical statements describing the queuing process. If this is the case, the second approach may be used. In the simulated sampling approach, a procedure known as the Monte Carlo technique is commonly used. By the use of a table of random numbers and of empirically determined prdbability distributions, statistics on arrivals and service time are duplicated in a mechanical way on a high-speed electronic computer. This method allows a research worker to study the effect of changing conditions without waiting for actual data over a long period of time. The simulated sampling approach has become more useful as a result of developments in high‘speed computers. In the current study, the first approach was followed and total variable cost of the check-out operation was minimized with respect to the amount of service facilities for a given arriving pattern of incom- ing‘units. Objectives of This Study The study attempts to test the applicability of a queuing model to the check-out operation of a super market. The check-out operation seems to have all the necessary features that make up a typical queuing prOb- lem. There are customers who demand service; as each customer reaches a service point, he receives a service. After a certain service time, he leaves. If the service point is not immediately available to him, he must wait his turn; in other words, he joins a queue. How long he will have to be in the waiting line depends on how many other customers have been to the store before him and also depends on how many service points are in Operation. Management can do little about the flow of customers to a store but it can adjust the number of check—out counters available to customers so that a certain criterion can be met. In most super markets, allocation of man power necessary in providing check-out service as well as control of the number of check-out stands Opened at any time is left to the discretion of the store manager. In making these decisions, he mainly relies on his experience and a rule-of-thumb 'work standard. Hence it appears plausible to analyze the check-out service by means of queuing theory so that the operational.prOblem involved can be dealt in quantitative terms. It is felt that this approach would be a supplement to a subjective way of dealing'with the problem as in the past. There are certain crucial assumptions on which a queuing model is based. These assumptions must be carefully checked in the light of the actual check-out operation to see if they are reasonable. Above all they must yield fruitful results. To begin with, the analysis by queuing theory is based upon: (I) the length of time between tw0 successive customers' arrivals and (2) the time used for servicing a customer. These two quantities are specified in terms of probability distributions. It is than natural to apply some statistical tests based on the hypothesized prObability distributions to empirically derived distribution functions. Like many a mathematical model, the queuing model need not corres- pond exactly to a real situation; if it can.be regarded as an.approxi- mation to the actual check-out operation, than it can be used to provide decisiOn criteria for the operation. A general method of determining the amount of check-out facilities which will minimize the expected total variable cost of the check-out operation is indicated, and three specific approaches based on this general method were proposed and they'were ap- plied to the data Obtained at one of the large super markets in Detroit. CHAPTER II QUEUING MODEL TO BE USED IN THIS STUDY Various queuing models can be constructed by altering specifica— tions in regards to: (l) the number of service "channels," (2) prob- ability distributions of customer arrivals and service times, (3) queue discipline, and (h) queue length. In the current study, the formulae of operational interest for the queuing model which has multiple exponential "channels" with Poisson arrivals, infinite queue and strict queue discipline1 were applied to the super market check-out operation in order to determine an optimal way to provide check-out service to customers from the standpoint of management. A Simplified Representation of the Check-out Operation at a Super Market In order to apply the above model, first consider a super market whichhas a finite mlmber of check-out stands. These check-out stands have identical service mechanisms and each of them can operate inde- pendently of the others. Furthermore, it is assumed that each stand 1Multiple exponential channels mean that there are more than one service point and the time needed for a customer to go through a service point follows the negative exponential distribution. Poisson arrivals refer to the assumption that the number of arriving customers per unit time is a Poisson variate. Infinite queue refers to situations in which every arriving customer must join the queue no matter how long it happens to be. Theoretically the queue may become infinite. Strict queue dis- cipline is the so-called "first come first served" rule. can be operated at the two different levels of average check-out rate, say “.1 and “.2. In this analysis, the rmmber of check-out stands to be made available to customers at any given time will be less than or equal to the number of checkeout stands that the super market has at the outset of the analysis. Next, customers are considered to arrive at the check-out area at a certain average rate. Suppose there are m-k check-out stands which have the average service rate ofu1 and there are k check-out stands with the average service rate of “2. A rule adopted here is that 'EiE x 100 percent of the incoming customers will be served by the check- out stands with the average service rate pl, and the remaining portion of customers will be serviced through those stands which have the average service rate p2, It is shown in Appendix A that adopting this rule will reduce the problem to a more familiar case of m equivalent service channels, i.e., each of the m check-out stands has the average service rate, say u, where p. is (m-RJul + kpz u, = m 0 As soon as each customer arrives at the check-out area, he moves into any check-out lane which is free to service him. If he finds all the lanes are occupied, he is assumed to form a hypothetical common queue. Under these conditions, a queue exists when the number of customers in the check-out area exceeds the mmber of operating check-out stands at any time and their difference is the length of queue. Probability Distributions of Customer Arrivals and Service Time The main feature of a queuing model rests in its characterization of the input process and capacity of service mechanism in terms of probability distributions. It is assumed that the customers arrive at "random," i.e., the number of arrivaL'Ls‘per unit time is a Poisson variable. Perhaps this is the simplest hypothesis about the input process. From this assumption, it follows that the time interval. between two consecutive arrivals has the negative exponential distribu- tion.2 As to the service time, i.e., the time necessary for a particular customer to be served, the assumption is that successive service times are statistically independent of one another and each is distributed by the negative exponential distribution. It should be noted that two types of service time are considered here. At first, these artificial schemes of representing customers' arrivals and service times may not seem‘realistic, because the infor- mation that no customer has arrived at the Check-out area for, say, tau minutes will generally increase our expectation that a customer will show up in the next mimte. It is also not natural to assume that service time obeys a negative exponential law, because one would in- tuitivelyfeel that the probability of service time approaching a very short duration of time must be close to zero. They have been, however, found useful in many situations which seem to have features similar to the check-out operation. Besides, considerable mathematical 2See Feller, (1950), p. 36h. lO simplifications can be achieved by these assumptions. One of the main objectives of this study, as stated at the outset, is to examine the applicability of these schemes to the check-out operation. These assump- tions are stated more completely in Appendix A. Expected Values of Various Quantities of Practical Interest in the Problem Under Study After the fluctuations of customer arrivals and service times have been expressed in terms of probabilities, other measurable quantities associated with the check‘out operation will be considered as stochastic variables which vary with time about some average values. There are two possible ways of studying these stochastic variables. The first deals with the steady state or stationary phenomena of the variables . The main purpose of this first approach is to determine how'the variables behave in the long run. The second approach has to do with the transient behavior of the variables, i.e., the exact behavior of the stochastic variables as a function of time. . In the current study, the first approach was adopted to study the stationary structure of the check-out process. Intuitively, one feels that the check-out process will approach a steady state, because there are restoring forces within the system which attempt to keep down the length of queue. In many cases, a probabilistic picture of steady state will give sufficient insight for one to be able to calculate important- quantities of the system and predict the system's overall behavior. Suppose the whole check-out process is considered as a system. This system can be in a number of possible states, which are specified by the number of units in the syStem, waiting for service, in service, etc. The steady state solution would give us the probability that the system is in each of the possible states. From these probabilities, average values of the various quantities of interest (mean number of customers in the system, average length of queue, etc.) and derived probabilities such as the probability that there are more than a certain number of customers waiting in each check-out lane can be calculated. The steady state distribution is given in the following. The derivation of this distribution is set forth in Appendix A. Although a minor modification had to be made to take account of the fact that not all the service points have the identical average service rate, the mathematical development in Appendix A essentially follows the presen- tation of Peller (1950). The author assembled all the assumptions which are needed to derive the steady state distribution and presented the lOgic underlying the derivation of steady state distribution in detailed form. The purpose is to facilitate the understanding of the technique used in this study. Let Pn : The probability that there are n customers in the check-out system. 9 x The ratio of the average arrival rate to the average service rate, per channel. Mp. u is defined as in P.8, m z The number of check-out stands that are rendering service to customers.3 3The quantityp/m is often called the relative traffic intensity. The term "relative" implies that the. traffic intensity is measured in relation to the capacity of‘the system. 12 The steady state distribution is as follows: -l Ill-'2 ' J m-l m o 330 j'. m-l)t m-p .0 Pn = P0 ET 0 < n g m (2.1) p P =- P0 n g m n mtmmm Given the explicit expressions for the state probabilities, as in (2.1), it is relatively straightforward to obtain the expressions for expected number of customers in the system, expected number of customers waiting for service, derived probabilities such as the probability of the length of queue being less than a certain fixed number. Some useful formulae are presented below and their derivations are also given in Appem-‘Ix A: pp. 76-77. Let Ls x The expected mmber of customers in the system. Lq 8 The expected number of customers in waiting line. q* x A given constant. m-l 1n n+1 ' m Q ,_ m LS '- P0 :0 (n-l)‘ + (hr-l)t(m—p)2 + (m—l)l(m-p) (2.2) pm+l ' ' ' Lq = P0 (xi-lumps? (2'3) ‘ * ’ m+q +1 Prob. (length of queue > q*) = 39.4.... (2.1:) mtmq (m-p) 13 Study of Volume of Daily Sales at the Detroit Super Market Under Study In order for the steady state solution to be valid, the average customer arrival rate and the average service rate nust, roughly speak-r ing,be neither rising nor falling. If they are stable, i.e., their fluctuations are short-term fluctuations around their constant mean values, the state probabilities and derived average values will be independent of time. As long as there is no basic change in check-out facilities, it is not too unrealistic to assume that the average service rate remains stable. However, average customer arrival rate does fluctuate. In fact, it is closely related to sales volume per unit time. Inspection of daily sales volume at this store in Detroit for a period of about two months indicated that variation is nearly periodic with periodicity of one week. This is shown in the following diagram in which sales volume for each week day in January and February of 1959 is plotted. Each vertical block represents a volume of sales for one day. A low sales volume for the first part of the week is in contrast with heavy week- end sales. Sales on 'Thursday seem to constitute a group by themselves. Study of this diagram suggests that the week could be subdivided into at least four periods so that within each period the customer arrival rate may be reasonably stable. The first three days of the week were combined into one period, and the remaining three days were analyzed separately. Initially it was conjectured that Friday and Saturday would have almost identical traffic intensity, Judging from the volume of their daily sales. Discussion with the store manager and anon S-IZFZ S-VI-Z os-L-z os-IE-I os-fia-I .mmma .Hm .ooa.c m .ooe .oaos boo ea posses bosom see or ossaoe modem eases éS-LI-I .N enemas 65-OI—I 08.2 .oma mmdflm 15 the others who are familiar with the check-out operation, however, re— vealed that the traffic pattern on Friday is quite different from that of Saturdw. On Friday before six o! clock, the incoming traffic is usually not much faster than an ordinary week day, but the traffic picks up considerably after six. Actually, more than half of the day's sale is usually made in the last two or three hours before the store closes. Hence, eventually Friday was not only studied separately from Saturday, but within Friday two separate analyses were made. Review of Literature In this section, the main sources of the theoretical study about the queuing model used here as well as the sources for other types of models are mentioned. Some applied works which have come to the author's attention and were found useful in connection with the preparation of this thesis are also discussed. The pioneering work in queuing theory was undertaken by A. K. Erlang some fifty years ago at Copenhagen in connection with telephone switching problems. Most of his papers are contained in a memoir. prepared by Brockmeyer _e_t g1_., (l9h8). An account of Erlang's work is also given by Fry (1928). A More recently, Feller (1950) discussed the queuing process as an example of simple time-dependent stochastic process and derived the state probability distribution in the case where the number of arrivals per unit time is a Poisson variable and service time is distributed by a negative exponential distribution. This was the model tested in this thesis. 16 An excellent survey of queuing theory is also to be found in the two articles by Kendall (1951, 1953). He considered, in the first paper, a queuing process with Poisson input and no specific assumption with respect to service time, i.e., the service time distribution can be one of the following three distributions: 1) constant or regular, 2) negative exponential, and 3) Erl'angianf. The distribution of queue size in statistical equilibrium was derived. In the second paper, the assumption regarding the input process was stated in a more general form-the inter-arrival times were independently and identically dis- tributed in an arbitrary manner. However, the service mechanism was supposed to be characterized by the negative exponential serVice time. The analysis of the system was carried out by applying the method of the imbedded Markov chain.5 The ergodic6 behavior of this Markov chain was investigated. A queuing system of the more general type was considered by Lindley (1952). No specific assumptions with respect to input and service mechanism were made except input is independently and identically distributed and service time is distributed by one of the three v—v—vm _‘ 4‘I.et t, 0 < t <", denote the inter-arrival time and A(t) its c.d.f. The density of the Erlangian distribution is ‘ i k .. .. dA(t) = LIE-L e 1‘“ tk 1 dt. rm) _ t For k a l, dA(t) -’ As A negative exponaltial. For k = G, dA(t) -9 0 constant. 5It is a method of transforming a sequence of random variables into a process which satisfied the Markovian property. See Kendall (1953): Pp° 3hlr3h2c 6Loosely translated, it means asymptotic properties. 1? distributions mentioned in connection with the papers‘ by Kendall The queuing systems considered by the aforementioned authors are all based on the strict queue discipline. The system becomes increas- ingly complmc to analyze as one allows for a more flexible rule. Although there is one article by Holly (19514) on this subject, the problem does not seem to have been treated extensively by the statis- ticisn. The theory of queues has a surprisingly wide range of applications. The four studies reviewed here represent only a small sample. The first empirical study is an example of the classical applica- tion of queuing theory. The study was conducted by Molina (1927). The objective of his study was to find a way to operate the telephone trunk- ing system economically yet consistent with good telephone service to the subscriber. In other words, the purpose of the study is to find a compromise between the number of circuits and the amount of equipment and the time necessary to complete a call. He assumed the number of incoming calls per unit time to be a Poisson variable and considered two alternative assumptions regarding holding time;7 viz., exponential holding time and constant holding time. It is to be noted that in the case of the constant holding time, he was able to obtain only approxi- mate solutions. The probability of a delay, which is greater than an interval of a certain length, was calculated for a given number of trunks under various arrival rates of incoming cells. These probabili- ties were used as action criteria in deciding if it was necessary to 7"Holding time" is a terminology of the telephone industry, and it is equivalent to service time. 16 add more circuits. Molina did not explicitly introduce the concept of cost into his study. Edie (1955) applied the theory in analyzing traffic delays at toll booths operated by the New York Port Authority at the Lincoln tunnel, George Washington bridge, etc. Since the major portion of expenses necessary in manning these toll booths is the salary of toll collectors, it was natural to consider a way to economize the toll collecting operation by reducing the number of collectors, yet at the same time maintain the policy of giving uniformly good service to the public. In the past the allocation of manpower and controlling the number of toll booths opened at any time were left to the discretion of the toll sergeants. The quantity of the service tended to vary appreciably from time to time. By means of the queuing theory Edie was able to provide methods for dealing with the problem in quantitative terms and was able to reduce toll collection expenses without impairing the quality of service. The queuing system used is similar to the one considered by Feller (1952). He made careful analyses of the incoming traffic, but not much was said about service time distributions. Again, the problem seemed to have been tackled mainly from the engineer's point of view, because there was little discussion on the cost aspect of the problem. In contrast to the first two studies, the cost concept was directly utilized together with the queuing theOry in solving an inventory prob- lem in the study made by Flagle (1956) . The stochastic element involved in the inventory problem is the random receipt of orders for the product. The problem was to determine the planned initial stock level that yields a minimum sum of expected storage and depletion costs. The first step 19 in solving the problem was to calculate the probability of experiencing each of the possible inventory states during a reorder period. Next the costs associated with the system in each of the possible states were estimated. There were three major expense items that comprised the cost. They were interest charges being incurred for carrying a certain level of stock, storage and handling fees, and loss of orders due to the in- ability of the system (shortage of stock) to fill an order. The costs associated with the first two items are proportional to the size of the inventory. The cost incurred by a loss of a customer or a potential customer is inversely proportional to the inventory level. After state probabilities and associated state costs have been obtained, expected cost was calculated for a given value of average order rate and deple- tion reserVes. The calculation was repeated by varying the value of depletion reserve until that value of depletion reserve which yielded a minimum expected cost was found. This technique was applied in minimizing the expected cost arising from the queuing system studied here. In spite of its wide use by the engineer, the theory of queues has not been applied frequently in the field of agricultural economics . As far as the author is aware, there has been only one report on an applied queuing problem in the Journal ofm Economics. Cox _e_t_ gl_., (1958) applied the theory in determining livestock unloading facilities. The problem was to decide on the number of docks needed to meet certain management requirements which were specified in terms of either maximum allowable waiting time for a truck to unload or the length of the maxi- mum allowable waiting line. The simulated sampling approach was adopted. 20 First probability distributions of arrivals and service time were esti- mated. Then an arrival number was drawn at random from the estimated distribution. For each arriving truck, a service time was also drawn at random from the estimated service time distribution. And a record of occupancy of the dock was kept. The process was repeated on a high speed computer until the probabilistic features of a waiting line formation were known. In this study, the authors were interested only in the probability distribution of the number of trucks waiting in line and the cost associated with this probability distribution was not dis- cussed. In closing this section, it should be noted that a comprehensive bibliography of queuing problems can be found in the book edited by McClosky and Coppinger (1956). CHAPTER III SOME STATISTICAL ANALYSES 0F CUSTOMER ARRIVALS AND SERVICE TIMES The analysis by queuing theory is based upon: (1) the length of time between two successive customers' arrivals, and (2) the time used for servicing a customer. These two quantities are specified in terms of probability distributions as mentioned in the previous chapter. It is then natural to apply some statistical tests based on the hypothe- sized probability distributions to empirically derived distribution functions. Although the hypothesis is that the probability distributions are negative exponential in both cases, empirically derived distribu- tions of the first quantity'were not directly tested against the negative exponential functions for goodness-of-fit. Instead, empirical prob- ability distributions of the number of customers arriving per unit time ‘were checked against Poisson distributions. As mentioned briefly in the previous chapter, assuming the customer arrivals per unit time to be distributed by a.Poisson.distribution implies that the length of time between.two consecutive arrivals has a negative exponential distribution.1 Furthermore, it is simpler to count the number of customers arriving at the check-out area per unit time than to directly measure how much later a customer arrives after his predecessor. 1ThiS'was demonstrated by Feller in his Probability Theory and Its Applications, pp. 363-367 22 The Goodness-of-fit Test The first type of data recorded was customer arrivals at the check- out area. Observations were taken by counting the number of customers arriving per one minute interval, with an exception of Thursday.‘2 An interval of one mirmte was used because it was about the shortest that permitted the observer to make recordings without losing the count. Observations were taken for each of the five periods within the week, and an actual frequency distribution was constructed from observations for each period by computing occurrences of each arrival class as a percentage of the total intervals observed. These percentages were then plotted against the arrival classes, as shown in Fig. 3, and frequency polygons were drawn. The frequency distribution with the higher average traffic volume per unit time tends to flatten out, and at its right-hand tail there is a tendency for the frequency to be higher. I In order to compare these actual frequency distributions with the theoretical distributions (in this case, Poisson), the theoretical distribution corresponding to each group of observations was obtained by estimating the mean from the observations and it was plotted in Fig. )4. The similarity of the curves in Fig. 3 to those in Fig. 1;, is quite evident. An empirical distribution based on observations on Thursday's traffic arrivals was not included in Fig. 3 because observations were- based on different time units. 2The arrival classes were based on a five-minute interval on Thursday. 23 0 Figure 3. Actual frequency distributions of customer 5 F arrivals. ‘5 to C) Fri . Evening N O 5‘“ ° Fri. Daytime Frequency of arrivals, percent '5 O l . . 1 2 3 customers per one minute interval. ‘ Figure 1;. Theoretical frequency of distribution h0 of customer arrivals. ‘\\ 0.91 customers/min. (Mon) 30 x 1.85 customers/min. (Fri. Daytime) . . 2. hi; customers/ min. (Sat. ) \ \ < 20 I 2. 56 customers/min. (Fri. Evening) Frequency of arrivals, percent. ’0 l 2‘ 3 h 5 6 7 Customers per one minute intervals. 2b An easier comparison beWeen the actual and the two theoretical distributions, Poisson and normal, can be made by referring to Fig. 5, 6, 7, 8 and 9. In each diagram, the actual distribution and two theoretical distributions estimated from the same set of observations are plotted together. The mean arrival rate and standard deviation are also presented in the diagram. One feature to be noted is that the normal curve appears to fit slightly better than Poisson to observations on Thursday. This is probably due to the fact that arrival classes on Thursday's observations are based on a five-minute interval instead of on the one-minute interval. When the duration of observation interval is prolonged, frequency of occurrences of the event that an extremely small number of customers coming in during a five-minute interval would tend to be small. Hence, the empirical distribution resembles a familiar bell-shaped normal curve. In addition to plotting frequency polygons, a statistical test was noplied to see which of the two theoretical distributions gives the better fit to the data. The test statistic used was the familiar quadratic expression whose values are larger the farther the observed frequencies differ from their means as calculated under the hypothesized distribution. It is known to have asymptotically a chi-square distribu- tion with T—K—l degrees of freedom where T and K are the number of classes and estimated parameters respectively. When the test statistic has been calculated, a probability level of fit can be found in a table of chi-square distribution. A perfect fit would show a probability level of 1.00, but a fit showing a probability level better than 0.05 (T O w 0 Frequency of arrivals, percent N *5 o Frequency of arrivals, percent a a 25 Figure 5. Comparison of Actual and Theoretical Customer Arrivals for Monday \ , - "'X Men Arrival Rate: 0.91 persons/one min. - T/"_“~~ K’;/, \\ \\ \ y \ \ Standard Deviation: 0.956 96" ' \f actual --- broken line : actual --- solid line : theoretical 1 A 2 3 14 5 customers/ min . Figure 6. Comparison of actual and theoretical customer arrivals for Thursday Mean arrival rate : 7.6 persons/5 min. Standard deviation : 2.63 persons/ 5 min. customers/ 5 min . Frequency of arrivals, percent. Frequency of arrivals, percent. h0_ 26 Figure 7. Comparison of actual and theoretical customer arrivals for Friday (before 6 P.M.) mean Arrival Rate: 1.76 Standard Deviation: 1.17 Customers per minute. Figure 8. Comparison of actual and theoretical customer arrivals for Friday (after 6 P.M.) mean.Arrival Rate: 2.56 Standard Deviation: 1.38 L L‘ #L l 2 3 Customers per minute. 28 TABLE I CUSTOMER.ARRIVAL GOODNESS-OF-FIT Average Number The Significance Arrival of One Level at which Rate Minute Chiesquare Statistic H0 is ngected Period Per Min. Intervals Poisson d.f. Normal d.f. Poisson Normal Mon. Tues. ‘Wéd- 0-91 19h 3-897 h 39-232 3 99% * Thurs. 1.50 365 7.155 12 6.681 11 9O 90 Fri. before 6 1.77 1h5 8.107 6 18.858 5 25 * Fri. after 6 2.56 113 13.193 6 lO.h8h 5 5 5 Sat. 2.hh 257 3.828 6 12.822 5 75 * Abbreviations: * a The significance level is less than 0.05. d.f. a Degrees of freedom. a theoretical distribution seem to support the reasonableness of the assumption that the incoming traffic of customers is of the Poisson type. And they also seem to suggest that statistical tests based on the normal approximation would be adequate forms large sample. Observations on another important quantity of the queuing theory, average service time, were also tested by the chi-square test. Since service time is a continuous variable, it was tested against a negative exponential function. 'As mentioned previously, two kinds of checkeout service were considered; 1) a checker alone at a check-out stand, and 2) a checker as well as package boy is at the stand. In each case, service time is directly measured by clocking the duration of time taken by'a checker when she starts to register a customer's purchases until 27 Figure 9. COmparison of Actual and Theoretical Customer Arrivals for Saturday 30. Mean Arrival Ratc:2.hh Standard deviation :1.h5 Frequency of Arrivals, Percent 3 h 5 o 7 Customers per minute 1 2 is generally taken to mean that the hypothesized distribution need not be rejected. Results of applying the test are given in Table I- The fit of the Poisson distributions seems to be very good, especially at the low traffic volume per unit time. The fit of the normal curves are not as satisfactory as the Poisson, although it appears to show some improve- ment when the number of intervals observed is relatively large. As indicated by the size of calculated chi-square statistic in Table 1, the fit of a.Poisson distribution to an empirically derived arrival distribution tends to deteriorate for a relatively large average arrival rate. This may'be explained by the fact that when.the traffic becomes extremely congested the distribution has a tendency to become constant. Results of chi-square tests as well as an inspection of those diagrams in which an.empirical frequency distribution is plotted against 29 she finishes packing groceries into paper bags. Computed chi-square statistics were relatively large which suggest that the data fit poorly to the negative exponential function. They were significant at the one percent level or less; in other words, values as large as the calculated statistics would be observed only one time out of a hundred trials by chance. This might have been expected because the assumption of a negative exponential function implies that the frequency of occurrences of service time being zero will be the largest, i.e., we-” reaches its: maximum at t a O. Ordinarily one would expect the highest frequency of check-out service times to be clustered around a certain average value which is different from zero. Inspection of the data indicated that they might have fitted better to another member of the gamma function family.3 Sinceqthe assumption of exponential service times makes the analytical @proach to a queuing problem manageable, the state prob- abilities were calculated based on this assumption. Some alternative assumptions as well as possible different approaches to the problem are mentioned in the last chapter. 30bservations on the check~out time per channel (which is run by a checker alone) were fitted experimntally to a gamma function of the following form: _ e Btwflr-l f(t) ‘3 8 5-3.)“ 'Ehe parameter r determines the shape of f(t); the parameter [3 determines its ‘scale,(r > 0,13 > 0). Estimates of the parameters r and £3 by the method of moment were 1.8143 and 0.957 respectively. The calculated chi-square statistic against this distribution was 8.793. Since the degree of freedom was 9, the null hypothesis that the observations came from the gamma distribution with r a 1.8h3 and £3 = 0.957 need not be rejected at the 50 percent level. 30 Statistical Properties of Average Durations of Service Times In a theoretical study of the probability structure associated with a queuing problem, values of average arrival and service rates are assumed to be known a M. In application of queuing theory, however, these quantities must be first estimated from observations. The esti- mates are subject to sampling fluctuations. In.this section some statistical properties of estimates of average duration of service times are discussed. Remarks made in this section on service time can be equally applied to customer's "idle" time,4 because they are defined in an analogous manner. - First the sampling distribution function of an estimated average service duration was derived. From this sampling distribution, a confidence interval about the estimated average service duration can be obtained to give us some measure of assurance that the true parameter does lie within the interval. At the same time, an.appropriate sample size can.be determined in order*that the probability that the sample mean will lie within a fixed distance from the population mean will meet at least a certain prespecified level. The confidence limits and sample sizes based on the exact sampling distribution are compared with those derived from the normal approximation. The normal approximation was found to be satisfactory in general. 'file sampling distribution was obtained by first forming a joint density function of all the Observations on service times and then 4Customer's idle time refers to a time interval between two consecutive customers' arrivals. 31 applying an appropriate transformation to the variables of the joint density function, and finally integrating out all the irrelevant vari- ables from the transformed joint density function. Details of the above procedure are presented in Appendix B. The desired cumulative distribution function and density function are respectively as follows: n n-l Prob.( e< y) = 1 - e’nW 2: 1.1 ‘ (3.1) - i=1 n A ‘ ‘ -1 .- g(6) ° 1%; 9 n 8 nine (3.2) where 8 x The maximim likelihood estimate of average service time. It is defined as n .3 ti 5 3 i=1 - n where ti is the i—th observation on the service time. n x The total number of observed service durations. LL 3 The average service rate. Note that 2‘- :- e where e is the “true" average service time. The cumulative distribution function (3.1) is an incomplete gamma function. It can also be considered as a right-hand tail of the Poisson distribution with the parameter (my) . From the density function (3.2) the mean and variance of a can be evaluated. A - A A i A E‘d af sg(e)de=-1- 0 P' Var.(5) = 4" (’é-E‘é)2g(é) d e = 31; 32 Since the mean and variance of 5 are known functions of the para- meter p, the normal approximation can be applied as a short cut in calculating a confidence interval of 6 as well as in determining a required sample size, when the sample'size is large. Confidence Interval Although the sampling distribution function ore has been found, it is not independent of an unknown parameter. As can be seen from the equation (3.1), it involves the unknown parameter p. In order to make a probability statement of the form: Prob. (a<6 k. C2[Lq(h, 3.1)] : Penalty cost per unit time. Then the expected cost for providing the check-out service, given fixed values of X and p. is C a (C +C2)P (11.1) )‘sp' a 1 n The optimal criterion dictates that the expected cost (h.1) is to be minimized with respect to u(m,k) for a given value of A. Hence the equation (h.l) is evaluated at all the feasible values that m and k may take. . Evaluation of the enacted cost by means of (h.l) can be somewhat Simplified, if one notes the fact that costs of employing a certain number of cashiers and bag boys are independent of the stationary dis- tribution Pn. The equation (h.l) can be reduced to the following form: CK”:- 01);:I Pn + fiCZPn (11-2) :3 C1 + z C2Pn n 1The functional notation is to emphasize the dependence of the state probability on the average arrival rate and average service rate. The average service rate, in turn, is a function of the number of checkers and package boys, (see p. 41 of this Chapter). Similar remarks apply to the cost functions 01 and 02. J40 Hence the problem may be stated as follows: "with respect to p,(m,k). Because of one of the simplifying assumptions that there should not be Minimize CA a more bag boys than cashiers at any tim, the function p.(m,k) would be defined at most at Ram-+21 points. Since in most super markets the mmber of check-out stands will rarely exceed ten, evaluation of the cost function Cx’p’is not unmanageable. Some Specific Solutions Three different objective functions based on 01.2) were formulated in this study. Their differences lie in the nature of the penalty cost fmction assumed. In the first formulation, a specific penalty function was introduced into the objective function. In the remaining tyro, the penalty cost was not included in terms of the dollar values of the "good will" lost as a result of keeping one customer waiting in line for one time unit.2 However, the length of queue was incorporated indirectly into the cost function as a constraint of minimization. l) Minimize (m - k)W1 + kHz + 8 (Lq) (11.3) with respect to m and k, . where m: The number of counters in operation or the number of checkers. k: The number of bag boys, (05 k: m) A _‘ 2"Good will" lost can be considered as the discounted net value of future business lost. hl W1: Cost per unit time of operating a counter without a bag boy W2: Cost per unit time of operating a counter with a cashier as well as a bag boy Lq: Ehrpected length of queue which can be computed by formula (A.18) in Appendix A. 5 ! Penalty cost function which is assumed known to management. Suppose 5 is a linear function, the cost function (11.3), may be written as follows: m+l Po p (m--k)W1 + sz + d (Jill) (lrn--l)t(1m-‘10)2 where d is considered as the dollar value of the good will lost as a result of keeping one cuStomer waiting in line for one unit time and p :5 l/u. Since there is an average of L cuStomers waiting per unit Q time, the average penalty cost per unit time is qu. In the above fonmilation the explicit expression for Lg was inserted. The average service'rate p is a function of m and k. The function is specified as follows : =(m’k)#1*kfl2 [1 'mr (1111‘) The symbols #1 and ",2 refer respectively to the average service rate of one check-vent stand operated by a cashier alone and the average service rate of a stand when it is run by a checker and bag boy. 2) Minimize (m - k)w1 + sz . (h.5) with respect to m and k, subject to *- < 112 where L* is the maxilmm allowable average length of queue. It is a parameter set by management. 3) Minimize (m - MRI + U2 (11.6) with respect to m and k, subject to :9 mg +1 w- P Prob.-(q>q)=—-'39l*r - 2m): The probability of more than two customerswaiting in each check-out lane. T.V.C. 'x The total variable cost evaluated by means of 04.14), cents per minute. (1) z The optimum check-out rule obtained by the first method, i.e., Min C + d Lq a ToVoCo m,k ‘ (2) x The optimum rule obtained by the second method, 108., Min '0 subject to L m,k q<2m (3) z The optimum rule obtained by the third method, i.e., Min C subject to Prob. (q > 2m) < 0.05. m,k 149 TABLE Iv OPTIMUM CHECK-OUT RULES FOR MONDAY, 1111180111, AND WEDNESDAY (i=0aD AA A‘ :‘h‘ ‘1.v.c. Optimum “a 5 m k c Lq Prob(q > 2m) (fi/min.) Rule 2.25 3 0 8.h3 1.699 7.80% 10.51 1.50 2 1 7.18 1.929 15.22 9.55 (2) 2.25 h 0 11.21; 0.310 1.1.62 1.69 3 1 9.99 0.399 - 10.h8 _ 1.13 2 2 8.7u 0.530 2.38 9.39 (1),(3) 2.25 5 0 1h.05 O-O7h - 1h.1h 1.80 h 1 12.80 0.105 - 12.93 1.35 3 2 11.55 0.152 - 11.73 2.25 6 0 16.86 0.018 - 16.88 1.87 5 1 15 .61 0 .028 - 15 .61; 1.50. n 2 1h.36 0.0h5 - 1h.h2 1.13 3 3 13.11 0.07h - 13.20 2.25 7 0 19.67 0.00h - 19.67 1.93 6 1 18.h2 0.007 - 18.h3 1.61 5 2 17.17 0.016" - 17.19 1.28 h 3 15.92 0.021 - 15.95 1.97 7 1 21.23 0.002 - 21.23 1.69 6 2 19.98 0.003 - 19.98 1.h1 S 3 18.73 0.006 - 18.73 1.13 h h 17.h8 0.012 - 17.h9 1.75 7. 2 22.79 a - 1.50 6 3 21.5h 0.002 - 1.2h S b 20.29 0.003 1.57 7 3 Zh-BS * " 1035 6 )4 23 .10 O .001 " 1.10 7 b 25-91 * - 1023 6 5 211.66 '3!” " 1.31 7 5 27 .h? -x- l.13 6 6 26.22 a- 1.21 7 6 29.03 * — 1.13 7 7 30 .59 * - J‘ *- : Lq is less than 0.001. - : Prob(q > 2m) is less than 1%. TABLE V OPTIMIM QiEGK-OUT RULES FOR THURSDAY (i=15n ‘ “ ‘ me‘ wmmm p“ m k 0 La Prob( q > 2m (gs/min.) Rule 3.78 h 0 11.2h 15.13h 52-9h 32.h3 2.8h 3 1 9.99 16.009 61.37 32.h0 1.89 2 2 8.7h 16.790 66.38 32.2h 3.78 5 0 1h.05 1.862 2.17 16.10 3.02 h 1 12.80 1.596 huh 15.03 (3) 2.27 3 2 11.55 1.799 8.21 1h.07 (2) 3.78 6 0 16.86 0.399 - 17.82 3.15 5 1 15.61 0.h69 - 16.23 2.52 h 2 1h.36 0.556 - 15.1h 1.89 3 3 13.11 0.671 1.53 1h.05 (1) 3.78 7 0 19.67 0.125 - 19.8h 3.2h 6 1 18.h2 0.156 - 18.6h 2.70 5 2 17.17 0.198 - 17.h5 2.16 h 3 15.92 0.253 - 16.27 3.31 7 1 21.23 0.053 - 21.30 2.8h 6 2 19.98 0.072 - 20.08 2.36 5 3 18.73 0.096 - 18.86 1.89 h h 17.h8 0.133- - 17.66 2.7h 7 2 22.79 0.025' - 22.82 2.52 6 3 21.5h 0.035 - 21.58 2.08 5 h 20.29 0.0h9 - 20.36 2 065 7 3 2'4 035 O .013 " 2.27 6 h 23.10 0.019 - 1089 5 S 21085 0.030 “ 2.h1 7 h 25.91 0.007' 2.06 6 5 21.66 0.011 2.21 7 5 27.h7 0.001 1.89 6 6 26.22 0.006 2.0a 7 6 29.03 0.002 - 1.89 7 7 30.59 0.001 - - 8 Prob (q > 2m) < 0.01. TABLE VI ' OPTIMUM CHECK-OUT RULES FOR FRIDAY BEFORE 6 P.M. (1:189 T.V.C. Optimim 7, m k c Lq Prob(q > 2m) (pf/min.) . Rule ho§7 S 0 in.os 8-h17 29.52 32.57 3.65 h 1 12.80 8.h61 35.82 31.h1 2.78 3 2 11.55 8.880 hh.85 31.09 (2) h.57 6 0 16.86 1.h25 1.26 20.00 3.81 5 1 15.61 1.526 2.9h 18.97 3.0h h 2 1h.36 1.667 8.13 18.03 (3) 2.28 3 3 13.11 1.8h8 8.51 17.17 (1) n.57 7 0 19.67 0.h3h - 20.63 3 .91 6 1 18 .112 0 .1193 19 .50 3.26 5 2 17.17 0.572 - 18.h3 2.61 h 3 15.92 0.672 1.06 l7.h0 h-00 7 1 21.23 0.180 - 3.h3 6 2 19.98 0.220 - 2.85 5 3 18.73 0.266 - 2 028 )4 )4 17 0’48 0 0332 " 3.55 7 2 22.79 0.08h - 3.01. 6 3 21. 51; 0.107 - 2.51 5 h 20.29 0.133 - 3.20 7 3 2h-35 0-0h3 - 2.7h 6 8 23.10 0.058_ - 2.28 5 5 21.85 0.080 - 2 091 7 )4 25 091 O .023 "' 2.89 6 5 2h.66 0.03h - 2.66 7 5 27.h7 0.013 - 2.28 6 6 26.22 0.020 2.h6 7 6 29.03 0.008 - 2 .28 ‘ 7 7 30.59 0 .005 - J -. : Prob (q > 2m) is less than 1%. 52 TABLE VII OPTIMUM CHIEG§~OUT RULES FOR FRIDAY AFTER 6 P.M. (X.= 2.55) P 8* 3 ‘A h; A T.V.C. OptimumE a m . k C Lq Prof(q > 2m) (c/min.) Rule 6.32 7 0 19.67 6.880 1h.18 33.h9 5.h2 6 1 18.h2 7.1h8 18.17 32.79 h.51 5 2 17.17 7.210 27.86 31.66 3.61 h 3 15.92 7.323 31.6h 30.63 (2) 5.53 7 1 21.23 1.7h3 1.78 2h.73 h-Yh 6 2 19.98 1.862 2.83 23.72 3.95 5 3 18.73 2.010 h.16 22.77 (3) 3.16 h h l7.h8 2.173 7.07 21.8h (l) h.92 7 2 22.79 0.727 - 2h.25 h.21 6 3 21.58 0.799 * 23.15 3.88 5 h 20.29 0.852 - - 22.00 hth 7 3 2h-35 0-3h7 * 25-0h 3.79 6 h 23.10 OohOh 23.91 3.16 5 5 21.85 0.h77 22.80 8.02 7 h 25.91 0.185 3.h5 6 5 2h.66 0.228 3-69 7 5 27-h7 0-107 ‘ 3016 6 6 26.22 0.135 "‘ 3.80 7 6 29.03 0.063 - 3.16 7 7 30.59 0.0h0 - - : Prob(q .> 2m) is less than 1%. TABLE VIII OPTIMUM CHECK-OUT RULES FOR SATURDAY (i = 2.1114) 7 fi 1* - T.v.c. Optimum“ E, m k C Lq Prof(q > 2m) (xi/min.) Rule 6.03 7 0 19.67 3.870 6.91 32.hh 5.17 6 l 18.h2 h.060 10.89 31.82 11.31 5 2 17.17 b.2633 13.30 31.21; 3-h6 h 3 15.92 h-hlé 18.67 30oh9 (2) 5.28 7 l 21.23 1.219 - 25.35 11.52 6 2 19 .98 1.305 1.16 211 .29 3-77 5 3 18.73 1.1139 1.97 23.149 3.01 h 11 17.118 1.562 8.16 22.63 (1),(3) 11.69 7 2 22 .79 0 .517 2h .50 1.02 6 3 21 .51. 0 .587 - 23 .118 3.31 5 h 20.29 0.625 - 22.35 11.22 7 3 211 .35 0 .2511 - 25 .19 3 .62 6 11 23 .10 0 .301; - 211 .10 3.01 5 5 21.85 0.360 - 23.03 308).} 7 )4 25.91 0.138 " 3.29 6 5 2h.66 0.171 - 3 -52 7 S 27 .117 0 .078 3.01 6 6 26.22 0.101 3.25 7 6 29.03 0.0h7 - 3 .01 7 7 30 059 O 0028 " - : Prob(q >»2m) is less than 1%. Sh From the foregoing tables, the optimum check-out rules for each period of the week can.be determined. However, even if the management is unable to specify parameters necessary for optimization, these tables would still provide useful informatidn because they have narrowed down a range of selection for optimal rules. As mentioned previously, rules considered here are limited to those which satisfy one of the conditions for the convergence of the stationary-prObability distribution. This condition states that p >-m. Hence, the rules in the table may be considered to have passed the initial screening. In most cases, a checkéout rule with a higher'operating cost would tend to be associated with a better grade of service as indicated by'a shorter expected length of queue and smaller Pron(q > 2m). However, there are some exceptions to this tendency. One may note that a number of check-out rules in the foregoing tables illustrates this point. For instance, on Saturday, the check—out rule (m = 5, k = 3) is to be preferred to the rule (m = 7, k = 0), because the application of the former would bring about the better service with smaller expenses as compared to the latter. Hence a rule such as (m a 7, k = O) has to be excluded from further consideration. The jOb can be always done more efficiently and economically by adopting the rule (m a 5, k = 3) in place of the rule (m - 7, k a 0). 'It may be worth noting that for given average arrival rate and cost function, the optimal rule (m,k) is not highly sensitive to the choice of the criterion Of optimality (at least not for the three criteria used here). This can be seen.in the following table. 55 TABLE IX OPTIMJM MILES FOR DIFFERENT AVERAGE ARRIVAL RATE AND DIFFERENT CRITERIA 0F OPTIMALITY ___. fi v—f \1 0.91 1.53 1.85 2.111. 2.55 Criter10h\mk mk mk mk mk (l) 22 3'3 33 1111 1411 (2) 21 32 32 143 143 (3) 22 111 112 hh 53 Before concluding the discussion on optimum checkvout rules, a question may be raised as to what effect the sampling fluctuations of estimates of average arrival rate and average service rate would have on determination of optimal check‘out rules. For this purpose, some results obtained in the second half of Chapter III will be used. The first item to be considered is the variation in 5 as estimates of A and u fluctuate. This is done by obtaining upper and lower limits of 5 from confidence limits of X and a. Letx*, and 1* be the upper and lower confidence limits, respectiiIely, of f for a given size of confidence coefficient; similarly 9* and 11* are the upper and lower limits of {1.3 awould * A then vary between its upper limit 25* and lower limit If: . The effect of variations ini and";~ on optimum check-rule can be studied by obtaining the optimum rules corresponding to those limits. 3Since 9, is calculated by the formula 11:: (m-k)“ " mi, (1;. 11') p is obtained by inserting upper confidence limits ofm [.11 and 112 into (11.11:) and 11* is obtained by inserting lower confidence limits of 111 and 112 into the equation. 56 In Table X, optimum rules for Saturday based on the upper and lower limits of ‘5‘, which in turn were obtained from the 90 percent confidence limits of X and a, as presented in Table III, page 35, are compared to those given in Table VIII of this chapter. TABLE X EFFECT OF VARIATION IN ESTIMATES OF A AND 31 ON OPTIMUM CHECK-OUT RULES A k ‘_A_‘ A —V— fi‘v j *— Method (1) Method (2) Method (3) m k m k ‘ m k Upper limit of 8 5 5 11 11 5 11 3 h h 1. 3 h 1. Lower limit 01.13 h 11 3 3 h 3 ‘A A _ This example suggests that selection of optimal rules by the methods proposed in this study is fortunately not very sensitive to variation in estimates of A and 11 due to sampling error. CHAPTER V SUMMARY OF RESULTS AND SUGGESTIONS FOR FURTHER STUDY The applications of queuing theory have been many and varied. They range from the design of airports to the scheduling of patients in clinics. Despite the fact that the check-out service at super markets appears to have all the necessary features that make up a typical queuing problem, as far as the author is aware, no attempt has been made to answer some important questions in connection with the efficient operation of check-out service more rigorously. For example, how many check-out stands should there be in operation to handle the customers ready for check-tout at any given time? Or, given that six employees are available, is it betterlto have six check-out stands operating or only three check-out stands with one package boy each? This thesis is chiefly concerned with procedures that can-be used to answer these questions in quantitative terms and in a logical manner. The procedures proposed here were applied to data obtained at one large super market in the Detroit area. An application of the procedures essentially involves a balancing of the cost incurred by providing a certain amount of check-out facili- ties (the cost mainly comprises the wages of checkers and package boys) for a given time period against the cost of losing customers in the 58 future because of inferior service standards. The first type of cost is essentially a function 0f the number of checkers and the number of package boys attending check-out stands during that time period. The second type of cost depends on the following three factors: 1) the number of checkers and the number of package boys, 2) the number of customers arriving at the check-out area during the time period, and 3) the rate at which each arriving customer is served. The management can not regulate the flow of customers to suit its available labor and facilities; however, it can decide on the amount of labor and facility requirements to meet a given flow of customers. Hence, if some func- tional relationships between the sum of these two coats and the three factors mentioned above can be specified, it will then be possible to determine the cost for given values of the factors. It was shown in this thesis that such functional relationships could be specified in a logical manner. The last two factors which comprise a main portion of the second type of cost are not known in advance. In order to get around this difficulty the probability distributions of these two quantities are estimated. From these stochastic quantities, an expected cost can be calculated by means of the theory of queues. The specific procedures. followed in this thesis are briefly described in the following. First, a queuing system which is inherent in any check-out Opera- tion at super markets was characterized in the following manner: Input: time intervals between two consecutive arrivals are independently and identically distributed by a negative eaqaonential distribution. 59 Service mechanism: number of check-out counters available is finite; time required to serve one customer at a counter has one of two different probability distributions depending on whether a package boy is at the counter or not; both distribu- tions are assumed to be negative exponential distributions . Qieue discipline: "first come, first served." The system can be in any of possible "states," specified by the number of customers in the queue, the number of customers being served, . or the total nunber of customers in the system. From the probabilistic characterizations of input and service mechanisms, the probabilities that the system is in each of the possible states independently of time were calculated. These probabilities are called steady state probabilities. Next the costs associated with the system in each state were esti- mated. From the steady state probabilities and their associated costs, the expected costs could be readily computed. The steady state probabilities are valid only when the average arrival rate and the average service rate can reasonably be considered stable. It is not unrealistic to assume that the latter will remain constant so long as there is no- basic change in the service mechanism. On the other hand, the average arrival rate varies from day to day, if not from hour to hour. It is known to be closely related to sales per unit of time. In order to apply the procedures developed in this study to the check-out operation at a super market in Detroit, sales records of the store were examined; ‘and the weds was divided into five periods so that within each period the assumption of stable average arrival rate would be more tenable. 60 Optimum check-out rules for each of the five periods were obtained separately and were shown in tabular forms. From the table, the effect of alternative optimal criteria on the rules can be readily seen. It should be noted that the thesis is .chiefly concerned with derivation of procedures in obtaining certain check-out rules which satisfy given optimum criteria. As such, institutional and managerial arrangements necessary in adopting the optimal check-out rules to the actual check-out operation were considered outside the scope of this thesis. Prior to calculating expected costs of the check-out operation, some statistical analyses were made of customer arrivals and service times in order to determine how well the assumptions of Poisson arrival and exponential service time will approximate the actual situation. The chirsquare test of goodness-of-fit was used. The test results indicated that in general the number of arriving customers per minute follows closely a Poisson distribution. The negative exponential distribution, however, did not seem to give the best fit to observations on service time. Since the empirically derived distribution was skewed to the left, another member of the gamma function family would probably have given a better fit.‘ Nevertheless, the steady state probabilities were calculated, based on this exponential service time hypothesis, because the hypothesis. renders the mathematics manageable . In the theoretical study of a queuing problem, the average arrival rate and the average service rate are treated as thOugh they were known a p_r_'_i_._9_r_'_i_. In'an applied problem, they have to be estimated by some statistical procedure; hence, they are subject to sampling fluctuations. 61 Since a choice of an Optimum check-out rule depends on the estimates of these quantities, it is natural to examine the sensitivity of the method of choosing optimal check-out rules to changes in the estimated average arrival rates and the estimeted average service rate. This was done by first obtaining the sampling distributions of these estimates and then calculating their confidence limits. From these limits, a range of variation in check-out rules was examined. This range was found to be very small when the procedures were applied to the data obtained at the store in Detroit. Although use of such a queuing model enables a research worker to analyze a given problem without going to the expense of actually dupli— cating the situation, there are several points that ought to be further examined for the model to be more useful. The calculated state probability distribution pm, for n = O, l, ..., can be checked for its accuracy by observing the frequency of the formation of queues of all possible lengths. One could operate the check-out stands for a period with fixed number of checkers and package boys, and observe the mmber of customers waiting for service at the end of every interval, say one minute, during the period. Experiment such as this is conceptually possible; however, the resource available to the author did not permit carrying out the experiment at this time. Little is known about the coefficient of the penalty function. Probably some ideas can be obtained if one were to ask the customer in the waiting line how much he considers his time is worth. Accurate information about this coefficient is much needed in obtaining the valid solution of a queuing problem such as this. It might be desirable to 62 consider enlisting the help of a psychologist in designing an experiment for such a purpose. - The hypothesis of exponential service time was used throughout this study, because of its mathematical simplicity. An alternative hypothesis is that of constant service time. A queuing model based on this hypothesis is briefly described below. The hypotheses with respect to input and queue discipline are the same as before. Let m : the number of check-out stands to be put in operation. k : the nunber of package boys. 1 : the average number of customers arriving per fixed time interval. In particular, the tim interval is set equal to the service timc. It should be noted that when A is measured in this manner, it will depend on the controll- able variables m and k because they affect the length of average service time. Each of the following set of equations relates the state probabili- ity at the beginning and end of the interval which is equal to service time: P(n) = P(n+m)e + P(n+m-1)7\e )‘+ ....+. P(m+1) 737171 e x m A n _ A ‘ +[ 2 P(i) nl ]e forn= o, 1,.... (5.1) :0 ~ ' Equation (5.1) states that the probability that there are n customers in the system at the end of the fixed interval is equal to the sum of the probabilities of the following n+1 contingencies: 1) there are n+m customers at the beginning 'of the interval and no customer comes during the interval............n) there are m+1 customers at the beginning of the interval and exactly n-l customers arrive during the interval, n+1) 63 there are less than 1111-1 people at the beginning of the interval but n people arrive during ’the interval, so that at the end there are still 11 customers waiting. It is not easy to solve this infinite set of equations.1 If the solution is obtainable at a reasonable cost, the state probability distribution may be calculated for each of the feasible average service times. The expected cost corresponding to each service time can also be calculated as in the model with exponential service time. If an assumption in regard to the service mechanism is such that an analytical approach to the queuing problem becomes so complex that it is impossible to obtain a solution, a simulated sampling approach may be adopted. Briefly, the procedure to be followed is this. Observations on customer arrivals and service times are examined and parameters of the theoretical distributions which are most likely to give the best fitto the data are estimated. By means of a table of random numbers, one can construct a scheme such that the drawing of a random number will be from the population which has a known probability distribution. This is done for both customer arrivals and service times, using their respective estimated probability distributions. For instance, a Inimber is drawn at random from the table of random numbers at the end of every fixed interval and if the mimber drawn falls between 0 and 9000 it is interpreted that no customer has arrived during that period; if it is between 9001 and 9999, then one customer h 1Everett (1953) suggested an iterative procedure to obtain an approximate solution. # k ~’--'~‘~~:'4- ‘-—'M~ ~ -~ -.’—\r ....-. 61: has arrived. In order to generate a sequence of random service times from a known distribution, all the four-digit numbers may be grouped according to the estimated service time distribution, and a certain service time is assigned to each group of numbers: Repeated drawings of numbers from the table will then give a sequence of service times ‘with the desired probability distribution. Next, the first random service time is assigned to the first customer; the second random service time to the second customer and so on. In this way, the congestion situation at the check-out area can be simulated. If such an experiment is carried out on a high-speed computer, enough data can be Obtained to construct a frequency distribution of the system in each of all the possible states in a very short period of time. The expected cost can.be calculated based on this frequency distribution. The process is repeated for different values of the parameters of the arrival distribution and service time distribution 'until that expected cost which meets a given optimal criterion is found. The above procedure is for the case of one service channel. If the prOblem involves more than one service channel and if each of them has a different prObability distribution, then as many sets of service times as the number of service channels have to be drawn. A realistic rule has to be set up to determine a manner in which a random service time is to be assigned to each of the incoming customers, and the congestion situation can.be simulated as before. In the light of recent developments of high-speed computers, there is much to be recommended for adopting the simulated sampling approach 65 to a queuing problem. The advantageof this approach is that there are more flexibilities in regard to the assumptions about input and service mechanism. It is quite likely that the future study of queuing problems by the Monte Carlo method will yield many fruitful reSults . 66 LITERATURE CITED Arrow, K., S. Harlin and H. Scarf, (1958), Studies in the Mathematical Theo of Inventory and Production, Stanford University Press, Sta—riord. Brockmeyer, E., H. Halstrom and A. Jensen, (19118), The Life and 1119er5 of A. K. Erlanjg, Copenhagen. Cox, 0. B., A. Glockstein and J. H. Greene, (1958), "Application of Qieuing Theory in Determining Livestock Unloading Facilities," Journal of Farm Economics, XL: 1011-116. ‘ Edie, L. C. (1955), "Traffic Delays at Toll Booths," Journal of Operations Research Society of America, Vol. 2. Everett, J. (1953), "State Probabilities in Congestion Problems Character- ized by Constant Holding Times ," Operations Research Society of America, November 1953, 1, 259-62. ‘ Feller, W., (1950), An Introduction to Probability Theory and its App_l_i.- cations, John Wiley and Sons, Inc. , New York Flagle, C. D., (1956), "Qieuing Theory and Cost Concepts Applied to a Problem in Inventory Control," Qpeyation Research for Management, Vol. II, Baltimore, Johns Hopkins Press, 160-177. 7 Fry, T. C. (1928), ProbabilitLani Its Engineering Use, New York: van Nostrand. Holley, Julian L. (1951;), "Waiting Line Subject to Priorities ," Journal oiOperatiqrys‘ Reseaych Society of Ameriyg, 2, 3111-3113. Kendall, D. G. (1953) , "Stochastic Processes Occurring in the Theory of Queues and Their Analysis by the Method of the Imbedded Markov Chair," Annals of MathematicalyStatistics, 211: 338-3511. Kendall, M. 0., (1951), "Some Problems in the Theory of Queues," Journal of the Royal Statistical Society, series B. Vol. XIII, 151-171. Lindley, D. V., (1952), "The Theory of Qieues with a Single Server," Proceedings of the Cambridge Philosophical Society, 11,8: 277-289. Marshall, B. 0. (19511), "Queuing Theory," Operations Research for Management, Vol. 1, Baltimore,Johns Hopkins Press, 1314. -1L18. 67 McClosky and Cappinger, (1956), gpcerationsjesearch for Management, VOl- II, Johns Hopkins Press. Molina, E. 6., (1927), "Application of the Theory of Probability to Tel hone Trunking Business," Bell fistem Technical Journal, Vol. 6, 614491;. fi' , Molina, E. 0., Poisson’s wonential Binomial Limit, Table I. New York: van Nostrand mpany. Salvosa, L. R., (1930), Tables of Pearson's me III Functions, Edwards Brothers, Inc. , Ann Arbor. Satty, ‘1'. L., (1957), "Resume of Useful Formulas in Qieuing Theory," Operation Research Society 01: America, Vol. 5, No. 2. APPENDICES 68 APPENDIX A STATE PRQBABILITY DISTRIBUTION The techniques of deriving state probability distributions have been.presented by'a number of authors1 in a highly technical and often abbreviated form. In this appendix, the assumptions and definitions upon which the derivation of state prObability distributions will proceed are set forth in detail and the derivation is presented step by step in order to facilitate an understanding of the logic behind these techniques. First of all, hypotheses about the service mechanism and input process have to be specified. Service time distribution: Let the service time be defined as the time which elapses while a particular customer is being served. The hypothesis about the service time is as follows: A check-out service It has started -pt = e (o < te< O ) Pm": extends beyond time t at time o (A.1) .For an interpretation of the parameter uq‘we take the expected value of t. Since the equation (A.1) defines the cumulative distribution function (c.d.f.) of service time in terms of its upper tail, we have to first obtain.the c.d.f. in its usual form in order to calculate mean of the random variate t. 1See Feller (1950), Kendall (1951) and Lindley (1952). 69 F(T'_s_ t) a 1 - e-pt the c.d.f. of t in the usual form. '3':- = “e Int the density function Hence 'E(t) = [éftpe‘m’ dt = (A.2) ‘Fh—J Since E(t) is the mean service time, p, can be considered as the average number of customers served per unit time. It is called the mean service rate. ' From (A.1), the conditional probability that a check-out service is completed between t and t + A t given that the service was being rendered at time t can be calculated. Pro 15 [Check-out service ends It did not end] ° between t and t + A t before time t Prob [Check-out service does not terminate before t,] a fbutendsbetweentandt+At¢ , Prob,[Check-out service did not end before t] e-ut -‘e -p(t +At) .‘M a l_e-pot . 1- [hummer— - Leg—2.... 1 = not + 0(At) (L3) The equation (A.3) is interpreted as follows: If at time t a! check-out stand is occupied, then the probability that the stand would terminate its operation during (t, t + A t) is pm; plus terms which approach zero faster than At. 70 Arrival Distribution: The hypothesis adopted throughout this analysis is that the customer arrivals consist of a Poisson process, i.e., the number of arrivals in time ‘1: being a Poisson variable with mean At, say. This implies that the time interval between two consecutive arrivals has the negative expond'ltial distribution.2 This time interval is often referred to as customer "idle" time. Prob, [Every oustomer is idle.at time o] ' and still is idle at time t =- Prob.[No customer coming in during that period ] -= e " H” (Al) Using (A.h), we can calculate the cenditional probability of exactly one arrival between (t, t 4- At) given that there is no arrival during (o,t). Prob. [Exactly one arrival No arrival during (t, t Hit) between (o,t) . l, _ ,3 -Mt - IA 1: + 0(‘At)' (A-S) A is the mean arrival rate. After the incoming traffic and the service mechanism have been characterized in terms of probability as above (Poisson arrival and exponential service time), the next thing to specify is the queue discipline. It is assumed that a check-out system follows the so—called 2A proof of this statement can be found in Feller ( 1950), pp. Bob-367. . 71 strict queue discipline. Since check-out stands, in the current study, are classified into two groups depending on whether a package boy is assisting a checker or not, it is necessary to adopt a rule in order to decide how each arriving customer moves into a check-out lane. Let p1 and “2 denote respectively the average service rate of one check-out stand that is operated by a checker alone and by a package boy and a checker together. Suppose there are m-rk check-out stands with the average service rate [.11 and k check-out stands with the average service rate“ 2. The rule is that LEI-15- fraction of the incoming customers "will go through the counters with p1 average service rate and the remaining fraction (1;?) will be served by the counters with pa average service rate. In other words, the assignment of each customer to a service channel is decided by tossing a coin with a ratio 235- : 3;; . This completes the specification of the system. With these assumptions, one can proceed to write equations which represent the detailed balancing of transitions between states for a stationary steady state. Two contingencies have to be recognized. In the first situation, the number of customers (11) present in the system is less than the number of check-out stands (m) which are in operation. The second situation is that the former is at least as great as the latter. Adopting the terminology of the theory of stochastic process, we shall say that the system is in state 151,, at time t when there are n customers in the check-out system at that time. The system will be in state En at time t + [it only under the following conditions: 72 1. The system is in En at time t and during (t, t L at) no customer arrives or departs. 2. The system is in ELI-1.1 at time t and exactly one customer comes 'in during (t, t Hit). 3. The system is in En+l at time t, and exactly one customer leaves the system. LL. During (t, t inst), two or more customers arrive or depart. It is assumed that the probability-of the last contingency becomes insignificant as n t —-> 0. Hence, it was not considered in calculation of the state probabilities. Since the first three situations are nutually exclusive, the probabilities of these contingencies are additive. Let Pn(t) denote the probability that the system is in state En at time t. First consider the situation :1 5 m. There the probability of exactly n customers in the system at time t + at is as follows: Pn(t:-At)=[1 -Mlt - (ll-(£119) u, + fik— I12)” 1Pn(t)+Mt Pn..l(t) . (“$241!ka, + irfiills [.12)At] and“) + 0(At). (A.6) From left to right, each term on the right hand side of (A.6) corres— ponds to the probability of a contingency in the order listed in the previous page. When the term Pn(t) is transposed to the left hand side of (A.6) and the resulting expression is divided byA t, we have the derivative of Pn( t) with respect to t by definition upon taking a limit of the ratio as At --> O. 73 To simplify notations, let (“9&4 ” £32 m (A.6) Then this derivative can be written as follows: d? t 3: ) - -( Mm“) Pn(t) 4: APn_1(t) t (n+l)uPn+1(t) (A.7) for n g m This is the same set of differential equations for the case where all the service channels have equivalent service capacities. Since the state probability Pn_1(t) is undefined for n-l < o, the differential equation (A.7) is valid only for m 3: n > 1. For n a 0, an equation similar to (A.6) has to be formulated. Po(t +At) = (l -).,-_,t) Po(t) *uAtPfit) + 0 (At) (A.8) The above relation says that the probability of no customer in the system at time .t + At is the sum of two independent probabilities: l) probability of no customer in the system at time t and no arrival during (t, t + At), and 2) probability of exactly one customer in the system at time t and he will leave the system during (t, t 4» At). From this equation, the derivative 93.3% is obtained in a similar manner as in (A.7). 9.13.3?! .. xpo(t) + pP1(t) (A.9) Theoretically transient solutions, i.e., the solutions which depend on the variate t, can be obtained by first deriving a partial differential 7h eqlation for the generating function of state probability distribution.:3 The mathematics, however, becomes rather involved. In the current study it is assumed that a statistical equilibrium exists i.e., lim Pn(t) = Pu“. exists , and only the so—called steady ,state solution ixbtoained from (As?) and (A.9). This can be done by setting 93%;). :3 o and 923%)- = o and solving the following set of simultanecms equations by recursionufor all relevant Pn's in terms of P0: 1P0 3 “P1 (N!- ann == M’n + (n + 1) P'Pni-l O < n s m (L10) :- The result of solving these relations relating the state probabilities is n- ‘ Pn== 319—8—- where o= l- (A.11) n‘ ’ I p The second contingency that needs to be considered is the situation in which there are more customers than the check-Pout stands in operation. The basic system of differential equations for n g m is derived from Pn(t + At) = (l - Mt - th)Pn(t) +Mt Pn..1(t) + m Mt Pm1(t)' + 0 (At) (A.12) The interpretation of the above equation is similar to that ,of (A.6) and (A.8). The differential equations are as follows: 3The partial differential equation for the generating function is given in Feller (1950), p. 396. 4Supression of the variable t indicates that the state probability Pn is independent of time t. 75' dIan“) dt = -( X + mu) Pn(t) +APn_1(t) man+l(t-) (A.13) Again a steady state solution is obtained by setting 9:39 = o. The following set of simultaneous equations are then solved by recursion. (M NIH.) Pn = )‘Pn-l + man+l (Alt) The solution is n a L,forngm>o. (1)-15) n-m ml m Pn From (A .11) and (A.15), the probability that the system is in any state except E0 can be calculated in terms of P0. In order to determine Po, we make use of the condition 5 Pn = 1 By means of (A.ll) and (A.15), this condition can be more explicitly written as follows: m-l n m . n “Po” §r*'% 3 9‘5] n-O n==m m then "F2 n m-l (A.16) P P m P31 =- r130 H + T1337" 7;") (A.1l), (A.15) and (A.l6),together completely specify the distribution of a statistically steady state. It should be noted from (A.15) that the series ngm £3 coverges only when p< m. This can be seen from the following argument:~ Divide both sides of (A.15) by P0 and sum it over the index n from m to '. I m o m .2 :2 a '2? 21 (Eng) (A.17) nan: Po n-m The right hand side of (Al?) is a geometric series, and it converges m f to a limit (Ii-17‘6Hpe) p < m was used as one of the criteria in eliminating unsatisfactory only when p < m. This convergence condition checkdout rules as explained 'in Chapter IV. When the state probability distributions have been obtained, one can proceed to determine means of a number of quantities which are of interest in a queuing problem as well as explicit expressions for derived probabilities. Quantities of special interest in the current study are the mean number of customers in queue and the probability that the rmmber of people in waiting line exceeds a certain pre— specified number. Let L be the mean queue length. ‘1 L'= E (n-m) P q n==m+1 n , 22212121. p0 nmlmmm. .911. 2. .2'2 =P°mtm [li-Zm +3(m)+ ] It can be seen that the quantity within the brackets converges ‘ 2 to a limit (#113) for p m, the quantity mm is defined to be the length of queue. Let n-m = q. q takes values from O, l,...,q*, The probability distribution of the random variate q is given by sub- stituting q for men in (A.15). II is: n: "U 0 5r -v- 5‘ e:- mi-q +1 2 P {14474-11 + ..... a ..o 3.1.... mt mq +1 ] m+q*tl [I a 1;" 5&1 F 3": 78 APPENDIX B THE DISTRIBUTION FUNCTION OF ESTDiATED AVERAGE SERVICE TIME Let the joint density of n observations on service times be n . —p 2‘. ti h(t1, t,,...,tn) =- tine i=1 (13.1) and let § denote the maxirnm likelihood estimate of average service time where One way to obtain the distribution of g is to apply the following transformation to all the ti's in the density (B.l): w1 = l o o ...0 t1 wz l l o ...0 t2 . l l 1 o..o .. (3.2) Wn l ' " l tn Then from the resulting transformed function, all the We except wn are integrated out. Note that wn =- n'é . From the formula (3.2), t's can be expressed in terms of w's explicitly. 79 t1\ = l o o w1\ \ t2 \ -1 l O o 0 W2 \ n l i o -l l o o \ (B.3) ’ / . o ' tn/ 0 ~l l wn The Jacobian of the transformation in this case is 5131 (NJ 1- 1 Hence we obtain the new density function of We as follows: 6 131 n w h(t1,...,tn) ‘62}: + =p. e'“ n (3.1;) where t's are expressed in terms of w's by the relation (B .3). Next step is-to find the appropriate region of integration for wl, ...,wn..1. From the first two equations in the system (B .3) and o' 5 t1 <~ for all i's, we see that or< w1 ng. Similarly from the lst, 2nd and 13rd- equations w,2 can be seen to take a value between 0 and w3, etc., and finally 0 < wn'g y. Hence the cunnlative distribution of wn is given by W w 2 - Prob (wn3 1% l e 131 l l t (8.7) The equation (B .7) is the desired distribution function. It is an incomplete gamma function and has the form of a Poisson distribution with the parameter my. ' ' " "air“! ‘. {\IU", 26 .._,-._V- : 3-x.‘ ‘J- W <2 I-e-o t u a 1 ~ I...