Queue theory book pdf

Among his research publications and books, Dr. Dimitar P. His research interests include differential and difference equations and queueing theory. The author of numerous research papers and three books, Dr. Waiting in lines is a staple of everyday human life. Without really noticing, we are doing it when we go to buy a ticket at a movie theater, stop at a bank to make an account withdrawal, or proceed to checkout a purchase from one of our favorite department stores.

Oftentimes, waiting lines are due to overcrowded, overfilling, or congestion; any time there is more customer demand for a service than can be provided, a waiting line forms.

Queuing systems is a term used to describe the methods and techniques most ideal for measuring the probability and statistics of a wide variety of waiting line models. Numerical examples are presented to guide readers into thinking about practical real-world applications, and students and researchers will be able to apply the methods learned to designing queuing systems that extend beyond the classroom.

Very little has been published in the area of queuing systems, and this volume will appeal to graduate-level students, researchers, and practitioners in the areas of management science, applied mathematics, engineering, computer science, and statistics. The Contributors Are :David D. Athreya; T. Subba Rao; H. Tijms; J. Hogenkamp; U. Narayan Bhat; Deepankar Medhi; D. Logothetis; V. Mainkar; K. Trivedi; M. Chaudhry; U.

Gupta; M. Mazumdar; S. Li; F. Chong; S. Sim; J. With its rigorous coverage of basic material and extensive bibliography of the queueing literature, the work may also be useful to applied scientists and practitioners as a self-study reference for applications and further research. This book has brought a freshness and novelty as it deals mainly with modeling and analysis in applications as well as with statistical inference for queueing problems.

With his 40 years of valuable experience in teaching and high level research in this subject area, Professor Bhat has been able to achieve what he aimed: to make [the work] somewhat different in content and approach from other books. This can be calculated iteratively using 2. Alternatively, B 4, 2 can be calculated from 2. The average number in queue Lq can be calculated using 2. This model is often referred to as the ampleserver problem.

A self-service situation is a good example of the use of such a model. We make use of the general birth -death results with. A and J. The value of. L is not restricted in any way for the existence of a steady-state solution. It also turns out we show this in Section 5. That is, Pn depends only on the mean service time and not on the form of the service-time distribution. It is not surprising that this is true here in light of a similar result we mentioned previously for M I M lei c, since Pn of 2.

The expected system size is the mean of the Poisson distribution of 2. L, and the waiting-time distribution function Wet is identical to the service-time distribution, namely, exponential with mean 1 I J. It has found from past surveys that people turning on their television sets on Saturday evening during prime time can be described rather well by a Poisson distribution with a mean of IOO,OOOIh.

Surveys have also shown that the average person tunes in for 90 min and that viewing times are approximately exponentially distributed. We now treat a problem where the calling population is finite of size M, and future event occurrence probabilities are functions of the system state.

A typical application of this model is that of machine repair, where the calling population is the machines, an arrival corresponds to a machine breakdown, and the repair technicians are the servers. Because of these assumptions, we can use the birth-death theory developed previously. For the machine repair problem, "number in system" corresponds to the number of broken machines. Abate and Whitt point out that computing values with 2. We can show, using properties of the Bessel functions, that 2.

However, since transient solutions require solving sets of differential equations, numerical methods can often be successfully employed. We treat this topic in some detail in Chapter 8, Section 8. A busy period begins when a customer arrives at an idle channel and ends when the channel next becomes idle.

A busy cycle is the sum of a busy period and an adjacent idle period, or equivalently, the time between two successive departures leaving an empty system, or two successive arrivals to an empty system. Therefore the CDF of the busy period is sufficient to describe the busy cycle also and is found as follows.

Now the Laplace transform of Po t , Po s , is the first coefficient of the power series P z, s and is thus found as P O,s.

It is not too difficult to extend the notion of the busy period conceptually to the multichannel case. Recall that for one channel a busy period is defined to begin with the arrival of a customer at an idle channel and to end when the channel next becomes idle. Then it should be clear that Pi-1 t will, in fact, be the required CDF, and its derivative the density. You are told that a small single-server, birth-death-type queue with finite capacity cannot hold more than three customers.

