Numerical Methods for Solving Discrete Event Systems | springerprofessional.de

Springer Professional

Top

2022 | Book

Read chapter Read first chapter

Numerical Methods for Solving Discrete Event Systems

With Applications to Queueing Systems

Authors: Winfried Grassmann, Javad Tavakoli

Publisher: Springer International Publishing

Book Series : CMS/CAIMS Books in Mathematics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access

About this book

This graduate textbook provides an alternative to discrete event simulation. It describes how to formulate discrete event systems, how to convert them into Markov chains, and how to calculate their transient and equilibrium probabilities. The most appropriate methods for finding these probabilities are described in some detail, and templates for efficient algorithms are provided. These algorithms can be executed on any laptop, even in cases where the Markov chain has hundreds of thousands of states. This book features the probabilistic interpretation of Gaussian elimination, a concept that unifies many of the topics covered, such as embedded Markov chains and matrix analytic methods.

The material provided should aid practitioners significantly to solve their problems. This book also provides an interesting approach to teaching courses of stochastic processes.

Advertisement

Table of Contents

Frontmatter

Chapter 1. Basic Concepts and Definitions

Abstract

This book is about stochastic systems, but instead of simulation, as in discrete event simulation, we use Markov chains to analyze these systems. This chapter provides the basic mathematical tools for this endeavor. We thus describe what a system is, and how to work with Markov chains. Since our systems are stochastic, we also review random variables and their distributions. Many systems covered in this book are in fact queueing systems, and we therefore discuss a notation to describe such systems, which is due to Kendall. We will also cover the so-called Little’s law, which provides a relation between expected waiting times and the expected number of elements in a given subsystem. To simplify our notations, we frequently use sets, which are covered in the last section of this chapter.

Winfried Grassmann, Javad Tavakoli

Chapter 2. Systems with Events Generated by Poisson or by Binomial Processes

Abstract

This chapter is mainly devoted to systems where all events are generated by Poisson processes. Hence, arrivals are Poisson, and so are moves from one waiting line to another, as well as departures. However, the rate of the process may depend on the state of the system. We will also discuss systems where the events are generated by binomial processes. Models include the M/M/1 queue, a tandem queue and several other examples.

Winfried Grassmann, Javad Tavakoli

Chapter 3. Generating the Transition Matrix

Abstract

Clearly, the only practical way to generate the transition matrix of any discrete event systems with more than a hundred states is by using a computer program. This chapter therefore describes efficient algorithms for the matrix generation. In order to create the transition matrix, we first have to enumerate all state vectors. Next, we have to give each state a state number, which can be used both as a row and a column number for the transition matrix. After that, the target states for each row must be determined, and these target states must be converted into state numbers in order to place the entries into the correct positions in the transition matrix. To accomplish these tasks, a number of enumeration algorithms are proposed, and their use to generate the transition matrix is explained.

Winfried Grassmann, Javad Tavakoli

Chapter 4. Systems with Events Created by Renewal Processes

Abstract

A frequent assumption in discrete event systems is that the times between events of a certain type, such as the times between arrivals, are independent random variables. Technically, this means that the process generating the event type in question forms a renewal processes, with the events being the renewals. We call a discrete event system a renewal event system if the times between events are renewal processes. Here, we include renewal processes that can be suspended, but that can be restarted at a later time. For instance, departures from a waiting line can form a renewal process, but this process ends as soon waiting line is empty, to be resumed as soon as there is an arrival. Renewal event systems are made Markovian by either using the time since the last event (the age) or the time to the next event (the remaining life) as supplementary state variables.

Winfried Grassmann, Javad Tavakoli

Chapter 5. Systems with Events Created by Phase-type Processes

Abstract

In this chapter, the times between events are assumed to have phase-type (PH) distributions. We first discuss these distributions, with emphasis on the the distributions that are sums or mixtures. The models used to demonstrate these distributions include multiserver queues and tandem queues.

