1.1 Motivation and Overview

Queueing and inventory systems are ubiquitous, and their analysis, performance evaluation, control, and optimization are major topics in Operations Research. Let us illustrate this with two examples.

Fast food restaurants deal with many difficult queueing and inventory situations. For instance, they prepackage hamburgers and put them on a shelf¹¹ This is called make-to-stock production. so that customers need not wait for their orders. The lifetime of prepackaged hamburgers is on the order of a few minutes, so when customers do not buy a hamburger in time, some must be scrapped. The question is how many hamburgers to stock so that both the probability of scrapping and that of lost sales²² Customers who do not buy because they have to wait. are small. Second, fast food restaurants keep an inventory of baked patties not yet turned into hamburgers.³³ A hamburger is a bun plus a baked patty. Baked patties have a longer lifetime than prepared hamburgers, but since preparing a hamburger from a baked patty takes time, customers may still have to wait. In this case too, the inventory level of these patties needs to be controlled. This does not conclude the matter: the rate of customer demand changes over time, so inventory levels for the different types of hamburgers and patties should vary with the time of day.⁴⁴ Inventory and queueing systems are tightly related by changing perspective. Hamburgers in stock can be interpreted as customers in queue waiting for service, where the `service time' as perceived by a hamburger is the time between the arrival of two customers that buy a hamburger.

As a second example, hospitals (call centers, courts, etc.) have a certain capacity to serve customers. The performance of hospitals is, in part, measured by the total number of jobs served per year and the sojourn-time distribution, that is, the distribution of the time a job spends in the system. Here the problem is to organize the system so that the average sojourn time is short without wasting capacity.

In all these examples, the performance of the stochastic system must be monitored and controlled. Typically, the following key performance measures (KPIs) are relevant for queueing systems.⁵⁵ Inventory systems have similar performance measures, such as the average time items spend on the shelf, the fraction of customers served from stock, and the fraction of lost sales.

The fraction of time \(p(n)\) that the system contains \(n\) customers. In particular, \(p(0)\) is the fraction of time the system is empty, hence measures the time-average idle time of servers.
The fraction of customers \(\pi(n)\) that 'see upon arrival' \(n\) customers in the system. This measure relates to customer perception of queue length, and hence to waiting time.
The average, variance, and/or distribution of the waiting time.
The average, variance, and/or distribution of the number of customers in the system.

With these examples in mind, let us give an overview of this book.

Chapter 2 shows how to construct rules that govern the dynamic behavior of many different queueing systems and inventory systems in discrete time. This has several purposes. First, these rules can often be easily implemented in computer code, which we can then use to simulate and observe system behavior over time.⁶⁶ Simulation is generally the best way to analyze practical stochastic systems, as realistic systems seldom yield to mathematics. The resulting sample paths⁷⁷ That is, realizations of these stochastic processes. can then be analyzed, visually or statistically. Second, we will use sample-path arguments to develop the theoretical results in later parts of the book.

In Chapter 3 we describe how to construct sample paths of continuous-time stochastic systems. In particular, we will be concerned with discrete-event simulation.⁸⁸ Nearly all professional simulation tools are built on the same principles.

Once the scope of queueing and inventory theory is clear, the stage is set for a more mathematical treatment of such systems. Despite the power of simulation, structural understanding of stochastic systems is difficult to obtain. Mathematical models, whether exact or approximate, help us reason about and improve such systems.

In Chapter 4 we develop some key results needed for the mathematical analysis of stochastic systems⁹⁹ Of which queueing systems are examples. . For this, we use sample paths¹⁰¹⁰ In fact, the same sample paths as those obtained through simulation. of stochastic processes, and by assuming that such sample paths capture the `normal' stochastic behavior, we can use these sample paths to estimate key performance measures.

In Chapter 5 we use these tools to build exact models for single-station queueing systems. We focus on developing an intuitive understanding of the analytical tools.¹¹¹¹ For most proofs and more extensive results, we refer to the bibliography at the end of the book.

In Chapter 6 we use approximations and results from probability theory to study how system parameters, such as service speed, batching rules, and outages, affect performance.

In Chapter 7 we study queueing networks, first in a deterministic and then in a stochastic setting.

It remains to discuss the rest of this first chapter. Section 1.2 introduces the Exponential distribution and relates it to the Poisson distribution. These two are arguably the most important distributions for modeling dynamic stochastic systems. In Section 1.3 we use simulation and some mathematics to explain why these distributions are particularly useful for modeling arrival processes in queueing systems and demand processes for inventory systems. The amount of computational work involved is considerable; in Section 1.4 we discuss Python code that handles the numerical aspects.

