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 arrivals of two successive customers who 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.

1. 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.
2. 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.
3. The average, variance, and/or distribution of the waiting time.
4. 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.

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⁸⁸Queueing systems are one example.. We use sample paths⁹⁹In fact, the same sample paths as those obtained through simulation. of stochastic processes to estimate key performance measures, assuming that these paths capture typical stochastic behavior.

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 fundamental and important algorithms that handle 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.

An important aim of this course is that you develop algorithmic thinking. You should learn to describe a method as a sequence of precise steps, trace what these steps do, and explain why they work. Here are a few important examples of algorithms we use throughout the course. Study them in detail; they are as important as the mathematical models we develop.

Throughout the book, we assume access to a dictionary: a mutable function \(D\) with a finite domain written as \(\pr{keys}(D)\). If \(k \in \pr{keys}(D)\), \(D(k)\) returns its stored value for \(k\).¹²¹²The call \(D(k)\) when \(k\) is absent results in an error. The assignment \(D(k)\gets v\) inserts or replaces the value at \(k\) in \(D\). The procedure \(\pr{values}(D)\) returns the list¹³¹³A list allows for duplicates, which we want; a set does not. \(\qb{D(q) : q \in \pr{keys}(D)}\). We assume that when \(D\) does not change, \(\pr{keys}(D)\) always returns the keys in the same order, hence, \(\pr{values}(D)\) is aligned in the same order.

We start with the concept of closure. Consider the following procedure.

