OVERVIEW
Discrete Event Systems: Modeling and
Performance Analysis is the first instructional text to be published
in an area that emerged in the early 1980s and that spans such disciplines as
systems and control theory, operations research, and computer science.
Developments in this area are impacting the design and analysis of complex
computerbased engineering systems. Designed for seniors and firstyear
graduate students, the book shows where Discrete Event Systems (DES) appear in
modern technological environments, such as computer networks, automated
manufacturing processes, and airport and highway traffic systems. The text
provides a unified framework for modeling, design, analysis, and control of these
"man made" dynamic systems.
OBJECTIVES OF THE TEXT

The classical probabilistic approach, using stochastic process theory.
 Computer simulation and sample
path analysis.
FEATURES OF THE TEXT
PREREQUISITES
A basic course on probability theory and some knowledge of
stochastic processes.
Familiarity with concepts from signals and systems.
Elementary differential equations and linear algebra.
SUPPLEMENTS
An Instructors Manual, containing solutions to the problems.
HOW TO ORDER THIS BOOK
A new version of this book, coauhored by Stephane Lafortune, was published
in 1999. A Second Edition was published in 2006:
http://www.springer.com/engineering/robotics/book/9780387333328
TABLE OF CONTENTS
Preface
Chapter 1 Systems and Models
1.1 Introduction 1.2 System and Control Basics 1.2.1 The Concept of
System 1.2.2 The InputOutput Modeling Process Static and Dynamic Systems
Timevarying and Timeinvariant Dynamic Systems 1.2.3 The Concept of State
1.2.4 The State Space Modeling Process Linear and Nonlinear Systems 1.2.5
Sample Paths of Dynamic Systems 1.2.6 State Spaces ContinuousState and
DiscreteState Systems Deterministic and Stochastic Systems 1.2.7 The Concept
of Control 1.2.8 The Concept of Feedback Openloop and Closedloop Systems
1.2.9 DiscreteTime Systems 1.3 DiscreteEvent Systems 1.3.1 The Concept of
Event Timedriven and Eventdriven Systems 1.3.2 Characteristic Properties of
DiscreteEvent Systems Untimed and Timed Models for
DiscreteEvent Systems 1.3.3 Examples of DiscreteEvent Systems Queuing Systems
Computer Systems Communication Systems Manufacturing Systems Traffic Systems
1.4 Summary of System Classifications 1.5 The Goals of System Theory
Chapter 2 Untimed
Models of DiscreteEvent Systems
2.1 Introduction 2.2 Languages and Automata Theory 2.2.1 Language
Notation and Definitions 2.2.2 FiniteState Automata State Transition Diagrams
Automata as Language Recognizers Nondeterministic Finite State Automata
Equivalence of FiniteState Automata and Regular Expressions 2.2.3 State
Aggregation in Automation 2.2.4 DiscreteEvent Systems as State Automata 2.2.5
State Automata Models for Queuing Systems 2.2.6 State Automata with Output
2.2.7 Supervisory Control of DiscreteEvent Systems 2.3 Petri Nets 2.3.1 Petri
Net Notation and Definitions 2.3.2 Petri Net Markings and State Spaces 2.3.3
Petri Net Dynamics 2.3.4 Petri Net Models for Queueing
Systems 2.3.5 Comparison of Petri Net and State Automata Models 2.4 Analysis of
Untimed Models of DiscreteEvent Systems 2.4.1
Problem Classification Boundedness Conservation Liveness and Deadlocks State Reachability
State Coverability Persistence Language Recognition
2.4.2 The Coverability Tree 2.4.3 Applications of the
Coverability Tree Boundedness
Problems Conseration Problems Coverability
Problems Coverability Tree Limitations
Chapter 3 Time Models of DiscreteEvent
Systems
3.1 Introduction 3.2 Timed State Automata 3.2.1 The Clock Structure
3.2.2 Event Timing Dynamics 3.2.3 A State Space Model 3.2.4 Queueing
Systems as Timed State Automata 3.2.5 The Event Scheduling Scheme 3.3 Timed
Petri Nets 3.3.1 Time Petri Net Dynamics 3.3.2 Queueing
Systems as Timed Petri Nets 3.4 Dioid Algebras 3.4.1
Basic Properties of the (max, +) Algebra 3.4.2 Modeling Queueing
Systems in the (max, +) Algebra
Chapter 4 Stochastic Timed Models for
DiscreteEvent Systems
4.1 Introduction 4.2 Definitions, Notations, and Classifications of
Stochastic Processes 4.2.1 Continuousstate and Discretestate Stochastic
Processes 4.2.2 Continuoustime and Discretetime Stochastic Processes 4.2.3
Some Important Classes of Stochastic Processes Stationary Processes Independent
Processes Markov Processes SemiMarkov Processes Renewal Processes 4.3
Stochastic Clock Structures 4.4 Stochastic Timed State Automata 4.5 The
Generalized SemiMarkov Process (GSMP) 4.5.1 Queueing
Systems as Generalized SemiMarkov Processes 4.5.2 GSMP Analysis 4.6 The
Poisson Counting Process 4.7 Properties of The Poisson Process 4.7.1
Exponentially Distributed Interevent Times 4.7.2 The Memoryless Property 4.7.3 Superposition of Poisson
Processes 4.7.4 The Residual Lifetime Paradox 4.8 The GSMP With a Poisson Clock
Structure 4.8.1 Distribution of Interevent Times
4.8.2 Distribution of Events 4.8.3 Markov Chains 4.9 Extensions of The
Generalized SemiMarkov Process
Chapter 5 Markov Chains
5.1 Introduction 5.2 DiscreteTime Markov Chains 5.2.1 Model
Specification 5.2.2 Transition Probabilities and the ChapmanKolmogorov Equations 5.2.3 Homogeneous Markov Chains 5.2.4
The Transition Probability Matrix 5.2.5 State Holding Times 5.2.6 State
Probabilities 5.2.7 Transient Analysis 5.2.8 Classification of State Null and
Positive Recurrent States Periodic and Aperiodic
States Summary of State Classifications 5.2.9 Steady State Analysis 5.2.10
Irreducible Markov Chains 5.2.11 Reducible Markov Chains 5.3 Continuoustime
Markov Chains 5.3.1 Model Specifications 5.3.2 Transition Function 5.3.3 The
Transition Rate Matrix 5.3.4 Homogeneous Markov Chains 5.3.5 State Holding
Times 5.3.6 Physical Interpretation and Properties of the Transition Rate
Matrix 5.3.7 Transition Probabilities 5.3.8 State Probabilities 5.3.9 Transient
Analysis 5.3.10 Steady State Analysis 5.4 BirthDeath Chains 5.4.1 The Pure
Birth Chain 5.4.2 The Poisson Process Revisited 5.4.3 Steady State Analysis of
BirthDeath Chains 5.5 Uniformzation of
ContinuousTime Markov Chains
Chapter 6 Introduction to Queueing Theory
6.1 Introduction 6.2 Specification of Queueing
Models 6.2.1 Stochastic Models for Arrival and Service Processes 6.2.2
Structural Parameters 6.2.3 Operating Policies 6.2.4 The A/B/m /K
Notation 6.2.5 Open and Closed Queueing Systems 6.3
Performance of a Queuing System 6.4 Queueing System
Dynamics 6.5 Little's Law 6.6 Analysis of Simple Markovian Queueing Systems 6.6.1
The M/M/1 Queueing System 6.6.2 The M/M/m
Queueing System 6.6.3 The M/M/ Queueing System 6.6.4 The M/M/1/K Queueing System 6.6.5 The M/M/m/m Queueing System 6.6.6 The M/M/1//N Queueing System 6.6.7 The M/M/m/K/N Queueing System 6.7 Markovian Queueing Networks 6.7.1 The Departure Process of the M/M/1
Queueing System 6.7.2 Open Queueing
Networks 6.7.3 Closed Queueing Networks Computation
of the Normalization Constant C(N) Mean Value Analysis 6.7.4 Product
Form Networks 6.8 NonMarkovian Queueing
Systems 6.8.1 The Method of Stages 6.8.2 Mean Value Analysis of the M/G/1
Queueing System 6.8.3 Software Tools for the Analysis
of General Queueing Networks
Chapter 7 Controlled Markov Chains
7.1 Introduction 7.2 The Nature of "Control" in Markov
Chains 7.3 Markov Decision Processes 7.3.1 Cost Criteria 7.3.2 Uniformization 7.3.3 The Basic Markov Decision Problem 7.4
Solving Markov Decision Problems 7.4.1 The Basic Idea of Dynamic Programming
7.4.2 Dynamic Programming and the Optimality Equation Convergence of the
Dynamic Programming Algorithm The Optimality Equation 7.4.3 Extensions to
Unbounded and Undiscounted Costs 7.4.4 Optimization of the Average Cost
Criterion 7.5 Control of Queueing Systems 7.5.1 The
Admission Problem 7.5.2 The Routing Problem 7.5.3 The Scheduling Problem
Chapter 8 Introduction to DiscreteEvent
Stimulation
8.1 Introduction 8.2 The Event Scheduling Simulation Scheme 8.2.1
Simulation of a Simple Queueing System 8.3 The
ProcessOriented Simulation Scheme 8.4 DiscreteEvent Simulation Languages 8.5
DiscreteEvent Simulation Using the Siman
Language 8.5.1 The MODEL File  Some Basic Block Functions 8.5.2 The MODEL File
 Some Data Collection Block Functions 8.5.3 The EXPERIMENT File 8.5.4 More
