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. 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.

2 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. 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.

3 We will begin by reviewing the necessary probabilistic background neededto understand the THEORY . 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 .

4 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. 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.

5 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!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.

6 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. 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.

7 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. 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.

8 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. For a service that requires many different phases of service (forexample, scanning groceries, paying for groceries, and bagging the groceries), anErlang distribution can be used with the parameterkequal to the number ofdifferent phases of define the number of people located in a queu-ing system, either waiting in line or in service, to be the state of the system attimet.

9 Att= 0, the state of the system is going to be equal to the number ofpeople initially in the system. The initial state of the system is noteworthy becauseit clearly affects the state at some futuret. Knowing this, we can definePij(t) asthe probability that the state at timetwill bej, given that the state att= 0 wasi. For a larget,Pij(t) will actually become independent ofiand approach a limit j. [W 1053] This limit is known as the steady -state of statej. Generally, if oneis looking at the steady -state probability ofj, it is incredibly difficult to determineQUEUING THEORY5 Figure a single-server birth-death process, births add oneto the current state and occur at rate . Deaths subtract one fromthe current state and occur at rate .the steps of arrivals and services that led up to the steady state.

10 Likewise, startingfrom a smallt, it is also very difficult to determine when exactly a system will reachits steady state, if it exists. Thus, for simplicity s sake, when we study a queuingsystem, we begin by assuming that the steady -state has already been birth-death process is a process wherein the system s state at anytis a nonneg-ative integer. The variable jis known as the birth rate at statejand symbolizesthe probability of an arrival occurring over a period of time. The variable jisknown as the death rate at statejand symbolizes the probability that a completionof service occurs over a period of time. Thus, births and deaths are synonymouswith arrivals and service completions respectively. A birth increases the state byone while a death decreases the state by one. We note that 0= 0, since it mustnot be possible to enter a negative state.