While the main text contains many examples and derivations, a considerable number of examples are left to the exercises. Also, some exercises check consistency between results derived for different models, thereby revealing important connections between different parts of the text.¹²¹² Note that while such checks are conceptually simple, the algebra can be tedious. The exercises are not intended to be easy; they require effort. Hints and solutions for the exercises are available at the end of the book.

True--False questions are simple statements that can be either true or false; your task is to determine which.

TF 1.1.1

Consider the following code.

a = 8
a += 9
a = 10
a -= 3

Claim: a = 10.

Solution

Did you actually try? Maybe see the 'hints' above!:

Solution, for real

False. The value of \(a\) changes from 8 to 17 to 10 to 7.

TF 1.1.2

Consider the following code.

a = [0, 2, 4, 6]
a[1] += 1

Claim: a = [0, 3, 4, 6].

Solution

Did you actually try? Maybe see the 'hints' above!:

Solution, for real

True.

TF 1.1.3

Consider the following code.

a = {-10: 1, 2: 8}
a[1] += 1

Claim: a = {-10: 1, 1: 1, 2: 8}.

Solution

Did you actually try? Maybe see the 'hints' above!:

Solution, for real

False. Since the key \(1\) is not yet in the dictionary \(a\), the code will fail.

TF 1.1.4

Consider the following code.

from collections import defaultdict

a = defaultdict(int)
a[-8] = 1
a[2] = 8
a[1] += 3
a[2] -= 3

Claim: a = {-8: 1, 1: 3, 2: 5}.

Solution

Did you actually try? Maybe see the 'hints' above!:

Solution, for real

True. Since we now use a defaultdict, we can add numbers with \(+=\) even when the key \(1\) is not yet present in the dictionary \(a\). As the key \(1\) is not present, the defaultdict provides the default value 0, after which 3 is added.

TF 1.1.5

Consider the following code.

from collections import defaultdict

a = defaultdict(int)
a[-8] = 1
a[2] = 8
a[1] += 3
a[2] -= 3

Claim: The keys of \(a\) are \(-8, 1, 2\) and the values \(1, 3, 5\).

Solution

Did you actually try? Maybe see the 'hints' above!:

Solution, for real

True. A dictionary maps a key to a value, for example, a student ID (the key) to a student name (the value).

Ex 1.1.6

For a discrete non-negative rv \(X\), use indicator functions to prove:

\(\E X = \sum_{k=0}^\infty G(k)\),
\(\sum_{i=0}^\infty i G(i) = \E{X^2}/2 - \E{X}/2\).

Hint

For (1) write \(\sum_{k=0}^\infty G(k) = \sum_{k=0}^\infty \sum_{m=k+1}^\infty \P{X=m}\); reverse the summations. Then note that \(\sum_{k=0}^\infty \1{k<m} = m\). For (2):

\begin{equation*} \sum_{i=0}^\infty i G(i) = \sum_{n=0}^\infty \P{X=n} \sum_{i=0}^\infty i \1{n\geq i+1}, \end{equation*}

and reverse the summations.

Solution

Did you actually try? Maybe see the 'hints' above!:

Solution, for real

For (1): observe first that \(\sum_{k=0}^\infty \1{m>k} = m\), since \(\1{m>k}=1\) if \(k<m\) and \(\1{m>k} = 0\) if \(k\geq m\). With this,

\begin{align*} \sum_{k=0}^\infty G(k) &= \sum_{k=0}^\infty \P{X>k} = \sum_{k=0}^\infty \sum_{m=k+1}^\infty \P{X=m} \\ & = \sum_{k=0}^\infty \sum_{m=0}^\infty \1{m>k} \P{X=m} = \sum_{m=0}^\infty \sum_{k=0}^\infty \1{m>k} \P{X=m} \\ &= \sum_{m=0}^\infty m\P{X=m} = \E X. \end{align*}

Since all terms are non-negative, interchanging the summations is valid.

For (2):

\begin{align*} \sum_{i=0}^\infty i G(i) &= \sum_{i=0}^\infty i \sum_{n=i+1}^\infty \P{X=n} = \sum_{n=0}^\infty \P{X=n} \sum_{i=0}^\infty i \1{n\geq i+1} \\ &= \sum_{n=0}^\infty \P{X=n} \sum_{i=0}^{n-1}i = \sum_{n=0}^\infty \P{X=n} \frac{(n-1)n}{2} \\ &= \sum_{n=0}^\infty \frac{n^2}{2} \P{X=n} - \frac{\E X}{2} = \frac{\E{X^2}}{2} - \frac{\E X}{2}. \end{align*}