Introduction to Discrete Event Systems 2nd Edition
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.
- RELATED WEB SITES
Resources including a multimedia introduction to Discrete Event Systems and a number of interactive java applets. - The library of routines UMDES-LIB.
- Information on the software package CTC.
- The “World of Petri Nets”