The finite-capacity constraint of Problem 2. Derive W t and w t the total-waiting-time CDF and its density as given by the equations 2. The approach is to plot the cumulative count of arrivals on the same graph as the cumulative count of departures. Then it can be seen that the area between these two step functions from the beginning of a busy period to the beginning of the next a busy cycle is the accumulated total of the system waiting times of all the customers who have entered into the system during this busy cycle.

Use this argument to derive an empirical version of Little's formula over a busy cycle. A graduate research assistant "moonlights" in the food court in the student union in the evenings. He is the only one on duty at the counter during the hours he works. Each customer is served one at a time and the service time is thought to follow an exponential distribution with a mean of 4 min.

Answer the following questions. If he can grade 22 papers an hour on average when working continuously, how many papers per hour can he average while working his shift?

A rent-a-car maintenance facility has capabilities for routine maintenance oil change, lubrication, minor tune-up, wash, etc. Cars arrive there according to a Poisson process at a mean rate of three per day, and service time to perform this maintenance seems to have an exponential distribution with a mean of :]4 day. This also increases their operating costs. Up to what value can the operating cost increase before it is no longer economically attractive to make the change?

The machine can paint one part at a time. The cost of owning and operating the painting machine is strictly a function of its speed. Determine the value of J. L that minimizes the cost of the painting operation.

So it does not require that all waiting customers form a single line, and instead they make every arrival randomly choose one of three lines formed before each server during the weekday lunch period.

But they are so traditional about managing their lines that barriers have been placed between the lines to prevent jockeying. Suppose that the overall stream of incoming customers has settled in at a constant rate of 60th Poisson-distributed and that the time to complete a customer's order is well described by an exponential distribution of mean seconds, independent and identically from one customer to the next.

Assuming steady state, what is the average total system size? What is the expected steady-state system size now? To celebrate the event, the campus book store ordered tee shirts. On the day of the sale, demand for shirts was steady throughout the day and fairly well described by a Poisson process with a rate of 66 per hour. There were four cash registers in operation and the average time of a transaction was 3.

Service times were approximately exponentially distributed. You are the owner of a small book store. You have two cash registers. Customers wait in a single line to purchase books at one of the two registers. The time to complete the purchase transactions for one customer follows an exponential distribution with mean 3 minutes. What is the hourly rate that you make money?

Now, what is the hourly rate that you make money? It has established 25 investigation teams to analyze and evaluate each accident or incident to make sure it is properly reported to accident investigation boards. Each of these teams is dispatched to the locale of the accident or incident as each requirement for such support occurs. Support is only rendered those commands that have neither the facilities nor qualified personnel to conduct such services.

Each accident or incident will require a team being dispatched for a random amount of time, apparently exponential with mean of 3 weeks. At any given time, two teams are not available due to personnel leaves, sickness, and so on. Find the expected time spent by an accident or incident in and waiting for evaluation. An organization is presently involved in the establishment of a telecommunication center so that it may provide a more rapid outgoing message capability. Overall, the center is responsible for the transmission of outgoing messages and receives and distributes incoming messages.

The center manager at this time is primarily concerned with determining the number of transmitting personnel required at the new center.

Outgoing message transmitters are responsible for making minor corrections to messages, assigning numbers when absent from original message forms, maintaining an index of codes and a day file of outgoing messages, and actually transmitting the messages. All outgoing messages will be processed in the order they are received and follow a Poisson process with a mean rate of 21 per 7-h day. Processing on messages requiring transmission must be started within an average of 2 h from the time they arrive at the center.

Determine the minimum number of transmitting personnel to accomplish this service criterion. If the service criterion were to require the probability of any message waiting for the start of processing for more than 3 h to be less than. A small branch bank has two tellers, one for receipts and one for withdrawals. Customers arrive to each teller's cage according to a Poisson distribution with a mean of h. The total mean arrival rate at the bank is h.

The service time of each teller is exponential with a mean of 2 min. However, since the tellers would have to handle both receipts and withdrawals, their efficiency would decrease to a mean service time of 2.

Compare the present system with the proposed system with respect to the total expected number of people in the bank, the expected time a customer would have to spend in the bank, the probability of a customer having to wait more than 5 min, and the average idle time of the tellers. The Hott Too Trott Heating and Air Conditioning Company must choose between operating two types of service shops for maintaining its trucks.