\begin{algorithm}
\caption{Construct a power function with a fixed exponent.}
\begin{algorithmic}[1]
\State \textbf{Input:} an exponent \(e\)
\State \textbf{Output:} a procedure \(\pr{apply}\) that maps \(b\) to \(b^e\)
\Procedure{power}{\(e\)}
    \Procedure{apply}{\(b\)}
        \Return \(b^e\)
    \EndProcedure
    \Return \(\pr{apply}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

With this scheme, we can build the following functions very efficiently:

Observe that the procedure \(\pr{power}\) returns an inner procedure \(\pr{apply}\). This inner procedure captures the variable \(e\) from its surrounding scope. As a result, the returned procedure remembers the value of \(e\). For example, consider \(\var{square}\gets\pr{power}\rb{2}\). The call \(\pr{power}\rb{2}\) returns a procedure with exponent \(2\) fixed; the assignment names that procedure \(\var{square}\). Calling it on a number completes the computation:

In general terms: the outer procedure \(\pr{power}\) specifies the general structure of a computation: it describes the pattern ``take a number and raise it to a fixed exponent,’’ without yet committing to a particular exponent. By calling the outer procedure and assigning its output to a new name, we specialize this general procedure. The returned procedure has the same structure, but with the free parameter \(e\) bound to a concrete value. In this way, we obtain a new, more specific procedure from a general computational template.

Caching is another use of closures in recursive procedures.¹⁴¹⁴We will use recursion on many occasions in this book. A recursion may reach the same state more than once. We store its result the first time so that instead of recomputing we can reuse that result on later visits.

A cache is a dictionary \(A\) with states as keys and their computed results as values. The procedure \(\pr{InCache}\) in Alg. 1.1.2 returns a closure¹⁵¹⁵Read procedures that end with a ? as a true/false answer to a question. Here, \(\pr{inCache?}(q)\) should be read as `is \(q\) in the cache?’. \(\pr{inCache?}\) that remembers \(A\) and tests whether \(q\) is one of its keys.

\begin{algorithm}
\caption{Construct a procedure that checks whether a cache contains a key.}
\begin{algorithmic}[1]
\State \textbf{Input:} a dictionary \(A\)
\State \textbf{Output:} a procedure \(\pr{inCache?}\) for testing key membership
\Procedure{InCache}{\(A\)}
    \Procedure{inCache?}{\(q\)}
        \Return \(q\in\operatorname{keys}(A)\)
    \EndProcedure
    \Return \(\pr{inCache?}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

For example, start with an empty dictionary \(A\) and set \(\pr{inCache?}\gets\pr{InCache}\rb{A}\). Then \(\pr{inCache?}(3)\) is false. After the in-place assignment \(A(3)\gets8\), \(\pr{inCache?}(3)\) is true. The closure sees the new value because it retains access to the same \(A\).

The Fibonacci numbers give a small example of the benefits of caching. They satisfy \(F_0=0\), \(F_1=1\), and \(F_n=F_{n-1}+F_{n-2}\) for \(n\geq2\). Direct recursion computes the same values repeatedly. For example, \(\pr{Fibonacci}\rb{5}\) computes \(F_3\) twice and \(F_2\) three times.¹⁶¹⁶The number of computations increases exponentially fast as a function of \(n\).

\begin{algorithm}
\caption{Compute a Fibonacci number by direct recursion.}
\begin{algorithmic}[1]
\State \textbf{Input:} a non-negative integer \(n\)
\State \textbf{Output:} the Fibonacci number \(F_n\)
\Procedure{Fibonacci}{\(n\)}
    \If{\(n\leq1\)}
        \Return \(n\)
    \EndIf
    \Return \(\pr{Fibonacci}\rb{n-1}+\pr{Fibonacci}\rb{n-2}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The cached version stores each value after computing it. Its inner procedure \(\pr{f}\) and the predicate \(\pr{inCache?}\) both retain access to the same dictionary \(A\).

\begin{algorithm}
\caption{Compute a Fibonacci number with a cache.}
\begin{algorithmic}[1]
\State \textbf{Input:} a non-negative integer \(n\)
\State \textbf{Output:} the Fibonacci number \(F_n\)
\Procedure{FibonacciCached}{\(n\)}
    \State \(A\gets\) an empty dictionary
    \State \(\pr{inCache?}\gets\pr{InCache}\rb{A}\)
    \Procedure{f}{\(k\)}
        \If{\(\pr{inCache?}\rb{k}\)}
            \Return \(A(k)\)
        \EndIf
        \If{\(k\leq1\)}
            \State \(v\gets k\)
        \Else
            \State \(v\gets\pr{f}\rb{k-1}+\pr{f}\rb{k-2}\)
        \EndIf
        \State \(A(k)\gets v\)
        \Return \(v\)
    \EndProcedure
    \Return \(\pr{f}\rb{n}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

Now each \(F_k\) with \(0\leq k\leq n\) is computed at most once: later visits retrieve its value from \(A\).

With closures we can build a procedure \(\pr{Map}\) in Alg. 1.1.5 to construct a map with default value \(d=0\), unless another value is supplied. Each call creates a private empty dictionary \(\var{store}\) and returns a procedure \(\pr{f}\) that retains access to it.¹⁷¹⁷A procedure that retains access to data created by its enclosing procedure is called a closure. It can take some time to get your head around a procedure that returns another procedure. Working through a few calls by hand helps. The same dictionary is available as \(\pr{f}.\var{store}\).

For example, \(\pr{g}\gets\pr{Map}()\) starts with an empty store. The first call \(\pr{g}(3)\) stores \(0\) under key \(3\) and returns \(0\). By convention, an assignment \(\pr{g}(k)\gets v\) is shorthand for \(\pr{g}.\var{store}(k)\gets v\). Thus, \(\pr{g}(3)\gets\pr{g}(3)+8\) changes the value at key \(3\) from \(0\) to \(8\), and a subsequent call to \(\pr{g}(3)\) returns \(8\).

\begin{algorithm}
\caption{Construct a map with a configurable default value.}
\begin{algorithmic}[1]
\State \textbf{Input:} a default value \(d\)
\State \textbf{Output:} a procedure \(\pr{f}\)
\Procedure{Map}{\(d = 0\)}
    \State \(\var{store}\gets\) an empty dictionary
    \Procedure{f}{\(k\)}
        \If{\(k\notin\pr{keys}(\var{store})\)}
            \State \(\var{store}(k)\gets d\)
        \EndIf
        \Return \(\var{store}(k)\)
    \EndProcedure
    \State \(\pr{f}.\var{store}\gets \var{store}\)
    \Return \(\pr{f}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The keys of \(\pr{f}\) are \(\pr{keys}(\pr{f}.\var{store})\), and \(\pr{f}.\var{store}(k)\) is the value at key \(k\). The procedures \(\pr{Keys}(\pr{f})\) and \(\pr{Values}(\pr{f})\) return the keys and values. For the map \(\pr{g}\) above, \(\pr{Keys}(\pr{g})=\qb{3}\) and \(\pr{Values}(\pr{g})=\qb{8}\).

\begin{algorithm}
\caption{Return the keys of a map.}
\begin{algorithmic}[1]
\State \textbf{Input:} a map procedure \(\pr{f}\)
\State \textbf{Output:} its keys
\Procedure{Keys}{\(\pr{f}\)}
    \Return \(\pr{keys}(\pr{f}.\var{store})\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\caption{Return the values of a map.}
\begin{algorithmic}[1]
\State \textbf{Input:} a map procedure \(\pr{f}\)
\State \textbf{Output:} its values
\Procedure{Values}{\(\pr{f}\)}
    \Return \(\pr{values}(\pr{f}.\var{store})\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The procedure \(\pr{Count}\) of Alg. 1.1.8 counts the occurrences of each observed value. It uses the map of Alg. 1.1.5 with default value zero. When a value \(q\) is encountered for the first time, \(\var{counter}(q)\) therefore returns zero, and the update sets it to one. Every later occurrence increases the stored value by one. Thus, after all observations, \(\var{counter}(q)\) is the number of times \(q\) occurred.

\begin{algorithm}
\caption{Count observations in each state.}
\begin{algorithmic}[1]
\State \textbf{Input:} observations \(\qb{x_1,\ldots,x_n}\)
\State \textbf{Output:} a map of counts \(\var{counter}\)
\Procedure{Count}{\(\qb{x_1,\ldots,x_n}\)}
    \State \(\var{counter}\gets\pr{Map}()\)
    \For{\(k=1,\ldots,n\)}
        \State \(\var{counter}(x_k)\gets \var{counter}(x_k)+1\)
    \EndFor
    \Return \(\var{counter}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The procedure \(\pr{Sum}\) of Alg. 1.1.9 returns the sum of the numbers in a list. It starts with \(\var{total}=0\) and adds each number to \(\var{total}\). Thus, it returns zero when the list is empty.

\begin{algorithm}
\caption{Sum the numbers in a list.}
\begin{algorithmic}[1]
\State \textbf{Input:} numbers \(\qb{x_1,\ldots,x_n}\)
\State \textbf{Output:} their sum \(\var{total}\)
\Procedure{Sum}{\(\qb{x_1,\ldots,x_n}\)}
    \State \(\var{total}\gets0\)
    \For{\(k=1,\ldots,n\)}
        \State \(\var{total}\gets \var{total}+x_k\)
    \EndFor
    \Return \(\var{total}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The procedure \(\pr{Normalize}\) of Alg. 1.1.10 turns a list of non-negative weights into a list of probabilities. It uses \(\pr{Sum}\) to compute the total of all weights and then divides each weight by this total. The resulting values sum to one.

\begin{algorithm}
\caption{Normalize non-negative weights into probabilities.}
\begin{algorithmic}[1]
\State \textbf{Input:} non-negative weights \(\qb{w_1,\ldots,w_n}\) with positive sum
\State \textbf{Output:} probabilities \(\qb{p_1,\ldots,p_n}\)
\Procedure{Normalize}{\(\qb{w_1,\ldots,w_n}\)}
    \State \(\var{total}\gets\pr{Sum}\rb{\qb{w_1,\ldots,w_n}}\)
    \For{\(k=1,\ldots,n\)}
        \State \(p_k\gets w_k/\var{total}\)
    \EndFor
    \Return \(\qb{p_1,\ldots,p_n}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The procedure \(\pr{Minimum}\) of Alg. 1.1.11 starts with \(m=+\infty\) and compares \(m\) with every observation. After iteration \(k\), \(m\) is the smallest of the first \(k\) observations. When the list is empty, the algorithm returns \(+\infty\).

\begin{algorithm}
\caption{Find the smallest observation.}
\begin{algorithmic}[1]
\State \textbf{Input:} observations \(\qb{x_1,\ldots,x_n}\)
\State \textbf{Output:} minimum \(m\), or \(+\infty\) if \(n=0\)
\Procedure{Minimum}{\(\qb{x_1,\ldots,x_n}\)}
    \State \(m\gets+\infty\)
    \For{\(k=1,\ldots,n\)}
        \State \(m\gets\min\{m,x_k\}\)
    \EndFor
    \Return \(m\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

Now it is time to practice. For each True–False question, decide whether the statement is true or false.

\begin{algorithm}
\begin{algorithmic}[1]
\Procedure{subtract}{\(b\)}
    \Procedure{f}{\(a\)}
        \Return \(a-b\)
    \EndProcedure
    \Return \(\pr{f}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\Procedure{Exceeds}{\(b\)}
    \Procedure{f}{\(w\)}
        \Return \(\1{w>b}\)
    \EndProcedure
    \Return \(\pr{f}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\Procedure{Map}{\(d\)}
    \State \(\var{store}\gets\) an empty dictionary
    \Procedure{f}{\(k\)}
        \If{\(k\notin\operatorname{keys}(\var{store})\)}
            \State \(\var{store}(k)\gets\text{???}\)
        \EndIf
        \Return \(\var{store}(k)\)
    \EndProcedure
    \State \(\pr{f}.\var{store}\gets \var{store}\)
    \Return \(\pr{f}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\Procedure{Normalize}{\(\qb{w_1,\ldots,w_n}\)}
    \State \(\var{total}\gets\pr{Sum}\rb{\qb{w_1,\ldots,w_n}}\)
    \For{\(k=1,\ldots,n\)}
        \State \(p_k\gets \text{???}\)
    \EndFor
    \Return \(\qb{p_1,\ldots,p_n}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\State \(T\gets0\), \(C\gets0\)
\For{\(k=1,\ldots,n\)}
    \State \(T\gets T+w_k\)
    \If{\(w_k>b\)}
        \State \(C\gets C+1\)
    \EndIf
\EndFor
\State \(\bar w\gets T/n\), \(q\gets C/n\)
\Return \(q\)
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} observations \(\qb{x_1,\ldots,x_n}\), supplied one at a time
\State \textbf{Output:} average \(\bar x\)
\State \(N\gets0\), \(T\gets0\)
\For{\(k=2,\ldots,n\)}
    \State \(N\gets N+1\)
    \State \(T\gets T+x_k\)
\EndFor
\State \(\bar x\gets T/N\)
\Return \(\bar x\)
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\caption{Find the largest observation.}
\begin{algorithmic}[1]
\State \textbf{Input:} waiting times \(\qb{w_1,\ldots,w_n}\), supplied one at a time
\State \textbf{Output:} maximum waiting time \(M\)
\State \(M\gets w_1\)
\For{\(k=2,\ldots,n\)}
    \State \(M\gets\max\{M,w_k\}\)
\EndFor
\Return \(M\)
\end{algorithmic}

\end{algorithm}

Exercises require pen and paper.

#+begin_exercise