Winfried Grassmann, Javad Tavakoli

Chapter 6. Execution Times, Space Requirements, and Accuracy of Algorithms

Abstract

The quality of an algorithm can be judged according to the following three criteria: how long it takes to obtain an answer, how much memory is required, and how accurate are the results. All these criteria will be covered in this chapter. The time needed for finding an answer is covered under the heading of time complexity , and the requirement for memory needed to execute the algorithm is covered under the heading of space complexity . Sources of inaccuracies include data errors, rounding errors and the errors due to truncation of sums or integrals.

Winfried Grassmann, Javad Tavakoli

Chapter 7. Transient Solutions of Markov Chains

Abstract

In the previous chapters, we have shown how to generate the transition matrices of discrete-event systems, and we found that these matrices are typically large, but they tend to be sparse. This requires the use of efficient numerical methods for finding transient probabilities. A particularly efficient method for finding transient solutions is the so called randomization or uniformization method which is discussed in details. Several applications are provided, including a tandem queue and waiting-time models.

Winfried Grassmann, Javad Tavakoli

Chapter 8. Moving toward the Statistical Equilibrium

Abstract

We have repeatedly referred to equilibrium distributions of Markov chains, but we have not yet addressed the question of whether or not they exist, and if they exist, whether or not they depend on the initial state. These are the questions addressed in this chapter. The tools to resolve these questions include the classification of states, as well as the characterization of transient solutions by eigenvalues.

Winfried Grassmann, Javad Tavakoli

Chapter 9. Equilibrium Solutions of Markov Chains and Related Topics

Abstract

In this chapter, we discuss how to find the equilibrium probabilities of ergodic, finite-state Markov chains. Mathematically, there is only a minor difference between the equilibrium equations of DTMCs and CTMCs. In particular, we discuss the state elimination method, a variant of Gaussian elimination that has probabilistic interpretation. This then leads to the fundamental matrix and its use. Iterative methods are also described, and illustrated by examples.

Winfried Grassmann, Javad Tavakoli

Chapter 10. Reducing the Supplementary State Space Through Embedding

Abstract

The state space of Markov chains increases exponentially with the number of state variables, and embedding helps reduce the need for supplementary state variables. Two types of embedding points are discussed: One can embed the process at the points where any of the events happens, or one can select a specific event type, such as arrivals, and use these as embedding points.

Winfried Grassmann, Javad Tavakoli

Chapter 11. Systems with Independent or Almost Independent Components

Abstract

The complexity of a system increases exponentially with the number of state variables, and for this reason, it is advantageous to divide the system into several subsystems which can be dealt with separately. This requires that the subsystems are independent. Two kinds of independence must be distinguished: Independence already for transient solutions, and independence only when the system is in equilibrium. To deal with the first kind of independence, Kronecker products are used. The second kind of independence leads to the discussion of Jackson networks.

Winfried Grassmann, Javad Tavakoli

Chapter 12. Infinite-state Markov Chains and Matrix Analytic Methods (MAM)

Abstract

In infinite-state Markov chains, one of the key questions is how to decide when the process diverges, and when it converges. This is discussed for systems where the rows repeat. These come in two flavors: the rows may consist of scalars, or they may consist of matrices. In both cases, we present algorithms to find the equilibrium probabilities if they exist. These algorithms are based on a generalization of the state elimination method. It is shown that this method is equivalent to the MAM method introduced by Neuts. Alternatively, one can use characteristic roots in the scalar case, and eigenvalues in the matrix-base case.

Winfried Grassmann, Javad Tavakoli

Backmatter

Title: Numerical Methods for Solving Discrete Event Systems
Authors: Winfried Grassmann
Javad Tavakoli
Copyright Year: 2022
Publisher: Springer International Publishing
Electronic ISBN: 978-3-031-10082-6
Print ISBN: 978-3-031-10081-9
DOI: https://doi.org/10.1007/978-3-031-10082-6

Premium Partner