It estimates that trucks will arrive at the maintenance facility according to a Poisson distribution with mean rate of one every 40 min and believes that this rate is independent of which facility is chosen.

In the first type of shop, there are dual facilities operating in parallel; each facility can service a truck in 30 min on average the service time follows an exponential distribution. In the second type there is a single facility, but it can service a truck in 15 min on average service times are also exponential in this case.

To help management decide, they ask their operations research analyst to answer the following questions: a How many trucks, on average, will be in each of the two types of facilities? They also know from previous experience in running dual-facility shops that the cost of operating such a facility is one dollar per minute including labor, overhead, etc.

What would the operating cost per minute have to be for operating the single-facility shop in order for there to be no difference between the two types of shops? The ComPewter Company, which leases out high-end computer workstations, considers it necessary to overhaul its equipment once a year. The maintenance time for a machine has an exponential distribution with a mean of 6 h. In this case, the maintenance time for a machine has an exponential distribution with a mean of 3 h.

For both alternatives, the machines arrive according to a Poisson input with a mean arrival rate of one every 8 h since the company leases such a large number of machines, we can consider the machine population as infinite. Which alternative should the company choose? For Problem 2. A small drive-it-through-yourself car wash, in which the next car cannot go through the washing procedure until the car in front is completely finished, has a capacity to hold on its grounds a maximum of 10 cars including the one in wash.

The company has found its arrivals to be Poisson with mean rate of 20 carsth, and its service times to be exponential with a mean of 12 min. What is the average number of cars lost to the firm every lO-h day as a result of its capacity limitations? Under the assumption that customers will not wait if no seats are available, Example 2. Her shop is open on Saturdays from A.

This office can seat an additional four people. Should Cutt rent? The Fowler-Heir Oil Company operates a crude-oil unloading port at its major refinery. The port has six unloading berths and four unloading crews. When all berths are full, arriving ships are diverted to an overflow facility 20 miles down river.

Tankers arrive according to a Poisson process with a mean of one every 2 h. It takes an unloading crew, on average, 10 h to unload a tanker, the unloading time following an exponential distribution. Tankers waiting for unloading crews are served on a first-come, first-served basis. Company management wishes to know the following: a On average, how many tankers are at the port? Assume that construction and maintenance costs would amount to X dollars per year.

The company estimates that to divert a tanker to the overflow port when the main port is full costs Y dollars. What is the relation between X and Y for which it would pay for the company to build an extra berth at the main port?

Fly-Bynite Airlines has a telephone exchange with three lines, each manned by a clerk during its busy periods.

During their peak three hours per h period, many callers are unable to get into the exchange there is no provision for callers to hold if all servers are busy. We may assume that the number of people not getting through during off-peak hours is negligible.

The three peak hours occur during the 8-h day shift. At all other times, one clerk can handle all the traffic, and since the company never closes the exchange, exactly one clerk is used on the off shifts. Assume that the cost of adding lines to the exchange is negligible. A call center has 24 phone lines and 3 customer service representatives. The time to process each call is exponential with a mean of 10 minutes. If all of the service representatives are busy, an arriving the phone lines.

If all of the customer is placed on hold, but ties up on phone lines are tied up, the customer receives a busy signal and the call is lost. Fixing the number of service representatives, what is the optimal number of phone lines you should have? Prove the iterative relationship in 2. Prove the relationship in 2. The Good Writers Correspondence Academy offers a go-at-your-own-pace correspondence course in good writing.

New applications are accepted at any time, and the applicant can enroll immediately. An applicant's mean completion time is found to be 10 weeks, with the distribution of completion times being exponential. On average, how many pupils are enrolled in the school at any given time? A manufacturer of a very expensive, rather infrequently demanded item uses the following inventory control procedure.

She keeps a safety stock of S units on hand. The customer demand for units can be described by a Poisson process with mean A. Every time a request for a unit is made a customer demand , an order is placed at the factory to manufacture another this is called a one-for-one ordering policy. If p z could be determined, one could optimize E[G] with respect to S. Hence relate p z to Pn. State explicitly what the input and service mechanisms are. Farecard machines that dispense tickets for riding on the subway have a mean operating time to breakdown of 45 h.

