Introduction to Discrete Event Systems, 1st and 2nd Editions

Christos G. Cassandras and Stephane Lafortune

The rapid evolution of computing, communication, and sensor technologies has brought about the proliferation of new dynamic systems, mostly technological and often highly complex. Examples are all around us: computer and communication networks; automated manufacturing systems; air traffic control systems; and distributed software systems. The “activity” in these systems is governed by operational rules designed by humans; their dynamics are therefore characterized by asynchronous occurrences of discrete events. These features lend themselves to the term discrete event system for this class of dynamic systems.

A substantial portion of this book is a revised version of Discrete Event Systems: Modeling and Performance Analysis (1993), written by the first author, which received the 1999 HAROLD CHESTNUT PRIZE awarded by the International Federation of Automatic Control for best control engineering textbook. This new expanded book is intended to be a comprehensive introduction to the field of discrete event systems, emphasizing breadth of coverage and accessibility of the material to readers with possibly different backgrounds. Its key feature is the emphasis placed on a unified modeling framework that transcends specific application areas and allows linking of the following topics in a coherent manner: language and automata theory, supervisory control, Petri net theory, (max,+) algebra, Markov chains and queuEing theory, discrete-event simulation, perturbation analysis, and concurrent estimation techniques. Until now, these topics had been treated in separate books or in research literature only.

Introduction to Discrete Event Systems is written as a textbook for courses at the senior undergraduate level or the first-year graduate level. It will be of interest to students in a variety of disciplines where the study of discrete event systems is relevant: control, communications, computer engineering, computer science, manufacturing engineering, operations research, and industrial engineering.

**Table of Contents**

Preface

1. Systems and Models

Introduction

System and Control Basics

Discrete Event Systems

Summary of System Classifications

The Goals of System Theory

Summary & Problems

Selected References

2. Languages and Automata

Introduction

The Concepts of Languages and Automata

Operations on Automata

Finite-State Automata

Analysis of Discrete-Event Systems

Summary & Problems

Selected References

3. Supervisory Control

Introduction

Feedback Control with Supervisors

Specifications on Controlled System

Dealing with Uncontrollability

Dealing with Blocking

Modular Control

Dealing with Unobservability

Decentralized Control

Summary & Problems

Selected Reference

4. Petri Nets

Introduction

Petri Net Basics

Comparison of Petri Nets and Automata

Analysis of Petri Nets

Summary & Problems

Selected References

5. Timed Models

Introduction

Timed Automata

Timed Petri Nets

Dioid Algebras

Concluding Comments

Summary & Problems

Selected References

6. Stochastic Timed Automata

Introduction

Stochastic Process Basics

Stochastic Clock Structures

Stochastic Timed Automata

The Generalized Semi-Markov Process

The Poisson Counting Process

Properties of the Poisson Process

Automata with Poisson Clock Structure

Extensions of the GSMP

Summary & Problems

Selected References

7. Markov Chains

Introduction

Discrete-Time Markov Chains

Continuous-Time Markov Chains

Birth-Death Chains

Uniformization of Markov Chains

Summary & Problems

Selected References

8. Introduction to Queueing Theory

Introduction

Specification of Queueing Models

Performance of a Queueing System

Queueing System Dynamics

Little’s Law

Simple Markovian Queueing Systems

Markovian Queueing Networks

Non-Markovian Queueing Systems

Summary & Problems

Selected References

9. Controlled Markov Chains

Introduction

Applying “Control” in Markov Chains

Markov Decision Processes

Solving Markov Decision Problems

Control of Queuing Systems

Summary & Problems

Selected References

10.Introduction to Discrete-Event Simulation

Introduction

The Event Scheduling Scheme

The Process-Oriented Simulation Scheme

Discrete-Event Simulation Languages

Random Number Generation

Random Variate Generation

Output Analysis

Summary & Problems

Selected References

11. Sensitivity Analysis & Concurrent Estimation

Introduction

Sample Functions and Their Derivatives

Perturbation Analysis: Some Key Ideas

PA of GI/G/ 1 Queuing Systems

IPA for Stochastic Timed Automata

Sensitivity Estimation Revisited

Extensions of IPA

Smoothed Perturbation Analysis (SPA)

PA for Finite Parameter Changes

Concurrent Estimation

Summary & Problems

Selected References

Appendices

I. Review of Probability Theory

II. IPA Estimator

Index

ERRATA

PDF file of Errata in the book: errata.pdf

If you find a typographical error or have any questions regarding any part of the book, please contact either author:

Christos G. Cassandras, cgc AT bu.edu

Stephane Lafortune, stephane AT eecs.umich.edu

INSTRUCTOR’S AIDS

– Solutions to all problems are available directly from the authors.

– Additional software, interactive web sites, animated presentations on special topics related to Discrete Event Systems are listed in Related Web Sites.

FEEDBACK TO AUTHORS

The authors would appreciate to hear your comments on the book, suggestions, specific questions, or any issue related to Discrete Event Systems.