Skip to main content

2013 | Buch

Queues

A Course in Queueing Theory

insite
SUCHEN

Über dieses Buch

Queueing theory (the mathematical theory of waiting lines in all its configurations) continues to be a standard major area of operations research on the stochastic side. Therefore, universities with an active program in operations research sometimes will have an entire course devoted mainly or entirely to queueing theory, and the course is also taught in computer science, electrical engineering, mathematics, and industrial engineering programs.

The basic course in queueing theory is often taught at first year graduate level, though can be taught at senior level undergraduate as well. This text evolved from the author’s preferred syllabus for teaching the course, presenting the material in a more logical order than other texts and so being more effective in teaching the basics of queueing theory.

The first three chapters focus on the needed preliminaries, including exposition distributions, Poisson processes and generating functions, renewal theory, and Markov chains, Then, rather than switching to first-come first-served memoryless queues here as most texts do, Haviv discusses the M/G/1 model instead of the M/M/1, and then covers priority queues. Later chapters cover the G/M/1 model, thirteen examples of continuous-time Markov processes, open networks of memoryless queues and closed networks, queueing regimes with insensitive parameters, and then concludes with two-dimensional queueing models which are quasi birth and death processes. Each chapter ends with exercises.

Inhaltsverzeichnis

Frontmatter
Chapter 1. The Exponential Distribution and the Poisson Process
Abstract
The exponential distribution is one of the major bricks in many models in operations research in general and in queueing theory in particular. Exponential random variables possess convenient properties, especially the memoryless property which makes the analysis of such models tractable. Also, they are simple to deal with as they are a single parameter family of distributions. At the same time, these distributions are a good model for representing real-life situations (such as interarrival times to a queueing system). Yet, this is not always the case and, as we will see throughout the book, more involved treatment is needed in cases where the assumption of an exponential distribution needs to be removed.
Moshe Haviv
Chapter 2. Introduction to Renewal Theory
Abstract
Let {X i } i = 1 be a series of independent and identically distributed nonnegative random variables. Assume they are continuous. In particular, there exists some density function f X (x), x≥0, such that \(F_{X}(x) \equiv \mathrm{P}(X_{i} \leq x) =\int _{ t=0}^{x}f_{X}(t)\,dt\), i ≥ 1. Imagine X i representing the life span of a lightbulb. Specifically, there are infinitely many lightbulbs in stock. At time t = 0, the first among them is placed. It burns out after a (random) time of X 1. Then it is replaced by a fresh lightbulb that itself is replaced after an additional (random) time of X 2, etc. Note that whenever a new lightbulb is placed all statistically starts afresh. Let \(S_{n} = \Sigma _{i=1}^{n}X_{i}\), n ≥ 1, and set S 0 = 0. Of course, \(S_{n+1} = S_{n} + X_{n+1}\), n ≥0.
Moshe Haviv
Chapter 3. Introduction to Markov Chains
Abstract
The topic of Markov processes is huge. A number of volumes can be, and in fact were, written on this topic. We have no intentions to be complete in this area. What is given in this chapter is the minimum required in order to follow what is presented afterwards. In particular, we will refer at times to this chapter when results we present here are called for. For more comprehensive coverage of the topic of Markov chains and stochastic matrices, see [9, 19, 41] or [42].
Moshe Haviv
Chapter 4. From Single Server Queues to M/G/1
Abstract
Sometimes production and manufacturing are complicated processes. Usually it has to do with limited facilities. For example, in order to produce a car the manufacturer may have to go through a number of working centers: a storage area with raw materials at one end, the quality control inspection at the other end, and a few assembly points in between. Various points along the production process interact. The outflow of one is the inflow of another. A slow machine may reduce the productivity of other working centers along the line which will be starved for more input. However, in order to gain some insight into such systems, we first have to look at single server systems in isolation. When looked at in isolation, each server (or servers who work in tandem) and the demand for its service can be modeled as customers arriving at service stations. If there is too great a delay in the service facility, a waiting line might form. The purposes of this chapter are:
  • To see why queues sometimes form;
  • To see what the main factors are in determining the length of the queue and the waiting time;
  • To show how waiting times and queue lengths are related (Little’s law);
  • To define the virtual waiting times and the actual waiting time;
  • To derive the mean waiting time (the Khintchine–Pollaczek formula) and the mean time of a busy period for single server queues with a Poisson arrival process.
