Introduction to Discrete Event Systems (eBook)

Christos G. Cassandras is Professor of Manufacturing Engineering and Professor of Electrical and Computer Engineering at Boston University. He received degrees from Yale University (B.S., 1977), Stanford University (M.S.E.E., 1978), and Harvard University (S.M., 1979; Ph.D., 1982). In 1982-84 he was with ITP Boston, Inc. where he worked on the design of automated manufacturing systems. In 1984-1996 he was a faculty member at the Department of Electrical and Computer Engineering, University of Massachusetts/Amherst. He specializes in the areas of discrete event and hybrid systems, stochastic optimization, and computer simulation, with applications to computer and sensor networks, manufacturing systems, and transportation systems. He has published over 200 refereed papers in these areas, and two textbooks. He has guest-edited several technical journal issues and serves on several journal Editorial Boards. Dr. Cassandras is currently Editor-in-Chief of the IEEE Transactions on Automatic Control and has served as Editor for Technical Notes and Correspondence and Associate Editor. He is a member of the IEEE CSS Board of Governors, chaired the CSS Technical Committee on Control Theory, and served as Chair of several conferences. He has been a plenary speaker at various international conferences, including the American Control Conference in 2001 and the IEEE Conference on Decision and Control in 2002. He is the recipient of several awards, including the 1999 Harold Chestnut Prize (IFAC Best Control Engineering Textbook) for Discrete Event Systems: Modeling and Performance Analysis, and a 1991 Lilly Fellowship. He is a member of Phi Beta Kappa and Tau Beta Pi. He is also a Fellow of the IEEE.Stéphane Lafortune is Professor of Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor. He received degrees from Ecole Polytechnique de Montréal (B.Eng., 1980), McGill University (M.Eng., 1982), and the University of California at Berkeley (Ph.D., 1986). He joined the University of Michigan in 1986. He specializes in the areas of discrete event systems, fault diagnosis, supervisory control, and optimization, with applications to communication networks and transportation systems. He has published over 130 refereed papers in these areas, and one textbook. Dr. Lafortune is currently Department Editor of the Journal of Discrete Event Dynamic Systems: Theory and Applications. He served as Associate Editor and Associate-Editor-at-Large of the IEEE Transactions on Automatic Control in the period 1993-1999. He was a plenary speaker at various international meetings, including the 1996 International Workshop on Discrete Event Systems (WODES’96). He is the recipient of several awards, including the 1994 and 2001 George S. Axelby Outstanding Paper Awards from the IEEE Control Systems Society. He is a Fellow of the IEEE.

Preface – Second Edition.- 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.- Control with Partial Controllability.- Nonblocking Control.- Control with Modular Specifications.- Control Under Partial Observation.- Decentralized Control.- Summary.- Problems.- Selected References.- 4 Petri Nets: Introduction.- Petri Net Basics.- Comparison of Petri Nets and Automata.- Analysis of Petri Nets.- Control of Petri Nets.- Summary.- Problems.- Selected References.- 5 Timed and Hybrid Models: Introduction.- Timed Automata.- Timed Petri Nets.- Dioid Algebras.- Alternative Timed Models.- Timed Automata with Guards.- Hybrid Models.- 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 Queueing 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 and Concurrent Estimation: Introduction.- Sample Functions and Their Derivatives.- Perturbation Analysis: Some Key Ideas.- PA of GI/G/1 Queueing Systems.- IPA for Stochastic Timed Automata.- Sensitivity Estimation Revisited.- Extensions of IPA.- Smoothed Perturbation Analysis (SPA).- IPA for Stochastic Hybrid Automata.- PA for Finite Parameter Changes.- Concurrent Estimation.- Summary.- Problems.- Selected References.- I: 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.- II: IPA Estimator.- Index.- About the Authors.