It takes a technician on average 4 h to repair a machine, and there is one technician at each station. Assume that the time to breakdown and the time to repair are exponentially distributed.

What is the number of installed machines necessary to assure that the probability of having at least five operational is greater than. Show for the basic machine repair model no spares that qn M , the failure arrival point probabilities for a population of size M, equal Pn M - 1 , the general-time probabilities for a population of size M - 1.

Derive qn M given by 2. While that is no proof, the statement can be shown to hold in general see Sevick and Mitrani, , or Lavenberg and Reiser, A coin-operated dry-cleaning store has five machines. The operating characteristics of the machines are such that any machine breaks down according to a Poisson process with mean breakdown rate of one per day.

A repairman can fix a machine according to an exponential distribution with a mean repair time of one-half day. Currently, three repairmen are on duty.

The manager, Lew Cendirt, has the option of replacing these three repairmen with a super-repairman whose salary is equal to the total of the three regulars, but who can fix a machine in one-third the time, that is, in one-sixth day.

Should he be hired? Suppose that each of five machines in a given shop breaks down according to a Poisson law at an average rate of one every 10 h, and the failures are repaired one at a time by two maintenance people operating as two channels, such that each machine has an exponentially distributed servicing requirement of mean 5 h. Very often in real-life modeling, even when the calling population is finite, an infinite-source model is used as an approximation.

To compare the two models, calculate L for Example 2. How do you think p affects the approximation? Find the average operating costs per hour of Example 2. What now is the best policy? Assume we have a two-state, state-dependent service model as described in Section 2. Suppose that the customers are lawntreating machines owned by the Green Thumb Lawn Service Company and these machines require, at random times, greasing on the company's twospeed greasing machine.

What is the optimal switch point k? Derive the steady-state system-size probabilities for a single-server model with Poisson input and exponential state-dependent service with mean rates f-ll 1 ; n 2. Suppose that customers balk at joining the queue when it is too long. Determine the steady-state probability that there are n in the system. Suppose that the M I Mil reneging model of Section 2.

Find the stationary system-size distribution. Derive the steady-state M I M solution directly from the transient. Use the properties of Laplace transforms to find the functions whose Laplace transforms are the following: a b c d 2.

Show that the moment generating function of the sum of independent random variables is equal to the product of their moment generating functions.

Use the result of Problem 2. That is, we allow changes of more than one over infinitesimal time intervals but insist on retaining the memoryless Markovian property.

The Chapman - Kolmogorov and backward and forward equations, plus the resultant balance equations, are all still valid, and together are the essence of the approach to solution for these nonbirth-death Markovian problems. We now recall the discussions of Section 1.

Figure 3. For an arbitrary batch-size distribution X, a general set of rate balance equations can be derived Problem 3. To solve the system of equations given by 3. Difference-equation methods are often used instead to solve the problem when the maximum batch is small. Under the proper parameter settings, the processes treated in this chapter meet the conditions of Theorem 1.

Multiplying each equation of 3. After the first stage many items are found to have one or more defects, which must be repaired before they enter the second stage. It is the job of one worker to make the necessary adjustments to put the assembly back into the stream of the process. The number of defects per item is registered automatically, and it exceeds two an extremely small number of times. But it is subsequently noted that the rates of defects have increased, although not continuously.

It is therefore decided to put another person on the job, who will concentrate on repairing those units with two defects, while the original worker works only on singles. When to add the additional person will be decided on the basis of a cost analysis. Now there are a number of alternative cost structures available, and it is decided by management that the expected cost of the system to the company will be based on the average delay time of assemblies in for repair, which is directly proportional to the average number of units in the system, L.

If a second repairer now sets up a separate service channel, the additional cost of his or her time is incurred, over and above the cost of the items in the queue. In this case, we have two queues. The expected number of required repairs in the system is then the sum of the expected values of the two streams. Using our values for the parameters gives a decision criterion of C 2 3. We specifically assume that customers arrive according to an ordinary Poisson process, service times are exponential, there is a single server, customers are served FCFS, there is no waiting-capacity constraint, and customers are served K at a time.

