Perturbation Analysis of Discrete Event Dynamic Systems

ISBN-13: 9780792391746 / Angielski / Twarda / 1991 / 433 str.

Yu-Chi Ho; (Larry) Ho Yu-Chi (Larry) Ho; Cao XI-Ren Cao

Opis

Dynamic Systems (DEDS) are almost endless: military C31 Ilogistic systems, the emergency ward of a metropolitan hospital, back offices of large insurance and brokerage fums, service and spare part operations of multinational fums . . . . the point is the pervasive nature of such systems in the daily life of human beings. Yet DEDS is a relatively new phenomenon in dynamic systems studies. From the days of Galileo to Newton to quantum mechanics and cosmology of the present, dynamic systems in nature are primarily differential equations based and time driven. A large literature and endless success stories have been built up on such Continuous Variable Dynamic Systems (CVDS). It is, however, equally clear that DEDS are fundamentally different from CVDS. They are event driven, asynchronous, mostly man-made and only became significant during the past generation. Increasingly, however, it can be argued that in the modem world our lives are being impacted by and dependent upon the efficient operations of such DEDS. Yet compared to the successful paradigm of differential equations for CVDS the mathematical modelling of DEDS is in its infancy. Nor are there as many successful and established techniques for their analysis and synthesis. The purpose of this series is to promote the study and understanding of the modelling, analysis, control, and management of DEDS. The idea of the series came from editing a special issue of the Proceedings of IEEE on DEOS during 1988.

Recenzje

' The book is strongly recommended for graduate students who have had courses in linear algebra, multivariate calculus and a first course in probability theory and stochastic process; as also for practitioners of operations research, engineering and applied mathematicians. ' Indian Journal of Technology October 1992

Spis treści

1. Introduction to Discrete Event Dynamic Systems.- 1.1 Introduction.- 1.2 Models of DEDS.- 2. Introduction to Perturbation Analysis.- 2.1 Notations.- 2.2 A Short History of the Perturbation Analysis Development.- 3. Informal Treatment of the Infinitesimal Perturbation Analysis (IPA) 2.- 3.1 The Basic Idea.- 3.2 Single Class Queueing Networks.- 3.3 A GSMP Formalism for IPA.- 3.4 Realization Ratios.- 3.5 The GI/G/1 Queue.- 3.6 Load Dependent Server and IPA.- 3.7 Remarks about PA.- 4. Foundation of Infinitesimal Perturbation Analysis.- 4.1 Sample Derivative and Interchangeability.- 4.2 Perturbation Analysis for Closed Jackson Network.- 1. Sample Performance Functions.- 2. Sample Derivative of Performance in Transient Periods.- 3. Derivative of Steady State Performance.- 4.3 Realization and Sensitivity Analysis.- 1. Realization Probability.- 2. Realization Index and The Convergence Theorems.- 3. Sensitivity of Throughputs.- 4. Calculation of Other Sensitivities.- 4.4 Sensitivity Analysis of Networks with General Service Distributions.- 4.5 IPA Estimates of the M/G/1 and GI/G/1 Queue.- 1. M/G/1 Queue: A Direct Approach.- 2. M/G/1 Queue: The Approach Based on Stochastic Convexity.- 4.6 Some Technical Proofs.- 5. Extensions of IPA.- 5.1 System Representation and PA.- 5.2 Another Sufficient Condition for Interchangeability.- 1. The Basic Idea.- 2. A sufficient condition based on the generalized semi Markov process model.- 3 Queueing network examples.- 5.3 Routing Probability Sensitivity.- 5.4 The Multiclass M/G/1 Queue and Networks.- 1. The Two Class M/M/1 Queue.- 2. The Rescheduling Approach.- 3. Approximate MultiClass Network Analysis and IPA.- 5.5 Smoothed Perturbation Analysis (SPA).- 6. Finite Perturbation Analysis.- 6.1 The Idea of “Cut-and-Paste”.- 1. A Simple Example of “Cut-and-Paste”.- 2. State vs. Event Matching.- 6.2 The State Matching vs. Event Matching Algorithms.- 1. Analytical Comparison of State Matching Algorithms vs. Event Matching Algorithms for a Simple System.- 2. Empirical Validation.- 6.3 “Cut-and-Paste” as a Generalization of the Rejection Method.- 6.4 First Order Propagation Rules and Approximate EPA.- 7. General Sensitivity Analysis.- 7.1 Efficient Sample Path Generation.- 1. The Standard Clock and the M/M/1 Example.- 2. IPA via the Standard Clock.- 3. The Alias Method of Choosing Event Types.- 7.2 Trajectory Projection and State Augmentation.- 1. Trajectory Projection of the Automata Model.- 2. State Augmentation Method for Markov Chains.- 7.3 The Likelihood Ratio Approach.- 1. A Markov Chain Example and Variance Reduction.- 2. Basic Analysis.- 3. An Example of the Variances of PA and LR Estimates.- 4. Comparison of the PA and Likelihood Ratio Estimates.- 5. DEDS models Revisited.- 8. Aggregation, Decomposition, and Equivalence.- 8.1 Equivalent Server and Aggregation.- 1. Product-Form Networks.- 2. General Networks.- 8.2 Perturbation Analysis on Aggregated Systems and Aggregated PA.- 1. Perturbation Analysis of Aggregated Systems.- 2. Aggregated Perturbation Analysis.- 3. Aggregation of Multiclass Queueing Networks -An Example.- 8.3 Aggregation and Decomposition of Markov Chains.- 1. The Case of v’(s) = 0.- 2. The Case Where v’(s) Can Be Calculated in Closed Form.- 8.4 Decomposition via the A-Segment Algorithm for very Large Markov Chains.- Appendix A. Elements of Queueing Theory.- Appendix B. elements of Discrete Event Simulation.- Appendix C. Elements of Optimization and Control Theory 3.- Appendix D. A Simple Illustrative Example of the Different Models of DEDS.- Appendix E. A Sample Program of Perturbation Analysis.- References.