Elaborate Models 8.5.5 Common Mistakes 8.6 Random Number Generation 8.6.1 The
Linear Congruential Technique 8.7 Random Variate Generation 8.7.1 The Inverse Transform Technique
8.7.2 The Convolution Technique 8.7.3 The Composition Technique 8.7.4 The
Acceptance  Rejection Technique 8.8 Output Analysis 8.8.1 Simulation
Characterizations 8.8.2 Parameter Estimation Point Estimation Interval
Estimation 8.8.3 Output Analysis of Terminating Simulations 8.8.4 Output
Analysis of NonTerminating Simulations Replications with Deletions Batch Means
Regenerative Simulation
Chapter 9 Sensitivity Analysis and Sample
Path Constructability
9.1 Introduction 9.2 Sample Functions and Their Derivatives 9.2.1
Performance Sensitivities 9.2.2 The Uses of Sensitivity Information 9.3
Perturbation Analysis: Some Key Ideas 9.4 Perturbation Analysis of GI/G/1 Queueing Systems 9.4.1 Perturbation Generation Derivatives
of Random Variated Scale and Location Parameters Parameters of Discrete Distributions 9.4.2 Perturbation
Propagation Infinitesimal and Finite Perturbaton
Analysis 9.4.3 Infinitesimal Perturbation Analysis (IPA) 9.4.4 Implementation
of IPA for the GI/G/1 System 9.5 IPA for Stochastic Time Automata 9.5.1 Event
Time Derivatives 9.5.2 Sample Function Derivatives 9.5.3 Performance Measure
Derivatives The Commuting Condition Continuity of Sample Functions Unbiasedness of IPA Estimators 9.5.4 IPA Applications
Sensitivity Analysis of Queueing Networks Performance
Optimization 9.6 The Sensitivity Estimation Problem Revisited 9.7 Extensions of
IPA 9.7.1 Discontinuities due to Multiple Customer Classes 9.7.2
Discontinuities due to Touting Decisions 9.7. Discontinuities due to Blocking:
IPA with Event Rescheduling 9.8 Smoothed Perturbation Analysis (SPA) 9.8.1
Systems with RealTime Constraints 9.8.2 Marking and Phantomizing
Techniques 9.9 Perturbation Analysis for Finite Parameter Changes 9.10 Sample
Path Constructability Techniques
Appendix 1: A Review of
Probability Theory
Appendix 2: DiscreteEvent Simulation Using the SIMAN Language
Appendix 3: Infinitesimal Perturbation Analysis (IPA) Estimators