AN EXPERIMENTAL EVALUATION OF QUEUEING THEORY by. David Goyder B. Com,, University of B r i t i s h Columbia, 1969 A Thesis Submitted i n P a r t i a l Fulfilment of The Requirements for the Degree of Master of Business Administration i n the Faculty of Commerce and Business Administration We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF A p r i l , BRITISH COLUMBIA 1970 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced deg ree a t t he U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r ag ree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the Head o f my Depar tment o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r . f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f Commerce and Business Administration The U n i v e r s i t y o f B r i t i s h Co l umb i a V a n c o u v e r 8, Canada • Date 30 A p r i l , 1970 ABSTRACT This thesis examines methods for predicting queue length of single server queues i n order to evaluate how the p r a c t i -tioner may achieve greatest accuracy. Because accuracy i s dependent on the correct.estimation of the rate parameters of the population d i s t r i b u t i o n s and the choice of the appro-p r i a t e method of p r e d i c t i o n , the e f f e c t s of errors i n both of these are examined. A computer simulation model written i n GPSS/360 i s used to create a r e a l world from which data i s drawn and where long run performance represents the correct s o l u t i o n . For four values of rho nine simulations are run, each with a unique combination of i n t e r - a r r i v a l and service time d i s t r i b u t i o n s . In each of the 36 runs 10,000 a r r i v a l s are generated from which two samples of s i z e 36 and 100 are taken and from which the generated queue s t a t i s t i c s form the standard. A s t a t i s t i c a l analysis i s used to detect samples taken from exponential d i s t r i b u t i o n s . The lack of a suitable t e s t for small samples led to the development of a t e s t based on the c o r r e l a t i o n c o e f f i c i e n t of the sample times and pre-computed standard data. Estimates for queue length are found with c l a s s i c a l queueing formulae and solution methods suggested by Marshall These predictions are done without p r i o r knowledge of rate parameters and queue type which are estimated from the samples. Then the estimated solutions are compared to the r e a l world solut i o n derived from the simulation. Estimation error for each method i s measured and conclusions are drawn as to t h e i r accuracy i n predicting queue length. It i s found that accurate queue length estimation i s possible using methods that can be applied without a great deal of p r i o r mathematical knowledge. The c l a s s i c a l formulae are accurate only when applied to queues with exponential i n t e r - a r r i v a l times and are found to over-estimate when applied to other queue types. The Increasing F a i l u r e Rate (IFR) bounds on queue length provide a s a t i s f a c -tory method of estimation for the general class of queues e i i i TABLE OF CONTENTS CHAPTER PAGE X INTRODUCTION . . . . . . . a . . . . . . . . . . . . . * * . . . . . . . . . 1 Statement of contents 1 Purpose of S t u d y . . o « . . . . . . o . . . . . . . . . . . . . » • 1 The Standard and Data Source 3 Method of Analysis«..•»..»....*o.. ........ 6 II STATISTICAL ANALYSIS OF DATA.............. 7 Consideration i n Choosing the Test........ 8 Tests based on L i f e Testing., 9 An Analytic Exponential t e s t . . . . . . . . . . . . . . 11 a. Correlation C o e f f i c i e n t 14 b. A Regression L i n e . . . . . . . . . . . . . . . . . . 15 c. A t - t e s t f o r the Ordinate... 15 Chi-Squared te s t for goodness of F i t . 16 Results of Applying Tests to the Sample Data. 17 Summary............. 26 III METHODS FOR THE ANALYSIS OF QUEUES.... 29 Assumptions.................... .....29 M/M/l Queue.......... 29 M/G/l Queue 30 G/G/1,G/M/1 Queue.... 30 G/G/l Bounds 31 TABLE OF CONTENTS (cont'd) CHAPTER PAGE III Computation of Lower Bound............. 33 IFR/G/1, DFR/G/1 Queues................ 34 Expected Wait and Queue Length......... 35 IV QUEUE ANALYSIS o o e o f t o o o * » o o i > * o o e » o o e e o o o o o 36 Evaluation of Sampling Er r o r s . . . . . . . . . . 37 Evaluation of Calculation Methods with Accurately Estimated Parameters 0..... 46 Results from Accurate Data..„.......... 47 Results from Inaccurate Data..........» 53 V AN APPLICATION AND CONCLUSION............ 58 CoriC llJLS XOI1S o a « » o o o o « o » * o o o a 6 4 0 » « o « 6 a » « « 61 BIBLIOGRAPHY© e o i > o * « » * e « » * e * 6 « * * « o * « e o o o 6 e o « » f t « 6 i > o « 63 APPENDIX I Increasing and Decreasing F a i l u r e Rate 64 II The Correlation C o e f f i c i e n t Test 66 V LIST OP TABLES TABLE PAGE I Frequency D i s t r i b u t i o n of Correlation C o e f f i c i e n t for Exponential and General Sample Di s t r i b u t i o n s ......................... 18 I i Type I and II Errors from Testing for Exponentials with Correlation C o e f f i c i e n t ... 0 20 III Frequency D i s t r i b u t i o n of C o e f f i c i e n t of Varia t i o n for Exponential and General Sai&ple Di s t r i b u t i o n s . . . . . . . . c . o . a < . a s . . . . . . . a 22 IV Type I and II Errors from Testing for Exponential with C o e f f i c i e n t of Variation 0 0 a a 23 V Type I and II Errors from t - t e s t that the Ordinate of a F i t t e d Regression Line Equals ZGITO 0 6 « o « 6 » * 6 e o e » * e « 6 o e « « * « e * e o o o o e « o o o e e * e « e 25 VI Type I and II Errors from Chi-Square Test of Rate D i s t r i b u t i o n of Sample Data ....... 27 VII Percent Error of Rho, Lamda, and Mu (Sample Size 36) 41 VIII Percent Error of Rho, Lamda, and Mu (Sample Size 100) .". 42 IX Sampling Errors for Rho, Lamda, and Mu as a Percent of Intended Simulated Values ......... 44 X Summary of Queue S t a t i s t i c s from Accurate Data . 48 XI Summary of Queue S t a t i s t i c s from Inaccurate Data (Sample Size 36) 54 LIST OF TABLES (cont.d) v i TABLE PAGE XII Summary of Queue S t a t i s t i c s from Inaccurate XIII Pre-computed Ordinate Values for the Correlation C o e f f i c i e n t Test. 0••.•«.••.•••»•» 69 V1X LIST OF FIGURES FIGURE PAGE 1 Di s t r i b u t i o n s used i n the Simulation „ o o . « 5 2 Plots of two D i s t r i b u t i o n s o o 0 s o o « o » 9 o o » o » o 13 3 E f f e c t i v e Direction of Change i n Rho for Changes i n Lamda and Mu. ••••...»•*<.••••. 39 4 D i s t r i b u t i o n of Percent Error i n Rho by 5 Comparison of Percent Error between Sample v i i i ACKNOWLEDGEMENT -I would l i k e to express my appreciation to Professor L» L. George for his guidance with the mathematical portions of t h i s t h e s i s . I am p a r t i c u l a r l y indebted to Professor H. C. Wilkinson for his d i r e c t i o n i n the preparation of t h i s paper and for conducting the simulation on which the work i s based. ix N O T A T I O N T N = time between n-th and (n+l)-th a r r i v a l , T N ~ A(t) , E [ T N ] = 1/X S n = service time of n-th customer, S n~ G(t), E t s n ^ = -^/^ u n = s n - Tn> u n ~ K<*> P = X/y (n) v ^ = n-th moment about o r i g i n of random variable with d i s t r i b u t i o n F. cx§ = variance of a random variable with d i s t r i b u t i o n F 2 °f~ f / ( v f ) 2 ' where c^ i s the c o e f f i c i e n t of v a r i a t i o n FC(t) = 1 - F(t) for any d i s t r i b u t i o n F CHAPTER I INTRODUCTION Statement of Contents This thesis w i l l present an analysis of single server queues to e s t a b l i s h how the p r a c t i t i o n e r might best solve his queueing problems 0 The approach i s to examine raw data of i n t e r - a r r i v a l and service times sampled from a simulated r e a l world? to calcul a t e queue s t a t i s t i c s e and to compare these to the long run performance of the simulation model. This simulation model, i n e f f e c t , provides the r e a l world solution with which we can compare our calculated predictions of queue length and waiting time. Some s t a t i s t i c a l procedures intended to aid the p r a c t i -tioner i n a r r i v i n g at his assumption of queue type w i l l be examined for t h e i r a p p l i c a b i l i t y , ease of use and accuracy. Purpose of Study Queueing theory has developed considerably over the past twenty years through the use of sophisticated mathematics. Perhaps the most widely applied portion of queueing theory i s derived from the c l a s s i c a l M/M/l s i t u a t i o n where the Poisson assumption makes the derivation of formulae for queue length and waiting times comparatively simple. The solut i o n of 2 non- Poisson queues i s considerably more d i f f i c u l t and has not produced such e a s i l y calculable formulae. Indeed the solut i o n to general single-server queues i s not expressed s o l e l y i n terms of the moments of the a r r i v a l and service d i s t r i b u t i o n but require moments of the i d l e time d i s t r i b u -t i o n which are hard to find.-*-Many queueing situations found i n industry (the c l a s s i c being the supermarket check-out problem) are assumed to be of the M/M/. type since the Poisson process i s found so often i n nature and the type of f a c i l i t y being analyzed often displays the c h a r a c t e r i s t i c s on which the Poisson i s founded. This assumption may be f a l s e . However with the added convenience i n applying the Poisson queueing formulae and i n the absence of a s i m i l a r l y convenient general set of formulae, the Poisson assumption i s made almost i n d i s c r i m i n a t e l y . This i s c e r t a i n l y coiiimon i n business where the p o t e n t i a l benefits associated with greater accuracy are often not considered worth the added cost of analysis. For these reasons i t i s our intention to f i n d the l e v e l of mathematical rigour required to a r r i v e at solutions to various Poisson and non-Poisson queues which are s u f f i c i e n t l y accurate f o r p r a c t i c a l purposes, and to measure the amount of error one can expect from a wrong assumption about queue type. XK.T. Marshall, Some Inequalities for Single Service Queues, Berkeley, Operations Research Center, University of C a l i f o r n i a , 1966, p. 6. The assumptions considered here are that a p a r t i c u l a r d i s t r i -bution of i n t e r - a r r i v a l or service times i s , or i s not d i s -tributed expontfen.tially „ Thus a single service queue may be 2 any of the following four types; 1) M/M/l 2) M/G/l 3) G/M/l 4) G/G/l A s u b - c l a s s i f i c a t i o n of the general [G] d i s t r i b u t i o n w i l l be introduced l a t e r i n the analysis to d i f f e r e n t i a t e between those having increasing f a i l u r e rate and decreasing f a i l u r e rate. These l a t t e r terms are defined i n Appendix I. r. Recognizing that a large part of the solution l i e s i n i d e n t i f y i n g the i n t e r - a r r i v a l and service time d i s t r i b u t i o n s , we s h a l l examine methods which d i f f e r e n t i a t e between expo-n e n t i a l and non-exponential d i s t r i b u t i o n s . The Standard and Data Source One of the greatest problems i n analysing queues empirically i s to e s t a b l i s h a suitable standard against which to measure the performance of the hypothesized s o l u t i o n . In t h i s study use of a computer simulation written i n GPSS/360 i s made as a r e a l world from which data can be drawn and where long run performance represents the correct s o l u t i o n . Single channel queues with t r a f f i c i n t e n s i t i e s (p) M denotes exponentiality d i s t r i b u t e d times and G denotes a l l other d i s t r i b u t i o n s of times. of .6, .7,08 and .9 were simulated. For each value of p nine simulations were run, each with a unique combination of - i n t e r - a r r i v a l and service time d i s t r i b u t i o n s . The basic d i s -t r i b u t i o n s from which each p a i r was selected are shown i n Figure 1. In each of the t h i r t y - s i x runs, 10,000 a r r i v a l s generated queue s t a t i s t i c s to form the standard. Two samples, of 36 and 100 sequential measures of i n t e r - a r r i v a l and service times, were taken at a r b i t r a r i l y chosen points from each run; the two sample sizes were used to reveal how much e f f e c t sample s i z e a c t u a l l y had on the accuracy of the s o l u t i o n . The en t i r e simulation was run independently of the writer and only the two samples from each run were released for a n a l y s i s . The generating d i s t r i b u t i o n s were not i d e n t i -f i e d u n t i l a l l c a l c u l a t i o n s were done and each sample was approached with no p r i o r information whatsoever. Since samples of li m i t e d s i z e are the only source of knowledge of the s i t u a t i o n a user faces, the queueing analysis as present-ed i n t h i s thesis i s worked from the samples alone. This pro-cedure i s to duplicate the i n d u s t r i a l user's p o s i t i o n as f a r as i s possible. The solution of queue length calculated by various methods i s l a t e r compared to the simulated standard. Conclu-sions are then drawn as to the effectiveness of queue type i d e n t i f i c a t i o n , the accuracy of each method and the superior-i t y of one method over another. 6 Methods of Analysis Each sample run i s analyzed i n two stages. F i r s t , some s t a t i s t i c a l tests are used to i d e n t i f y the type of d i s t r i b u t i o n from which the sample times were drawn. As an analyst in.business would generally need a r e a d i l y usable procedure P the tests considered are r e l a t i v e l y simple to ca l c u l a t e and are elementary to apply. I t i s assumed an analyst would be l i m i t e d to a desk c a l c u l a t o r and s l i d e rule for his c a l c u l a t i o n s . The second step i s analysis of queue operating , c h a r a c t e r i s t i c s by several methods of c a l c u l a t i o n . Solutions for queue length are found from the c l a s s i c a l M/M/l queueing ' 3 formulae and from equations for G/G/l queues given by Marshall. Values for upper and lower bounds on queue length for both M/M/l and G/G/l based solutions are also worked out. Calculations for both M/M/l and G/G/l are made for a l l samples. This w i l l permit us to compare computed queue lengths for each sample under correct and incorrect assumptions of queue type. We can then derive the amount of error that can be expected to r e s u l t from analysis based on erroneous i d e n t i f i c a t i o n of queue type. Ibid. , p. 4 , CHAPTER II STATISTICAL ANALYSIS OF DATA The comparative ease with which one can f i n d solutions for queues with exponential i n t e r - a r r i v a l times from the M/M/l or the Pollaczek - Khintchine formulae makes analysis of t h i s d i s t r i b u t i o n imperative. When a successful analysis i s possible i t can be extended to the service time d i s t r i b u t i o n with very l i t t l e a d d i t i o n a l e f f o r t and s i g n i f i c a n t benefits i n speed of computation. One i s not so much concerned with a c t u a l l y i d e n t i f y i n g a d i s t r i b u t i o n or c l a s s i f y i n g i t as one of the known t h e o r e t i c a l d i s t r i b u t i o n s , as with ascertaining i f i t comes from the exponential or not. Considerations i n Choosing the Test Standard tests such as the chi-squared and Kolmogorov-Smirnov t e s t s , while very popular, have c e r t a i n l i m i t a t i o n s . The Kolmogorov - Smirnov i s very powerful with an extensive body of data but w i l l give errors with less than one hundred 4 observations. There are not many p r a c t i c a l situations where i t i s possible to take as many as 100 samples i n steady state. In f a c t , i n these experiments the two samples tested are siz e t h i r t y - f i v e and one hundred. I t i s the smaller one which i s 4W, F e l l e r , "On the Kolmogorov - Smirnov Limit Theorems for Empirical D i s t r i b u t i o n " , Annals of Math. Stat., 19, pp. 177-189, c i t e d i n IBM System/JbU S c i e n t i r i c subroutine Package, Version I I I , White P l a i n s , N.Y., IBM Corporation. 8 being tested, being of p r a c t i c a l s i z e , and the larger i s used mainly as a control* The Kolmogorov - Smirnov t e s t i s then of l i t t l e value except for larger bodies of data. I t may be noted here as well that L i l l i e f o r s observes that c r i t i c a l values determined i n t h i s t e s t are not correct when one or more parameters are estimated from the sample.-* tThe computation of t h i s test i s a d i f f i c u l t and lengthly proce-dure, rendering i t yet again unsuitable for our purposes. The chi-squared t e s t for goodness of f i t i s perhaps the c l a s s i c t e s t for the f i t of d i s t r i b u t i o n s . Its applica-t i o n too has l i m i t a t i o n s when the sample i s small. The short-comings encountered with t h i s t e s t are discussed i n greater d e t a i l l a t e r i n t h i s chapter.. Tests Based on L i f e Testing Epstein** wrote a paper concerned with s t a t i s t i c a l techniques i n l i f e t e s t i n g of exponentials. These are tests of the assumption that any given sample data come from an exponential d i s t r i b u t i o n . Two tests are examined i n t h i s H.W. L i l l i e f o r s , "On the Kolmogrov - Smirnov Test for Normality with Mean and Variance Unknown", J.A.S.A. 62, (1967) pp.399-402, c i t e d i n IBM System/360, S c i e n t i f i c Sub-routine Package, Version I I I , White P l a i n s , N.Y. IBM Corporation. ^B. Epstein, Test for the V a l i d i t y of the Assumption that the underlying D i s t r i b u t i o n of L i f e i s Exponential, Washington, D.C., U.S. Dept. of Commerce, Of f i c e of Technical Services, 19 59. present thesis? one graphical test which i s of some value, and one a n a l y t i c a l which i s based on a f a l s e assumption„ For the sake of continuity the l a t t e r i s presented f i r s t . An Analytic Exponential Test This t e s t uses a basic property of the Poisson process which i s ; ^ • -" , o . i f one observes a Poisson process for a fixed length of time T and i f r events occur i n [0,T] at times, t ^ t2 < ' t ^ . • • t r T, then these times (after being subjected to a random permutation) can be considered as r independent observations of a random variable uniformly d i s t r i b u t e d over [0,T]". Thus for r even moderately large (assumed to be larger r than 10) £ t ^ i s approximately normally d i s t r i b u t e d with i = l mean LL. and variance by the Central Limit Theorem, By r standardising 2 fci , the resultant s t a t i s t i c should be i= l e a s i l y found i n a table of areas under the normal curve. At the same time confidence l i m i t s around the mean can e a s i l y be computed . This i s an a t t r a c t i v e t e s t for our purpose because of the simple computation and speed i n providing a tes t of the hypothesis. 7 Ibid., p. 7. 10 This t e s t however i s invalids Consider the following example? -Let t = t = ( 1 1=t - 5 be successive i n t e r v a l times 1 2 20 from a stochastic process„ Let T = 10 0 To t e s t that the process i s exponential, the 20 times must be tested to see i f they are uniformly d i s t r i b u t e d on [0,T]„ The expectation of r Z tj_ i s rT = (20) (10) = 100. The standard deviation i s i= l 2 2 / E l * = /20(T) = 12.9 / 12 /T2 The 95% confidence acceptance i n t e r v a l f or the sample i s 100 ± (1.96) (12.9) = 74.7, 125.3. The observed sum I t i = 100 so, c l e a r l y , the hypothesis that the tj_ are exponential i s accepted. But these data came from the degenerate d i s t r i b u -t i o n and thus the tes t i s inva l i d a t e d . The error l i e s i n the standardization of the random va r i a b l e . The standardization of a random variable X with a f i n i t e mean and variance i s defined (denoted by X*), X* = x - E(x) °x * X* i s approximately normally d i s t r i b u t e d with mean zero and variance one. However any random variable must be standard-i z e d with i.ts..,own._.mean and variance. When exponential data i s tested the standardized variable i s N(0,1). With any other data the d i s t r i b u t i o n of the random variable i s not determined. "In the above example merely juggling T w i l l 11 cause the t e s t to r e j e c t or accept a r b i t r a r i l y . A Graphical Exponential Test In a well known procedure using p r o b a b i l i t y paper, data are plotted to see i f they form a s t r a i g h t l i n e . A s t r a i g h t l i n e indicates that the data are d i s t r i b u t e d with the same function as was used to construct the paper. This procedure i s commonly used with normally d i s t r i b u t e d data and normal p r o b a b i l i t y graph paper. The usual procedure plots the observations on the l i n e a r scale and cumulative proportions on the non-linear scale. For small samples one may o l o t the i n d i v i d u a l observations against i for 8 T T ~ I i — 1, 2 , xxo Epstein shows that a s i m i l a r p l o t t i n g procedure can be used f o r tes t i n g exponentials. He suggests that the ordered times s t a t i s t i c s t ,<t ,<t ,„.<t be plotted 1 2 3 n against the quantity 9 y = In (l-F(ti>' . where i = 1, 2, n, (1) where F(tj_) = i and where y i s the ordinate. If.the .exponential assumption i s correct, the plotted points w i l l be f i t t e d well by a s t r a i g h t l i n e passing through the o r i g i n with slope equal to the r e c i p r o c a l mean of the t ^ ' s , 8B.E. Cooper, S t a t i s t i c s for Experimentalists, Braunschweig, Germany, 1969, p. 82. "~ " 12 but as Cooper y points outs One c r i t i c i s m of t h i s procedure i s that no -formal t e s t of straightness exists at present". The expression (1) i s developed from the cumulative density function for the exponential F(t) given by P(t) 0 t < 0 - x t 1 - e i f t >, 0 , and i t reduces to, y In f n + 1 n + 1 -for ease of computation. The data may be plotted i n two ways. P l a i n graph paper may be used to p l o t the natural logarithms of the ordinate with the ordered times t ^ f t2<> ..... t n . Taking natural logarithms can be avoided by p l o t t i n g n '+' 1 with the times on semi-log graph paper. This l a t t e r proce-dure i s recommended f o r the normal user i n business since i t considerably reduces the time required to arr i v e at a s a t i s -factory answer and avoids the conversion of data where mistakes can occur. Figure 2 shows both exponential data and uniformly d i s t r i b u t e d data plotted on semi-log paper. I t must be further emphasized that t h i s procedure i s not a t e s t as such, but a method of providing an i n d i c a t i o n that the exponential assumption may be j u s t i f i e d . We now extend th i s " g r a p h i c a l procedure by applying some a n a l y t i c a l techniques and tests to develop a measure of how n"+ "1 -Ibid., p. 83. 14 well the sample data i s approximated by the exponential d i s t r i b u t i o n s The t h e o r e t i c a l s t r a i g h t l i n e f i t t e d to the plotted points of an exponential has slope equal to the exponential parameter and passes through the origin,, There are a number of a n a l y t i c a l procedures available for describing plotted data and f i t t e d s t r a i g h t l i n e s . Those considered are; a. c o r r e l a t i o n c o e f f i c i e n t b. a regression l i n e y = a + bx c. a t - t e s t for the ordinate a) C o r r e l a t i o n C o e f f i c i e n t This i s a measure of scatter i n d i c a t i n g the degree of r e l a t i o n s h i p between one variable and another. I t i s compar-a t i v e l y easy to c a l c u l a t e with the aid of an adding machine or mechanical desk c a l c u l a t o r and w i l l provide the degree of r e l a t i o n s h i p between sample times and the s t a t i s t i c y = In f n + 1 n + 1 - i" The user would have pre-computed y*s with the sum and sum of squares for several sample s i z e s . After a sample of a s p e c i f i c s i z e has been gathered, computation of a c o r r e l a t i o n c o e f f i c i e n t would produce a s t a t i s t i c that the analyst could compare to some pre-computed standard c o n f i -dence i n t e r v a l s . The analysis of the sample generated for t h i s thesis produced a marked difference i n c o r r e l a t i o n c o e f f i c i e n t for exponential and non-exponential d i s t r i b u t i o n s , i n d i c a t i n g that t h i s may be a v a l i d t e s t . Results of a p p l i -cation are presented i n a l a t e r section of t h i s chapter. 15 b) A Regression l i n e y = a + bx A more precise r e s u l t i s obtained by f i t t i n g a regres-sion l i n e to the data 0 Here the l i n e should be y = 0 + bx where b i s equal to one over the mean of the d i s t r i b u t i o n . We are l i m i t e d i n the analysis of the regression by our lack of knowledge of population parameters. We do know however that the population alpha i s zero and a t - t e s t can be used. The b c o e f f i c i e n t cannot be tested as the population mean i s unknown. A te s t for l i n e a r i t y i s not possible since two or more y values do not occur for each t ? there i s a one to one i correspondence. c) A t - t e s t for the Ordinate I f we assume the underlying process to be exponential, the population ordinate w i l l be zero. With the sample stan-dard error of a, a t - t e s t i s constructed such that i f jt.j exceeds the c r i t i c a l value ta/2, n - 2 shown i n tables, we r e j e c t the n u l l hypothesis that the casual d i s t r i b u t i o n was exponential. The following t e s t s t a t i s t i c i s computed and the r e s u l t of a p p l i c a t i o n to the sample data follow i n a l a t e r section of t h i s chapter. _ a - 0 _ a " -ST ~ S a 16 Chi-Squared Test for Goodness of f i t The X 2 t e s t for goodness of f i t i s probably the best known teste I t to has l i m i t a t i o n s related to the amount of data available„ A ru l e of thumb found i n many references requires the number of expected observations i n any one class to be at l e a s t 5 before the chi-square t e s t can be considered accurate. Pa r i gives add i t i o n a l l i m i t a t i o n s on sample s i 2 e 6 ^ He suggests that the t e s t gives reasonably good r e s u l t s i n the case of larger samples? ..."defined for present purposes as consisting of at l e a s t 100 items. Samples of less than 50 items are generally considered unreliable i n many appli c a t i o n s " . Cochran suggests that the r e s t r i c t i o n on the expected number i n each class can be relaxed to at l e a s t o n e . ^ He also suggests that the combining of classes weakens the s e n s i t i v i t y of the chi-square t e s t . The chi-square i s used i n t h i s work to t e s t the hypothesis that the sample data came from the Poisson. Classes were combined to ensure at l e a s t one expected obser-vation i n each c e l l . Since the mean i s used i n generating the Poisson i s the sample mean, the number of degrees of 10 ! ~ Boris P a r i , Basic S t a t i s t i c s , New York, Doubleday and Company Inc, 1967, p.l99~T ^George W. Snedecor and William G. Cochran, S t a t i s t i c a l Methods, Iowa, Iowa State University Press, 1967, p.235. 17 freedom must be reduced by t h i s one estimated parameter. 1 / The r e s u l t s of these tests follow 0 Results of Applying Tests to the Sample Data Each of the procedures or tests described i n the previous section was applied to the sample d i s t r i b u t i o n s to f i n d out how accurately each t e s t i d e n t i f i e d those d i s t r i b u -tions which were generated from the exponential population used i n the simulation model, From these r e s u l t s we deduce the r e l a t i v e worth of each t e s t and f i n d that only one, the " c o r r e l a t i o n c o e f f i c i e n t t e s t " , provides consistent r e s u l t s . In addition the c o e f f i c i e n t of v a r i a t i o n , while not a formal te s t s t a t i s t i c by i t s e l f , i s described because i t helps to detect those d i s t r i b u t i o n s that come from the exponential population. A procedure for t e s t i n g sample data useful to the p r a c t i t i o n e r as well as pre-computed data w i l l be found i n Appendix I I . a) Correlation C o e f f i c i e n t We have previously discussed the c o r r e l a t i o n c o e f f i -c i e n t as a measure of s c a t t e r . From the computed s t a t i s t i c s and the times t i the c o r r e l a t i o n c o e f f i c i e n t was computed. The r e s u l t i n g c o e f f i c i e n t s for each exponential and non-exponential d i s t r i b u t i o n are c o l l e c t e d i n Table I. i 2 d . f . = (No. of classes) - (No. of estimated parameters) - 1. TABLE I Frequency D i s t r i b u t i o n of Correlation C o e f f i c i e n t for Exponential and General Sample D i s t r i b u t i o n 1 Exponential General 1 Sample siz e 36 100 36 10 0 Correlation C o e f f i c i e n t .820-.829 1 .830-.839 22 1 .840-.849 0 1 .850-.859 4 6 .860-.869 4 4 .870-.879 4 8 .830-.889 6 10 .890-.899 11 11 .900-.909 8 2 .910-.919 3 5 .920-.929 1 3 .930-.939 0 1 .940-.949 1 1 .950-.959 0 .960-.969 2 1 .970-.979 3 2 .980-.989 8 9 .990-.999 9 12 Mean .9797 .9883 .8906 .8818 St. Dev. .0166 .0078 .0272 .0196 95% Confidence 1.0000 1.0000 .9440 .9202 Limits .9472 .9729 .9372 .8434 19 An increase i n sample s i z e considerably reduces the stan-dard error of the c o r r e l a t i o n c o e f f i c i e n t and may provide a s i g n i f i c a n t t e s t with a yet to be determined r e l a t i o n s h i p between them. This needs to be tested with additional d i s t r i b u t i o n s and with d i f f e r i n g sample s i z e s . I t would appear that the s i g n i f i c a n t mark i n the current data i s ,93, a c o e f f i c i e n t greater than t h i s figure i n d i c a t i n g exponentiality. Even with a sample siz e of 36 the type 1 and II errors shown i n Table II are not s i g n i f i -cant i n t h i s case and may prove not to be so i n general. The 1,96 standard deviation confidence l i m i t s around the mean c o r r e l a t i o n c o e f f i c i e n t are shown. I t should be noted that a s i g n i f i c a n t difference exists between the lower l i m i t f o r the non-exponential, This gives further encouragement to the hypothesis that the c o r r e l a t i o n c o e f f i c i e n t i s a useful t e s t s t a t i s t i c f or detecting exponential d i s t r i b u t i o n s and warrants further i n v e s t i g a t i o n . A supplementary i n d i c a t o r of exponentiality i s found i n the c o e f f i c i e n t of v a r i a t i o n . This was used and tested i n much the same manner as the c o r r e l a t i o n c o e f f i c i e n t and i s presented here as an add i t i o n a l s t a t i s t i c to be used with the former recognizing that using i t alone i t can give very mis-leading r e s u l t s . This quantity i s a r e l a t i v e measure of dispersion where the standard deviation i s expressed as a percentage of the mean. Using the same procedure as before the c o e f f i c i e n t of v a r i a t i o n for each sample s i z e are grouped i n d i s t r i b u t i o n s . TABLE II Type 1 and II Errors from Testing for Exponentials with Correlation C o e f f i c i e n t N u l l Hypothesis EQt D i s t r i b u t i o n i s Exponential i f c c . > .930 Type 1 Error Type II Error Sample s i z e No./24* % No,/48* % 36 1 4 . 2 2 4.2 100 *The difference between these quantities i s due to the greater number of combinations of queue type with general d i s t r i b u t i o n s 21 These are shown i n Table III« Again the exponential can be d i f f e r e n t i a t e d . The t h e o r e t i c a l c o e f f i c i e n t of v a r i a t i o n for an exponential d i s t r i b u t i o n i s 1, -and a l l c o e f f i c i e n t s found for the sample non-exponential d i s t r i b u t i o n s were less than .8 . I t i s suggested that a confidence band of 1. - .3 could be used to accept random data as being from an exponen-t i a l 0 The c r u c i a l point to be remembered here i s that while a t h e o r e t i c a l exponential d i s t r i b u t i o n has a c o e f f i c i e n t of v a r i a t i o n of one, (from c v = s.d./mean) ; other non-exponen-t i a l d i s t r i b u t i o n can also have a c o e f f i c i e n t of one. Thus only when the c o r r e l a t i o n c o e f f i c i e n t i s close to 1.0 can the c o e f f i c i e n t of v a r i a t i o n be v a l i d l y used to confirm exponen-t i a l i t y . This c o e f f i c i e n t i s used however, as a formal t e s t for the IFR condition i n a general d i s t r i b u t i o n as explained i n Appendix I. This i s not to be confused with the use being made of t h i s quantity above. The Type I and Type II errors r e s u l t i n g from applying the c o e f f i c i e n t to the sample data i s shown i n Table IV. I t i s concluded that inferences should be drawn from t h i s table cautiously and the c o e f f i c i e n t should be applied with the same degree of caution for the reasons mentioned above. TABLE III Frequency D i s t r i b u t i o n of C o e f f i c i e n t of Variation for Exponential and General Sample Dis t r i b u t i o n s Exponential General Sample size 36 100 36 100 Co e f f i c i e n t of Variation .1- .199 2 .2- .299 5 6 .3- .399 1 14 12 .4- .499 0 11 13 .5- .599 0 13 16 .6- .699 4 2 3 1 ,7- .799 3 3 .8- .899 5 3 .9- .999 3 2 1.0- 1.099 3 6 1.1- 1.199 1 5 1.2- 1.299 3 2 1.3- 1.399 1 0 1.4- 1.499 0 1.5- 1.599 ..: 1 Mean .9042 1.0080 .4297 .4404 St Dev. .2267 .2115 .1203 .1064 95% Confidence 1.3492 1,4158 .6657 .6464 Limits .4492 ,5858 ,1937 ,2344 TABLE IV Type 1 and Type II Errors for Testing for Exponentials with C o e f f i c i e n t of V a r i a t i o n N u l l Hypothesis Hos D i s t r i b u t i o n i s Exponential i f Cv 2 e [ . 7 , 1.3J Type 1 Error Type II Error Sample size No./24 % No./43 % 36 5 21.0 100 5 21.0 N> 24 b) A Regression l i n e y==.afbx No d i r e c t use was made of t h i s regression l i n e except i n connection with the t - t e s t for the ordinate which i s discussed i n the next sub-section. Tests of l i n e a r i t y could not be performed for reasons mentioned previously and the lack of knowledge of the population mean prevented an analysis of variance and F-tests. c) t-Test This t e s t provided the l e a s t i n t e r e s t i n g r e s u l t s and i no conclusions could be drawn except that the t e s t i s unsatisfactory. The r e s u l t s are summarized i n Table V and are inconclusive since both types I and II errors were p l e n t i f u l . d) Chi-Squared Test This t e s t did not produce s a t i s f a c t o r y r e s u l t s e i t h e r . I t was possible to manipulate the r e s u l t s at w i l l when constructing a Poisson d i s t r i b u t i o n . A r r i v a l rate d i s t r i b u t i o n s were constructed from the sample times using a time u n i t chosen for its convenience. I n i t i a l l y the time u n i t was chosen to give the same number of units as events, thereby making the a r r i v a l rate equal to 1 .0 . I f t h i s was always done, a user would only need one set of figures for the t h e o r e t i c a l d i s t r i b u t i o n thus making his job of t e s t i n g easier. This t e s t produced such inaccu-TABLE V . Type I and II Errors from t-Test that Ordinate of F i t t e d Regression l i n e Equals Zero* Ho: a = o Type I Error Type II Error Sample si z e No./24 % No,/48 % 36 14 58.0 22 46.0 100 22 92.0 4 8.4 * at a .01 significance l e v e l 26 rate r e s u l t s however that a search was made for a better time u n i t . No s a t i s f a c t o r y time unit was found as can be seen from Table VI which shows the r e s u l t s from chi-square tests on the sample data for eight d i f f e r e n t time unit values. The eight values i n the left-hand column show the number of a r r i v a l s per time unit? the actual time unit being a function of the t o t a l elapsed time of i n t e r - a r r i v a l times over the sample and the number of a r r i v a l s . As i n the t - t e s t these r e s u l t s are inconclusive. Summary There does not appear to be a simple t e s t for expo-nen t i a l d i s t r i b u t i o n s that i s s a t i s f a c t o r y under a vari e t y of conditions e s p e c i a l l y small sample s i z e s . For guidance the graphical t e s t i s use f u l . The t e s t based on the c o r r e l a t i o n c o e f f i c i e n t has promise but needs more extensive examination and t r i a l with d i f f e r e n t sample sizes and a larger s e l e c t i o n of d i s t r i b u t i o n s . I t would be of i n t e r e s t to t r y some non-exponential d i s t r i b u t i o n s constructed to have a c o e f f i c i e n t of v a r i a t i o n close to one. The t e s t for the IFR and DFR properties described i n Appendix I, using the c o e f f i c i e n t of v a r i a t i o n , appears to be the only r e l i a b l e t e s t at present. The s i g n i f i c a n c e of IFR and DFR properties w i l l become apparent i n Chapter IV and therefore deserve reference here due to that importance. A procedure f o r te s t i n g a d i s t r i b u t i o n , e a s i l y used by a non-technical person, i s shown i n Appendix I I . This i s TABLE VI Type 11 and II Errors from Chi-Square Test* of Rate Distributionsof Sample Data Sample s i z e 36 100 Ave rate per time unit** Type 1/24 Type 11/24 Type 1/48 Type 11/48 .05 0 48 0 48 .10 0 48 0 48 .30 5 33 . 13 6 .50 11 6 17 0 .75 9 10 19 0 1.00 13 1 18 0 1.25 16 2 19 1 1.50 14 4 20 ~ 0 *at .01% l e v e l of Significance **see text for explanation of time u n i t . 28 the " c o r r e l a t i o n c o e f f i c i e n t t e s t " and uses pre-computed data points for comparison,, The method of c a l c u l a t i o n , with formulae, shows a p o t e n t i a l user the steps required to a r r i v e at conclusive evidence based on t h i s t e s t as to the nature of the d i s t r i b u t i o n , CHAPTER I I I METHODS FOR THE ANALYSIS OF QUEUES I n t h i s c h a p t e r we examine t h e s o l u t i o n methods used t o f i n d queue l e n g t h and w a i t i n g t i m e s . A ssumptions A b r o a d and not c o m p l e t e l y j u s t i f i a b l e a s s u m p t i o n used t h r o u g h a l l t h e queue a n a l y s i s i s t h a t o f s t e a d y s t a t e . T h i s p e r m i t s t h e use o f e q u i l i b r i u m s o l u t i o n s . However, t h e major-i t y o f s i t u a t i o n s f a c e d by t h e s m a l l b u s i n e s s o p e r a t o r may not be s t e a d y s t a t e . An example i s a s p a r e p a r t s c o u n t e r where t h e pace o f b u s i n e s s i n c r e a s e s i n t h e e a r l y morning t h e n d e c r e a s e s o v e r t h e l u n c h p e r i o d and may peak a g a i n i n t h e a f t e r n o o n . These problems can be overcome by i s o l a t i n g each p e r i o d w i t h changed a r r i v a l p a t t e r n s and p e r f o r m i n g s e p a r a t e a n a l y s e s . However, t h i s does not f u l l y a c c o u n t f o r t r a n s i e n t .-.behaviour. -• M/M/l Queue Ex p e c t e d system l e n g t h , L = —£— (1) 1-P (2) 30 2 Expected queue length, Lq = (3) 1 - p Var (Lq)= P 2 + P 3 - P* (4) ( 1 - P ) 2 M/G/l Queue These are the Pollaczek - Khintchine formulae? \ 2 ~ 2 j. _ 2 Expected system length, L = p + ° -Expected queue length, Lq = X 2a£ + p 2 (6) 2(1 - p) G/G/l, G/M/l Queues The solution of queue length and waiting time for the general case i s complex and the exact formulae depend on the moments of the i d l e time d i s t r i b u t i o n as shown by Marshall. J The expected wait i n queue i s found to be: Wq = E(U 2) E ( I 2 ) -2E(U) 2E(I) - X 2(a^ + a§) + ( l - P ) 2 v h ( 2 ) { 7 ) 2X(1 - P) 2 % where Un = Sn - Tn, The i d l e time d i s t r i b u t i o n i s ^ M a r s h a l l , p. 4. found from the fundamental i d e n t i t y , wn+l = m a x Wn + Un] But l e t t i n g X n = - min [0, Wn + Un] w„.i - Xn = Wn + Un 'n+1 From the above where Xn > o Xn. = I The variance of the expected wait i n queue i s shown by Marshall to be a 2 _ E(U) f E ( U 2 ) | 2 •2E(U) . E(I 3) [ E ( I 2 ) ' + 3E(I) ** l2E(I). Wq -3E(U) \ X(v<3> - vi 3>) V 3 ( p 4 2 ) ~ - ( 2 ) •v. ) 3(1 - p ) X2 (a 2 + a 2) -f (1 21 2 2X(1 - p ) re,h (8) - „(3) where a^h = v£ fvv(2)1 From successive i n t e r - a r r i v a l and service times (Tn and Sn) one can compute Xn and the moments of the i d l e time d i s t r i b u t i o n . While a tedious task by hand, they can be derived e a s i l y on a computer? such was our case. I t i s doubt-f u l that the average user under consideration would be a computer or compute these quantities by hand. To obviate t h i s problem, Marshall's bounds on expected wait for the G/G/l queue are shown. G/G/l Bounds a) Upper bound 32 Wq = X ( g a + qg> (9) 2(1 - p) By multiplying both numerator and denominator by X t h i s expression becomes Wq = a| + a 2(1/X - 1/u) which i s Kingman's heavy t r a f f i c approximation,, The l a t t e r states: "For t h i s approximation to be v a l i d , the denominator must be small compared to the square root of the numerator".^ This bound i s expected to be high for rho values of .9 or l e s s , although i t w i l l be accurate as an equality f o r rho greater than .9 . This bound i s p a r t i c u l a r l y useful because i t only depends on the f i r s t two moments of the i n t e r - a r r i v a l and service time d i s t r i b u t i o n . b) Lower bound The lower bound £<E(W)(Wq) i s found as the solution of X = / j ' K c(u)du, where Un = (Sn - Tn) - K(U ) . (10) This bound i s shown by Marshall to be unique f o r rho less than 1. The computation of K c(u) requires the convolution of Sn and Tn. ^ J . F . C . Kingman, "The Heavy T r a f f i c Approximation i n the Theory of Queues", Proceedings of the Symposium on Conjestion Theory, ed Walter L. Smith and William J . Wilkinson, Chapel H i l l , The University of North Carolina Press, 1965, p. 137-157. 33 Computation of lower bound As an a l t e r n a t i v e to computing the convolution of (Sn - Tn) the d i s t r i b u t i o n of K(u) i s found from each sample using empirical density functions„ Let T - F T(x) and S~ F g(x) If ' 0 X < x 1 . F T(x) < 1/T • x x < X < x 2 then P T(x) : i = l u ( x i " x ) x T< X where U i s the Then f (s) X 1 t f* .(s) • f* (-S) The Laplace transform of U n = S n - T n i s which equals = ± E e-sl°A> £ n . 3=1 e s ( S i ) - s(Tj) n 1 n i = l 1 n 2 n 2 E E e I 2 E e " s ( U k ) n k=l 0, 1, . = F n ( U ) We now solve for x the lower bound i n x = / 00 ( 1 - F n(u)) du -X which i s solved computationally x I m=n2 U m where Un = S i - T x and Un?-= S n - T n Thus the bound can be found very e a s i l y from the sample generation of data points for the K c(u) d i s t r i b u t i o n . For each n a r r i v a l s n 2 points are used i n the d i s t r i b u t i o n , thus for a very small amount of data quite a precise d i s t r i b u t i o n can be expected. IFR/G/1, DFR/G/1 Queues Tighter bounds on the expected wait i n queue can be found for these two classes. (See Appendix I) The bounds on IFR(DFR)/G/1 queues are generally stronger than those mentioned previously, bounding the expected number i n the queue to at most, one customer. data. One great asset i n t h i s lower bound i s the s e l f -a) IFR/G/1 Queue J - (p + C 2) i . < w, q < J XJ - (p + c 2) < L Q < XJ 35 where 2X(1 - p ) b) DFR/G/1 Queue. I < Wq < J and \Z < L a < J (P + C 2)/2 where J i s as above and 5, i s the solution to the lower bounds i n the G/G/l case. Expected Wait and Queue Length Comparative queue c h a r a c t e r i s t i c s can e a s i l y be computed from the following r e l a t i o n s h i p s : L = \w!5 . Lq = XWq • W = Wq + 1 y Lq = L - p Computation solut i o n on the computer. This i s a st r a i g h t forward task except for the solution to the lower bound equation (10) which was found, as explained, through the use of the empirical density function. 1 5J.D. L i t t l e , "A Proof of the Queueing Formula: L = XW", Operations Research, Vol. 9, (1961), pp. 383-387. A l l formulae shown i n t h i s section are coded for CHAPTER IV QUEUE ANALYSIS In t h i s chapter we apply the t h e o r e t i c a l methods to the sample data generated from the simulation model, i n order that we may estimate queue length. These estimators w i l l then be compared to the simulated r e a l world sol u t i o n and th e i r accuracy evaluated. There are three steps i n t h i s process. The f i r s t c i s to e s t a b l i s h the accuracy of the sample parameters as estimates of the population parameters. This i s important since many of the c l a s s i c a l queueing cal c u l a t i o n s depend s o l e l y on the expested values of the population d i s t r i b u t i o n s . Only the calc u l a t i o n s for the general lower bound (10)"^ and the moments of the i d l e time d i s t r i b u t i o n on the other hand, r e l y d i r e c t l y on the i n t e r a c t i o n between s p e c i f i c sequential i n t e r - a r r i v a l and service times, as can be appreciated from U n = S n - T n . The importance of the f i r s t moment of the sample d i s t r i b u t i o n s i s emphasized by i t s use i n the "c o r r e l a t i o n c o e f f i c i e n t t e s t " and i n the computation of rho which, of course, subsequently 5,affects queue length estimates. The second step i s an evaluation of the queueing c a l -c u l a t i o n methods themselves. Since some serious errors do r e s u l t when estimating the population d i s t r i b u t i o n parameters only those queue with a calculated rho within 5% of the simulated 16 Numbers i n brackets i n t h i s section r e f e r to equation numbers i n Chapter I I I . 37 rho w i l l be used i n t h i s step 0 This w i l l give us a measure of the a b i l i t y of the. various methods chosen for estimating queue length to perform, under the same parameters that the simulation used. One would not expect to f i n d disagreement between the simulated and calculated queue length for these samples e The t h i r d step i s to evaluate the o v e r a l l r e s u l t . Having established some knowledge of the behaviour of the methods used i n queue length estimation under optimum conditions we w i l l better understand the errors i n estimating queue length r e s u l t i n g from errors i n estimating d i s t r i b u t i o n parameters. Runs which have an estimated rho considerably i n error from the simulated rho w i l l be examined to f i n d the best method of approach to minimize o v e r a l l error i n estimating queue length. Step One; Evaluation of Sampling Errors Since the majority of queue operating c h a r a c t e r i s t i c s depend on the expected i n t e r - a r r i v a l and service times through t h e i r composition of rho, and as the Pollaczek-Khintchine formulae depend on the c o e f f i c i e n t of v a r i a t i o n squared as we l l , i t i s most desireable to accurately predict these expected values i f one anticipates t h e i r successful a p p l i c a t i o n i n queue-ing a nalysis. In some exploratory simulation runs, to test the operation of the experiment, large discrepancies between the simulation parameter mean and the sampled mean occurred. I t was thought that t h i s was due to the integer form of data with a low mean of 38 ten. To prevent d i s t o r t i o n or bias from the simulation, the mean was raised to one thousand, i n the case of i n t e r - a r r i v a l times, to produce integers with three s i g n i f i c a n t d i g i t s . This new data was then read by the queue programs with the decimal point displaced two positions l e f t . The new data then was accurate to one one hundredth of a time u n i t . The blame for "bad" data could not now be l a i d with the simulation. We should note at t h i s time that the random number generator i s considered to be s u f f i c i e n t l y random that r e s u l t s w i l l not be biased by c y c l i n g of the random number s t r i n g . The IBM stan-i dard random number generator i s tested to generate two to the 17 twenty-ninth d i g i t s before repeating. Before we look at the s p e c i f i c figures for lamda, mu, and rho, consider the e f f e c t s on rho of a change i n lamda and mu. As would be expected from the well known re l a t i o n s h i p p = X/u t a f r a c t i o n a l change i n lamda w i l l cause a propor-t i o n a l change i n rho. Thus i f the a r r i v a l rate i s increased by ten percent, the t r a f f i c i n t e n s i t y (rho) w i l l increase by the same ten percent. This i s not true with mu. A f r a c t i o n a l change i n mu, denoted b, w i l l cause a change i n rho equal to - •*-—;—r . This means that a 20% increase i n the service b + 1 rate w i l l improve.the t r a f f i c . i n t e n s i t y by only 16.7%, The combined e f f e c t of change i n lamda and mu, denoted by a and b respectively, on rho can be expressed as c=^ ^ , where c i s the f r a c t i o n a l change i n rho. This r e l a t i o n s h i p i s very pertinent to the application •••'Subroutine RANDU, I B M System/360 S c i e n t i f i c Subroutine Package Version I I I , White Plains, N.Y., I B M Corp. of queueing r e s u l t s when considering the cost of a l t e r i n g or service rate's* I t i s mentioned here s o l e l y to aid the reader i n understanding how errors i n the estimation of population parameters can e f f e c t the subsequent queue analysis* E s s e n t i a l l y errors i n mu w i l l have less e f f e c t on rho although the diminishing e f f e c t i s only obvious when errors i n mu are larger than approximately ten percent. An add i t i o n a l problem concerns the d i r e c t i o n of change i n rho caused by the combined errors i n lamda and mu. The following Figure 3 shows the d i r e c t i o n a l change i n lamda and mu Sign of a Sign of b Change i n Condition • rho + + + a > b - + - - .. .- a > b F i g . 3 E f f e c t i v e d i r e c t i o n of change i n rho, for changes of lamda and mu. In the following presentation of the actual data, a l l errors are shown as a percent error from the intended value -from the simulation model. This gives us a unit of comparison that i s common to a l l q u a n t i t i e s . Since each sample of data was generated independently, each estimated rho i s considered as a separate e n t i t y and while the mean percent error o v e r a l l i n the values of rho may be close to zero, t h i s i s not an i n d i c a t o r of accuracy as one can see from the data presented, Tables VII and VIII show sample values as well as percent error of lamda, mu, and rho fo r the two sample s i z e s . To help the reader i n i n t e r p r e t i n g these tables, errors i n the estimation of rho, shown as a percent of the intended values of rho i n the simulation model, are grouped by t h e i r deviation from zero i n f i v e percent steps ignoring the d i r e c t i o n of error, Figure 4 below shows t h i s grouping for the two sample s i z e s 0 % Error ± Class Frequency by Sample Size Boundries 36 100 0 - 4 , 9 7 15 5 - 9.9 12 7 10 -14.9 8 6 15 -19.9 2 3 20 -24,9 3 2 25 -29.9 1 2 30 -34,9 2 1 35 -39 .9 1 3T 3T F i g . 4 D i s t r i b u t i o n of Percent Error i n Rho by Sample Size. I t should be emphasized here that the error i n rho i s calculated on the intended value of rho and not the actual simulated r e s u l t . As the largest deviation of the simulated rho from the intended value was less than one percent i n a l l but two cases, both of whose deviations were within 1,5%, the intended values are considered s u f f i c i e n t l y accurate. Use of the intended values also aides i n the presentation of data where, fo r example, .9 i s Key to Tables VII and VIII Run Number Intended Rho Estimated Rho Percent Error i n Estimating Rho Intended Lamda Percent Error i n Estimating Lamda Intended Mu Percent Error i n Estimating Mu TABLE V I I P e r c e n t E r r o r o f Rho s Lamda , and Mu (Sample S i z e 36) t l ) 12.) (3) (4) (5) (6) (~7) (8) 1 0.9 1.130 25.555 0.1 20.000 0.111 -3.700 2 0 . 8 0. 7k5 -6.875 0.1 7.000 0.125 14.400 3 0.7 0.855 22.143 0.1 19 . 000 0. 143 -2.700 4 0.6 0.590 r l . 66 7 0.1 -1.000 0.167 0.800 5 0.9 0.979 8.-778 0. 1 7.000 0.111 -1.900 6 0.8 0.741 -7.375 0.1 - 8 . 0 0 0 0.125 -0.800 7 0.7 0.779 11,286 0. 1 11.000 0.143 -0.600 8 0.6 0. 624 4.000 0. 1 1.000 0.167 -2.800 9 0.9 0.921 2.333 0.1 -12 .000 O . i l l -13.600 10 0.8 0.846 5. 750 •0.1 6.000 0.125 0.800 11 0.7 0.472 -32.571 0.1 -22.000 0. 143 15.500 12 0.6 0.532 -11.333 0.1 11.000 0.167 24.800 13 0.9 1.060 17.778 0.1 . 1.000 0. I l l -14.50 0 14 0.8 0.850 ' 6.250 0.1 0.0 0.125 -5.600 15 0.7 0.624 -10.857 0.1 -2.000 0. 14 3 9.9 00 16 0.6 0.553 -7. 833 0.1 -7.000 0.167 1.400 17 0.9 0.980 8.889 0.1 5.000 0. I l l -2.800 18 0.8 0.856 7.000 0.1 0.0 0.125 -6.400 19 0.7 0. 700 - 0 .000 0.1 2.000 0. 143 1.500 20 0.6 0.601 0.167 0. 1 -5.000 0.167 -5.200 21 0.9 0.694 -22.889 , 0. 1 -18 . 000 0. I l l 6.200 22 0.8 0. 703 -12.125 0.1 2.000 0. 125 16.000 23 0.7 0.781 11.571 0. 1 9.000 • 0.143 -2.000 24 0.6 0.542 -9.667 0.1 -6 . 0 0 0 0.167 3.800 25 0.9 0.889 -1.222 0.1 9 . 0 0 0 0.111 9.800 26 0.8 1.070 3 3.75 0 0.1 16.000 0. 125 -12.800 27 0.7 . 0.844 20.571 0.1 1 9 . 0 0 0 0.143 -1.300 28 0.6 0.505 -15.833 0.1 -7.000 0.167 9.800 29 0.9 0. 811 -9.889 0.1 - 5 . 0 0 0 0.111 6.200 30 0.8 0.693 -13. 375. 0.1 -17.000 0. 125 -4.800 31 0.7 0.957 36.714 0.1 26 . 0 0 0 0.143 -7.600 32 0.6 0.519 -13.500 0.1 - 7 . 0 0 0 0. 157 7.400 33 0.9 1.020 13.353 0.1 6.0 0 0 0.111 -6.400 3k 0.8 0.765 -4.375 0.1 -6.000 0.125 -1.600 35 0.7 0.640 -8.571 o . i - -1.000 0.143 8.500 36 0.6 0.545 -9.167 0.1 -12.000 0.167 -2.800 TABLE VIII Percent Error of RHo, Lamda, and Mu (Sample Size 100) (1) (2) (3) (4) (5) (6) (7) (8) 1 0.9 0.894 -0 .667 0.1 8.000 0.111 8 .900 2 0.8 1.050 31.250 0.1 18.000 . 0.125 . -9 .600 3 0.7 0.633 -9 .571 0.1 -5 .000 0.143 5. 700 4 0.6 0.631 5.167 •0.1 -5 .000 0.167 -9 .400 5 0 .9. 0.923 2.556 0.1 -1 . 0 0 0 0.111 -2 .800 6 0.8 0.750 -6 .250 0.1 2.000 0 .125 8. 800 7 0.7 0.711 1.571 0.1 10 .0 00 0.143 8.500 8 0.6 0.608 1.333 0.1 10.000 0 . 1 6 7 • 8.000 9 0.9 0.754 -16.222 0.1 -10 .000 0.111 7.100 10 0.8 0.842 5.250 0.1 7.000 0 .125 1.600 11 0.7 0.689 -1 .571 0.1 -1 .000 0.143 0.300 12 0.6 0.579 -3 .500 0.1 -4 .000 0.167 ' -1.000 13 0.9 0.878 -2 .444 0.1 2.000 0.111 4.400 14 0.8 0.714 -10.750 0.1 4. 000 0.125 16.300 15 0.7 0.778 11.143 0.1 3.000 0.143 -7 .600 16 0.6 0. 585 -2 .500 0.1 1.000 0.167 3.200 17 0.9 0.826 -8 .222 0.1 -8 .000 0 .111 0.800 18 0.8 0.777 -2 .875 0.1 -2 .000 0.125 0.800 19 0.7 0.832 18.857 0.1 14.000 0.143 -4 .100 20 0.6 0.588 -2 .000 0.1 2.000 0.167 4.400 21 0.9 0.871 -3 .222 0,1 2.000 0.111 5. 300 22 0.8 0. 843 5. 375 0.1 -1 .000 0.12.5 -5 .400 23 0.7 C.506 -27 .714 • 0.1 -12 .000 0 . 1 4 5 21.800 24 0.6 0. 474 -21.000 0.1 -8 .000 0.167 16.400 25 0.9 0.997 10.778 0.1 -12 .000 0.111 -20 .800 26 0. 8 0.787 -1 .625 0.1 0.0 - 0.125 1.600 27 0.7 0.890 27.143 0.1 0.0 0.143 -21 .600 28 0.6 0.529 -11 .833 0.1 -5 .000 0.167 8.000 29 0.9 1.020 13.333 0.1 12.000 0.111 -1.900 30 0.8 0.766 -4 .250 0. i -3 .000 0 .125 -3 .200 31 0.7 0.718 2.571 0.1 -5 .000 0.143 -7 .600 32 0.6 0.539 -10 .167 0.1 -3 .000 0 .167 8.000 33 0.9 0.9 75 8.3 33 0.1 8.000 0.111 -1 .000 34 0.8 0,969 21.125 0.1 ,16. 000 0.125 -4 .000 35 0.7 0.567 -19.000 0.1 -7 .000 0.143 14.800 36 0.6 0.589 -1 .833 0.1 5.000 0 .167 6.800 43 s u f f i c i e n t l y accurate for .893 and the extra decimals do not provide any s i g n i f i c a n t information. Estimates of rho from the larger samples are not s i g n i -f i c a n t l y more accurate than those from the smaller sample. The notable difference l i e s i n the larger number of estimates with errors of f i v e percent or less r e s u l t i n g from the larger sample s i z e . Even so, approximately half of the estimates are s t i l l greater than ten percent i n error from the r e a l world rho as determined i n the simulation model. This leads us to con-clude that no s i g n i f i c a n t benefit can be gained from the increased sample s i z e . I t also follows that the large samples do not improve our knowledge of the accuracy of the smaller samples i n t h e i r a b i l i t y to s a t i s f a c t o r i l y estimate rho. There does not appear to be any evidence here to j u s t i f y increasing the sample s i z e from 36 to 100. Furthering our analysis of the error i n estimation of rho, the data from the two sample sizes i s grouped i n Table IX by intended rho value. We notice that the mean percent error i s small for a l l parameters with no s i g n i f i c a n t differences between the small and large sample r e s u l t s . This proximity to zero for a l l parameters i s expected since group means c a l c u l a -ted from both p o s i t i v e and negative values would tend toward zero unless an unusual bias was present at the time of selec-t i o n of s p e c i f i c i n t e r - a r r i v a l and service times. There i s no reason to-believe that there was. There appears to be a s l i g h t difference between samples i n t h e i r respective maximum negative errors. Eight of the twelve values i n the larger sample are smaller than the TABLE IX Sampling Errors for Lamda, Mu, and Rho as Percentage of Intended Simulated Values Sample Sizes 36 1 0 0 Variable Mean % Error Stn Dev. Max(+) % Error Max(-) % Error Mean % Error Stn Dev. Max(-f) % Error Max(-) % Error .9 X 1 . 4 4 1 1 . 5 4 2 0 . 0 0 1 8 . 0 0 0 . 1 1 8 . 5 7 1 2 . 0 0 1 2 . 0 0 y - 2 . 2 9 8 . 5 6 9 . 8 0 1 4 . 5 0 0 . 0 • 8 . 8 2 8 . 9 0 2 0 . 8 0 p 4 . 7 4 1 4 . 7 0 2 5 . 5 6 2 2 . 8 9 0 . 4 6 9 . 4 5 1 3 . 3 3 1 6 . 2 2 . 8 X 0 . 0 9 . 5 7 1 6 . 0 0 1 7 . 0 0 3 . 9 9 8 . 4 7 1 8 . 0 0 8 , 0 0 y - 0 . 0 8 9 . 5 2 1 6 . 0 0 1 2 , 3 0 . 7 1 8 , 0 6 1 6 . 8 0 9 . 6 0 •p . 9 5 1 4 . 5 0 3 3 . 7 5 1 3 , 3 8 4 . 1 3 1 3 . 7 3 3 1 . 2 5 1 0 . 7 5 . 7 X 6 . 7 7 1 4 . 4 8 2 6 , 0 0 2 2 . 0 0 - 0 . 3 3 8 . 2 7 1 4 , 0 0 1 2 . 0 0 y 2 . 3 5 7 . 3 6 1 5 , 5 0 7 . 6 0 1 . 1 8 1 3 . 1 6 2 1 . 8 0 2 1 . 6 0 P 5 . 5 8 2 0 . 8 9 3 6 , 7 1 3 2 . 5 7 0 , 3 8 1 7 . 4 8 2 7 . 1 4 2 7 . 7 1 . 6 X - 3 . 6 6 6 . 6 5 1 1 , 0 0 1 2 . 0 0 - 0 . 7 7 5 . 7 3 1 0 , 0 0 8 . 0 0 y 4 . 1 3 9 . 1 6 2 4 . 8 0 5 . 2 0 4 . 9 3 7 . 1 3 1 6 . 4 0 9 , 4 0 P 7 . 2 0 6 . 6 3 4 , 0 0 1 5 . 8 3 - 5 , 1 5 7 . 9 0 5 . 1 7 2 1 . 0 0 45 corresponding values i n the sample of 36 observations. This trend i s reversed i n the maximum p o s i t i v e errors where only f i v e of the twelve are smaller. This tends to confirm the lack of any objective evidence of benefits i n accuracy i n estimating population parameters by increasing sample s i z e . Considering each of the 72 values of lamda, mu, and rho i n d i v i d u a l l y , the. following Figure 5 v e r i f i e s that l i t t l e can be gained from the larger sample i n estimating the three para-meters. Error from 100 s i z e was Lamda Mu •Rho Larger 17 19 14 Same 0 1 0 Smaller 19 16 22 3T IS" . Is" F i g . 5 Comparison of percent error between sample s i z e s . These errors are of course further compounded by the d i f f e r e n t e f f e c t s that errors i n lamda and mu have on rho, e s p e c i a l l y with respect to sign. This i s noticed most of a l l i n the c a l c u l a -tions for M/M/l queues (see Tables VII and VIII) where both lamda and mu have greater error i n the larger sample s i z e , yet rho has less error o v e r a l l , as indicated i n the f i r s t run of each sample s i z e . One remembers from Chapter II that the chance of an incorrect i d e n t i f i c a t i o n of a d i s t r i b u t i o n was reduced by using the larger sample s i z e . I t w i l l be shown l a t e r i n t h i s chapter 46 that i d e n t i f i c a t i o n of the shape of the d i s t r i b u t i o n i s important i n a r r i v i n g at accurate estimates of queue length. For t h i s purpose alone the user i s j u s t i f i e d i n taking a larger sample. Step 2; Evaluation of Calculation Methods With Accurately Estimateo rH?aliir^ I t i s important to decide which of the methods shown i n the previous chapter we w i l l consider within the grasp of the average user. Having s e t t l e d t h i s , we can then t e s t to see i f any are s a t i s f a c t o r y i n consistently and accurately estimat-ing queue length. We w i l l assume that the analyst i s able to f i n d a best estimate f o r lamda and mu from the data a v a i l a b l e . From t h i s the c a l c u l a t i o n of rho follows. With t h i s the user has access to solutions to a l l the c l a s s i c a l formulae for M/M/l queues. From the variance of the service time d i s t r i b u t i o n he can compute the c o e f f i c i e n t of v a r i a t i o n and i s subsequently able to solve for M/G/l queues with the Pollaczek-Khintchine formulae. The computation required f o r a p p l i c a t i o n of the G/G/l equation for Wq (7) i s considered too complex to be used i n everyday analysis. The procedure for finding the general lower bound i s of t h i s class too. The upper G/G/l bound i s dependent on the f i r s t two moments of the i n t e r - a r r i v a l and service d i s t r i b u t i o n s only and i s thus usable by the analyst. The bounds on queues that meet the IFR condition (see Appendix I and Chapter II (12)) r e l y on the same bounds and are also 47 /included. Only the upper bound (13) for the DFR condition j i s included since the lower DFR bound i s the same as the G/G/l lower bound. In Step 1 we saw that errors i n rho are caused by errors i n predicting the estimated a r r i v a l and service rates. Before the true values of rho and queue length were revealed to t h i s writer, the estimation and c a l c u l a t i o n of queue lengths for each of the 72 runs had been, completed using the most accurate estimates of the population parameters that could be derived from the sample data. In t h i s section we w i l l evaluate the a b i l i t y of the methods described i n Chapter III to con-s i s t e n t l y f i n d accurate solutions. This can only be accomplished i f one has accurate input data. Otherwise the errors a r i s i n g from inaccurate estimation of the parameters w i l l i n t e r f e r e with the estimation of queue length. The sample runs analyzed below a l l have a rho that was confirmed to be within plus or minus f i v e percent of the true value i n the parent simulation run, when the true values were revealed. These twenty two runs of the seventy-two w i l l be considered the "accurate data". Because six estimated rho values exceeded 1.0 they were discarded and the remaining 44 runs comprise the data which w i l l be examined i n Step 3. Results from Accurate Data The operating c h a r a c t e r i s t i c s of these runs are shown i n Table X. In most cases there i s at l e a s t one method fo r which the error i n estimation i s small while the most consistent 47(a) Key to Tables X, XI, and XII Column 1 Run Number 2 Queue Type 3 Intended Rho 4 Average Queue Length from Simulation 5 Estimated Queue Length by General Method 6 Percent Error i n (5) 7 Estimated Queue Length from C l a s s i c a l Formulae 8 Percent Error i n (7) 9 IFR Lower Bound, DFR bounds marked # 10 . IFR Upper Bound, DFR bounds marked # 11 Percent Error i n the Mean of (9) and (10) compared to (4) TABLE X Summary of Queue S t a t i s t i c s from Accurate Data Sample Size 36 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) M/ M/l 0.6 0.82 0.82 0.61 0.85 3.92 0.6 9 1.39 27.23 8 M/G2/1 0.6 0.64 0.64 1. 10 0.72 13.34 0.38 1.01 9. 73 9 M/G3/1 0.9 5.37 7.50 39. 65 7.56 40.86. 7.10 8.03 40.91 19 G2/G2/1 0.7 0.50 0.66 31.60 1.63 225.80 0 .39 0.91 30.40 20 G2/G2/1 0.6 0.28 0.22 -20 .86 0.90 2 2 4.32 0.02 0.48 -10 .43 25 G3/ M/l 0.9 5.17 6.77 31.00 7.12 37 . 79 6.65 7.40 35.93 34 G3/G3/1 0.8 1.86 1.21 -34 .84 2. 49 33.93 0.97 . 1.59 -31 .02 Sample Size 100 1 f-i/ M/l 0.9 7.74 8.90 15.10 7.50 -3 .02 0.32 4.63 -68 .02 5 M/G2/1 0.9 4.10 7.83 91.05 7.24 76. 57 0.25 1.06 -84 .10 7 M /G2/1 0.7 1.07 1.12 4. 10 1.29 2 0.5 0 1.17 1.99 47.06 8 M /G2/1 0. 6 0.64 0.61 - 3 . 7 7 0.65 • 1.73 0.13 0.47 -52 .83 11 M /G3/1 • 0.7 1.18 0.90 -23 .79 1.17 - 0 . 5 9 0.17 1.15 -43 .86 12 M /G3/1 0.6 0.67 0.58 - 1 3 . 26 0.60 -10 .13 0.43 1.15 17. 36 13 G2/G3/1 0.9 3.08 2.85 - 7 . 50 6.30 104.64 2.54 3.15 ' - 7 . 4 9 16 G2/G3/1 0.6 0.3 4 0.41 21.89 0.82 143. 79 0.20 0. 70 34. 3 2 18 G2/G2/1 0.8 0.97 0.92 -5 .25 2.71 179.30 0.62 1.18 - 7 . 26 20 G2/G2/1 0.6 0.28 0.27 - 4 . 3 2 0. 84 201.08 0.05 0.51 0. 72 21 G2/ M/l 0.9 5.48 4.58 -16 .55 5.89 7.38 4.16 4.81 -18 .30 26 G3/ M/l 0.8 2.49 2.18 -12 .15 2.92 17.38 2.05 2.6 9 - 4 . 6 1 30 G3/G2/1 0.8 1.36 0.94 -30 .98 2.51 84.21 0.68 1.29 -27 .64 31 G3/G2/1 0.7 0.69 0.67 -2 .62 1.82 165.65 0.44 1.04 3 .08 36 G3/G3/1 0.6 0.43 0. 48 12.18 0.84 97.42 0.27 0. 84 29. 39 CO 49 method o v e r a l l i s the G/G/l so l u t i o n . This, unfortunately, i s one method assumed too complex for the average user. The predictions shown i n Table X w i l l be evaluated i n two groups? those with exponential i n t e r - a r r i v a l s f i r s t , followed by the general a r r i v a l queues. To make reference to the various solu t i o n methods i n the following discussion easier, the solutio n method for the M/M/l or M/G/l queue type w i l l be referred to as the exponential sol u t i o n . S i m i l a r l y the solution method for the G/G/l queue w i l l be c a l l e d the general sol u t i o n . Reference to the bounds used i n estimating queue length w i l l be made i n the normal manner, i . e . the IFR bounds. a) M/M/l and M/G/l Queues Nine of the twenty-two sample queues are discussed here and w i l l be referred to by t h e i r unique run number. Runs 4 and 1 are M/M/l and the exponential solution estimates queue length accurately i n both instances. Even i n the r e l a t i v e l y congested queue, run 1, the soluti o n i s within 3% of the simulated r e s u l t . This degree of accuracy i s expected and helps to confirm the sa t i s f a c t o r y operation of the entire experiment. The general method estimates .queue length with an acceptable degree of error although these solutions are less consistent than the exponential ones. The exponential solutions to the M/G/l queues are less s a t i s f a c t o r y although only i n runs 9 and 5 are the errors excessive. These l a t t e r runs are marked by very consistent solutions from the general method as w e l l . The consistency 50, between the general and exponential solutions i n these runs suggests that either these methods both overestimate queue length or the simulated value i s not a steady state value. In the following evaluation of the G/G/l queues, we w i l l see that the exponential method considerably overestimates queue length and i t i s suspected that t h i s may be the case i n these M/G/l queues. In view of t h i s i t i s hard to reconcile the consistency of the general and exponential estimations i n these two runs, p a r t i c u l a r l y when the error i n the general estimation i s d i s t i n c t l y higher than i n a l l other general estimations i n the twenty-two runs. Except for runs 9 and 5 the estimation of queue length for M/G/l queues i s considered acceptable by both methods although the only method used by an analyst w i l l be the exponential. The IFR bounds span the simulated solution i n only three of the nine runs under discussion. In two cases the c o e f f i c i e n t of v a r i a t i o n of the inter-=-arrival time d i s t r i b u t i o n s exceeds 1,0 and DFR bounds are computed. These s u b s t a n t i a l l y under-estimate the simulated s o l u t i o n . The bounds that f a i l to include the simulated solution within t h e i r span are both high and low with no apparent trend, and are not considered a r e l i a b l e estimator of queue length i n the exponential a r r i v a l time case. One may conclude from t h i s f i r s t set of runs that the c l a s s i c a l queueing formulae w i l l generally be r e l i a b l e i n estimating queue length i n those si t u a t i o n s f o r which they are intended, and w i l l be of p r a c t i c a l use to the average user 51 i n the business community0 Errors i n estimation may occur when service times are not d i s t r i b u t e d exponentially, but the magni-tude of these errors and any method of t h e i r p r e d i c t i o n i s not known* b) G/G/l Queues The estimated solutions to these queues are more consis-tent with each other than i n the previous section. These solu-tions are estimated within 30% of the true figure by the general method while the errors i n the IFR bound estimated solution tend to be compatable i n si z e and i n d i r e c t i o n . Table 10 shows that the general solution and the IFR bound solution estimated more accurately i n the larger sample queue than i n the smaller. We have already suggested that l i t t l e b enefit i s gained from the larger sample size i n estimating queue length since population parameters are not estimated with noticeable improvement i n accuracy. The evidence i n t h i s table tends to refute t h i s arguement and support the idea that the larger sample does permit better estimates for queue length for the general i n t e r - a r r i v a l time queue. Equation (7) from Chapter I I I f o r the expected wait i n the queue depends on the moments of the i d l e time d i s t r i b u t i o n . The same number of observations that are i n the sample go into computing the shape of t h i s d i s t r i b u t i o n so that a more accurate estimation of the i d l e time d i s t r i b u t i o n parameters w i l l r e s u l t from the larger sample. This would account for greater accuracy i n the general solution method. 52 The estimated solutions to queue length by the IFR bounds seem more r e l i a b l e i n these general queues than was found i n the exponential examples. Nine of the thirteen bounds span the simulated queue r e s u l t s , and the remaining four are not grossly inaccurate. The average, of these two bounds i s compared to the simulated figure and the percent differences are shown i n Table X. This i s a crude and u n s c i e n t i f i c method of estimation as we have no knowledge of where s p e c i f i c a l l y any solution should l i e within the span of these bounds. I t i s done here to measure how large estimation error w i l l be with a makeshift method based on these bounds. Even so, errors i n estimation of queue length are not s i g n i f i c a n t l y worse than from the general s o l u t i o n . This means that the IFR bounds can be used to give as r e l i a b l e , and i n some cases more r e l i a b l e , solutions than the general case. Reliable i n t h i s context i s within 20%. In the absence of a more accurate alternate method t h i s amount of error must be accepted, even though for most purposes i t i s not considered to be excessively i n c o r r e c t . This i s p a r t i c u l a r l y so when we are discussing f r a c t i o n a l expected queue lengths. A 20% error i n an expected queue length of say .6 i s only .12 and estimation i n t h i s case i s not seriou s l y i n error. The exponential s o l u t i o n method overestimates i n a l l cases i n t h i s second group of queues. The resultant solutions do not contribute at a l l to our finding of actual queue lengths but c e r t a i n l y do point out the necessity of accurate d i s t r i b u -t i o n i d e n t i f i c a t i o n . In a l l but three cases, at l e a s t 100% 53 error occurred. By assuming that a queueing problem i s M/M/l when i n fac t i t i s not, the analyst i s l i k e l y to considerably overestimate the r e a l queue length. From experimental runs analyzed one may conclude that provided correct i d e n t i f i c a t i o n of the i n t e r - a r r i v a l and ser-vice d i s t r i b u t i o n s i s made, and i t appears from Chapter II that t h i s can be done, an analyst can f i n d estimates of queue length (Lq) with a high p r o b a b i l i t y of less than 20% error. This, of course, assumes that population parameters, lamda and.mu, are accurately estimated. The assumption that a queue i s of the M/M/l type should be made cautiously, Overestimation errors exceed 100% i f the assumption i s f a l s e . On the other hand i f a l l queues are assumed to be G/G/l, errors from applying the IFR solu t i o n method w i l l not be as correspondingly excessive. I t appears safer to assume that a l l queues are of the general type unless some p o s i t i v e i d e n t i f i c a t i o n of the i n t e r - a r r i v a l pattern i s made. Only then i s i t advisable to apply the c l a s s -i c a l queueing formulae for exponential a r r i v a l s . Step 3; Results from Inaccurate Samples Calcula t i o n of estimated queue length from t h i s body •> of data by any of the methods, did not provide s a t i s f a c t o r y answers. A l l errors i n estimation were large, i n d i c a t i n g a re l a t i o n s h i p between errors i n estimating rho and queue length. The re s u l t s are shown i n Tables XI and XII. a) M/M/l Queues The c l a s s i c a l formulae produce exceptionally high TABLE XI Summary of Queue S t a t i s t i c s From Inaccurate Data (Sample Size 36) (1) (2) (3) (4) (5) (6) (7) (8) ( 9 ) (10) (11) 2 M/ M / l 0 . 8 2 . 96 2 . 05 - 3 0 . 80 2 . 13 - 2 5 . 27 2 . 00 2 . 77 - 1 9 . 44 3 M/ M / l 0 . 7 1 . 64 4 . 73 1 8 8 . 71 5 . 02 2 0 6 . 22 0 . 25 2 . 08 - 2 8 . 86 5 M / G 2 / 1 0 . 9 4 . 10 3 2 . 31 6 8 7 . 76 3 0 . 55 6 4 4 . 8 4 0 . 28 1 . 41 - 7 9 . 31 6 M / G 2 / 1 0 . 8 1 . 92 2 . 01 4 . 52 1 . 47 - 2 3 . 45 0 . 19 0 . 96 - 7 0 . 15 7 M / G 2 / 1 0 . 7 1 . 07 1 . 44 3 3 . 8 3 1 . 83 7 5 . 68 1 . 4 5 2 . 21 6 9 . 66 10 M / G 3 / 1 0 . 3 2 . 43 4 . 06 6 6 . 94 3 . 55 4 5 . 97 0 . 24 1 . 65 - 6 1 . 25 11 M / G 3 / 1 0 . 7 1 . 18 0 . 3 4 - 7 1 . 21 0 . 32 - 7 2 . 4 8 0 . 1 o - L O 0 . 78 - 59 . . 57 12 M / G 3 / 1 0 . 6 0 . 67 0 . 31 - 5 3 . 50 0 . 49 - 2 7 . 12 0 . 0 9 0 . 55 - 5 1 . 79 14 G 2 / G 3 / 1 0 . 8 1 . 32 1 . 68 2 7 . 42 4 . 82 2 6 5 . 0 0 1 . 43 2 . 01 3 0 . 34 15 G 2 / G 3 / 1 0 . 7 0 . 6 1 0 . 28 - 5 4 . 4 1 1 . 03 68 . 9 5 0 . 0 8 0 . 4 9 - 5 3 . 35 16 G 2 / G 3 / 1 0 . 6 0 . 34 0 . 29 - 1 2 . 72 0 . 6 3 10 2 . 37 0 . 0 3 • 0 . 4 7 - 2 6 . 92 17 G 2 / G 2 / 1 0 . 9 2 . 36 1 5 . 05 5 3 6 . 90 ' 4 6 . 84 1 8 8 2 . 27 1 4 . 7 2 1 5 . 38 5 3 6 . 8 6 18 G 2 / G 2 / 1 0 . 8 0 . 97 1 . 78 8 3 . 63 5 . 09 42 3 . 79 1 . 39 . 2 . 0 0 7 4 . 41 21 G 2 / M / l 0 . 9 5. 48 0 . 79 - 3 5 . 52 1 . 5 7 - 7 1 . 30 0 . 54 0 . 98 - 8 6 . 13 22 G 2 / M / l 0 . 8 1 . 86 0 . 93 - 5 0 . 24 1 . 66 - 1 0 . 8 3 0 . 6 9 1 . 22 - 4 8 . 37 23 G 2 / M / l 0 . 7 0 . 97 1 . 9 8 1 0 2 . 87 2 . 78 1 85 . 5 4 1 . 75 2 . 40 1 1 3 . 28 2k G 2 / M / l 0 . 6 0 . 52 0 . 20 - 6 1 . 27 0 . 64 2 3 . 51 0 . Ob 0. 47 - 5 0 . 19 2 7 G 3 / M / l . 0 . 7 1 . 17 2 . 77 1 3 7 . 50 4 . 58 2 9 2 . 29 2 . 0 5 3 . 3 i 1 5 5 . 18 28 G 3 / M / l 0 . 6 0 . 65 0 . 35 - 4 7 . 18 0 . 51 - 2 1 . 57 0 . 25 0 . 74 - 2 4 . 66 29 G 3 / G 2 / 1 0 . 9 3 . 52 1 . 42 - 6 0 . 89 3 . 48 - 4 . 00 1 . 17 1 . 8 1 - 5 8 . 88 30 G 3 / G 2 / 1 0 . 8 1 . 36 0 . 68 - 5 0 . 29 1 . 56 1 4 . 54 0 . 36 0 . 9 1 - 5 3 . 52 31 G 3 / G 2 / 1 0 . 7 0 . 69 1 0 . 11 1 3 7 1 . 03 2 1 . 24 2 9 9 1 . 41 9 . 5 2 1 0 . 35 1 3 4 6 . 29 32 G 3 / G 2 / 1 0 . 6 0 . 37 0 . 31 - 1 6 . 25 0 . 56 5 1 . 76 0. 0 6 0 . 56 - 1 6 . 30 35 G 3 / G 3 / 1 0 . 7 0 . 80 0 . 66 - 1 7 . 45 1 . 14 4 3 . 54 0 . 40 0 . 99 - 1 2 . 19 36 G 3 / G 3 / 1 0 . 6 0 . 4 3 0 . 32 - 2 5 . 76 0 . 65 5 2 . 9 5 0 . 13 0 . 62 - 1 2 . 88 <J1 t t a . TABLE XII Summary of Queue S t a t i s t i c s From Inaccurate Data (Sample Size 100) (1) (2) (3) (4) (5) (6) 3 M/ M/l 0.7 1.64 1.09 -33.37 4 M/ M/l 0.6 0.82 0. 79 -2.82 6 M/G2/1 0.8 1.92 1.42 -25.90 .9 M/G3/1 0.9 5.37 . 1.85. -65.46 10 M/G3/1 0.8 2. 43 4.64 90.71 14 G2/G3/1 0.8 1.32 0.85 -35.38 15 G2/G3/1 0.7 0.61 1.11 81.86 17 G2/G2/1 0.9 2.36 1.01 -57.17 19 G2/G2/1 0.7 0.50 1.56 212.5 0 22 G2/ M/l ' 0.8 1.86 2.09 11.85 23 G2/ M/l 0.7 0.97 0.26 -72.82 2k G2/ M/l 0.6 0.52 0.23 -55.88 25 G3/ M/l 0.9 5.17 232.39 4396.79 27 G3/ M/l 0.7 1.17 4.53 2 8 7.76 28 G3/ M/l 0.6 0.65 0.31 -52.37 32 G3/G2/1 0.6 0.37 0.32 -12.20 33 G3/G3/1 0.9 3.67 21.26 479.92 3k G3/G3/1 0.8 1.86 15. 8 8 8 0 8.89 35 G3/G3/1 0.7 0.80 . 0.39 -50.88 (7) (8) (9) (10) (11) 1. 09 -33. 43 0. 38 1. 52 -26. 63 1. 0 8 32. 31 0. 83 1. 5 2 43. 88 1. 53 -20. 49 0. 18 0. 80 -74. 54 1. 80 -56. 42 0. 20 1. 63 -82. 94 3. 50 44. 12 0. 26 1. 78 -53. 20 1. 78 35. 15 0. 60 1. 15 -33. 33 2. 73 340. 24 0. 86 1. 44 87. 9 9 3. 94 66. 57 0. 76 1. 29 -56. 58 4. 11 722. 40 1. 28 1. 93 221. 10 4. 52 142. 31 1. 90 2. 47 17. 32 0. 52 -46. 77 0. 14 0. 53 -65. 49 0. 43 -17. 73 0. 08 0. 46 -48. 07 286 . 16 5437 . 11 231. 52 232 . 54 4383 . 81 7. 18 514. 38 4. 29 4. 99 297. 39 0. 59 -9. 4 7 0. 17 0. 66 -36. 49 0. 63 70. 73 0. 0 6 0. 58 -12. 47 38. 73 9 56 . 36 20. 95 21. 72 482. 00 30. 76 1556 . 3 8 16. 72 17. 51 821. 54 0. 74 . -6. 41 0. 20 0. 74 -40. 45 queue lengths when rho approaches one, As a r e s u l t , over-estimation of rho at high values provides t h e o r e t i c a l l y correct but r e s u l t s impossible i n p r a c t i c a l s i t u a t i o n s . Yet underestimation of rho at lower values may provide almost no e f f e c t at a l l on queue length. I t i s v i r t u a l l y impossible to draw consistent conclusions as to the size of error from the M/M/l queue r e s u l t s , i n the absence of any apparent trend, other than to say that a l l estimates were increasingly i n -accurate as. rho was estimated with greater error, b) G/G/l Queues The need for an accurate estimation of rho i s i n d i -cated i n these runs too. The r e l a t i o n s h i p between errors has a more consistent trend i n the general a r r i v a l queues 0 In each run shown i n Tables XI and XII for t h i s class of queues, the sign of the estimation error i n rho and i n queue length i s the same. L i t t l e use can be made of t h i s f a c t i n reducing p r e d i c t i o n errors when rho error i s unknown. I t i s i n t e r e s t i n g to note that even i n terms of errors, the G/G/l queue tends to behave with greater s t a b i l i t y than the M/M/l queue. In none of the runs with inaccurately found rho values did errors compensate for themselves to produce good estimates fo r queue length from poor data. The occurence of accurate queue p r e d i c t i o n i n t h i s case would, of course, be by accident. One cannot conclude that t h i s form of accident would never occur; one can suggest that i t i s very u n l i k e l y , based on the runs generated i n t h i s experiment. In cases where a poor pr e d i c t i o n of rho i s recognized 57 by an afvalyst because of his experience and his f e e l for the system some compensation for expected error can be made. This may be i n the form of additional sampling to provide some addi-t i o n a l comparative estimates of rho or i t may be merely an adjustment based on i n t u i t i o n . The analyst i s advised i n t h i s s i t u a t i o n to compute solutions for a range of rho values to determine the behaviour of the s p e c i f i c queue i n question. He then can determine the e f f e c t of erroneous rho values. Summary Ess e n t i a l to successful analysis of any queueing problem are accurate predictions of population parameters. E a s i l y applied methods e x i s t for finding of adequate solutions to queueing problems provided the parameters used are accurate to approximately 5% of the true value. I f these parameters are not good predictions even the expert w i l l f a i l to ar r i v e at s a t i s -factory answers. The method of soluti o n for M/M/l queues, the c l a s s i c a l queueing formulae, are shown to provide accurate predictions of queue length provided the exponential assumption i s correct. Misapplication of these formulae w i l l seriously overestimate queue length. The IFR bounds while not p a r t i c u l a r l y s a t i s -factory for the M/M/l s i t u a t i o n do give as accurate a solution as any of the other methods considered when applied to G/G/l queues. CHAPTER V AN APPLICATION AND CONCLUSION The actual process that an analyst could use i s exemplified here. This i s followed by a reca p i t u a l a t i o n of our findings. An Application Let us assume that a service s t a t i o n operator also o f f e r s a car washing service on his l o t . Because of the nature of the extra services he o f f e r s i n the washing and cleaning of cars, such as vacuuming, tar removal, and engine cleaning, cars to not move through his plant d e t e r m i n i s t i c a l l y as i s usual. Let us assume that he thinks he w i l l lose customers i f they are forced to wait i n a queue of three cars or longer on the average. He needs to know how long the average queue of cars w i l l be and how long a customer w i l l spend on the average getting his car washed. The service s t a t i o n operator has spe c i a l cards that are stamped by a time clock when a car enters the wash and are stamped again when i t leaves. To c o l l e c t the data he needs for his queueing analysis he records the time of a r r i v a l on the card when a car joins the queue for washing. From the three times recorded for each car he computes the time each car spent i n the queue and i n the wash. These are the i n t e r -a r r i v a l and service times. "The mean i n t e r - a r r i v a l and service times are easy to 59 compute. By squaring each of the i n t e r - a r r i v a l and service times, summing them, and d i v i d i n g by the number of cars observed, the variance i s found. Let us suppose that the values tfound i n t h i s example ares a) average i n t e r - a r r i v a l time 10 minutes, with variance 54.4 minutes and, b) average service time 6.45 minutes, with variance 23.7 minutes. The parameters lamda and mu are the r e c i p r o c a l s of the averages shown above. X = .1 a r r i v a l s per minute. xi = .155 services per minute. Rho i s then computed p = X = .1 = «64; V .155 t h i s value being the i n t e n s i t y of use of the f a c i l i t y expressed as a f r a c t i o n of one. I d e n t i f i c a t i o n of the type of each d i s t r i b u t i o n i s the next step i n t h i s analysis. Reference to Appendix II shows pre-computed data with which to compute the t e s t s t a t i s t i c and the • method of computation. Assume that the following c o r r e l a t i o n c o e f f i c i e n t s were computed; a) i n t e r - a r r i v a l d i s t r i b u t i o n .86 b) service d i s t r i b u t i o n .87 This would indicate that both d i s t r i b u t i o n s are not exponentially d i s t r i b u t e d and the IFR bound method w i l l be used. To v e r i f y that both d i s t r i b u t i o n s do have the IFR property, the t e s t mentioned i n Appendix I w i l l be used. The c o e f f i c i e n t s of 6 0 v a r i a t i o n are computed with, C 2 = variance mean"*" The example c o e f f i c i e n t s are; 54 e4 a) i n t e r - a r r i v a l d i s t r i b u t i o n H H T " ~ «544 b) service d i s t r i b u t i o n 23.7 r 6.45 = .570, therefore both d i s t r i b u t i o n s have the IFR property. Using equation (12) of Chapter III the IFR bounds are found; J = Ca 2 + X i g l = (.544) + (.1)(.1)(23.7) " T T I ^ P T " 9 r2TTTTrrri"6i .781 = .072 = 10.82 Lower bound on queue length: * J " ( P 2 + Ca 2 ) = i 082 - .64 •+ .-54.4 LB = (2)" " * ~ ~TTf— = 1.082 - .592 .590 Upper bound on queue length: UB = XJ = 1.082 The average of these bounds i s .84 and t h i s i s assumed to be the estimate of queue length. Using the relationships between queue length and time spent queueing, the service s t a t i o n operator can compute the t o t a l time that a customer w i l l spend having his car washed on the average. 61 From Wq = Lq_ = ,84 = 8,4 we f i n d the average wait i n queue A .1 . to be 8,4 minutes. The t o t a l time spent i n the car wash i s then W = Wq + 1 = 8.4 +6.45 = 14.85 minutes. I t takes y approximately 15 minutes on the average to be processed by th i s f a c i l i t y . Conclusions Successful a p p l i c a t i o n of queue length estimation methods i s dependent upon the i d e n t i f i c a t i o n of exponentially d i s t r i b u t e d inter«*arrival and service time d i s t r i b u t i o n s . I d e n t i f i c a t i o n i s made d i f f i c u l t by the lack of a consistent te s t which detects exponentiality i n small samples, A t e s t i s developed i n t h i s thesis from a well known graphical procedure. This t e s t consistently detects samples that are drawn from exponential d i s t r i b u t i o n s and rejects those that are not. Samples of 36 and 100 observations were tested. An a t t r a c t i v e feature of t h i s t e s t i s i t s ease i n ap p l i c a t i o n . When i d e n t i f i c a t i o n i s possible, appropriate methods for estimating queue length are accurate for most p r a c t i c a l a p p l i c a t i o n s . C l a s s i c a l queueing methods when applied to M/M/l / and M/G/l queues provide s a t i s f a c t o r y estimates but serious overestimation r e s u l t s from t h e i r a p p l i c a t i o n to G/G/l and G/M/l queues. Thus the assumption that a queue i s exponential must be made with care. The method f o r successful queue length p r e d i c t i o n i n general i s considered too complex for p r a c t i c a l a p p l i c a t i o n and IFR and DFR bounds are a s a t i s f a c t o r y replacement. The average of the upper and lower bounds i n IFR case provides a pred i c t i o n that i s as accurate as the solution from the complex general c a l c u l a t i o n . Regardless of which method i s chosen for estimation inaccurate p r e d i c t i o n of queue length w i l l r e s u l t from inaccurate estimation of rate parameters of the sampled population d i s t r i b u t i o n s . 63 BIBLIOGRAPHY Barlow, E, Richard and Frank Proschan, Mathematical Theory of R e l i a b i l i t y , New York, John Wiley & Sons, Inc., 19671 p. 12-35. Cooper, B.E, S t a t i s t i c s for Experimentalists, Braunschweig, Germany, Pergamon Press, 1969, pp.366. Cox, D.R., and Walter L. Smith, Queues, Methuen's Monographs on Applied Probability~and S t a t i s t i c s , London," Metheun & Co. Ltd., 1967, pp .180. Goddard, L.S., Mathematical Techniques of Operational Research, New York, Pergamon Press, ITlT3~7~°pT85-IT0. H i l l i e r , Frederick S., and Gerald J . Lieberman, Intro-duction to Operation Research, San Francisco, C a l i f . , , Holden-Day, Inc., 1968, p.285-306. Marshall, Kneale Thomas, Some Inequalities for Single Server Queues, Berkeley, Operation Research Center, College of Engineering, University of C a l i f o r n i a , 1966, p.1-29. P a r i , Boris, Basic S t a t i s t i c s , Garden C i t y , New York, Doubleday & Company Inc., 1967, p.223-244. Parzen, Emanuel, Modern P r o b a b i l i t y Theory and i t s Applications, New York, John Wiley & Sons, Inc., 1965, p.371-374. Smith, L. Walter and Williem E. Wilkenson, eds. Proceedings of the Symposium on Conjestion Theory, Held at the University of North Carolina at Chapel H i l l , Aug.24-26, 1964. Chapel H i l l , The University of North Carolina Press, 1965, p.137-157. Snedecor, George and William G. Cochran, S t a t i s t i c a l Methods, Ames, Iowa, The Iowa State University Press, Sixth ed. 1967, p.231-238, Wagner, Harvey M, P r i n c i p l e s of Operations Research,with Applications to Managerial Decisions, Englewood C l i f f s , New Jersey, Prentice H a l l Inc., 1969, p.8-64. APPENDICES 64 APPENDIX I INCREASING AND DECREASING FAILURE RATE The information contained i n t h i s appendix i s taken from Barlow and Proschans Mathematical Theory of R e l i a b i l i t y , (John Wiley & Sons, 1967) which may be used as a more extensive reference. I t has been found that c e r t a i n objects tend to f a i l , as time progresses, with increasing or decreasing p r o b a b i l i t y . Phenomena with increasing f a i l u r e rate (IFR) f a i l i n the period {t, t+dt] over time (t) with increasing p r o b a b i l i t y . Those with decreasing f a i l u r e rate (DFR) f a i l with less p r o b a b i l i t y over time. Applications are found, i n the case of IFR i n the computation of mortality tables and empirical evidence suggests DFR i s found i n most s o l i d state e l e c t r o n i c components. When applied to queueing, IFR i s used to mean that the p r o b a b i l i t y of an a r r i v a l during [t, t+dt] increases over time. Conversely DFR implies a decreasing p r o b a b i l i t y . Hence r e f e r -ence w i l l be made to IFR/G/1 and DFR/G/1 queues, A S t a t i s t i c a l Test for IFR and DFR The c o e f f i c i e n t of v a r i a t i o n (s.d./mean) for IFR d i s t r i b u t i o n s i s less than one and for DFR i s greater than one. A d i s t r i b u t i o n with a c o e f f i c i e n t of v a r i a t i o n equal to one i s exponentially d i s t r i b u t e d and displays both IFR and DFR properties. I d e n t i f i c a t i o n thus displays both IFR and DFR properties. I d e n t i f i c a t i o n of these properties can be made by 65 comparing a d i s t r i b u t i o n ' s c o e f f i c i e n t o f v a r i a t i o n t o one and d r a w i n g t h e a p p r o p r i a t e c o n c l u s i o n . 66 APPENDIX II In t h i s appendix we w i l l t e s t two samples of data to present i n d e t a i l the t e s t for exponentiality using the co r r e l a t i o n c o e f f i c i e n t . This procedure uses pre-computed data for comparison with the observed data. The pre-computed figures are shown i n Table XIII and are arranged for use with sample sizes of 25, 35, 50, 75, and 100. The sum, sum of squares, mean and variance are included. These figures are natural logarithms of the s t a t i s t i c for the c o r r e l a t i o n c o e f f i c i e n t t e s t shown i n Chapter II and represent the' ordinate values. For example Size n, the numbers i n Table XIII are computed from ded for 35 successive a r r i v a l s of customers i n a queue. They should be read by column for the correct sequence or occur-rence. y = lnf The following times are the i n t e r - a r r i v a l times recor-15.59 17 .37 5.83 4.13 .60 1.88 65 25.77 .74 1.52 7.07 4.04 3.16 7.41 9.43 4.10 26.64 10.57 5.36 1.05 17.37 3.09 20.61 14.72 11.65 34.40 3.73 .46 2.75 29.71 4.92 27.08 3.87 .99 5.94 Before a c t u a l l y c a l c u l a t i n g the c o r r e l a t i o n c o e f f i -cent, several summations are to be found that make i t easier 67 Rep-resenting the s p e c i f i c i n t e r a r r i v a l times by x we compute, Ex = 333.24, Ex 2 = 6310.0, Exy = 594.8, Ex = 9.52 n where y i s defined above. Calculating the c o r r e l a t i o n c o e f f i c i e n t using the y values f o r sample s i z e 35 taken from Table XIII we f i n d , r = Exy - xEy /(Ex 2 - xTx) (Ey 2 - yiy.) = 594.8 - (9.52) (33.28) _ _ _ • (6310.0 - (9.52) (333.24)) (56.98 - (.95) (33.28)) = 277.968 281.924 = .986 Since t h i s figure exceeds .93 we assume that the i n t e r a r r i v a l time d i s t r i b u t i o n i s exponential. The service times corresponding to the inter-arrival times are l i s t e d by column i n order of occurrence. 5.04 4.62 12.58 13.01 2.93 .28 17.44 9.41 2.46 10.24 11.12 15.15 4.08 15.69 16.90 .01 12.54 5.04 14.92 3.94 .77 4.42 16.27 13.42 10.47 17.36 5.27 7.90 14.63 14.43 7.07 1.71 11.66 3.78 14.27 above we compute, = 321.7, x = 4033.1 , xy = 452.8, _x = 9.19 n and using the same y values as above f i n d for the co r r e l a t i o n c o e f f i c i e n t , r = 56.98 - (9.19)(33.28) • (4033.1 - (9.19) (321.7)) (56.98 - (. 95) (33.28)) 68 = 146o82 165,06 = .889 This r i s less than „93 and we conclude that the service times are not exponentially d i s t r i b u t e d . This queue i s i d e n t i f i e d as M/G/l, TABLE XIII Pre-computed Ordinate Values for the Correlation C o e f f i c i e n t Test Sample Size 25 Sample Size 0.039 0.028 0.080 0.057 0.123 0.087 0.16 7 0.113 0.214 0.150 ' 0 . 262 0 . 182 0.314 0.216 0. 368 ..0 . 251 0.42 5 0.2 88 0.486 0.325 0.5 50 0.3G5 0.619 0.405 0.693 0.448 0.773 0.492 0.860 0.539 0.95 6 0.588 1.061 0.6 39 1.17 9 0.6 93 1.312 0.750 1.466 0.811 1.649 0.875 1.872 0.944. 2.159 1.019 2.565 1.099 3.258 1.186 1.281 Zy = 23,449 J Zy 2 = 38.698 y = .938 1.386 1. 50 4 638 1.79 2 1. 974 2. 197 2.485 2.890 3.584 Zy = 33.287 Zy 2 = 56.987 y = .951 TABLE X I I I (cont'd) Sample S i z e 50 0.020 0.713 0 . 0 4 0 0.754 0.061 0.796 0.082 0 . 8 41 0.103 0.887 0.12 5 0.936 0.148 0.987 0.171 1.041 0. 194 1.099 0.218 • 1.159 0.2 43 1.2 24 0.268 1.293 0.294 1.367 0.321 1.447 0.348 1.534 0. 376 1.629 0.405 1.735 0.435 1.852 0. 466 1.986 0.498 2.140 0.531 2.322 0.565 2. 546 0.600 2.833 0.636 3.239 0.674 3.932 Zy = 48.113 Zy 2 = 85.038 y = .962 TABLE XIII (cont 8d) Sample Size 7 5 0.013 0.720 0.027 • 0 .747 0 . 0 ii 0 0.775 0.054 0.80 4 0.068 0.834 . 0.082 0 . b 6 5 0.097 0. 89 7 0.111 0.9 30 - 0.126 0.963 0. I ' l l 0.9 99 0. 156 1.035 0.172 1.073 0.188 1.112 0. 2 04 1.153 0.2 20 1.19 5 0.236 1.240 0.253 1.286 0.2 70 1.3 35 0.288 1.386 0.305 1.440 0.323 1.498 0.342 ' 1.558 0.360 ••' 1.623 0. 379 1.692 0.399 1.766 0.419 1.846 0.439 1.933 0.460 2.028 0.481 2.134 0.502 2.251 0.524 2.335 0.547 2.539 0.570 2.721 0.593 2.944 0.617 3.232 0.642 3.6 38 0.667 4.331 0.693 Zy = 72.914 Zy 2 = 132.656 y = .972 72 TABLE XIII (cont'd) Sample Size 100 0 . 0 1 0 0 . 4 2 5 1 . 1 1 9 0 . 0 2 0 ' 0 . 4 4 1 1 . 1 4 9 0 . 0 3 0 0 . 4 5 6 1 . 1 8 1 0 . 0 4 0 • 0.4 72 1 . 2 1 4 0 . 0 5 1 0 . 4 8 8 1 . 2 4 8 0. 0 6 1 0 . 5 0 4 . 1 . 2 8 3 0 . 0 7 2 0 . 5 2 1 1 . 3 1 9 0 . 0 8 3 0 . 5 3 8 1 . 3 5 7 0 .09 3 0 . 5 5 5 1. 3 9 6 0 . 1 0 4 0 . 5 7 2 1 . 4 3 7 0 . 1 1 5 0.59 0 1 . 4 3 0 0 . 1 2 6 - 0 . 6 0 8 1 . 5 2 4 0 . 1 3 8 0 . 6 2 6 1 . 5 7 1 0 . 1 4 9 0 . 6 4 5 1 . 6 1 9 0 . 1 6 1 0 . 6 6 4 1 . 6 7 1 0 . 1 7 2 0 . 6 8 3 1 . 7 2 5 0 . 1 8 4 0 . 7 0 3 1 . 7 8 2 0 . 1 9 6 0 . 7 2 3 1 . 8 4 3 0 . 2 0 8 0.7 44 1 . 9 0 7 0 . 2 2 1 0 . 7 6 5 1 . 9 7 6 0 . 2 3 3 0 . 7 8 6 2 . 0 5 0 0 . 2 4 6 0 . 8 0 8 2 . 1 3 0 0 . 2 5 8 0 . 8 3 1 2 . 2 1 7 0 . 2 7 1 0 . 8 5 4 2 . 3 1 3 0 . 2 8 4 0 . 8 7 7 2 . 4 1 8 0 . 2 9 8 0 . 9 0 2 2 . 5 3 6 0 . 3 1 1 0 . 9 2 6 2. 6 6 9 0 . 3 2 5 0 . 9 5 2 2 . 8 2 3 0 . 3 3 8 0 . 9 7 8 3 . 0 0 6 0 . 3 5 2 1 . 0 0 4 3 . 2 2 9 0. 3 6 7 1 . 0 3 2 3 . 5 1 7 0 . 3 8 1 1 . 0 6 0 3 . 9 2 2 0 . 3 9 6 1 . 0 8 9 4 . 6 1 5 0.410 Ey = 97.772 Ey 2= 180.862 y = .978
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Experimental evaluation of queueing theory
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Experimental evaluation of queueing theory Goyder, David 1970
pdf
Page Metadata
Item Metadata
Title | Experimental evaluation of queueing theory |
Creator |
Goyder, David |
Publisher | University of British Columbia |
Date Issued | 1970 |
Description | This thesis examines methods for predicting queue length of single server queues in order to evaluate how the practitioner may achieve greatest accuracy. Because accuracy is dependent on the correct estimation of the rate parameters of the population distributions and the choice of the appropriate method of prediction, the effects of errors in both of these are examined. A computer simulation model written in GPSS/360 is used to create a real world from which data is drawn and where long run performance represents the correct solution. For four values of rho nine simulations are run, each with a unique combination of inter-arrival and service time distributions. In each of the 36 runs 10,000 arrivals are generated from which two samples of size 36 and 100 are taken and from which the generated queue statistics form the standard. A statistical analysis is used to detect samples taken from exponential distributions. The lack of a suitable test for small samples led to the development of a test based on the correlation coefficient of the sample times and pre-computed standard data. Estimates for queue length are found with classical queueing formulae and solution methods suggested by Marshall. These predictions are done without prior knowledge of rate parameters and queue type which are estimated from the samples. Then the estimated solutions are compared to the real world solution derived from the simulation. Estimation error for each method is measured and conclusions are drawn as to their accuracy in predicting queue length. It is found that accurate queue length estimation is possible using methods that can be applied without a great deal of prior mathematical knowledge. The classical formulae are accurate only when applied to queues with exponential inter-arrival times and are found to overestimate when applied to other queue types. The Increasing Failure Rate (IFR) bounds on queue length provide a satisfactory method of estimation for the general class of queues. |
Subject |
Queuing theory |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-05-09 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0093315 |
URI | http://hdl.handle.net/2429/34370 |
Degree |
Master of Science in Business - MScB |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1970_A4_5 G69.pdf [ 4.79MB ]
- Metadata
- JSON: 831-1.0093315.json
- JSON-LD: 831-1.0093315-ld.json
- RDF/XML (Pretty): 831-1.0093315-rdf.xml
- RDF/JSON: 831-1.0093315-rdf.json
- Turtle: 831-1.0093315-turtle.txt
- N-Triples: 831-1.0093315-rdf-ntriples.txt
- Original Record: 831-1.0093315-source.json
- Full Text
- 831-1.0093315-fulltext.txt
- Citation
- 831-1.0093315.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0093315/manifest