OVERVIEW

Discrete Event Systems: Modeling and Performance Analysis is the first instructional text to be published in an emerging area 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:

    1. The classical probabilistic approach, using stochastic process theory.
    2. 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

    To order this book you may contact

    Richard D. Irwin, Inc.
    1333 Burr Ridge Parkway
    Burr Ridge, IL 60521
    Tel: (708) 789-6938

    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
               Conservation 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 Uniformization 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.3 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
    To CODES

    To ECE Home Page

    ecewebmaster@ecs.umass.edu