QUEUING THEORY

1 QUEUING THEORYRYAN paper defines the building blocks of and derives basic queuingsystems. It begins with a review of some probability THEORY and then definesprocesses used to analyze QUEUING systems, in particular the birth-death pro-cess. A few simple queues are analyzed in terms of steady-state derivationbefore the paper discusses some attempted field research on the THEORY is a branch of mathematics that studies and models the act ofwaiting in lines. This paper will take a brief look into the formulation of queuingtheory along with examples of the models and applications of their use.

2 The goalof the paper is to provide the reader with enough background in order to prop-erly model a basic QUEUING system into one of the categories we will look at, whenpossible. Also, the reader should begin to understand the basic ideas of how to de-termine useful information such as average waiting times from a particular first paper on QUEUING THEORY , The THEORY of Probabilities and TelephoneConversations was published in 1909 by Erlang, now considered the fatherof the field. His work with the Copenhagen Telephone Company is what promptedhis initial foray into the field. He pondered the problem of determining how manytelephone circuits were necessary to provide phone service that would prevent cus-tomers from waiting too long for an available circuit.

3 In developing a solution tothis problem, he began to realize that the problem of minimizing waiting time wasapplicable to many fields, and began developing the THEORY s switchboard problem laid the path for modern QUEUING THEORY . Thechapters on QUEUING THEORY and its applications in the book operations research :Applications and Algorithms by Wayne L. Winston illustrates many expansions12 RYAN BERRYof QUEUING THEORY and is the book from which the majority of the research of thispaper has been the second section of this paper, we will begin defining the basic queuingmodel. We will begin by reviewing the necessary probabilistic background neededto understand the THEORY .

4 The we will move on to discussing notation, queuingdisciplines, birth-death processes, steady-state probabilities, and Little s queuingformula. In the next section we will begin looking at particular QUEUING will study the population size, the customer capacity, the number of servers, self-service queues, and the machine repair model, to name a few. We will be calculatingsteady-state probabilities and waiting times for the models when possible, while alsolooking at examples and applications. We will conclude the paper by taking a peekat some field research studying the QUEUING system at a Basic QUEUING ModelTo begin understanding queues, we must first have some knowledge of probabil-ity THEORY .

5 In particular, we will review the exponential and Poisson and Poisson Probability exponentialdistribution with parameter is given by e tfort 0. IfTis a randomvariable that represents interarrival times with the exponential distribution, thenP(T t) = 1 e tandP(T > t) =e distribution lends itself well to modeling customer interarrival times orservice times for a number of reasons. The first is the fact that the exponentialfunction is a strictly decreasing function oft. This means that after an arrival hasoccurred, the amount of waiting time until the next arrival is more likely to besmall than large.

6 Another important property of the exponential distribution iswhat is known as the no-memory property. The no-memory property suggests thatthe time until the next arrival will never depend on how much time has alreadypassed. This makes intuitive sense for a model where we re measuring customerarrivals because the customers actions are clearly independent of one s also useful to note the exponential distribution s relation to the Poissondistribution. The Poisson distribution is used to determine the probability of aQUEUING THEORY3certain number of arrivals occurring in a given time period. The Poisson distributionwith parameter is given by( t)ne tn!

7 Wherenis the number of arrivals. We find that if we setn= 0, the Poissondistribution gives use twhich is equal toP(T > t) from the exponential relation here also makes sense. After all, we should be able to relate theprobability that zero arrivals will occur in a given period of time with the probabilitythat an interarrival time will be of a certain length. The interarrival time here, ofcourse, is the time between customer arrivals, and thus is a period of time withzero these distributions in mind, we can begin defining the input and outputprocesses of a basic QUEUING system, from which we can start developing the Input begin modeling the input process, we definetiasthe time when theith customer arrives.

8 For alli 1, we defineTi=ti+1 tito betheith interarrival time. We also assume that allTi s are independent, continuousrandom variables, which we represent by the random variableAwith probabilitydensitya(t). Typically,Ais chosen to have an exponential probability distributionwith parameter defined as the arrival rate, that is to say,a(t) = e is easy to show [W 1045] that ifAhas an exponential distribution, then forall nonnegative values oftandh,P(A > t+h|A t) =P(A > h)This is an important result because it reflects the no-memory property of the ex-ponential distribution, which is an important property to take note of if we remodeling interarrival distribution the can be used to model interarrival times (if the exponen-tial distribution does not seem to be appropriate) is the Erlang distribution.

9 AnErlang distribution is a continuous random variable whose density function relies4 RYAN BERRYon a rate parameterRand a shape parameterk. The Erlang probability densityfunction isf(t) =R(Rt)k 1e Rt(k 1)! Output like the input process, we start analysis of theoutput process by assuming that service times of different customers are indepen-dent random variables represented by the random variableSwith probability den-sitys(t) = e t. We also define as the service rate, with units of customers perhour. Ideally, the output process can also be modeled as an exponential randomvariable, as it makes calculation much simpler.

10 Imagine an example where fourcustomers are at a bank with three tellers with exponentially distributed servicetimes. Three of them receive service immediately, while the fourth has to wait forone position to clear. What is the probability that the fourth customer will be thefinal one to complete service?Due to the no-memory property of the exponential distribution, when the fourthcustomer finally steps up to a teller, all three remaining customers have an equalchance of finishing their service last, as the service time in this situation is notgoverned by how long they have already been served. Thus, the answer to thequestion is 1 , the exponential distribution does not always represent servicetimes accurately.