Introduction to Stochastic Processes and Simulation

6Queueing Systems

CONCEPTS DISCUSSED IN THIS CHAPTER.– This chapter directly applies a lot of what was covered in the previous chapter, especially the Poisson process.

After some definitions relating to queueing systems, we study the M/M/1 queue.

We then look at the more complex M/M/S queue.

The lengthy calculations are given in the appendix.

Recommended reading: [FAU 79, PHE 77, RUE 89].

6.1. Introduction

The phenomenon of queueing is common: waiting at a counter, the build-up of traffic jams and congestion, etc. To control these phenomena, we need to model them.

A queueing system is composed of queues and several stations. In what follows, we will only consider the case of a single queue. Figure 6.1 shows a queueing system with a single queue and a single station.

Individuals (as the elements are often called by analogy with a human queue) arrive in the queue from a source that can be infinite (open systems) or finite (closed systems). They advance in the queue following a particular priority, then are “served” individually at a station. They then leave the system.

Figure 6.1. Queueing system

Two important parameters, usually stochastic, determine the behavior of the system over time:

• - the frequency of arrival of individuals;
• - the duration of service at the station.

Historically, the phenomenon of queueing has been studied since the beginning of the 20th Century, often ...