| |
| |
Preface - Second Edition | |
| |
| |
Preface | |
| |
| |
Organization of Book | |
| |
| |
| |
Systems and Models | |
| |
| |
| |
Introduction | |
| |
| |
| |
System and Control Basics | |
| |
| |
| |
The Concept of System | |
| |
| |
| |
The Input-Output Modeling Process | |
| |
| |
| |
The Concept of State | |
| |
| |
| |
The State Space Modeling Process | |
| |
| |
| |
Sample Paths of Dynamic Systems | |
| |
| |
| |
State Spaces | |
| |
| |
| |
The Concept of Control | |
| |
| |
| |
The Concept of Feedback | |
| |
| |
| |
Discrete-Time Systems | |
| |
| |
| |
Discrete Event Systems | |
| |
| |
| |
The Concept of Event | |
| |
| |
| |
Characteristic Properties of Discrete Event Systems | |
| |
| |
| |
The Three Levels of Abstraction in the Study of Discrete Event Systems | |
| |
| |
| |
Examples of Discrete Event Systems | |
| |
| |
| |
Hybrid Systems | |
| |
| |
| |
Summary Of System Classifications | |
| |
| |
| |
The Goals Of System Theory | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Languages and Automata | |
| |
| |
| |
Introduction | |
| |
| |
| |
The Concepts of Languages and Automata | |
| |
| |
| |
Language Models of Discrete-Event Systems | |
| |
| |
| |
Automata | |
| |
| |
| |
Languages Represented by Automata | |
| |
| |
| |
Nondeterministic Automata | |
| |
| |
| |
Automata with Inputs and Outputs | |
| |
| |
| |
Operations on Automata | |
| |
| |
| |
Unary Operations | |
| |
| |
| |
Composition Operations | |
| |
| |
| |
State Space Refinement | |
| |
| |
| |
Observer Automata | |
| |
| |
| |
Equivalence of Automata | |
| |
| |
| |
Finite-State Automata | |
| |
| |
| |
Definition and Properties of Regular Languages | |
| |
| |
| |
Regular Expressions | |
| |
| |
| |
State Space Minimization | |
| |
| |
| |
Analysis Of Discrete-Event Systems | |
| |
| |
| |
Safety and Blocking Properties | |
| |
| |
| |
Partially-Observed DES | |
| |
| |
| |
Event Diagnosis | |
| |
| |
| |
Software Tools and Computational Complexity Issues | |
| |
| |
| |
Formal Verification and Model Checking | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Supervisory Control | |
| |
| |
| |
Introduction | |
| |
| |
| |
Feedback Control with Supervisors | |
| |
| |
| |
Controlled Discrete Event Systems | |
| |
| |
| |
Control Under Partial Observation | |
| |
| |
| |
Specifications on Controlled System | |
| |
| |
| |
Modeling of Specifications as Automata | |
| |
| |
| |
The Need for Formal Methods | |
| |
| |
| |
Control with Partial Controllability | |
| |
| |
| |
Controllability Theorem | |
| |
| |
| |
Realization of Supervisors | |
| |
| |
| |
The Property of Controllability | |
| |
| |
| |
Some Supervisory Control Problems and Their Solutions | |
| |
| |
| |
Computation of <$>K^{\uparrow C}<$>: Prefix-Closed Case | |
| |
| |
| |
Computation of <$>K^{\downarrow C}<$> | |
| |
| |
| |
Nonblocking Control | |
| |
| |
| |
Nonblocking Controllability Theorem | |
| |
| |
| |
Nonblocking Supervisory Control | |
| |
| |
| |
Computation of <$>K^{\uparrow C}<$>: General Case | |
| |
| |
| |
Dealing with Blocking Supervisors | |
| |
| |
| |
Control with Modular Specifications | |
| |
| |
| |
Control Under Partial Observation | |
| |
| |
| |
Controllability and Observability Theorem | |
| |
| |
| |
Realization of P-Supervisors | |
| |
| |
| |
The Property of Observability | |
| |
| |
| |
Supervisory Control Problems Under Partial Observation | |
| |
| |
| |
The Property of Normality | |
| |
| |
| |
Decentralized Control | |
| |
| |
| |
Conjunctive Architecture | |
| |
| |
| |
Disjunctive Architecture | |
| |
| |
| |
Combined Architecture | |
| |
| |
| |
Realization of Decentralized Supervisors | |
| |
| |
| |
The Property of Coobservability | |
| |
| |
| |
Undecidability in Decentralized Control | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Petri Nets | |
| |
| |
| |
Introduction | |
| |
| |
| |
Petri Net Basics | |
| |
| |
| |
Petri Net Notation and Definitions | |
| |
| |
| |
Petri Net Markings and State Spaces | |
| |
| |
| |
Petri Net Dynamics | |
| |
| |
| |
Petri Net Languages | |
| |
| |
| |
Petri Net Models for Queueing Systems | |
| |
| |
| |
Comparison of Petri Nets and Automata | |
| |
| |
| |
Analysis Of Petri Nets | |
| |
| |
| |
Problem Classification | |
| |
| |
| |
The Coverability Tree | |
| |
| |
| |
Applications of the Coverability Tree | |
| |
| |
| |
Linear-Algebraic Techniques | |
| |
| |
| |
Control of Petri Nets | |
| |
| |
| |
Petri Nets and Supervisory Control Theory | |
| |
| |
| |
State-Based Control of Petri Nets | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Timed and Hybrid Models | |
| |
| |
| |
Introduction | |
| |
| |
| |
Timed Automata | |
| |
| |
| |
The Clock Structure | |
| |
| |
| |
Event Timing Dynamics | |
| |
| |
| |
A State Space Model | |
| |
| |
| |
Queueing Systems as Timed Automata | |
| |
| |
| |
The Event Scheduling Scheme | |
| |
| |
| |
Timed Petri Nets | |
| |
| |
| |
Timed Petri Net Dynamics | |
| |
| |
| |
Queueing Systems as Timed Petri Nets | |
| |
| |
| |
Dioid Algebras | |
| |
| |
| |
Basic Properties of the (max, +) Algebra | |
| |
| |
| |
Modeling Queueing Systems in the (max, +) Algebra | |
| |
| |
| |
Alternative Timed Models | |
| |
| |
| |
Timed Automata with Guards | |
| |
| |
| |
Model Definition | |
| |
| |
| |
Model Execution | |
| |
| |
| |
Parallel Composition | |
| |
| |
| |
Untiming | |
| |
| |
| |
Hybrid Models | |
| |
| |
| |
Hybrid Automata | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Stochastic Timed Automata | |
| |
| |
| |
Introduction | |
| |
| |
| |
Stochastic Process Basics | |
| |
| |
| |
Continuous-state and Discrete-state Stochastic Processes | |
| |
| |
| |
Continuous-time and Discrete-time Stochastic Processes | |
| |
| |
| |
Some Important Classes of Stochastic Processes | |
| |
| |
| |
Stochastic Clock Structures | |
| |
| |
| |
Stochastic Timed Automata | |
| |
| |
| |
The Generalized Semi-Markov Process | |
| |
| |
| |
Queueing Systems as Stochastic Timed Automata | |
| |
| |
| |
GSMP Analysis | |
| |
| |
| |
The Poisson Counting Process | |
| |
| |
| |
Properties of the Poisson Process | |
| |
| |
| |
Exponentially Distributed Interevent Times | |
| |
| |
| |
The Memoryless Property | |
| |
| |
| |
Superposition of Poisson Processes | |
| |
| |
| |
The Residual Lifetime Paradox | |
| |
| |
| |
Automata with Poisson Clock Structure | |
| |
| |
| |
Distribution of Interevent Times | |
| |
| |
| |
Distribution of Events | |
| |
| |
| |
Markov Chains | |
| |
| |
| |
Extensions of the GSMP | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Markov Chains | |
| |
| |
| |
Introduction | |
| |
| |
| |
Discrete-Time Markov Chains | |
| |
| |
| |
Model Specification | |
| |
| |
| |
Transition Probabilities and the Chapman-Kolmogorov Equations | |
| |
| |
| |
Homogeneous Markov Chains | |
| |
| |
| |
The Transition Probability Matrix | |
| |
| |
| |
State Holding Times | |
| |
| |
| |
State Probabilities | |
| |
| |
| |
Transient Analysis | |
| |
| |
| |
Classification of States | |
| |
| |
| |
Steady State Analysis | |
| |
| |
| |
Irreducible Markov Chains | |
| |
| |
| |
Reducible Markov Chains | |
| |
| |
| |
Continuous-Time Markov Chains | |
| |
| |
| |
Model Specification | |
| |
| |
| |
Transition Functions | |
| |
| |
| |
The Transition Rate Matrix | |
| |
| |
| |
Homogeneous Markov Chains | |
| |
| |
| |
State Holding Times | |
| |
| |
| |
Physical Interpretation and Properties of the Transition Rate Matrix | |
| |
| |
| |
Transition Probabilities | |
| |
| |
| |
State Probabilities | |
| |
| |
| |
Transient Analysis | |
| |
| |
| |
Steady State Analysis | |
| |
| |
| |
Birth-Death Chains | |
| |
| |
| |
The Pure Birth Chain | |
| |
| |
| |
The Poisson Process Revisited | |
| |
| |
| |
Steady State Analysis of Birth-Death Chains | |
| |
| |
| |
Uniformization of Markov Chains | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Introduction to Queueing Theory | |
| |
| |
| |
Introduction | |
| |
| |
| |
Specification of Queueing Models | |
| |
| |
| |
Stochastic Models for Arrival and Service Processes | |
| |
| |
| |
Structural Parameters | |
| |
| |
| |
Operating Policies | |
| |
| |
| |
The A/B/m/K Notation | |
| |
| |
| |
Open and Closed Queueing Systems | |
| |
| |
| |
Performance of A Queueing System | |
| |
| |
| |
Queueing System Dynamics | |
| |
| |
| |
Little's Law | |
| |
| |
| |
Simple Markovian Queueing Systems | |
| |
| |
| |
The M/M/1 Queueing System | |
| |
| |
| |
The M/M/m Queueing System | |
| |
| |
| |
The M/M/∞ Queueing System | |
| |
| |
| |
The M/M/1/K Queueing System | |
| |
| |
| |
The M/M/m/m Queueing System | |
| |
| |
| |
The M/M/1//N Queueing System | |
| |
| |
| |
The M/M/m/K/N Queueing System | |
| |
| |
| |
Markovian Queueing Networks | |
| |
| |
| |
The Departure Process of the M/M/1 Queueing System | |
| |
| |
| |
Open Queueing Networks | |
| |
| |
| |
Closed Queueing Networks | |
| |
| |
| |
Product Form Networks | |
| |
| |
| |
Non-Markovian Queueing Systems | |
| |
| |
| |
The Method of Stages | |
| |
| |
| |
Mean Value Analysis of the M/G/1 Queueing System | |
| |
| |
| |
Software Tools for the Analysis of General Queueing Networks | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Controlled Markov Chains | |
| |
| |
| |
Introduction | |
| |
| |
| |
Applying ""Control"" in Markov Chains | |
| |
| |
| |
Markov Decision Processes | |
| |
| |
| |
Cost Criteria | |
| |
| |
| |
Uniformization | |
| |
| |
| |
The Basic Markov Decision Problem | |
| |
| |
| |
Solving Markov Decision Problems | |
| |
| |
| |
The Basic Idea of Dynamic Programming | |
| |
| |
| |
Dynamic Programming and the Optimality Equation | |
| |
| |
| |
Extensions to Unbounded and Undiscounted Costs | |
| |
| |
| |
Optimization of the Average Cost Criterion | |
| |
| |
| |
Control of Queueing Systems | |
| |
| |
| |
The Admission Problem | |
| |
| |
| |
The Routing Problem | |
| |
| |
| |
The Scheduling Problem | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Introduction to Discrete-Event Simulation | |
| |
| |
| |
Introduction | |
| |
| |
| |
The Event Scheduling Scheme | |
| |
| |
| |
Simulation of a Simple Queueing System | |
| |
| |
| |
The Process-Oriented Simulation Scheme | |
| |
| |
| |
Discrete-Event Simulation Languages | |
| |
| |
| |
Random Number Generation | |
| |
| |
| |
The Linear Congruential Technique | |
| |
| |
| |
Random Variate Generation | |
| |
| |
| |
The Inverse Transform Technique | |
| |
| |
| |
The Convolution Technique | |
| |
| |
| |
The Composition Technique | |
| |
| |
| |
The Acceptance-Rejection Technique | |
| |
| |
| |
Output Analysis | |
| |
| |
| |
Simulation Characterizations | |
| |
| |
| |
Parameter Estimation | |
| |
| |
| |
Output Analysis of Terminating Simulations | |
| |
| |
| |
Output Analysis of Non-Terminating Simulations | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Sensitivity Analysis and Concurrent Estimation | |
| |
| |
| |
Introduction | |
| |
| |
| |
Sample Functions and their Derivatives | |
| |
| |
| |
Performance Sensitivities | |
| |
| |
| |
The Uses of Sensitivity Information | |
| |
| |
| |
Perturbation Analysis: Some Key Ideas | |
| |
| |
| |
PA of GI/G/1 Queueing Systems | |
| |
| |
| |
Perturbation Generation | |
| |
| |
| |
Perturbation Propagation | |
| |
| |
| |
Infinitesimal Perturbation Analysis (IPA) | |
| |
| |
| |
Implementation of IPA for the GI/G/1System | |
| |
| |
| |
IPA for Stochastic Timed Automata | |
| |
| |
| |
Event Time Derivatives | |
| |
| |
| |
Sample Function Derivatives | |
| |
| |
| |
Performance Measure Derivatives | |
| |
| |
| |
IPA Applications | |
| |
| |
| |
Sensitivity Estimation Revisited | |
| |
| |
| |
Extensions of IPA | |
| |
| |
| |
Discontinuities due to Multiple Customer Classes | |
| |
| |
| |
Discontinuities due to Routing Decisions | |
| |
| |
| |
Discontinuities due to Blocking: IPA with Event Rescheduling (RIPA) | |
| |
| |
| |
Smoothed Perturbation Analysis (SPA) | |
| |
| |
| |
Systems with Real-Time Constraints | |
| |
| |
| |
Marking and Phantomizing Techniques | |
| |
| |
| |
IPA for Stochastic Hybrid Automata | |
| |
| |
| |
Stochastic Fluid Models (SFMs) | |
| |
| |
| |
Sample paths of SFMs | |
| |
| |
| |
Comparing SFMs to Their DES Counterparts | |
| |
| |
| |
IPA for a Single-Class Single-Node SFM | |
| |
| |
| |
IPA for SFMs with Multiple Classes, Multiple Nodes and Feedback | |
| |
| |
| |
PA for Finite Parameter Changes | |
| |
| |
| |
Concurrent Estimation | |
| |
| |
| |
The Sample Path Constructability Problem | |
| |
| |
| |
Uses of Concurrent Estimation: ""Rapid Learning"" | |
| |
| |
| |
Sample Path Constructability Conditions | |
| |
| |
| |
The Standard Clock Approach | |
| |
| |
| |
Augmented System Analysis | |
| |
| |
| |
The ""Time Warping"" Algorithm | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Selected References | |
| |
| |
| |
Review of Probability Theory | |
| |
| |
| |
Basic Concepts and Definitions | |
| |
| |
| |
Conditional Probability | |
| |
| |
| |
Random Variables | |
| |
| |
| |
Conditional Distributions | |
| |
| |
| |
Functions of Random Variables | |
| |
| |
| |
Expectation | |
| |
| |
| |
Characteristic Functions | |
| |
| |
| |
Random Sequences and Random Processes | |
| |
| |
| |
IPA Estimator | |
| |
| |
Index | |
| |
| |
About the Authors | |