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 computer-based engineering systems. Designed for seniors and first-year 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

• Explain the characteristics of DES and show how they differ from classical systems.
• Describe the differences between various modeling approaches, from simple to more complex untimed to timed, and deterministic to stochastic.
• Develop two general directions in analyzing DES models:

- The classical probabilistic approach, using stochastic process theory.
- Computer simulation and sample path analysis.

• Show how to simulate DES using commercially available software or from first principles.
• Provide the basis for further study in such areas as advanced queuing theory, dynamic control of DES perturbation analysis, and sample path constructability techniques.

FEATURES OF THE TEXT

• Focus on the timed aspects of DES. The fundamentals of untimed models and analysis are presented in Chapter 2 to give the student an overview of the entire field.
• Introduction to queuing theory (Chapter 6) as a method of analysis and performance evaluation.
• Introduction to the dynamic control of queuing systems and problems such as admission control, routing, and scheduling (Chapter 7).
• Discussion of sensitivity analysis and techniques of sample path constructability for DES to introduce readers to recent research in the field (Chapter 9).
• Explicit instructions for building discrete event simulation models.
• Computer codes illustrating perturbation analysis algorithms.

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, co-auhored by Stephane Lafortune, was published in 1999. A Second Edition was published in 2006:

http://www.springer.com/engineering/robotics/book/978-0-387-33332-8

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 Input-Output Modeling Process Static and Dynamic Systems Time-varying and Time-invariant 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 Continuous-State and Discrete-State Systems Deterministic and Stochastic Systems 1.2.7 The Concept of Control 1.2.8 The Concept of Feedback Open-loop and Closed-loop Systems 1.2.9 Discrete-Time Systems 1.3 Discrete-Event Systems 1.3.1 The Concept of Event Time-driven and Event-driven Systems 1.3.2 Characteristic Properties of Discrete-Event Systems Untimed and Timed Models for Discrete-Event Systems 1.3.3 Examples of Discrete-Event 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 Discrete-Event Systems
2.1 Introduction 2.2 Languages and Automata Theory 2.2.1 Language Notation and Definitions 2.2.2 Finite-State Automata State Transition Diagrams Automata as Language Recognizers Nondeterministic Finite State Automata Equivalence of Finite-State Automata and Regular Expressions 2.2.3 State Aggregation in Automation 2.2.4 Discrete-Event 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 Discrete-Event 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 Discrete-Event 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 Discrete-Event 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 Discrete-Event Systems
4.1 Introduction 4.2 Definitions, Notations, and Classifications of Stochastic Processes 4.2.1 Continuous-state and Discrete-state Stochastic Processes 4.2.2 Continuous-time and Discrete-time Stochastic Processes 4.2.3 Some Important Classes of Stochastic Processes Stationary Processes Independent Processes Markov Processes Semi-Markov Processes Renewal Processes 4.3 Stochastic Clock Structures 4.4 Stochastic Timed State Automata 4.5 The Generalized Semi-Markov Process (GSMP) 4.5.1 Queueing Systems as Generalized Semi-Markov 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 Semi-Markov Process

Chapter 5 Markov Chains
5.1 Introduction 5.2 Discrete-Time Markov Chains 5.2.1 Model Specification 5.2.2 Transition Probabilities and the Chapman-Kolmogorov 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 Continuous-time 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 Birth-Death Chains 5.4.1 The Pure Birth Chain 5.4.2 The Poisson Process Revisited 5.4.3 Steady State Analysis of Birth-Death Chains 5.5 Uniformzation of Continuous-Time 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 Non-Markovian 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 Discrete-Event Stimulation
8.1 Introduction 8.2 The Event Scheduling Simulation Scheme 8.2.1 Simulation of a Simple Queueing System 8.3 The Process-Oriented Simulation Scheme 8.4 Discrete-Event Simulation Languages 8.5 Discrete-Event 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 Non-Terminating 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 Real-Time 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: Discrete-Event Simulation Using the SIMAN Language
Appendix 3: Infinitesimal Perturbation Analysis (IPA) Estimators