Moshe Haviv
Chapter 5. Priorities and Scheduling in M/G/1
Abstract
So far we have assumed that all customers are treated equally. In particular, the next to enter service could not be decided due to certain parameters that are customer-dependent. This was the case regardless of which of the FCFS, LCFS, or random-order policies was assumed. In this chapter we deviate from this assumption and allow some discrimination among customers. Thus, some customers may be treated better than others.
Moshe Haviv
Chapter 6. M/G/1 Queues Using Markov Chains and LSTs
Abstract
In examining the M/G/1 model in the previous chapter, we dealt there mainly with mean values, such as the mean number of customers in the system or the mean queueing time. Here we will give more details. For example, we will look for the distribution of time in the system spent by a customer and for the distribution of the number of customers in the queue. It is easy to see that the former distribution varies with the queueing regime while the latter does not (as long as it is nonpreemptive, non-anticipating, and work-conserving), so we need to specify what it is. Naturally, we assume it to be FCFS.
Moshe Haviv
Chapter 7. The G/M/1 Queueing System
Abstract
Consider a first-come first-served single-server queue. Assume that service requirements are independent and follow an identical exponential distribution with a parameter μ. This assumption implies that during a (not necessarily continuous) period of time of length t, the number of customers possibly served by the server has a Poisson distribution with parameter μt. The reason we use the term “possibly” is that in practice what can happen is that during that period or part of it, the system might be empty and hence, although service is ready to be provided, there is no one there to enjoy it. One more thing to observe here is that if one stops the clock when the server is idle, then the departure process under the new clock is a Poisson process. As always, the interarrival times have some continuous distribution with a density function denoted here by g(t) for t ≥ 0 and that they are independent. In other words, the arrivals form a renewal process. Finally, we assume independence between the arrival and the service processes.
Moshe Haviv
Chapter 8. Continuous-Time Markov Chains and Memoryless Queues
Abstract
We next define the model of a discrete state-space continuous-time Markov process. Let N = { 0, 1, 2, ,n} be the possible states of a process. The value of n can be finite or infinite but N should be discrete. Note that we use a numerical value to present a state just for convenience. In fact, state-i is nothing more than a name and is selected for reference purposes. Yet, in many cases these names have a meaning and their use may lead to a natural presentation of a state, such as the number of customers in a queue (when applicable).
Moshe Haviv
Chapter 9. Open Networks of Exponential Queues
Abstract
Part of the model described here coincides with the one described in Example 9 in Chap. 8. For the sake of completeness we start here from scratch. Suppose M single-server service stations are located in a network. To station i there requires an external Poisson arrival process with rate λ i , 1 ≤ iM. Each time a job visits station i it requires a service of a length that follows an exponential distribution with parameter μ i , 1 ≤ iM. In each station service a job is provided on a first-come first-served (FCFS) basis1. Once a job completes its service in station i, it moves to station j with probability P ij .
Moshe Haviv
Chapter 10. Closed Networks of Exponential Queues
Abstract
Suppose M single-server service stations are located in a network. Service times in station i follow an exponential distribution with parameter μ i , 1 ≤ iM. There are N customers (or jobs) who are “trapped” in the network and move from one station to another as soon as service ends at the former station. These dynamics are governed by a transition (stochastic) matrix P. Specifically, once a job ends its service in station i, it hops to the queue in front of server j with probability P ij . Of course, P ij ≥ 0, 1 ≤ i, jM, and \(\Sigma _{j=1}^{M}P_{ij} = 1\). There is no need to assume that P ii = 0, 1 ≤ iM. However, we assume that P (or more precisely, a Markov chain whose transition probabilities are given in P) is irreducible.
Moshe Haviv
Chapter 11. Insensitivity and Product-Form Queueing Models
Abstract
Most of the analysis done so far assumed a FCFS queueing regime. Yet some, indeed many, of our results (for example, those concerning mean waiting times) hold for any work-conserving, nonanticipating and nonpreemptive regime. For example, instead of a FCFS regime, we can assume a random regime such that, upon service completion, the next to commence service is selected at random from all those waiting. Another example is the last-come first-served without preemption regime (LCFS), where the next to commence service is the one who has been waiting the least. Indeed, in all of these entrance policies for the G/G/1 queue, the distribution of the number in the system, and hence, by Little’s law, the mean waiting time, is invariant with the queueing regime. Of course, many differences exist. For example, the variance of the waiting time in a FCFS queue is smaller than the corresponding value under LCFS. See [33].
Moshe Haviv
Chapter 12. Two-Dimensional Markov Processes and Their Applications to Memoryless Queues
Abstract
We have already seen Markov processes in which each state is represented by a vector. These Markov processes offer a convenient way to refer to a state (in fact, this was nothing more than giving names to states). Such was the case, for example, when we dealt with open and closed networks of queues, and with multiclass single-server queues. In this respect there is nothing new in this chapter where the states will be represented by two-dimensional vectors; that is, a state will be referred to by the pair of nonnegative integers (i, j). However, in an attempt to generalize some results from one-dimensional birth-and-death precesses, we will impose the following restrictions on the model:
Moshe Haviv
Backmatter
Metadaten
Titel
Queues
verfasst von
Moshe Haviv
Copyright-Jahr
2013
Verlag
Springer New York
Electronic ISBN
978-1-4614-6765-6
Print ISBN
978-1-4614-6764-9
DOI
https://doi.org/10.1007/978-1-4614-6765-6