1.1 Motivation and Overview
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. In this book, we learn to construct models of these systems, evaluate their performance, and compare ways to improve it. 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 shelf1This 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 sales2Customers 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.3A 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.4Inventory 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.5Inventory 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 fraction of time all servers are idle.
- 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.6Simulation is generally the best way to analyze practical stochastic systems, as realistic systems seldom yield to mathematics. The resulting sample paths7That 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 systems8Queueing systems are one example.. We use sample paths9In 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.10For 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 develops patterns for algorithmic thinking and organizing computational ideas. Section 1.3 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.4 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.5 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.11Note that while such checks are conceptually simple, the algebra can be tedious. The exercises are not intended to be easy. Hints and solutions for the exercises are available at the end of the book.
In the final stages of improving the document I used Claude and Codex to find typos, grammatical and mathematical errors, and to check notational consistency.