We consider two variations of this bulk-service model. The variations arise from how the system operates when there are less than K in the system. We call these two models the full-batch model and the partial-batch model. In the full-batch model, the server processes exactly K customers at a time. If less than K customers are in the system, then the server remains idle until there are K customers, at which point the server processes the K customers simultaneously.

This model could represent, for example, a ferry that waits until there are exactly K cars on board before it departs. Furthermore, when there are less than K in service, new arrivals immediately enter service up to the limit K and finish with the others, regardless of the entry time into service.

This model could represent, for example, a tour in which late arriving customers join the tour up to a maximum of K in the tour and finish as a group. The basic model is a non-birth -death Markovian problem. The stochastic balance equations are given as see Problem 3. Let us now determine the number of roots less than one. For this, an appeal is made to Roucbe's theorem see Section 2.

It can be found that there is exactly one root say, ro in 0, 1 see Problem 3. The stationary solution has the same geometric form 2. Then, Lq can be derived from Wq using Little's law. It installs new machinery that permits the washing of two cars at once and one if no other cars wait. A car that arrives while a single car is being washed joins the wash and finishes with the first car. There is no waitingcapacity limitation.

The time to wash a car is exponentially distributed with a mean of 5 min. What is the average line length? The characteristic equation from 3. Let us now assume that the batch size must be exactly K, and if not, the server waits until such time to start. Then the equations in 3. From the last equation of 3. This can be shown using 3. Hence from 3. To do this we again appeal to Rouche's theorem see Section 2. The generating function P z has the property that it must converge inside the unit circle.

Applying Rouche's theorem to the denominator see Problem 3. We denote this by ZOo A major observation is that the roots of the denominator are precisely the reciprocals of those of the characteristic equation 3. This inverse relationship can be seen for the MIMll queue by comparing 2. In fact, it can be shown that the zeros of the characteristic equation of any system of linear difference equations with constant coefficients are the reciprocals of the poles of the system's generating function.

We have already seen this sort of thing in Example 3. Returning now to the generating function, we see that dividing the denominator by the product z - 1 z - zo results in a polynomial with K - 1 roots inside the unit circle.

Substituting the right-hand side above into 3. To treat this policy in general requires methods more advanced than those used in this chapter. In many practical situations, however, the exponential assumptions may be rather limiting, especially the assumption concerning service times being distributed exponentially. Now, we consider a special class of these distributions where 0: is restricted to be a positive integer.

For a particular value of k, the distribution is referred to as an Erlang type-k or Ek distribution. The Erlang family provides more flexibility in modeling than the exponential family, which only has one parameter.

As k increases, the Erlang becomes more symmetrical and more closely centered around its mean. In practical situations, the Erlang family provides more flexibility in fitting a distribution to real data than the exponential family provides.

The Erlang distribution is also useful in queueing analysis because of its relationship to the exponential distribution. The proof of this property is left as an exercise; see Problem 2. This property makes it possible to take advantage of the Markovian property of the exponential distribution, even though the Erlang distribution itself is not Markovian Section 1.

There are several implications of this model. First, all steps or phases of the service are independent and identical. Second, only one customer or test at a time is allowed in the service mechanism. That is, a customer enters phase 1 of the service, then progresses through the remaining phases, and must complete the last phase before the next customer enters the first phase. This rules out assembly-line-type models where, as soon as a customer finishes one phase of service, another can enter it.

The Erlang has greater flexibility than the exponential to fit observed data Figure 3. Although the physical system may not contain any phases, the use of phases helps from a mathematical perspective, because the time spent in each phase is exponential.

Thus the beneficial properties of the exponential distribution are preserved, even though the overall distribution is not exponential. The main drawback is that using phases increases the size of the state space and model complexity. Finally, we point out that the CDF of the Erlang distribution 3. Consider a Poisson process with arrival rate kf,. The probability that there are exactly n arrivals by time t is e-kl-'t kf,. Lt n In!. Thus the probability that there are k or more arrivals by time t is F t , given in 3.

No access codes are included. Your email address will not be published. Save my name, email, and website in this browser for the next time I comment. Selected: Fundamentals of Queueing Theory…. Previous Product.